Unicode Collation Algorithm

Der Unicode Collation Algorithm (kurz UCA) ist der vom Unicode-Konsortium veröffentlichte Algorithmus, um Zeichenketten aus Unicode-Zeichen zu vergleichen und so alphabetisch zu ordnen. Er ist dabei bewusst so offen gehalten, dass sprachspezifische Besonderheiten und besondere Anwenderwünsche berücksichtigt werden können. Zum Algorithmus steht außerdem eine Tabelle mit Standardwerten für die Sortierung zur Verfügung, die Default Unicode Collation Element Table (DUCET). Daneben stellt das Common Locale Data Repository entsprechende Tabellen für viele weitere Sprachen zur Verfügung, die etwa in der Implementierung des ICU-Projekts genutzt werden.

Anforderungen

Die große Anzahl an Zeichen, die in Unicode kodiert sind, macht es schwierig, Zeichenketten zu sortieren. So ist etwa nicht klar, ob Wörter aus griechischen Buchstaben vor solchen aus kyrillischen Buchstaben stehen sollten oder umgekehrt. Auch entspricht die Reihenfolge, in der die einzelnen Zeichen kodiert sind, nicht immer der gewünschten Reihenfolge bei der Sortierung.

In verschiedenen Sprachen bestehen unterschiedliche Auffassungen über die Reihenfolge einzelner Buchstaben. Beispielsweise werden in deutschen Lexika Wörter mit å so sortiert, als stünde dort ein gewöhnliches a, während in skandinavischen Sprachen das å ein eigener Buchstabe ist, der nach dem z kommt. Selbst innerhalb einer Sprache können solche Unterschiede vorkommen, etwa im Deutschen, wo das ä teilweise wie ein a, teilweise wie ein ae behandelt wird.

Es kommt auch vor, dass nicht einfach nach einzelnen Zeichen sortiert werden kann. So wird der Digraph ch im traditionellen Spanisch als eigener Buchstabe behandelt, der zwischen c und d kommt.

Ferner können je nach Anwendung bestimmte zusätzliche Anforderungen gestellt werden, beispielsweise könnte St. wie Sankt einsortiert werden.

Geschichte

Autoren des Algorithmus sind Mark Davis und Ken Whistler. Die erste Version wurde am 30. März 1997 veröffentlicht.^[1] Zum Stand September 2012 liegt der Algorithmus in der Version 26 vor. Mit ISO 14651 existiert ein ähnlicher Algorithmus der ISO, der allerdings weniger Möglichkeiten bietet.^[2] Mit neueren Versionen kamen immer mehr Konfigurationsmöglichkeiten hinzu, etwa die Möglichkeit, Zahlen numerisch zu sortieren.

Algorithmus

Um zwei Zeichenketten zu vergleichen, geht der Algorithmus in verschiedenen Schritten vor und vergleicht die beiden Zeichenketten auf verschiedenen Ebenen. Die Anzahl und Bedeutung der Ebenen kann dabei prinzipiell frei gewählt werden, Standard sind jedoch drei Ebenen mit folgenden Bedeutungen:

Ebene 1: Grundbuchstaben

Auf der ersten Ebene werden die Zeichenketten gemäß ihrer Grundbuchstaben verglichen. Akzente, Groß- und Kleinschreibung, Satzzeichen und Ähnliches werden dabei üblicherweise ignoriert. So werden auf dieser Ebene die Wörter Müll und Mull als gleich betrachtet, das Wort Muli kommt aber davor.

Ebene 2: Akzente

Stimmen die Wörter in den Grundbuchstaben überein, werden als Nächstes die Akzente verglichen. In fast allen Sprachen wird dabei von links nach rechts nach dem ersten Unterschied gesucht, und dann nach einer festen Reihenfolge sortiert: Buchstaben ohne Akzent zuerst, die anderen Akzente in einer festen Reihenfolge. So ergibt sich etwa die Reihenfolge cote – coté – côte – côté. Eine Ausnahme bildet das kanadische Französisch: Hier wird traditionell nach dem letzten Unterschied sortiert: cote – côte – coté – côté.

Ebene 3: Groß- und Kleinschreibung

Stimmen die Wörter auch in den Akzenten überein, so wird nach der Groß- und Kleinschreibung sortiert, wobei meist die Kleinbuchstaben vor die Großbuchstaben sortiert werden.

