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

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 с двумя символами и т. д., включая даже пустую последовательность без символов вообще. Лексикографический порядок на множестве всех этих конечных слов упорядочивает слова следующим образом: ${\displaystyle \varepsilon }$

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

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

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

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

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

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

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

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

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

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

Моноид слов

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

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

• а является префиксом 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}$

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

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

Лексикографический порядок определяет порядок n -арного декартова произведения упорядоченных множеств, который является полным порядком, когда все эти множества сами по себе полностью упорядочены. Элементом декартова произведения является последовательность, ^th элемент которой принадлежит для каждого. Поскольку при оценке лексикографического порядка последовательностей сравниваются только элементы, имеющие одинаковый ранг в последовательностях, лексикографический порядок распространяется на декартовы произведения упорядоченных множеств. ${\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}$

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

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

Пусть – свободная абелева группа ранга , элементами которой являются последовательности целых чисел, а операцией является сложение . Групповой заказ — это общий заказ , совместимый со сложением, т. е. ${\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-циклами (синим цветом). Векторы инверсии (отмечены красным) перестановок в порядке колексов находятся в порядке ревколексов , и наоборот.

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

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. Эгберт Харцхайм (2006). Заказанные наборы . Спрингер. стр. 88–89. ISBN 978-0-387-24222-4.
2. Франц Баадер; Тобиас Нипков (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 , Нью-Йорк, Нью-Йорк, США: ACM, 21 (2): 16–18, doi : 10.1145/24554.24557 , S2CID  10226875.

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

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