Что такое лексикографический порядок

@Просто Саша · Регистрация: 27.11.2017

Author24 — интернет-сервис помощи студентам

Меня интересует правильно ли я расположил сейчас буквы русского алфавита в лексикографическом порядке:

А, а, Б, б, В, в, ..., Я, я.

@Bring · 02.04.2018, 01:52

ААА, AAБ, ААВ, ААГ...ЯЯЯ.

@Просто Саша · 02.04.2018, 02:02 **[ТС]**

Сообщение от Bring

ААА, AAБ, ААВ, ААГ...ЯЯЯ

Ну а строчные буквы вы куда задевали?
Их что нет в природе?

Добавлено через 4 минуты
Я вообще так понимаю, что есть три вида упорядочивания символов национальных алфавитов:

1) Бинарный порядок, в котором символы упорядочены в соответствии со своими числовыми кодами.
2) Лексикографический порядок, в котором символы упорядочены по алфавиту, но при этом прописная буква больше больше соответствующей строчной.
3) Словарный порядок. То же самое, что и лексикографический, только в этом случае прописная буква равна соответствующей строчной, иными словами регистронезависмый порядок (case-insensitive).

nd2 · 02.04.2018, 02:40

Сообщение от Просто Саша

но при этом прописная буква больше больше соответствующей строчной.

Меньше (strcmp() проверь). А < а.

@Просто Саша · 02.04.2018, 03:28 **[ТС]**

Сообщение от nd2

Меньше (strcmp() проверь). А < а.

Так ты же делай разницу между бинарным порядком и лексикографическим.
Это совершенно разные вещи.

Вот лексикографический: A, a, Б, б, ... Я, я
Вот бинарный: А, Б, ..., Я, а, б, ..., я

Неужели не всекаешь?

Добавлено через 1 минуту
strcoll сравнивает строки в соответствии с лексикографическим порядком
strcmp сравнивает строки в соответствии с бинарным порядком

nd2 · 02.04.2018, 03:48

Сообщение от Просто Саша

strcmp сравнивает строки в соответствии с бинарным порядком

http://ru.cppreference.com/w/c... yte/strcmp

@Просто Саша · 02.04.2018, 10:00 **[ТС]**

Сообщение от nd2

http://ru.cppreference.com/w/cpp/string/byte/strcmp

Неправильно там указано. Твой cppreference.com видать домохозяйки писали.

Вот правильно как:

Функции strcmp отличаются от функций strcoll тем, что сравнение strcmp является порядковым и не зависит от языкового стандарта. strcoll сравнивает строки лексикографически с использованием категории LC_COLLATE текущего языкового стандарта. Дополнительные сведения о LC_COLLATE категории, в разделе setlocale _wsetlocale.

https://msdn.microsoft.com/ru-... 9k731.aspx

Croessmah · 02.04.2018, 11:28

Сообщение от Просто Саша

strcoll сравнивает строки лексикографически

Лексикографическое сравнение применимо не только к символам алфавита.
https://ru.wikipedia.org/wiki/... ий_порядок

Сообщение от Просто Саша

Вот бинарный: А, Б, ..., Я, а, б, ..., я

Смотря как посмотреть. С точки зрения значений байт, все они имеют разные значения и strcmp осуществляет именно лексикографическое сравнение на основании значений байт.

@CheshireCat · 02.04.2018, 11:39

Внесу-ка и я свои пять копеек.
С лексикографическим порядком есть еще закавыка: в некоторых языках по правилам языка одна строчная буква при переводе в верхний регистр может превращаться в две заглавных.... И наоборот.

@0x10 · 02.04.2018, 11:50

Сообщение от Просто Саша

Меня интересует правильно ли я расположил сейчас буквы русского алфавита в лексикографическом порядке:
А, а, Б, б, В, в, ..., Я, я.

Вопрос поставлен некорректно.
«Лексикографический» предполагает алгоритм сравнения — последовательности сравниваются по первому элементу, пустая меньше, а дальше сравниваются хвосты. Т.е. это про порождение из порядка над элементами порядка их последовательностей. Ты же фокусируешься на порядке над элементами, а он уже зависит от реализации.

strcmp действительно упорядочивает последовательности лексикографически, принимая за значения элементов их числовые коды и используя порядок для них.

@Просто Саша · 02.04.2018, 14:01 **[ТС]**

Сообщение от 0x10

Вопрос поставлен некорректно.

Вопрос поставлен очень даже корректно.
Если Вы напираете на алгоритм, так приведите тогда результат его работы.