Weitere Ebenen

Bei Bedarf können sich weitere Ebenen anschließen, um eine noch feinere Unterscheidung zu ermöglichen. Häufig wird als Abschluss nach den einzelnen Codepunkten sortiert. Dies stellt sicher, dass zwei unterschiedliche Zeichenketten immer in derselben Reihenfolge sortiert werden.

Sortiergewichte

Um Zeichenketten zu vergleichen, liefert der Algorithmus zu einer Zeichenkette aus Unicode-Zeichen einen binären Sortierschlüssel. Dieser Schlüssel wird dann im eigentlichen Sortieralgorithmus beim Vergleich verwendet. Zur Bestimmung des Sortierschlüssels wird eine Tabelle verwendet, die für einzelne Zeichen oder Zeichenkombinationen für alle Ebenen binäre Gewichte auflistet, eine sogenannte Collation Element Table. Einem Eintrag können dabei auch mehrere Gewichte pro Ebene zugewiesen werden. Ein Gewicht von 0000 bedeutet dabei, dass das entsprechende Zeichen auf dieser Ebene ignoriert werden soll. Für Zeichen, die nicht in der Tabelle aufgeführt werden, muss ein Gewicht berechnet werden. Für die Standardtabelle ist dies nur bei CJKV-Schriftzeichen der Fall, für die Berechnung der Gewichte ist auch ein Algorithmus angegeben.

Zunächst wird die Zeichenkette in möglichst lange Stücke zerlegt, die einen Eintrag in der Tabelle haben, und die zugehörigen Gewichte aus der Tabelle ausgelesen. Diese Gewichte werden zunächst für jede Ebene einzeln aneinander gehängt, wobei 0000 weggelassen wird. Für eine kanadisch-französische Sortierung wird die Reihenfolge in Ebene 2 umgekehrt. Die Schlüssel für die einzelnen Ebenen werden zuletzt durch 0000 getrennt zu einem einzigen Sortierschlüssel aneinander gehängt.

Beispiele

Die meisten dieser Beispiele für Einträge einer Collation Element Table sind der DUCET in der Version 6.1.0 entnommen.^[3] Angegeben sind hier jeweils die Gewichte der ersten drei Ebenen als Hexadezimalzahlen. Die Gewichte werden durch Punkte getrennt und in eckige Klammern eingeschlossen.

Einfache Buchstaben

Zeichen	Gewichte	Anmerkung
a	`[15D4.0020.0002]`	`15D4` ist das Gewicht für den Grundbuchstaben a.
A	`[15D4.0020.0008]`	Das große A unterscheidet sich erst auf der dritten Ebene vom kleinen a.
b	`[15EA.0020.0002]`	`15EA` ist das Gewicht für den Grundbuchstaben b, dieser kommt nach a (mit etwas Platz für benutzerspezifische Ergänzungen).
c	`[1602.0020.0002]`
z	`[187A.0020.0002]`
α	`[190E.0020.0002]`	Nach den Buchstaben des lateinischen Alphabets folgen die der anderen Alphabete, etwa des griechischen.

Buchstaben mit Akzenten, Ligaturen und Buchstabenkombinationen

Buchstaben mit diakritischen Zeichen werden in ein Grundzeichen und folgende kombinierende Zeichen zerlegt.

Zeichen	Gewichte	Anmerkung
à	`[15D4.0020.0002], [0000.0035.0002]`	Nach dem Gewicht für a folgt das Gewicht für den Gravis, der auf Ebene 1 unberücksichtigt (`0000`) bleibt.
å	`[15D4.0020.0002], [0000.0043.0002]`	Im Normalfall wird das å als Variante des a aufgefasst.
å	`[187B.0020.0002]`	Im Schwedischen wird ein abweichendes Gewicht verwendet, hier folgt das å als eigener Buchstabe nach dem z.
ä	`[15D4.0020.0002], [0000.0047.0002]`
æ	`[15D4.0020.0004], [0000.0139.0004], [1631.0020.001F]`	æ wird auf der ersten Ebene wie ae behandelt.
ch	`[1603.0020.0002]`	Im traditionellen Spanisch wird ch wie ein Buchstabe behandelt, der nach c kommt.

Steuerzeichen, Symbole und Ziffern

