Лексикографический порядок

Generalization of the alphabetical order of dictionaries to sequences of elements of an ordered set

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

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

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

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

Определение

Слова в лексиконе (наборе слов, используемых в каком-либо языке) имеют общепринятый порядок, используемый в словарях и энциклопедиях , который зависит от базового порядка алфавита символов, используемых для построения слов. Лексикографический порядок — это один из способов формализации порядка слов с учетом порядка базовых символов.

Формальное понятие начинается с конечного множества A , часто называемого алфавитом , которое полностью упорядочено . То есть для любых двух символов a и b в A , которые не являются одним и тем же символом, либо a < b, либо b < a .

Слова A — это конечные последовательности символов из A , включая слова длины 1, содержащие один символ, слова длины 2 с 2 символами и т. д., включая даже пустую последовательность без символов вообще. Лексикографический порядок на множестве всех этих конечных слов упорядочивает слова следующим образом: ${\displaystyle \varepsilon }$

1. Если даны два разных слова одинаковой длины, скажем , a = a ₁ a ₂ ... a _k и b = b ₁ b ₂ ... b _k , порядок двух слов зависит от алфавитного порядка символов в первом месте i , где два слова различаются (считая с начала слов): a < b тогда и только тогда, когда a _i < b _i в базовом порядке алфавита A .
2. Если два слова имеют разную длину, то обычный лексикографический порядок дополняет более короткое слово «пробелами» (специальный символ, который рассматривается как меньший, чем каждый элемент A ) в конце до тех пор, пока слова не станут одинаковой длины, а затем слова сравниваются, как в предыдущем случае.

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

В лексикографическом порядке слово «Томас» появляется перед «Томпсон», потому что они впервые различаются на пятой букве («а» и «р»), а буква «а» стоит перед буквой «р» в алфавите. Поскольку это первое различие, в этом случае пятая буква является «наиболее существенным различием» для алфавитного порядка.

Важным свойством лексикографического порядка является то, что для каждого n множество слов длины n вполне упорядочено лексикографическим порядком (при условии, что алфавит конечен); то есть каждая убывающая последовательность слов длины n конечна (или, что эквивалентно, каждое непустое подмножество имеет наименьший элемент). ^{[1] [2]} Неверно, что множество всех конечных слов вполне упорядочено; например, бесконечное множество слов {b, ab, aab, aaab, ... } не имеет лексикографически самого раннего элемента.

Системы счисления и даты

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

Одним из недостатков римской системы счисления является то, что не всегда сразу очевидно, какое из двух чисел меньше. С другой стороны, с позиционной записью индо -арабской системы счисления сравнивать числа легко, потому что естественный порядок натуральных чисел совпадает с вариантом shortlex лексикографического порядка. Фактически, с позиционной записью натуральное число представляется последовательностью числовых цифр , и натуральное число больше другого, если либо оно имеет больше цифр (игнорируя ведущие нули), либо количество цифр одинаковое, а первая (самая значимая) цифра, которая отличается, больше.

Для действительных чисел, записанных в десятичной системе счисления , используется немного другой вариант лексикографического порядка: части слева от десятичной точки сравниваются, как и прежде; если они равны, части справа от десятичной точки сравниваются с лексикографическим порядком. Заполнение 'blank' в этом контексте представляет собой конечную цифру "0".

Если также рассматриваются отрицательные числа, то для сравнения отрицательных чисел необходимо изменить порядок. Обычно это не проблема для людей, но может быть проблемой для компьютеров (проверка знака занимает некоторое время). Это одна из причин принятия представления в виде дополнения до двух для представления целых чисел со знаком в компьютерах.

Другой пример несловарного использования лексикографического упорядочения появляется в стандарте ISO 8601 для дат, который выражает дату как YYYY-MM-DD. Эта схема форматирования имеет преимущество в том, что лексикографический порядок последовательностей символов, представляющих даты, совпадает с хронологическим порядком : более ранняя дата CE меньше в лексикографическом порядке, чем более поздняя дата до 9999 года. Такое упорядочение дат упрощает компьютерную сортировку дат, избегая необходимости в отдельном алгоритме сортировки.