Насколько я понимаю, лексикографический порядок - это именно и есть упорядочение по алфавиту, где приоритет отдается прописным буквам, в том смысле, что они считаются меньшими, и неважно каким числовым кодом они представлены в используемой кодировке.

А вот бинарный порядок он чисто упорядочивает по числовому коду, который имеет символ в данной кодировке.
Вопрос в другом, в некоторых кодировках все символы алфавита идут в естественном порядке, а в некоторых нет.
И ваш strcmp обломится на букве Ё, а вот strcoll нет.

Добавлено через 8 минут
Да и сами эти функции работают по разному?

C++

1
2
3

setlocale(LC_ALL, "Russian_Russia.1251");
cout << strcoll("а", "Б") << endl; // -1, что означает "a" < "Б"
cout << strcmp("а", "Б") << endl; // 1, что означает "a" > "Б"

Вот и видно одна из них сравнивает бинарно (strcmp), а вторая лексикографически (strcoll).

Croessmah · 02.04.2018, 14:08

Сообщение от Просто Саша

Насколько я понимаю, лексикографический порядок - это именно и есть упорядочение по алфавиту

Не только.
Вот есть

C++

1 2	std::vector<int> vec1 { /.../ }; std::vector<int> vec2 { /.../ };

их же тоже можно сравнить лексикографически, а букв вообще нет.
А strcmp сравнивает лексикографически основываясь на значении байт, а не на порядке символов в алфавите языка.

@Просто Саша · 02.04.2018, 14:31 **[ТС]**

Сообщение от Croessmah

Не только.
Вот есть

Нет, ну я знаю, как рекурсивно определяется это понятие.
Я спрашивал применительно к русскому алфавиту.

nd2 · 02.04.2018, 15:24

Сообщение от Просто Саша

Неправильно там указано.

Правильно. И strcmp() и strcoll() сравнивают лексикографически, только strcoll() ещё и локаль учитывает.

Сообщение от Просто Саша

Насколько я понимаю, лексикографический порядок - это именно и есть упорядочение по алфавиту

А как там в алфавите - это в локали прописывается.

Сообщение от Просто Саша

где приоритет отдается прописным буквам, в том смысле, что они считаются меньшими

От локали зависит. В английской - прописные лексикографически меньше, а в русской - наоборот:

Сообщение от Просто Саша

C++

1 2	setlocale(LC_ALL, "Russian_Russia.1251"); cout << strcoll("а", "Б") << endl; // -1, что означает "a" < "Б"

@Просто Саша · 02.04.2018, 15:37 **[ТС]**

Сообщение от nd2

Правильно. И strcmp() и strcoll() сравнивают лексикографически, только strcoll() ещё и локаль учитывает.

Тоже неправильно, и та и другая функция учитывает локаль.

Сообщение от nd2

От локали зависит. В английской - прописные лексикографически меньше, а в русской - наоборот:

Я уже устал повторять, что задавал я вопрос именно про русский алфавит, но снова неверно. И в том и в другом алфавите прописные буквы расположены раньше строчных. В английской это вообще не зависит от локали, там во всех локалях английские буквы как в таблице ASCII. Что касается русского, то такое отклонение наблюдается только для koi8-r. Во всех остальных кодировках прописные буквы расположены раньше строчных, во всяеом случае это справедливо для Юникода и cp1251.

nd2 · 02.04.2018, 15:45

Сообщение от Просто Саша

Во всех остальных кодировках прописные буквы расположены раньше строчных, во всяеом случае это справедливо для Юникода и cp1251.

Раньше, значит прописные должны быть лексикографически меньше? Ты же сам привёл пример с cp1251, где видно, что, для этой кодировки, прописные больше:

Сообщение от Просто Саша

C++

1 2	setlocale(LC_ALL, "Russian_Russia.1251"); cout << strcoll("а", "Б") << endl; // -1, что означает "a" < "Б"

@Просто Саша · 02.04.2018, 16:18 **[ТС]**

Сообщение от nd2

Раньше, значит прописные должны быть лексикографически меньше?

Сообщение от nd2

Ты же сам привёл пример с cp1251, где видно, что, для этой кодировки, прописные больше:

Ну тут похоже я сам немного запутался, потому что изначально опирался на вот такое предположение: А, а, Б, б, В, в, ..., Я, я.

А на самом деле, нужно вот так: а, А, б, Б,..., я, Я
Между прочим и для английского языка точно такой же лексикографический порядок:

a, A, b, B,..., z, Z

Я поэтому и задавал этот вопрос, КАК РАСПОЛОЖИТЬ БУКВЫ АЛФАВИТА В ЛЕКСИКОГРАФИЧЕСКОМ ПОРЯДКЕ.
Наслышался всякого разного словоблудия, а вот конкретного ответа так никто и не дал.