Zeichen	Gewichte	Anmerkung
LRM	`[0000.0000.0000]`	Steuerzeichen wie z. B. das Links-nach-rechts-Zeichen werden vollständig ignoriert.
$	`[15A4.0020.0002]`
€	`[15BC.0020.0002]`
1	`[15CB.0020.0002]`
2	`[15CC.0020.0002]`
²	`[15CC.0020.0014]`	Hochgestellte Ziffern unterscheiden sich analog zu Großbuchstaben erst auf der dritten Ebene von der Grundziffer.
9	`[15D3.0020.0002]`

Satz- und Leerzeichen

Bei Satz- und Leerzeichen gibt es verschiedene Möglichkeiten, die Gewichte zu wählen.

In vielen Implementierungen, etwa in PHP^[4] werden diese Zeichen so gewichtet, wie in der Tabelle angegeben.

Zeichen	Gewichte	Anmerkung
gewöhnliches Leerzeichen	`[020A.0020.0002]`
geschütztes Leerzeichen	`[020A.0020.001B]`	Das geschützte Leerzeichen wird erst auf Ebene 3 vom gewöhnlichen unterschieden.
Bindestrich-Minus (-)	`[020E.0020.0002]`
Halbgeviertstrich (–)	`[0216.0020.0002]`
Komma (,)	`[0221.0020.0002]`
Doppelpunkt (:)	`[0237.0020.0002]`
Ausrufezeichen (!)	`[025E.0020.0002]`
Punkt (.)	`[0273.0020.0002]`
Apostroph (')	`[02EA.0020.0002]`
Apostroph (’)	`[02EC.0020.0002]`
Anführungszeichen (")	`[02F1.0020.0002]`
Anführungszeichen (“)	`[02F2.0020.0002]`
Anführungszeichen („)	`[02F4.0020.0002]`
öffnende Klammer (()	`[02FB.0020.0002]`
schließende Klammer ())	`[02FC.0020.0002]`
Schrägstrich (/)	`[0372.0020.0002]`

Ursprünglich war geplant, diese Zeichen als Standardverhalten überhaupt nicht zu berücksichtigen, ihnen also wie Steuerzeichen das Gewicht [0000.0000.0000] zu geben.^[5]

In der derzeitigen Fassung des Algorithmus wird als Standardverhalten etwas Ähnliches gefordert: Auch hier wird als Gewicht [0000.0000.0000] gewählt, aber dafür noch eine vierte Ebene angefügt, in der als Gewicht der eigentlich für die Ebene 1 angegebene Wert verwendet wird, während andere Zeichen den in dieser Ebene höchstmöglichen Wert FFFF erhalten.

Daneben existieren noch weitere Varianten, zwischen denen der Benutzer wählen kann.

Anpassung

Die Standardtabelle kann auf viele Arten angepasst werden:

Es können sprachspezifische Änderungen an den einzelnen Gewichten vorgenommen werden und zusätzliche Zeichenkombinationen mit Gewichten aufgenommen werden. Für viele Sprachen stehen entsprechend angepasste Tabellen bereits zur Verfügung. Für benutzerdefinierte Anpassungen existiert eine eigene Syntax, diese anzugeben, die von geeigneten Programmen in eine Tabelle mit entsprechenden Sortiergewichten übersetzt werden kann.
Bei Bedarf kann angegeben werden, dass auf der zweiten Ebene vom Ende der Zeichenkette aus sortiert werden soll, wie es im kanadischen Französisch üblich ist. Prinzipiell ist dies auch für andere Ebenen möglich, wenn auch nicht sinnvoll.
Es kann gewählt werden, auf wie vielen Ebenen der Vergleich stattfinden soll. Diese Zahl wird als Stärke bezeichnet. Der Standard ist 3, aber sofern die Tabelle Gewichte für mehr Ebenen angibt, kann auch eine größere Zahl gewählt werden. Es kann aber auch eine kleinere Zahl gewählt werden, wenn ein kurzer Sortierschlüssel Priorität gegenüber einer detaillierten Sortierung hat.
Für bestimmte Zeichen (meist Leer- und Satzzeichen) kann zwischen verschiedenen Varianten für die Gewichte gewählt werden.

Der Standard beschreibt noch viele weitere Optionen.

Varianten

Es gibt verschiedene Methoden den Algorithmus abzuändern, etwa um kürzere binäre Schlüssel zu erhalten. So ist es möglich, auf die trennenden 0000 zu verzichten, sofern die Gewichte von Ebene zu Ebene abnehmen. Daneben gibt es noch weitere Varianten, die zu stärkeren Einsparungen führen.

Beispiel

Es sollen die Begriffe Nina, Nino, NINO, Niño und Ninu in alphabetische Reihenfolge gebracht werden. Sie werden in einzelne Buchstaben zerlegt, deren Gewichte bestimmt und daraus die Sortierschlüssel zusammengesetzt. Im Schlüssel ist der Teil, der zur ersten Ebene gehört, blau unterlegt, die zweite Ebene grün, die dritte gelb.

Nina kommt als erstes, das Wort unterscheidet sich bereits auf der ersten Ebene vom folgenden Wort Nino (Unterstreichung). Dieses wiederum stimmt auf den beiden ersten Ebenen mit NINO überein, erst in der dritten Ebene ergibt sich ein Unterschied. Beim nächsten Wort Niño ist der Schlüssel wegen der Tilde in der zweiten und dritten Ebene länger als bei den anderen Worten, diese Tilde liefert auch den ersten Unterschied zum vorhergehenden Wort. Als letztes kommt Ninu, das sich wiederum bereits auf der ersten Ebene von den vorangehenden Wörtern unterscheidet.

Würde man diese Wörter nach Codepunkten sortieren, ergäbe sich stattdessen die Reihenfolge NINO – Nina – Nino – Ninu – Niño.

Wort	zerlegt				Sortierschlüssel
Nina	N	i	n	a	`1734.16B2.1734.15D4.0000.0020.0020.0020.0020.0000.0008.0002.0002.0002`
Nina	`[1734.0020.0008]`	`[16B2.0020.0002]`	`[1734.0020.0002]`	`[15D4.0020.0002]`
Nino	N	i	n	o	`1734.16B2.1734.1756.0000.0020.0020.0020.0020.0000.0008.0002.0002.0002`
Nino	`[1734.0020.0008]`	`[16B2.0020.0002]`	`[1734.0020.0002]`	`[1756.0020.0002]`
NINO	N	I	N	O	`1734.16B2.1734.1756.0000.0020.0020.0020.0020.0000.0008.0008.0008.0008`
NINO	`[1734.0020.0008]`	`[16B2.0020.0008]`	`[1734.0020.0008]`	`[1756.0020.0008]`
Niño	N	i	ñ	o	`1734.16B2.1734.1756.0000.0020.0020.0020.004E.0020.0000.0008.0002.0002.0002.0002`
Niño	`[1734.0020.0008]`	`[16B2.0020.0002]`	`[1734.0020.0002], [0000.004E.0002]`	`[1756.0020.0002]`
Ninu	N	i	n	u	`1734.16B2.1734.181B.0000.0020.0020.0020.0020.0000.0008.0002.0002.0002`
Ninu	`[1734.0020.0008]`	`[16B2.0020.0002]`	`[1734.0020.0002]`	`[181B.0020.0002]`

Suchalgorithmus

Teile des Algorithmus können auch bei Textsuchen Anwendung finden, etwa wenn mit einer Suche nach ss auch Wörter mit ß gefunden werden sollen. Eine Übereinstimmung soll in diesem Fall dann erkannt werden, wenn das Suchwort und der mögliche Treffer auf der ersten Ebene übereinstimmen.

Weblinks

Offizielle Formulierung des Algorithmus (englisch)
Demonstration des Algorithmus
ICU User Guide: Collation Introduction (englisch)

Einzelnachweise

↑ Erste Revision des UCA
↑ Unicode-FAQ: Collation What are the differences between the UCA and ISO 14651?
↑ allkeys.txt, Version 6.1.0
↑ PHP manual: The Collator class
↑ UCA, Version 1, Abschnitt Variable Collation Elements

[1] Erste Revision des UCA

[2] Unicode-FAQ: Collation What are the differences between the UCA and ISO 14651?

[3] ys.txt, Version 6.1.0

[4] PHP manual: The Collator class

[5] UCA, Version 1, Abschnitt Variable Collation Elements

[1]

[2]

[3]

[4]

[5]