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

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

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

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

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

Мотивация и определение [ править ]

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

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

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

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

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

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

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

Системы счисления и даты [ править ]

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

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

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

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

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

Моноид слов [ править ]

Моноид слов над алфавитом $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

b = uyw

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

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

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

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

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

В частности, для двух частично упорядоченных наборов $A$ и $B$ лексикографический порядок декартового произведения $A \times B$ определяется как

(a, b) \leq (a', b')

тогда и только тогда, когда

a < a'

или

(a = a' и b \leq b')

.

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

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

В отличие от конечного случая, бесконечное произведение хороших порядков не обязательно хорошо упорядочено лексикографическим порядком. Например, набор счетно бесконечных двоичных последовательностей (по определению, набор функций от неотрицательных целых чисел до ${0, 1}$ , также известный как пространство Кантора ${0, 1} ω$ ) не является хорошо упорядоченным; подмножество последовательностей , которые имеют ровно один $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$ бесконечно, это не так.

Конечные подмножества [ править ]

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

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

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

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

.

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

Групповые заказы ${\ Displaystyle \ mathbb {Z} ^ {п}}$ [ править ]

Пусть - свободная абелева группа ранга $n$ , элементы которой представляют собой последовательности из $n$ целых чисел, а операция - сложение . Порядок группы на это общий порядок , который совместит с добавлением, то есть ${\ Displaystyle \ mathbb {Z} ^ {п}}$ ${\ Displaystyle \ mathbb {Z} ^ {п}}$

{\ displaystyle a <b \ quad \ Longleftrightarrow \ quad a + c <b + c.}

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

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

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

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

Колексикографический порядок [ править ]

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

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

a 1 a 2 ... a k < lex b 1 b 2 ... b k,

если

a i < b i

для первого

i,

где

a i

и

b i

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

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

a 1 a 2 ... a k < colex 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 <...

.

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

Мономы [ править ]

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

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

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

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

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

[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].

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

См. Также [ править ]

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

Ссылки [ править ]

^ а б Эгберт Харцхейм (2006). Заказанные наборы . Springer. С. 88–89. ISBN 978-0-387-24222-4.
^ a b Франц Баадер; Тобиас Нипков (1999). Перезапись терминов и все такое . Издательство Кембриджского университета. С. 18–19. ISBN 978-0-521-77920-3.
^ Calude, Cristian (1994). Информация и случайность. Алгоритмическая перспектива . Монографии EATCS по теоретической информатике. Springer-Verlag . п. 1 . ISBN 3-540-57456-5. Zbl 0922.68073 .
^ Robbiano, L. (1985). Упорядочения терминов на кольце многочленов. В Европейской конференции по компьютерной алгебре (стр. 513-517). Springer Berlin Heidelberg.
^ Weispfenning, Volker (май 1987), "Приемлемые Заказы и линейные формы", SIGSAM Bulletin , Нью - Йорк, Нью - Йорк, США: ACM, 21 (2): 16-18, DOI : 10,1145 / 24554,24557 , S2CID 10226875 .

Внешние ссылки [ править ]

Учебные материалы, связанные с лексикографией и колексикографией, заказать в Викиверситете

[Harzheim-1] а б Эгберт Харцхейм (2006). Заказанные наборы . Springer. С. 88–89. ISBN 978-0-387-24222-4.

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

[3] Calude, Cristian (1994). Информация и случайность. Алгоритмическая перспектива . Монографии EATCS по теоретической информатике. Springer-Verlag . п. 1 . ISBN 3-540-57456-5. Zbl 0922.68073 .

[4] Robbiano, L. (1985). Упорядочения терминов на кольце многочленов. В Европейской конференции по компьютерной алгебре (стр. 513-517). Springer Berlin Heidelberg.

[5] Weispfenning, Volker (май 1987), "Приемлемые Заказы и линейные формы", SIGSAM Bulletin , Нью - Йорк, Нью - Йорк, США: ACM, 21 (2): 16-18, DOI : 10,1145 / 24554,24557 , S2CID 10226875 .

[1]