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. 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. 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:

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.

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.

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

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