Grundsätzliche Probleme beim lexikalischen Sortieren

Warum sortiert man nicht einfach mit der compareTo-Methode der Klasse String? Weil die Ergebnisse äußerst unbefriedigend sind: Sortiert wird lediglich nach der Position in Unicode. Großbuchstaben werden damit immer vor Kleinbuchstaben einsortiert, Umlaute ganz am Ende: A < Z < a < z < ä. So wird z.B. "Ziege" vor "abgeben" einsortiert, was nicht unbedingt wünschenswert ist. Diesem Problem wäre noch einfach zu begegnen, leider aber halten Grapheme natürlicher Sprachen noch einige Besonderheiten bereit:

Expansion

Das Problem der Expansion besteht darin, daß manche Zeichen beim Einsortieren wie eine Folge von zwei Zeichen behandelt werden, also zu diesen zwei Zeichen expandiert werden.

Zum Beispiel wird im Deutschen das 'ß' so wie 'ss' einsortiert: Fusion < Fuß < Fussel.

Ähnlich behandelt das deutsche Telefonbuch ö wie oe, im Gegensatz zum Duden, wo ö wie o behandelt wird. In Österreich folgt ö erst nach o:

Beispiel

 

Duden:	Göbel <Goethe	<Goldmann<Götz
Telefonbuch:	Göbel <Goethe	<Götz <Goldmann
Österreich:	Goethe<Goldmann<Göbel	<Götz

Kontraktion

Das Problem der Kontraktion besteht darin, daß in manchen Sprachen eine Folge von zwei Zeichen so behandelt werden wie ein Zeichen. Im Deutschen gibt es keine Kontraktion, deswegen nehmen wir ein Beispiel aus dem Spanischen. Die Zeichenfolge 'ch' steht für ein Phonem und wird deswegen zwischen die Buchstaben c < ch < d einsortiert: coco < chocolate < doce.

Groß- und Kleinschreibung

Bei der Groß- und Kleinschreibung besteht das Problem, daß sie als Suchkriterium erst relevant wird, wenn alle Buchstaben des Wortes gleich sind. 'fliege' sollte also vor 'Fliege', aber nach 'Fliesen' eingeordnet werden.

Für den Programmierer heißt das, daß er erst nach der Buchstabenreihenfolge sortieren muß, und dann, in einem zweitem Schritt, die Groß- und Kleinschreibung testen muß.

Akzente und andere diakritische Zeichen

Ähnlich wie mit der Groß- und Kleinschreibung verhält es sich mit den diakritischen Zeichen (z. B. auch die Pünktchen auf den Umlauten). Auch sie werden erst sekundär wichtig. So gilt im Französisch:

accent aigu < accent gràve < accent circonflexe

Also: a < á < à < â

Beispiele: élevé < élève

créées < créer

Eine weitere Frage besteht darin, ob die Akzente wichtiger sind als die Groß- und Kleinschreibung. Meistens sieht es so aus, daß man drei Abfragen hintereinander durchführen muß: Erst das Sortieren nach den Zeichenwerten(primär), dann nach den Akzenten(sekundär) und schließlich nach der Groß- und Kleinschreibung(tertiär).

Naiver Lösungsansatz

Eine Zeichensortierfolge für das Deutsche könnte so aussehen: a < A < ä < Ä < b < B < ? < o < O < ö < Ö < p < P < ? < s < S < ß < t < T < u < U < ü < Ü < ? < z < Z

Solch eine geänderte Einzeichensortierfolge kann man leicht durch eine Umsetzungstabelle char [] collatingCodes realisieren: collatingCodes[i] ist der Sortierrang des Zeichens mit ASCII-Code i. Wenn man z.B. a den Sortierrang 0 zuordnet, A den Sortierrang 1, ä den Rang 2 usw., dann muß das Array collatingCodes so besetzt sein: collatingCodes['a'] = 0; collatingCodes['A'] = = 1; ...

Wenn man sich dabei auf den Bereich des ASCII-Codes beschränken kann, dann braucht man nur eine Umsetzungstabelle für 256 Einträge und nicht für die 65536 Einträge des Unicodes. Durch ein paar if-Abfragen kann man die benötigte Länge der Tabelle auf Kosten der Laufzeit weiter reduzieren.

Dabei sind aber dann die oben angesprochenen Anforderungen (Expansion, Kontraktion, Groß- und Kleinschreibung, diakritische Zeichen) noch nicht behandelt worden.

Zusätzliche Probleme durch Unicode

Neben der Ermittlung der Sortierrangfolge ist auch die Frage der Gleichheit zweier Zeichenketten wichtig. Für beides ist wichtig zu wissen, daß die Unicode-Darstellung einer Zeichenfolge nicht unbedingt eindeutig ist und deshalb eine Normierung auf eine eindeutige Standarddarstellung nötig ist.

