Lexikographische Ordnung – einfach erklärt

Grundidee und Definition

Die lexikographische Ordnung überträgt eine lineare Ordnung einfacher Elemente auf zusammengesetzte Objekte. Ihr bekanntestes Beispiel ist das Sortieren von Wörtern im Lexikon: Zuerst entscheidet der erste Buchstabe, bei Gleichheit der zweite usw. Ist ein Wort Anfangsteil eines anderen, steht das kürzere zuerst, etwa „Tal“ vor „Talent“. Bei einem Standardalphabet spricht man deshalb oft einfach von alphabetischer Ordnung. Sortierte Suchbegriffe lassen sich auch in sehr großen Mengen schnell finden.

Ausgangspunkt ist ein quasigeordnetes Alphabet \left(\Sigma,\leq\right), also eine Zeichenmenge \Sigma mit einer Vergleichsrelation \leq. Eine Zeichenkette a=(a_1,a_2,\ldots) ist lexikographisch kleiner als b=(b_1,b_2,\ldots), wenn am ersten Index i, an dem sie verschieden sind, a_i echt kleiner als b_i ist: a_i\leq b_i\wedge b_i\not\leq a_i. Alternativ ist a kleiner, wenn a ein gleichwertiger Anfang von b ist, aber kürzer ist.

Üblicherweise wird für die zusammengesetzte Ordnung dasselbe Zeichen \leq, beziehungsweise < für die strikte Ordnung, verwendet wie im Alphabet. Eine Quasiordnung bleibt dadurch eine Quasiordnung; ebenso werden totale Quasiordnungen, Halbordnungen und Totalordnungen jeweils wieder zu solchen Ordnungen. Besonders häufig ist die Totalordnung.

Bei Folgen mit fester endlicher Länge entfällt die Regel für unterschiedlich lange Ketten. Für Paare gilt: (a_1,a_2)<(b_1,b_2), wenn entweder a_1<b_1 oder a_1=b_1 und a_2<b_2.

Alltagsbeispiele

Datumsangaben als Tripel (Jahr, Monat, Tag) werden lexikographisch zeitlich geordnet. Datum X liegt vor Datum Y, wenn sein Jahr kleiner ist; bei gleichem Jahr sein Monat früher liegt; oder bei gleichem Jahr und Monat sein Tag kleiner ist.

Auch ein Medaillenspiegel folgt diesem Prinzip: Zuerst zählt die Zahl der Goldmedaillen, dann bei Gleichstand die Zahl der Silbermedaillen, danach die Zahl der Bronzemedaillen. Daher liegt Land 1 mit 10,5,7 vor Land 2 mit 8,7,4, dieses vor Land 3 mit 8,5,7, danach folgen Land 4 mit 5,3,7 und Land 5 mit 5,3,2.

Unendliche Folgen und Verallgemeinerungen

Auch unendliche Folgen können lexikographisch verglichen werden. (s_i)_{i\in\mathbb N} ist kleiner als (t_i)_{i\in\mathbb N}, wenn beide vor einem Index k übereinstimmen, aber s_k<t_k gilt. Bei \Sigma=\{0,1,2,3,4,5,6,7,8,9\} lassen sich Folgen als Dezimalbrüche für reelle Zahlen zwischen 0 und 1 lesen. Die lexikographische Ordnung entspricht dann im Wesentlichen der reellen Ordnung auf [0,1]. Eine Ausnahme ergibt sich bei abbrechenden Dezimalbrüchen: Sie haben zwei verschiedene Folgen, zum Beispiel 0{,}14=0{,}14000\ldots=0{,}13999\ldots, obwohl (1,3,9,9,9,\ldots)<(1,4,0,0,0,\ldots) gilt.

Allgemeiner kann der Indexbereich eine beliebige wohlgeordnete Menge W sein. Für Funktionen f,g\colon W\to X mit linear geordnetem X gilt f<g, wenn am kleinsten Element w von W, an dem sie verschieden sind, f(w)<g(w) ist. Die dadurch entstehende Ordnung der Funktionen ist wieder linear.