Моноид слов

Моноид слов над алфавитом A — это свободный моноид над A . То есть, элементы моноида — это конечные последовательности (слова) элементов A (включая пустую последовательность длины 0), а операция (умножение) — это конкатенация слов . Слово u является префиксом (или «усечением») другого слова v , если существует слово w такое, что v = uw . Согласно этому определению, пустое слово ( ) является префиксом каждого слова, а каждое слово является префиксом самого себя (с w ); необходимо соблюдать осторожность, если эти случаи должны быть исключены. ${\displaystyle \varepsilon }$ ${\displaystyle =\varepsilon }$

С этой терминологией приведенное выше определение лексикографического порядка становится более кратким: если задано частично или полностью упорядоченное множество A и два слова a и b над A, такие, что b непусто, то a < b в лексикографическом порядке, если выполняется хотя бы одно из следующих условий:

• a — это префикс b
• существуют слова u , v , w (возможно, пустые) и элементы x и y из A такие, что

х < у

а = uxv

б = уыв

Обратите внимание, что из-за префиксного условия в этом определении, где находится пустое слово. ${\displaystyle \varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,}$ ${\displaystyle \varepsilon }$

Если является полным порядком на , то таким же является и лексикографический порядок на словах Однако, в общем случае это не вполне порядок , даже если алфавит вполне упорядочен. Например, если A = { a , b } , язык { a ⁿ b | n ≥ 0, b > ε } не имеет наименьшего элемента в лексикографическом порядке: ... < aab < ab < b . ${\displaystyle \,<\,}$ ${\displaystyle A,}$ ${\displaystyle A.}$ ${\displaystyle A}$

Поскольку многие приложения требуют хорошо упорядоченных слов, часто используется вариант лексикографических порядков. Этот хорошо упорядоченный, иногда называемый shortlex или квазилексикографическим порядком , состоит в том, чтобы сначала рассмотреть длины слов (если length( a ) < length( b ) , то ), и, если длины равны, использовать лексикографический порядок. Если порядок на A является хорошо упорядоченным, то же самое верно и для shortlex порядка. ^{[2] [3]} ${\displaystyle a<b}$

Декартовы произведения

Лексикографический порядок определяет порядок на n -арном декартовом произведении упорядоченных множеств, который является полным порядком, когда все эти множества сами полностью упорядочены. Элемент декартова произведения — это последовательность, чей ^{элемент} принадлежит для каждого Поскольку при оценке лексикографического порядка последовательностей сравниваются только элементы, имеющие одинаковый ранг в последовательностях, лексикографический порядок распространяется на декартовы произведения упорядоченных множеств. ${\displaystyle E_{1}\times \cdots \times E_{n}}$ ${\displaystyle i}$ ${\displaystyle E_{i}}$ ${\displaystyle i.}$

В частности, даны два частично упорядоченных множества и ${\displaystyle A}$ ${\displaystyle B,}$лексикографический порядок декартова произведения определяется как ${\displaystyle A\times B}$ $${\displaystyle (a,b)\leq \left(a^{\prime },b^{\prime }\right){\text{ if and only if }}a<a^{\prime }{\text{ or }}\left(a=a^{\prime }{\text{ and }}b\leq b^{\prime }\right),}$$

Результатом является частичный порядок. Если и полностью упорядочены , то результатом также является полный порядок. Таким образом, лексикографический порядок двух полностью упорядоченных множеств является линейным расширением их порядка произведения . ${\displaystyle A}$ ${\displaystyle B}$

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