nd2 · 02.04.2018, 16:46

Сообщение от Просто Саша

А на самом деле, нужно вот так: а, А, б, Б,..., я, Я

Это для 1251, для 866 - уже нет.

@Просто Саша · 02.04.2018, 17:02 **[ТС]**

Сообщение от nd2

Это для 1251, для 866 - уже нет.

Так что выходит нет стандарта на лексикографический порядок?

@0x10 · 02.04.2018, 17:42

Сообщение от Просто Саша

Так что выходит нет стандарта на лексикографический порядок?

Нет понятия лексикографического порядка для элементов последовательности. Лексикографический порядок — это порядок последовательностей, см. вики. А отношение порядка на элементах определяется конкретной реализацией.

@Просто Саша -1 / 25 / 4 Регистрация: 27.11.2017 Сообщений: 375
	02.04.2018, 14:31 [ТС]	13
	Сообщение от Croessmah Не только. Вот есть Нет, ну я знаю, как рекурсивно определяется это понятие. Я спрашивал применительно к русскому алфавиту. 0

@Просто Саша -1 / 25 / 4 Регистрация: 27.11.2017 Сообщений: 375
	02.04.2018, 17:02 [ТС]	19
	Сообщение от nd2 Это для 1251, для 866 - уже нет. Так что выходит нет стандарта на лексикографический порядок? 0

@Просто Саша -1 / 25 / 4 Регистрация: 27.11.2017 Сообщений: 375
		1
	Что такое лексикографический порядок 02.04.2018, 01:33. Показов 13974. Ответов 27 Метки нет (Все метки) Меня интересует правильно ли я расположил сейчас буквы русского алфавита в лексикографическом порядке: А, а, Б, б, В, в, ..., Я, я. 0

@Bring 133 / 53 / 43 Регистрация: 09.05.2015 Сообщений: 565
	02.04.2018, 01:52	2
	ААА, AAБ, ААВ, ААГ...ЯЯЯ. 0

@Просто Саша -1 / 25 / 4 Регистрация: 27.11.2017 Сообщений: 375
	02.04.2018, 02:02 [ТС]	3
	Сообщение от Bring ААА, AAБ, ААВ, ААГ...ЯЯЯ Ну а строчные буквы вы куда задевали? Их что нет в природе? Добавлено через 4 минуты Я вообще так понимаю, что есть три вида упорядочивания символов национальных алфавитов: 1) Бинарный порядок, в котором символы упорядочены в соответствии со своими числовыми кодами. 2) Лексикографический порядок, в котором символы упорядочены по алфавиту, но при этом прописная буква больше больше соответствующей строчной. 3) Словарный порядок. То же самое, что и лексикографический, только в этом случае прописная буква равна соответствующей строчной, иными словами регистронезависмый порядок (case-insensitive). 0

nd2 3437 / 2816 / 1249 Регистрация: 29.01.2016 Сообщений: 9,426
	02.04.2018, 02:40	4
	Сообщение от Просто Саша но при этом прописная буква больше больше соответствующей строчной. Меньше (strcmp() проверь). А < а. 0

@Просто Саша -1 / 25 / 4 Регистрация: 27.11.2017 Сообщений: 375
	02.04.2018, 03:28 [ТС]	5
	Сообщение от nd2 Меньше (strcmp() проверь). А < а. Так ты же делай разницу между бинарным порядком и лексикографическим. Это совершенно разные вещи. Вот лексикографический: A, a, Б, б, ... Я, я Вот бинарный: А, Б, ..., Я, а, б, ..., я Неужели не всекаешь? Добавлено через 1 минуту strcoll сравнивает строки в соответствии с лексикографическим порядком strcmp сравнивает строки в соответствии с бинарным порядком 0

nd2 3437 / 2816 / 1249 Регистрация: 29.01.2016 Сообщений: 9,426
	02.04.2018, 03:48	6
	Сообщение от Просто Саша strcmp сравнивает строки в соответствии с бинарным порядком http://ru.cppreference.com/w/c... yte/strcmp 0

@Просто Саша -1 / 25 / 4 Регистрация: 27.11.2017 Сообщений: 375
	02.04.2018, 10:00 [ТС]	7
	Сообщение от nd2 http://ru.cppreference.com/w/cpp/string/byte/strcmp Неправильно там указано. Твой cppreference.com видать домохозяйки писали. Вот правильно как: Функции strcmp отличаются от функций strcoll тем, что сравнение strcmp является порядковым и не зависит от языкового стандарта. strcoll сравнивает строки лексикографически с использованием категории LC_COLLATE текущего языкового стандарта. Дополнительные сведения о LC_COLLATE категории, в разделе setlocale _wsetlocale. https://msdn.microsoft.com/ru-... 9k731.aspx 0