Ein mengenlehrelicher Spezialfall benutzt eine Ordinalzahl \lambda als Indexmenge und Werte 0 und 1. 2^\lambda steht bijektiv zur Potenzmenge von \lambda: Einer Teilmenge X wird ihre Kennfunktion f_X zugeordnet, mit f_X(\sigma)=1 für \sigma\in X und f_X(\sigma)=0 für \sigma\notin X. Für jede wohlgeordnete Teilmenge S von lexikographisch geordnetem 2^\lambda gilt |S|\leq|\lambda|. Der im Artikel dargestellte Induktionsbeweis nutzt Einschränkungen auf kleinere Ordinalzahlen sowie den ersten Unterschied zwischen einem Element und seinem direkten Nachfolger.

Einsatz in der Informatik

Computer vergleichen Inhalte einzelner adressierbarer Speicherstellen, etwa Bytes mit 8 Bits, auf unterster Ebene total geordnet. Wenn Ziffern oder Buchstaben so auf Bitkombinationen abgebildet sind, dass diese Ordnung der üblichen Ziffern- oder Alphabetordnung entspricht, können daraus Zeichenketten und andere zusammengesetzte Datentypen lexikographisch verglichen werden.

Entspricht die Reihenfolge der Vergleichsränge den Speicheradressen, heißt dies Big-Endian: Das höherwertige Byte hat die niedrigere Adresse. Bei Little-Endian hat es die höhere Adresse. Weil sich der Vergleich oft schon am ersten, höchstrangigen Byte entscheidet, ist unmittelbarer Zugriff auf dieses Byte günstig.

Zahlen fester Länge werden auf vielen neueren Maschinen Little-Endian gespeichert und meist als 2, 4, 8 oder 16 Bytes mit besonderen Maschineninstruktionen verglichen; dabei wird das lexikographische Prinzip nicht zusammengesetzt angewendet. Bei Langzahlarithmetik für ganze Zahlen beliebiger Länge beginnt der numerische Vergleich am höchstrangigen Ende. Vorher müssen die Längen durch führende Nullen angeglichen werden. Danach vergleicht man gleichrangige Stellen. Die Verarbeitung läuft beim Vergleichen und bei der Division von hochrangig zu niedrigstrangig, bei Addition, Subtraktion und Multiplikation umgekehrt.

Bitketten sind Zeichenketten über \Sigma=\{0,1\}. Bei kompakter Speicherung von einem Bit je Ziffer können im letzten, niedrigstrangigen Wort Füllbits auftreten. Der lexikographische Vergleich beginnt dennoch mit der höchstrangigen Komponente. Auf Little-Endian-Maschinen muss das höchstrangige Wort hierfür den höchsten Index haben, wenn die vorhandenen Vergleichsinstruktionen für Wörter verwendet werden sollen.

Bei Zeichenketten liegt die erste und höchstrangige Komponente auf jedem Maschinentyp an der niedrigsten Adresse, sie sind also im Big-Endian-Stil gespeichert. C und C++ bieten dafür strcmp für unterschiedlich lange nullterminierte Zeichenketten mit eingeschränktem Alphabet, memcmp für gleich lange Bytefolgen mit vollem Zeichensatz und wcscmp für unterschiedlich lange 16-Bit-wide strings des Typs wchar_t, jeweils mit den genannten Einschränkungen durch Abschlusszeichen.

Lexikographische Präferenzen

In der Mikroökonomik beschreibt eine lexikographische Präferenz eine strenge Rangfolge von Gütern. Für Güterbündel \mathbf{x}_i=(x_i^1,x_i^2,\ldots,x_i^m) mit i=a,b ist die Präferenz-Indifferenz-Relation R lexikographisch, wenn \mathbf{x}_aR\mathbf{x}_b genau dann gilt, wenn x_a^1>x_b^1 oder x_a^1=x_b^1 und zugleich x_a^2\geq x_b^2. Ein Bündel ist also mindestens so gut wie ein anderes, wenn es mehr vom ersten Gut enthält; nur bei gleicher Menge des ersten Guts entscheidet die Menge des zweiten Guts.

Eine lexikographische Präferenzenordnung ist vollständig, asymmetrisch und damit auch antisymmetrisch, negativ transitiv und transitiv. Nach Debreu (1959) kann sie nicht durch eine Nutzenfunktion repräsentiert werden.