Lexikografické uspořádání

Lexikografické uspořádání neboli slovníkové řazení je matematický pojem z oboru teorie uspořádání, který formalizuje vlastnosti uspořádání „podle abecedy“ pro potřeby práce s lineárně uspořádanými množinami.

Je-li $X$ množina lineárně uspořádaná relací $R$, pak lze na množině všech konečných posloupností prvků z $X$ zavést lineární uspořádání zvané lexikografické , které dvě posloupnosti porovná podle prvního prvku, v němž se liší.

Například budiž X množina 26 symbolů $\{a,b,c,\ldots ,z\}$, uspořádaná vztahem $a\prec b\prec c\prec \ldots \prec z$. Konečné posloupnosti symbolů se nazývají slova. Pak slovo $abcd$ předchází slovu $abdc$, protože první odlišný znak je na třetí pozici a $c$ předchází $d$. Je-li shodná část stejná (tj. jedno slovo je počátečním úsekem druhého), pak kratší slovo předchází delšímu: $a$ i $ab$ předchází slovům $abc$ a $abcd$.

Lexikografické uspořádání je tedy přesně to abecední třídění, které lidé běžně používají ve slovnících, rejstřících apod.

Lineární uspořádání je abstraktní struktura, tj. lze uspořádat množiny jakýchkoli objektů: čísel, funkcí, symbolů apod. X může být jakákoli neprázdná množina (i nekonečná, dokonce sebevětší mohutnosti) s lineárním uspořádáním. Např. je-li $X$ množina prvních 26 přirozených čísel, lze s ní pracovat obdobně, jako s množinou symbolů: Posloupnost $(1;2;3;4)$ předchází posloupnosti $(1;2;4;3)$ přesně tak, jako slovo $abcd$ předcházelo $abdc$, a předchází i posloupnosti $(1;2;3;4;5)$.

Vlastnosti

Lexikografické uspořádání není přes svou nepřehlednou definici nic záhadného - odpovídá přesně tomu, čemu rozumíme pod pojmem „uspořádání podle abecedy“.
Pokud vezmeme jako množinu X seznam znaků nějaké abecedy a jako R uspořádání těchto znaků v abecedě, pak není lexikografické uspořádání nic jiného, než určení pořadí všech slov s nějakou určitou délkou. Pokud bychom navíc definovali způsob, jak porovnat dvě různě dlouhé uspořádané n-tice, můžeme rovnou začít řadit telefonní seznam.

Definice lexikografického uspořádání se ale neomezuje pouze na lineárně uspořádané podkladové množiny. Relace R může být v této definici jakékoliv uspořádání.
Uvažujme na chvilku o množině $X=\{1,2,3,4\}\,\!$ a jejím uspořádání $R=\{[1,1],[2,2],[3,3],[4,4],[1,3],[2,4],[1,4],[2,3]\}\,\!$.
Relace R je uspořádání, takže k ní můžeme definovat lexikografické uspořádání množiny všech uspořádaných trojic z $X^{3}=X\times X\times X\,\!$ .
Protože prvky 1 a 2 nejsou porovnatelné podle $R\,\!$, dostáváme následující vztahy:

• $[1,2,4]\leq _{Le}[1,3,1]\,\!$
• trojice $[1,1,1]\,\!$ a $[2,4,4]\,\!$ nejsou v lexikografickém uspořádání podle $R\,\!$ porovnatelné - stačí si dosadit do definice a vidíme, že není splněna ani jedna řádka, které podmiňují porovnatelnost v lexikografickém uspořádání.

Použití

Při řešení mnoha matematických problémů se ukazuje jako potřebné „přenést“ uspořádání nějaké množiny i na uspořádané dvojice (nebo obecně n-tice) prvků z této množiny. Lexikografické uspořádání je jednou z možností (i když zdaleka ne vždy tou nejlepší), jak něco takového provést - dobrým příkladem je definice ordinálního součtu a ordinálního součinu.

Maximo-lexikografické uspořádání

Lexikografické uspořádání je sice lineární, ale není dobrým uspořádáním. Tj. nelze je izomorfně zobrazit na žádné ordinální číslo.

Proto v něm existují slova, kterým předchází nekonečně mnoho jiných slov. To může být problém v řadě počítačových algoritmů, jak teoretických (teorie vyčíslitelnosti), tak i v praxi: Pokud program prochází slova v lexikografickém pořadí (a nějak je testuje, např. na podobnost se zadaným řetězcem při nějakém druhu vyhledávání), pak po prázdném slovu otestuje slovo $a$, pak $aa,aaa,aaaa,\dots$ a nikdy se nedostane ke slovu $b$ ani mnoha dalším.

Tento problém řeší maximo-lexikografické uspořádání, které porovnává slova především podle délky a teprve mezi slovy stejné délky rozhoduje lexikograficky. Takové uspořádání nad konečnou abecedou je nejen dobrým uspořádáním, ale navíc každému slovu předchází slov jen konečně mnoho, takže zmíněný program postupně projde slova všechna, počínaje nejkratšími.

Portály: Matematika