Croessmah Неэпический 17869 / 10634 / 2054 Регистрация: 27.09.2012 Сообщений: 26,736 Записей в блоге: 1
	02.04.2018, 11:28	8
	Сообщение от Просто Саша strcoll сравнивает строки лексикографически Лексикографическое сравнение применимо не только к символам алфавита. https://ru.wikipedia.org/wiki/... ий_порядок Сообщение от Просто Саша Вот бинарный: А, Б, ..., Я, а, б, ..., я Смотря как посмотреть. С точки зрения значений байт, все они имеют разные значения и strcmp осуществляет именно лексикографическое сравнение на основании значений байт. 0

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	02.04.2018, 11:39	9
	Внесу-ка и я свои пять копеек. С лексикографическим порядком есть еще закавыка: в некоторых языках по правилам языка *одна* строчная буква при переводе в верхний регистр может превращаться в две заглавных.... И наоборот. 0

@0x10 3257 / 2059 / 351 Регистрация: 24.11.2012 Сообщений: 4,909
	02.04.2018, 11:50	10
	Сообщение от Просто Саша Меня интересует правильно ли я расположил сейчас буквы русского алфавита в лексикографическом порядке: А, а, Б, б, В, в, ..., Я, я. Вопрос поставлен некорректно. «Лексикографический» предполагает алгоритм сравнения — последовательности сравниваются по первому элементу, пустая меньше, а дальше сравниваются хвосты. Т.е. это про порождение из порядка над элементами порядка их последовательностей. Ты же фокусируешься на порядке над элементами, а он уже зависит от реализации. strcmp действительно упорядочивает последовательности лексикографически, принимая за значения элементов их числовые коды и используя порядок для них. 0

@Просто Саша -1 / 25 / 4 Регистрация: 27.11.2017 Сообщений: 375
	02.04.2018, 15:37 [ТС]	15
	Сообщение от nd2 Правильно. И strcmp() и strcoll() сравнивают лексикографически, только strcoll() ещё и локаль учитывает. Тоже неправильно, и та и другая функция учитывает локаль. Сообщение от nd2 От локали зависит. В английской - прописные лексикографически меньше, а в русской - наоборот: Я уже устал повторять, что задавал я вопрос именно про русский алфавит, но снова неверно. И в том и в другом алфавите прописные буквы расположены раньше строчных. В английской это вообще не зависит от локали, там во всех локалях английские буквы как в таблице ASCII. Что касается русского, то такое отклонение наблюдается только для koi8-r. Во всех остальных кодировках прописные буквы расположены раньше строчных, во всяеом случае это справедливо для Юникода и cp1251. 0

@Просто Саша -1 / 25 / 4 Регистрация: 27.11.2017 Сообщений: 375
	02.04.2018, 16:18 [ТС]	17
	Сообщение от nd2 Раньше, значит прописные должны быть лексикографически меньше? Сообщение от nd2 Ты же сам привёл пример с cp1251, где видно, что, для этой кодировки, прописные больше: Ну тут похоже я сам немного запутался, потому что изначально опирался на вот такое предположение: А, а, Б, б, В, в, ..., Я, я. А на самом деле, нужно вот так: а, А, б, Б,..., я, Я Между прочим и для английского языка точно такой же лексикографический порядок: a, A, b, B,..., z, Z Я поэтому и задавал этот вопрос, КАК РАСПОЛОЖИТЬ БУКВЫ АЛФАВИТА В ЛЕКСИКОГРАФИЧЕСКОМ ПОРЯДКЕ. Наслышался всякого разного словоблудия, а вот конкретного ответа так никто и не дал. 0

nd2 3437 / 2816 / 1249 Регистрация: 29.01.2016 Сообщений: 9,426
	02.04.2018, 16:46	18
	Сообщение от Просто Саша А на самом деле, нужно вот так: а, А, б, Б,..., я, Я Это для 1251, для 866 - уже нет. 0

@0x10 3257 / 2059 / 351 Регистрация: 24.11.2012 Сообщений: 4,909
	02.04.2018, 17:42	20
	Сообщение от Просто Саша Так что выходит нет стандарта на лексикографический порядок? Нет понятия лексикографического порядка для элементов последовательности. Лексикографический порядок — это порядок последовательностей, см. вики. А отношение порядка на элементах определяется конкретной реализацией. 0