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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

Для вещественных чисел, записанных в десятичной записи , используется несколько иной вариант лексикографического порядка: части слева от десятичной точки сравниваются, как и раньше; если они равны, части справа от десятичной точки сравниваются в лексикографическом порядке. Заполнение «Пробел» в этом контексте представляет собой конечную цифру «0».

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

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

Моноид слов

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

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

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

х < у

а = uxv

б = да

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

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

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

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

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

В частности, даны два частично упорядоченных набора $A$ и $B,$ тот лексикографический порядок декартова произведения $A\times B$ определяется как $(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),$

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

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

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

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

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

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

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

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

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

Например, используя естественный порядок целых чисел, лексикографический порядок подмножеств трех элементов $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

.

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

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

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

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

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

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

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

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

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

от 1 до 2 ... до k < Лекс b 1 b 2 ... b k,

если

a i < b i

для первого

i,

где

a i

и

b i

различаются,

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

от 1 до 2 ... до k < колекс b 1 b 2 ... 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 < ...

.

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

Мономы

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

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

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

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

Степенной обратный лексикографический порядок состоит также в сравнении сначала суммы степеней, а в случае равенства сумм степеней - в использовании обратного колексикографического порядка. То есть, учитывая два вектора экспоненты, один имеет $[a_{1},\ldots ,a_{n}]<[b_{1},\ldots ,b_{n}]$ если либо $a_{1}+\cdots +a_{n}<b_{1}+\cdots +b_{n},$ или $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}.$

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

В лексикографическом порядке одни и те же векторы экспоненты упорядочены как $[0,0,2]<[0,1,1]<[0,2,0]<[1,0,1]<[1,1,0]<[2,0,0].$

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

См. также

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

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Эгберт Харцхайм (2006). Заказанные наборы . Спрингер. стр. 88–89. ISBN 978-0-387-24222-4 .
^ Jump up to: Перейти обратно: ^а ^б Франц Баадер; Тобиас Нипков (1999). Переписывание терминов и все такое . Издательство Кембриджского университета. стр. 18–19. ISBN 978-0-521-77920-3 .
^ Калуде, Кристиан (1994). Информация и случайность. Алгоритмический взгляд . Монографии EATCS по теоретической информатике. Спрингер-Верлаг . п. 1 . ISBN 3-540-57456-5 . Збл 0922.68073 .
^ Роббиано, Л. (1985). Упорядочение термов на кольце полиномов. На Европейской конференции по компьютерной алгебре (стр. 513–517). Шпрингер Берлин Гейдельберг.
^ Вайспфеннинг, Волкер (май 1987 г.), «Допустимые порядки и линейные формы», Бюллетень SIGSAM , 21 (2), Нью-Йорк, Нью-Йорк, США: ACM: 16–18, doi : 10.1145/24554.24557 , S2CID 10226875 .

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

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

[Harzheim-1] Jump up to: Перейти обратно: ^а ^б Эгберт Харцхайм (2006). Заказанные наборы . Спрингер. стр. 88–89. ISBN 978-0-387-24222-4 .

[BaaderNipkow1999-2] Jump up to: Перейти обратно: ^а ^б Франц Баадер; Тобиас Нипков (1999). Переписывание терминов и все такое . Издательство Кембриджского университета. стр. 18–19. ISBN 978-0-521-77920-3 .

[3] Калуде, Кристиан (1994). Информация и случайность. Алгоритмический взгляд . Монографии EATCS по теоретической информатике. Спрингер-Верлаг . п. 1 . ISBN 3-540-57456-5 . Збл 0922.68073 .

[4] Роббиано, Л. (1985). Упорядочение термов на кольце полиномов. На Европейской конференции по компьютерной алгебре (стр. 513–517). Шпрингер Берлин Гейдельберг.

[5] Вайспфеннинг, Волкер (май 1987 г.), «Допустимые порядки и линейные формы», Бюллетень SIGSAM , 21 (2), Нью-Йорк, Нью-Йорк, США: ACM: 16–18, doi : 10.1145/24554.24557 , S2CID 10226875 .

[1]

[2]

[3]

[4]

[5]