В отличие от конечного случая, бесконечное произведение вполне порядков не обязательно вполне упорядочено лексикографическим порядком. Например, множество счетно бесконечных двоичных последовательностей (по определению, множество функций от натуральных чисел до , также известное как пространство Кантора ) не является вполне упорядоченным; подмножество последовательностей, которые имеют ровно один (то есть, { 100000..., 010000..., 001000..., ... } ), не имеет наименьшего элемента в лексикографическом порядке, индуцированном , поскольку 100000... > 010000... > 001000... > ... является бесконечной нисходящей цепью . ^[1] Аналогично, бесконечное лексикографическое произведение также не является нётеровым , поскольку 011111... < 101111... < 110111 ... < ... является бесконечной восходящей цепью. ${\displaystyle \{0,1\},}$ ${\displaystyle \{0,1\}^{\omega }}$ ${\displaystyle 1}$ ${\displaystyle 0<1,}$

Функции над упорядоченным множеством

Функции от вполне упорядоченного множества до полностью упорядоченного множества можно идентифицировать с помощью последовательностей, индексированных по элементам из Таким образом, они могут быть упорядочены в лексикографическом порядке, а для двух таких функций и лексикографический порядок, таким образом, определяется их значениями для наименьшего из таких, что ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y.}$ ${\displaystyle f}$ ${\displaystyle g,}$ ${\displaystyle x}$ ${\displaystyle f(x)\neq g(x).}$

Если также вполне упорядочен и конечен, то полученный порядок является вполне упорядоченным. Как показано выше, если бесконечно, то это не так. ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$

Конечные подмножества

Упорядочения 3- подмножеств представлены в виде наборов красных квадратов, возрастающих последовательностей (синим цветом) или их индикаторных функций , преобразованных в десятичную систему счисления (серым цветом). Серые числа также являются рангом подмножеств во всех подмножествах , пронумерованных в колексикографическом порядке и начинающихся с 0. Лексикографический (lex) и колексикографический (colex) порядки находятся сверху, а соответствующие обратные порядки (rev) снизу. Переход от порядка к его обратному порядку осуществляется либо путем чтения снизу вверх вместо сверху вниз, либо путем замены красного и белого цветов. ${\displaystyle \{1,\ldots ,6\},}$ ${\displaystyle \{1,\ldots ,6\},}$

В комбинаторике часто приходится перечислять, а значит, и упорядочивать конечные подмножества заданного множества Для этого обычно выбирают порядок на Тогда сортировка подмножества эквивалентна преобразованию его в возрастающую последовательность. Лексикографический порядок на полученных последовательностях индуцирует, таким образом, порядок на подмножествах, который также называется лексикографическим порядком . ${\displaystyle S.}$ ${\displaystyle S.}$ ${\displaystyle S}$

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

Например, используя естественный порядок целых чисел, лексикографическое упорядочение подмножеств из трех элементов имеет вид ${\displaystyle S=\{1,2,3,4,5,6\}}$

123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <

234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456 .

Для упорядочения конечных подмножеств заданной мощности натуральных чисел часто удобнее использовать колексикографический порядок (см. ниже), поскольку все начальные сегменты конечны, и, таким образом, колексикографический порядок определяет изоморфизм порядка между натуральными числами и множеством множеств натуральных чисел. Это не относится к лексикографическому порядку, поскольку в случае лексикографического порядка мы имеем, например, для каждого ${\displaystyle n}$ ${\displaystyle 12n<134}$ ${\displaystyle n>2.}$

Групповые заказы Zн

Пусть будет свободной абелевой группой ранга , элементы которой являются последовательностями целых чисел, а операция — сложением . Порядок группы на — это полный порядок , совместимый со сложением, то есть ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle n,}$ ${\displaystyle n}$ ${\displaystyle \mathbb {Z} ^{n}}$ $${\displaystyle a<b\quad {\text{ if and only if }}\quad a+c<b+c.}$$

Лексикографический порядок — это групповой порядок по ${\displaystyle \mathbb {Z} ^{n}.}$

