Введение

Обобщение алфавитного порядка словарей на последовательности элементов упорядоченного множества

В математике лексикографический или лексикографический порядок (также известный как лексический порядок или словарный порядок) является обобщением алфавитного порядка словарей на последовательности упорядоченных символов или, в более общем случае, элементов полностью упорядоченного множества. Существует несколько вариантов и обобщений лексикографического порядка. Один из вариантов применяется к последовательностям различной длины путем сравнения их длин перед сравнением элементов. Другой вариант, широко используемый в комбинаторике, упорядочивает подмножества данного конечного множества, задавая общее упорядочение этому множеству и преобразуя подмножества в неубывающие последовательности, к которым затем применяется лексикографический порядок. Обобщение определяет порядок на n-арном декартовом произведении частично упорядоченных множеств; этот порядок является полным порядком тогда и только тогда, когда все факторы декартова произведения полностью упорядочены.

Определение

Слова в лексиконе (набор слов, используемых в каком-либо языке) имеют установленный порядок, используемый в словарях и энциклопедиях, который зависит от порядка символов, лежащего в основе алфавита, используемого для построения слов. Лексикографический порядок – это один из способов формализации порядка слов, учитывая порядок символов алфавита. Формальное определение начинается с конечного множества A, часто называемого алфавитом, которое полностью упорядочено. То есть, для любых двух символов a и b в A, которые не совпадают, либо a < b, либо b < a. Словами над A называются конечные последовательности символов из A, включая слова длиной 1, состоящие из одного символа, слова длиной 2, состоящие из двух символов, и так далее, а также пустую последовательность, не содержащую символов. Лексикографический порядок на множестве всех этих конечных слов упорядочивает слова следующим образом:

Для двух различных слов одинаковой длины, скажем, и , порядок этих слов зависит от алфавитного порядка символов в первой позиции i, где слова различаются (считая от начала слов): a < b тогда и только тогда, когда ai < bi в порядке символов алфавита A. Если два слова имеют разную длину, обычный лексикографический порядок дополняет более короткое слово "пустышками" (специальным символом, который считается меньшим, чем любой элемент A) в конце, пока слова не станут одинаковой длины, после чего слова сравниваются, как в предыдущем случае. Однако в комбинаторике для второго случая часто используется другая конвенция, согласно которой более короткая последовательность всегда меньше более длинной последовательности. Этот вариант лексикографического порядка иногда называют коротким лексикографическим порядком (shortlex). В лексикографическом порядке слово "Thomas" предшествует слову "Thompson", поскольку они впервые различаются на пятой букве ('a' и 'p'), а буква 'a' стоит перед буквой 'p' в алфавите. Поскольку это первое различие, в данном случае пятая буква является "наиболее значимым различием" для алфавитного упорядочения. Важным свойством лексикографического порядка является то, что для каждого n множество слов длины n хорошо упорядочено по лексикографическому порядку (при условии, что алфавит конечен); то есть, любая убывающая последовательность слов длины n конечна (или, эквивалентно, любое непустое подмножество имеет наименьший элемент). Неверно, что множество всех конечных слов хорошо упорядочено; например, бесконечное множество слов {b, ab, aab, aaab, …} не имеет лексикографически наименьшего элемента.

Числовые системы и даты

Лексикографический порядок используется не только в словарях, но и обычно для чисел и дат. Один из недостатков римской системы счисления заключается в том, что не всегда очевидно, какое из двух чисел меньше. С другой стороны, при использовании позиционной нотации индусско-арабской системы счисления сравнение чисел легко, поскольку естественный порядок натуральных чисел совпадает с вариантом «короткого лекса» лексикографического порядка. Фактически, при позиционной нотации натуральное число представляется последовательностью числовых цифр, и одно натуральное число больше другого, если оно имеет больше цифр (игнорируя ведущие нули) или количество цифр одинаково, а первая (наиболее значащая) различающаяся цифра больше. Для действительных чисел, записанных в десятичной нотации, используется несколько иной вариант лексикографического порядка: части, расположенные слева от десятичной точки, сравниваются как и прежде; если они равны, то части, расположенные справа от десятичной точки, сравниваются в лексикографическом порядке. В этом контексте заполнение «пустым» значением – это замыкающий ноль. При рассмотрении также отрицательных чисел порядок сравнения отрицательных чисел необходимо изменить на противоположный. Это обычно не представляет проблемы для людей, но может быть проблемой для компьютеров (проверка знака требует времени). Это одна из причин использования представления в дополнительном коде для представления знаковых целых чисел в компьютерах. Другой пример несловарного использования лексикографического упорядочения встречается в стандарте ISO 8601 для дат, который представляет дату в формате ГГГГ ММ ДД. Эта схема форматирования имеет то преимущество, что лексикографический порядок последовательностей символов, представляющих даты, совпадает с хронологическим порядком: более ранняя дата нашей эры меньше в лексикографическом порядке, чем более поздняя дата до 9999 года. Такой порядок дат упрощает автоматизированную сортировку дат, избавляя от необходимости в отдельном алгоритме сортировки.