Ein Grund für diese Nichteindeutigkeit liegt in unterschiedlichen Strategien zur Kombination von Buchstaben mit diakritischen Zeichen. Im klassischen ASCII-Code werden diakritische Zeichen wie die Akzente und die Umlautzeichen mit den entsprechenden Buchstaben als ein einziges Zeichen mit einem einzigen Code implementiert (á oder ä zum Beispiel, Codes 0xE1 bzw. 0xE4). Bei der Definition des Unicodes dagegen verfolgt man angesichts der Fülle von diakritischen Zeichen (z.B. für Lautschriften) und betroffener "Grundzeichen" die Strategie, die Kombination eines Grundzeichens mit einem diakritischen Zeichen als Folge zweier Zeichen zu implementieren, á zum Beispiel als Folge der Zeichen a und ´, mit den Codes 0x0061 und 0x0341.

Ein weiteres Beispiel für Nichteindeutigkeit der Unicodedarstellung einer Zeichenkette liegt bei nichtarabischen Ziffernsätzen. Bei den römischen Zahlen gibt es den Fall, daß eine Ziffer durch zwei Buchstaben dargestellt wird, die 4 z.B. durch die zwei Buchstaben IV. Der Unicode definiert zusätzlich die römische 4 als eigenes Zeichen. Um beide Möglichkeiten als gleich zu behandeln, muß man die compatibility Versionen verwenden.

Zum Erzielen von Eindeutigkeit kann man also entweder alle Einzeichendarstellungen in Mehrzeichendarstellungen zerlegen (Decomposition) oder Mehrzeichendarstellungen zu Einzeichendarstellungen zusammenfassen (Composition). Dabei werden noch zwei Grundstrategien "canonical" und "compatibility" unterschieden, so daß man insgesamt 4 Umwandlungsarten unterscheidet:

• canonical decomposition (D)
• canonical composition (C)
• compatibility decomposition (KD, K anscheinend für compatibility)
• compatibility composition (KC)

Die kanonische Decomposition scheint den neueren Darstellungsstrategien des Unicode zu folgen, während sich die compatibility decomposition eher an konventionellen Mehrzeichendarstellungen orientiert.

Bei Unicode ist dies beschrieben in: http://www.unicode.org/unicode/reports/tr15/

Die Lösung: java.text.RuleBasedCollator

De Klasse RuleBasedCollator kann

• Regeln interpretieren, mit denen der Programmierer lexikographische Besonderheiten einer Sprache definiert. Die Regeln werden in Textform an den Konstruktor RuleBasedCollator( String rules ) übergeben und dort in eine effiziente Tabellenstruktur überführt. Meistens reicht es jedoch, die bereitgestellten Standartregeln zu benutzen.
• den lexikographischen Stringvergleich zweier Strings anhand der umgesetzten Regeln durchführen, Methode int compare(String string1, String string2).
• zu einem String einen sogenannten CollationKey errechnen. Ein CollationKey ist eine für den lexikographischen Stringvergleich optimierte Stringdarstellung.

Für den einmaligen Vergleich zweier Strings ist die Methode compare des RuleBasedCollator schneller, da der Vergleich direkt durchgeführt wird.

Beim Sortieren aber, wo ein String in der Regel mehrfach mit anderen Strings verglichen wird, spart man Rechenzeit auf Kosten von Speicherplatz, wenn man zunächst zu allen Strings die CollationKeys errechnet und dann anhand der CollationKeys sortiert.

Sortierregeln

Zunächst einmal bietet SUN Standardregeln für jedes Land und jede Sprache. Die kulturellen Besonderheiten eines Landes bzw. einer Sprache bzw. einer Region werden in einem sogenanten Locale (Klasse java.utility.Locale) zusammengefaßt. Dabei handelt es sich z.B. um Regeln für die Zeitdarstellung (z.B. 15.30 Uhr versus 3.30 pm), Regeln für die Darstellung numerischer Werte (1,37 DM versus 1.37 $) und eben auch Regeln für die lexikographische Sortierfolge.

Das Betriebssystem des Computers verwaltet, welches Locale auf dem Computer das Standard-Locale ist. Normalerweise wird das bei der Installation des Betriebssystems festgelegt. Das Runtime-System eines Java-Programms ermittelt in der Startphase eines Programms das Locale des Betriebssystem und stellt es für das Java-Programm in Form einer Instanz der Klasse java.lang.Locale zur Verfügung (Locale.getDefault( )).

An das Standard-Locale angepaßte Sortierregeln kann man so verwenden:
RuleBasedCollator collator = (RuleBasedCollator) RuleBasedCollator.getInstance( );

Alternativ kann man die Sortierregeln des eingestellten Locale erweitern. Das geht, indem man sich mit
String rules = collator.getRules( );
die eingestellten Regeln holt und einen neuen Collator mit den alten Regeln und zusätzlichen Regeln erzeugt, indem man die alten und die neuen Regeln über Stringverkettung zusammensetzt. Hierfür eignet sich besonders der Einsatz der Modifikationsregel @, s.u.
collator = new RuleBasedCollator(rules + "...");

Eigene Sortierregeln

Man kann auch die Sortierregeln vollständig selbst definieren. Es empfiehlt sich dabei aber vielleicht, die Sortierregeln eines von SUN bereitgestellten Locale als Vorlage zu nehmen. Man findet sie im Quelltext der Klasse java.text.CollationRules.