Лексикографический порядок может также использоваться для характеристики всех групповых порядков на ^{[4] [5]} Фактически, линейные формы с действительными коэффициентами определяют отображение из в которое является инъективным, если формы линейно независимы (оно может быть также инъективным, если формы зависимы, см. ниже). Лексикографический порядок на изображении этого отображения индуцирует групповой порядок на Теорема Роббиано заключается в том, что каждый групповой порядок может быть получен таким образом. ${\displaystyle \mathbb {Z} ^{n}.}$ ${\displaystyle n}$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle \mathbb {R} ^{n},}$ ${\displaystyle \mathbb {Z} ^{n}.}$

Точнее, для заданного порядка группы на существуют целочисленная и линейная формы с действительными коэффициентами, такие, что индуцированное отображение из в обладает следующими свойствами: ${\displaystyle \mathbb {Z} ^{n},}$ ${\displaystyle s\leq n}$ ${\displaystyle s}$ ${\displaystyle \varphi }$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle \mathbb {R} ^{s}}$

• ${\displaystyle \varphi }$является инъекционным;
• результирующий изоморфизм из к образу является порядковым изоморфизмом, когда образ снабжен лексикографическим порядком по ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle \varphi }$ ${\displaystyle \mathbb {R} ^{s}.}$

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

Упорядочения 24 перестановок {1,...,5}, которые являются 5-циклами (синим цветом). Векторы инверсии (красным цветом) перестановок в порядке colex находятся в порядке revcolex , и наоборот.

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

a ₁ a ₂ ... a _k < ^lex b ₁ b ₂ ... b _k, если a _i < b _i для первого i, где a _i и b _i различаются,

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

a ₁ a ₂ ... a _k < ^colex b ₁ b ₂ ... b _k если a _i < b _i для последнего i где a _i и b _i различаются

В целом, разница между колексикографическим и лексикографическим порядками не очень существенна. Однако при рассмотрении возрастающих последовательностей, как правило, для кодирования подмножеств, два порядка существенно различаются.

Например, для упорядочения возрастающих последовательностей (или наборов) двух натуральных чисел лексикографический порядок начинается с

12 < 13 < 14 < 15 < ... < 23 < 24 < 25 < ... < 34 < 35 < ... < 45 < ... ,

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

12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 < ... .

Основное свойство колексикографического порядка для возрастающих последовательностей заданной длины заключается в том, что каждый начальный сегмент конечен. Другими словами, колексикографический порядок для возрастающих последовательностей заданной длины индуцирует изоморфизм порядка с натуральными числами и позволяет перечислять эти последовательности. Это часто используется в комбинаторике , например, в доказательстве теоремы Крускала–Катоны .

Одночлены

При рассмотрении многочленов порядок членов в общем случае не имеет значения, так как сложение коммутативно. Однако некоторые алгоритмы , такие как деление многочленов в столбик , требуют, чтобы члены были в определенном порядке. Многие из основных алгоритмов для многомерных многочленов связаны с базисами Грёбнера , концепцией, которая требует выбора порядка монома , то есть полного порядка , который совместим с моноидной структурой мономов . Здесь «совместимый» означает, что если операция моноида обозначена мультипликативно. Эта совместимость подразумевает, что произведение многочлена на моном не меняет порядок членов. Для базисов Грёбнера должно быть выполнено еще одно условие, а именно , что каждый непостоянный моном больше монома 1. Однако это условие не требуется для других связанных алгоритмов, таких как алгоритмы для вычисления касательного конуса . ${\displaystyle a<b{\text{ implies }}ac<bc,}$

Поскольку базисы Грёбнера определяются для полиномов с фиксированным числом переменных, обычно мономы (например , ) отождествляют с их векторами экспонент (здесь [1, 3, 0, 1, 2] ). Если n — число переменных, то каждый порядок монома является ограничением на порядка монома (см. выше § Порядки групп для классификации). ${\displaystyle x_{1}x_{2}^{3}x_{4}x_{5}^{2}}$ ${\displaystyle \mathbb {N} ^{n}}$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle \mathbb {Z} ^{n},}$

Одним из таких допустимых порядков является лексикографический порядок. Исторически он был первым, который использовался для определения базисов Грёбнера, и иногда его называют чистым лексикографическим порядком, чтобы отличать его от других порядков, которые также связаны с лексикографическим порядком.

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

Обратный лексикографический порядок степени также состоит в сравнении сначала общих степеней, и, в случае равенства общих степеней, в использовании обратного колексикографического порядка. То есть, если даны два вектора экспонент, то имеем, если либо или $${\displaystyle [a_{1},\ldots ,a_{n}]<[b_{1},\ldots ,b_{n}]}$$ $${\displaystyle a_{1}+\cdots +a_{n}<b_{1}+\cdots +b_{n},}$$ $${\displaystyle a_{1}+\cdots +a_{n}=b_{1}+\cdots +b_{n}\quad {\text{ and }}\quad a_{i}>b_{i}{\text{ for the largest }}i{\text{ for which }}a_{i}\neq b_{i}.}$$

Для этого упорядочения одночлены первой степени имеют тот же порядок, что и соответствующие неопределенные члены (это было бы не так, если бы использовался обратный лексикографический порядок). Для сравнения одночленов от двух переменных той же общей степени этот порядок совпадает с лексикографическим порядком. Это не относится к большему количеству переменных. Например, для экспоненциальных векторов одночленов второй степени от трех переменных для степени имеем обратный лексикографический порядок: $${\displaystyle [0,0,2]<[0,1,1]<[1,0,1]<[0,2,0]<[1,1,0]<[2,0,0]}$$

Для лексикографического порядка те же векторы экспоненты упорядочиваются следующим образом: $${\displaystyle [0,0,2]<[0,1,1]<[0,2,0]<[1,0,1]<[1,1,0]<[2,0,0].}$$

Полезным свойством обратного лексикографического порядка степени является то, что однородный многочлен является кратным наименьшей неопределенности тогда и только тогда, когда его ведущий одночлен (его больший одночлен) является кратным этой наименьшей неопределенности.

Смотрите также

• Сопоставление
• Порядок Клини–Брауэра
• Лексикографические предпочтения — применение лексикографического порядка в экономике.
• Лексикографическая оптимизация — алгоритмическая задача нахождения лексикографически максимального элемента.
• Топология лексикографического порядка на единичном квадрате
• Лексикографическое упорядочение в тензорной абстрактной индексной нотации
• Лексикографически минимальное вращение строки
• порядок лексимин
• Длинная линия (топология)
• слово Линдона
• Звездный продукт , другой способ объединения частичных заказов
• Короткий заказ
• Порядки декартового произведения полностью упорядоченных множеств

Ссылки

1. Egbert Harzheim (2006). Упорядоченные множества . Springer. стр. 88–89. ISBN 978-0-387-24222-4.
2. Франц Баадер; Тобиас Нипков (1999). Переписывание терминов и все такое . Cambridge University Press. С. 18–19. ISBN 978-0-521-77920-3.
3. Calude, Cristian (1994). Информация и случайность. Алгоритмическая перспектива . Монографии EATCS по теоретической информатике. Springer-Verlag . стр. 1. ISBN 3-540-57456-5. Збл  0922.68073.
4. Роббиано, Л. (1985). Упорядочение терминов в кольце многочленов. В Европейской конференции по компьютерной алгебре (стр. 513-517). Springer Berlin Heidelberg.
5. Weispfenning, Volker (май 1987 г.), «Допустимые порядки и линейные формы», SIGSAM Bulletin , 21 (2), Нью-Йорк, США: ACM: 16–18, doi : 10.1145/24554.24557 , S2CID  10226875.

Внешние ссылки

• Учебные материалы по лексикографическому и колексикографическому порядку в Викиверситете