Alphabetisierung auf Computer

Prinzipien, Probleme und eine Lösungsverbesserung

Von Hans Christophersen

Einleitung

In diesem Artikel werde ich einige Probleme der rechnergestützten Alphabetisierung beschreiben, die aufkommen, wenn die zu sortierenden Zeichenfolgen nationale Sonderzeichen beinhalten. Die von mir untersuchten kommerziellen Softwareprogramme sind alle unzulänglich, indem die jeweiligen länderspezifischen lexikographischen Alphabetisierungsregeln nicht ausreichend – wenn überhaupt – berücksichtigt sind, was unbefriedigend ist.
Nach der Beschreibung von Alphabetisierungsprinzipien und einer Darstellung einiger der im Computerbereich zu bewältigenden Probleme lege ich meinen Vorschlag zu einem Algorithmus vor, der möglichst viele der lösbaren Probleme berücksichtigen sollte.
Ich habe aus Rücksicht auf Sprachwissenschaftler ohne größere Programmierkenntnisse versucht, einen großen Teil meiner Darstellung allgemein verständlich zu halten, und habe die schwierigsten computertechnischen Beschreibungen zuletzt kommen lassen.

Internationale Alphabetisierung

Die Alphabetisierung dient dem leichteren Wiederfinden von Informationen, welches eine gewisse Einheitlichkeit der Sortierweisen voraussetzt. Am größten sind die Schwierigkeiten, wenn Wörter aus mehreren Sprachen in einer Liste vorkommen, z.B. Namen im Telefonbuch.
Das Anbieten einer internationalen Alphabetisierung ist etwas verheißungsvoll. Insofern es sich um die Buchstaben A-Z und a-z handelt, liegt die Reihenfolge in den untersuchten europäischen Sprachen fest, und etwaige Abweichungen in anderen Sprachen ließen sich durch entsprechende Änderungen in der Konstantentabelle des letzten im Artikel wiedergegebenen Programms implementieren. Einige nationale Sonderzeichen bereiten aber eine unüberwindliche Schwierigkeit im Versuch, zu einer total internationalen Alphabetisierung zu gelangen, indem diese nach verschiedenen nationalen Regeln widerstreitend einzusortieren sind. Ein Beispiel wäre der Buchstabe ö, den man nach deutschen Regeln unter o sortiert, jedoch nach schwedischen Regeln zuletzt im Alphabet einordnet.
Wir sind also gezwungen, den Begriff internationale Alphabetisierung etwas einzuengen. Um Widersprüchlichkeiten zu vermeiden, muß eine Sprache den Vorrang haben, so daß (sofern möglich) alle Alphabetisierungsregeln dieser Sprache berücksichtigt werden. Sonderzeichen, die dieser Sprache fremd sind, lassen sich nach den Regeln der jeweiligen Sprache einsortieren, so z.B. ß unter ss in einem schwedischen Lexikon, weil ß auf Schwedisch nicht vorkommt.
Die in den von mir untersuchten Sprachen vorkommenden Sonderregeln lassen sich in vier Gruppen einordnen:

1. Sonderbuchstaben mit eigener Einordnung:
Die hervorgehobenen Sonderbuchstaben haben in den Alphabeten der aufgeführten Länder ihren Sonderplatz im Verhältnis zu den gemeinsamen Buchstaben wie folgt:
1) Dänisch und Norwegisch: ... Z, Æ, Ø, Å. ... z, æ, ø, å.
2) Schwedisch: ... Z, Å, Ä, Ö. ... z, å, ä, ö.
3) Isländisch: ... X, Y, Þ, Æ, Ö. ... x, y, þ, æ, ö.
4) Spanisch: ... N, Ñ, O, ... n, ñ, o ...

2. Sonderbuchstaben mit Zusammensortierung:
I. Folgende Buchstaben sind Ligaturen, die zum Sortierungszweck in ihre Bestandteile zerlegt werden:
1) Französisch: Œ und œ (sortiert als OE od. Oe und oe).
2) Deutsch: ß (sortiert als ss, jedoch nach der geschriebenen Zeichenfolge ss, obwohl ursprünglich eine Ligatur aus s + z).
II. Folgende Sonderzeichen werden als D/d mit diakritischem Zeichen (Zusatzzeichen) behandelt:
1) Färöisch: Ð und ð.
2) Isländisch: Ð, ð, und der hier nicht wiedergebbare Buchstabe d mit einem Querstrich.

3. Buchstabenkombinationen mit eigener Einordnung (Digraphe):
1) Dänisch/Norwegisch: aa (als å; dänisch vor 1948 und norwegisch vor 1917 als aa).
2) Spanisch: ch (zwischen c und d); ll (zwischen l und m).
(Auf Spanisch kommt lynchar vor llaca und czar vor chabacanada.)

Notiz: Nach einem Zeitungsbericht 1994 soll diese spanische Sondereinordnug wegfallen und die Alphabetisierung somit computergerechter werden. Das prinzipielle Problem einer Nationalen Sonderregelung ist aber trotzdem da und könnte sich auf eine beliebige in diesem Artikel unberücksichtigte Sprache beziehen. Deshalb sehe ich keinen Grund, von diesen spanischen Beispielen wegzusehen. Sie können wenigstens als Stellvertreter für ähnliche Alphabetisierungsprobleme anderer Sprachen angesehen werden. Auch im Wallisischen werden die Kombinationen ch und ll wie im Spanischen alphabetisiert, neben anderen Buchstabenkombinationen.

4. Buchstaben mit Zusammensortierung:
Buchstaben mit diakritischen Zeichen (mit Ausnahme von den oben erwähnten in den angegebenen Sprachen) werden mit dem Basisbuchstaben (Grundbuchstaben) ohne diakritisches Zeichen zusammensortiert, und zwar als wären die diakritischen Zeichen nicht da. Erst wenn zwei Zeichenfolgen ohne Rücksicht auf diakritische Zeichen gleich sind, werden die diakritischen Zeichen zur Entscheidung der Reihenfolge herangezogen. Ein Buchstabe ohne diakritisches Zeichen geht immer demselben Buchstaben mit diakritischem Zeichen voraus. Wir haben also eine Reihenfolge wie z.B.: Foret, Forêt, Forez. Ein Beispiel wie Foréz, Forèz zeigt uns aber den Bedarf einer Festlegung der Reihenfolge der diakritischen Zeichen.
Im Französischen ist die Reihenfolge wie folgt:

Nach dänischer Norm wird in derselben Reihenfolge sortiert (d.h. é, è, ê, ë), wenn diese Zeichen in Eigennamen vorkommen. Im Italienischen dagegen sind die beiden ersten Akzente umzutauschen, also z.B. è vor é.
Erfolgt die Sortierung beispielsweise in der in einem VAX-Computer im eingebauten Zeichensatz vorgegebenen Reihenfolge (ANSI mit kleineren Abweichungen), werden die mit diakritischen Zeichen versehenen Buchstaben folgendermaßen eingeordnet: ` ´ ^ ˜ ¨ . Es ist hier die Tilde ( ˜ ) hinzugekommen. In nicht-spanischen Sprachen wäre es schon angebracht, die Tilde als diakritisches Zeichen anzusehen, aber im Spanischen werden ñ und Ñ als eigenständige Buchstaben angesehen, wie oben unter Sonderbuchstaben mit eigener Einordnung angegeben.
Ein Kollege hat mich darauf aufmerksam gemacht, daß die ANSI-Festlegung der Reihenfolge ` ´ nach italienischer Norm mit der größeren Durchschlagskraft des italienischen Lobbyismus in Amerika zusammenhängen könnte.

Alternative Sortierkriterien
Dänisch: Früher war die Zusammensortierung von v und w üblich mit der Präzedenz v vor w, z.B. die Reihenfolge: ver, wer, vet. In dem Wörterbuch Nudansk Ordbog wurde dies Prinzip bis Mitte der 1980er Jahre benutzt, gilt jedoch jetzt als veraltet und wird kaum mehr benutzt.
Nach der Rechtschreibreform 1948 wurde die eine Laut bezeichnende Buchstabenkombination (Digraph) aa durch den bereits aus dem Schwedischen bekannten Buchstaben å ersetzt, jedoch durfte nach eigener Wahl in Eigennamen aa beibehalten werden. Die standardisierten Alphabetisierungsregeln besagen, daß aa als å (letzter Buchstabe des dänischen Alphabets) zu sortieren ist, auch wenn aa als langes a auszusprechen ist, z.B. im Flußnamen Maas, was aber den meisten Leuten sinnlos vorkommt, und deshalb wird der Regel öfters nicht gefolgt, z.B. im Telefonbuch.
Deutsch: Heutzutage betrachtet man meist ä, ö, ü als bzw. a, o, u mit diakritischem Zeichen ¨ (Umlaut). In älteren Wörterbüchern war es bei Alphabetisierung üblich, diese Buchstaben in ihren ursprünglichen Bestandteilen aufzulösen: ae, oe, ue (das Umlautzeichen ¨ ist die Reminiszenz eines handgeschriebenen altdeutschen e, das stilisiert zu zwei Strichen wurde, später zu zwei Punkten). Das erste Prinzip führt zu einer Reihenfolge wie: ae, aeh, afh, äg, äi. Das zweite Prinzip führt zur Reihenfolge: ae, äg, aeh, äi, afh. Das erste Prinzip ist das gebräuchlichste und in Österreich und in der Schweiz das einzige, aber das zweite findet man beispielsweise in deutschen Telefonbüchern, z.B. Grützner vor Gruffke, und in den Staatsbüchereien.

Drei wahlfreie Sortierungskriterien
1) Mit bedeutsamem Leerzeichen (»Nichts vor Etwas«)
Beispiel: à condition, a conto, Ackja, Acre.
Das Leerzeichen wird berücksichtigt und hat dabei den niedrigsten Sortierwert aller Zeichen, d.h. es kommt vor allen sichtbaren Zeichen. Dies Kriterium wird u.a. von Büchereien benutzt und gilt als die Hauptregel nach dänischer Norm (Dansk Standard Nr. 377).

2) Streng alphabetisch (»Zeichen für Zeichen«)
Beispiel: Ackja, à condition, a conto, Acre.
Das Leerzeichen wird nicht berücksichtigt. Diese Reihenfolge haben z.B. Duden Deutsches Universalwörterbuch, Duden Rechtschreibung und das dänische Rechtschreibwörterbuch.

3) Nach Zusammengehörigkeit
Beispiel: Affe, Affengeschwindigkeit, Affenhaus, Affekt.
Bedeutungsähnliche und abgeleitete Wörter und Zusammensetzungen werden zusammengehalten, obwohl dadurch keine regelrechte Alphabetisierung eingehalten ist.
Eine modifizierte Form des Zusammengehörigkeitskriteriums findet man in Duden Das große Wörterbuch der deutschen Sprache in 6 Bänden. Die obigen Beispielswörter findet man hier in der Reihenfolge: Affe, Affekt, Affenhaus, Affengeschwindigkeit. Affe ist von den Affen-Zusammensetzungen getrennt; diese sind aber in zwei Gruppen gegliedert, und weil Affenhaus zur ersten, Affengeschwindigkeit zur zweiten Gruppe gehört, kommt Affenhaus zuerst, obwohl es streng alphabetisch zuletzt kommen müßte.

Bei Computersortierung ist das erste Kriterium das einfachste zu handhaben, indem zwei Zeichenfolgen sich vergleichen lassen, so wie sie dastehen.
Nach dem zweiten Kriterium wären zuerst die Leerzeichen von den beiden zu vergleichenden Zeichenfolgen zu entfernen, aber gleichzeitig müßte man die ursprünglichen Zeichenfolgen zum abermaligen Vergleich bereithalten für den Fall, daß zwei Zeichenfolgen nach der Leerzeichenentfernung gleich sind, da sonst eine eindeutige Reihenfolge nicht festlegbar sein würde. Nehmen wir als Beispiel die beiden Zeichenfolgen a ba und aba. Ohne Leerzeichen sind aba und aba gleich, aber es wäre unzweckmäßig, wenn man nicht wissen könnte, ob ein Sortierverfahren zur einen oder anderen Reihenfolge führt.
Das Zusammengehörigkeitsprinzip läßt sich von den Einzelwörtern heraus nicht durchführen und könnte in einem Computersortierverfahren nur dann benutzt werden, wenn in einer Datenbank zusätzliche Informationen zur Festlegung der Reihenfolge (Sortierschlüssel) zur Verfügung stehen.
Eine besondere Schwierigkeit bereiten zusammengesetzte englische Wörter, die entweder getrennt, mit Bindestrich oder zusammen geschrieben werden. Gleichbedeutende Wörter würden durch die Alphabetisierung voneinander getrennt werden können.
Sind die zu sortierenden Wörter einem elektronisch gespeicherten Text zu entnehmen, entstehen bei vorkommenden Silbentrennungen Schwierigkeiten. Ein Bindestrich kann am Ende einer Zeile der Silbentrennung dienen, kann aber auch fester Bestandteil eines Wortgefüges sein, aber im Falle der Silbentrennung wird nach den deutschen Rechtschreibregeln ck zu kk. Beispielsweise wird Lücke mit Silbentrennung zu Lük-ke, aber ein angenommener Personenname Lükke wäre auch als Lük-ke zu trennen.
In den untersuchten Sprachen gilt die Regel, daß alle Ziffern vor allen Buchstaben stehen sollen, und daß Groß- und Kleinbuchstaben zusammenzusortieren sind. Großbuchstaben haben in den meisten Sprachen Vorrang vor Kleinbuchstaben (also z.B. Karl vor karl), aber in Schweden ist es umgekehrt.

Sortierfolge der Sonderzeichen
In der Computersortierung ist es üblich, die Sonderzeichen mit den Buchstaben gleichgestellt anzusehen, so daß auch die Sonderzeichen eine alphabetische Reihenfolge haben. Dieses Verfahren ist übrigens erforderlich, wenn ein Lemma ausschließlich aus einem oder mehreren Sonderzeichen besteht, was z.B. in einem Index eines Computerfachbuches gut möglich ist; ein Beispiel wäre der Verschiebungsoperator << als Lemma.
In der traditionellen Lexikographie werden die Sonderzeichen dreierlei eingestuft:
Als Blindzeichen: Die bei der Interpunktion benutzten Zeichen, sowie Komma und Fragezeichen, bleiben unberücksichtigt. Es wird also sortiert, als wenn ein solches Zeichen nicht vorhanden wäre. Apostophe (z.B. in: Peter's Bar) und Auslassungsstriche (z.B. in: Männer- und Frauenberufe) werden ebenfalls als Blindzeichen angesehen. Blindzeichen: . , ; : ? ! ( ) [ ] » « " „ ” ' -
Ein Sonderfall ist der Gedankenstrich, —, der von zwei Zwischenräumen umgeben ist. Diese Dreierfolge wird als ein einziger Zwischenraum behandelt. Der Gedankenstrich ist also blind, aber von zwei Zwischenräumen entfällt der eine.

Als Zwischenraum: Binde- und Schrägstriche werden als Zwischenraum angesehen. Beispiele: Heinz-Dieter (einzuordnen wie: Heinz Dieter), und/oder (einzuordnen wie: und oder). Jedoch keine Regel ohne Ausnahme, indem Binde- und Schrägstriche in folgenden Fällen als Blindzeichen angesehen werden: Wenn zwei Teile eng zusammengehören und nicht getrennt vorkommen könnten (z.B. U-Boot), und wenn eine Schreibweise mit oder ohne Sonderzeichen üblich ist (z.B. die Abkürzung S/W = SW = schwarz/weiß). In einem von mir verfaßten EDV-Abkürzungswörterbuch wurden alle Sonderzeichen bei der alphabetischen Einordnung außer Acht gelassen, da das Auffinden eines Lemmas sonst erschwert worden wäre, indem einige Abkürzungen mit Bindestrich, Schrägstrich, Zwischenraum oder zusammengeschrieben vorkommen können. In diesem Wörterbuch kommen auch folgende drei verschiedene Lemmata vor: A&T, A/T und AT. Wenn die drei Folgen zusammensortiert werden, entsteht die Frage der Reihenfolge untereinander. Hier habe ich die angegebene gewählt (& kommt vor / im Computeralphabet), da ich keine andere genormte Festlegung kenne.

Nach der Aussprache: Sigel werden wie das voll ausgeschriebene, entsprechende Wort einsortiert. Das Sigel & wird also im deutschsprachigen Kontext durch und ersetzt, im englischen and und im schwedischen durch och. Diese Regel führt keineswegs zu einer einheitlichen internationalen Alphabetisierungsweise und ist bei der Computersortierung sehr aufwendig.

Zum Buchstabenbegriff

Die Buchstaben der jeweiligen länderspezifischen Alphabete lassen sich in folgende Gruppen einteilen:
Einfache Buchstaben: Buchstaben, die in allen lateinischen Alphabeten vorkommen und mit Ausnahme von einigen Buchstabenkombinationen (dänisch/norwegisch aa und spanisch ch und ll) einheitlich einzusortieren sind, sind einfache Buchstaben. Das sind die Buchstaben A-Z und a-z, also die Buchstaben, die im Englischen die einzigen sind.
Buchstaben mit diakritischen Zeichen: Das sind Buchstaben, die mit den Basisbuchstaben zusammensortiert werden ohne Rücksicht auf die diakritischen Abweichungen, so lange in den zu vergleichenden Wörtern andere Unterschiede bestehen. Z.B. ist é wegen der Zusammensortierung mit e als ein Buchstabe mit diakritischem Zeichen anzusehen. Wenn auf deutsch ö nicht in oe zerlegt wird (wobei öm vor ok kommt, weil als oem angesehen), sondern nach den modernsten Prinzipien (d.h. ok vor öm), ist ¨ als diakritisches Zeichen anzusehen, weil der Umlautbuchstabe nicht aufgelöst wird und kein Sonderbuchstabe mit eigener Einordnung ist.
Sonderbuchstaben: Diese Gruppe zerfällt in vier Untergruppen:
I) Sonderbuchstaben ohne Ähnlichkeit mit einfachen Buchstaben: Zu dieser Gruppe gehört der isländische Buchstabe þ, der seinen besonderen Platz im Alphabet hat.
II) Sonderbuchstaben mit Ähnlichkeit mit einfachen Buchstaben: Dies sind Buchstaben, die nach nationaler Konvention ihren Sonderplatz im Alphabet einnehmen, obwohl sie unmittelbar als Buchstaben mit diakritischen Zeichen vorkommen. Beispiele sind der nordische Buchstabe å und das schwedische ö (im Gegensatz zum deutschen ö).
III) Ligaturen mit Auflösungsmöglichkeit: Dies sind Buchstaben, die außer als Ligaturen auch als getrennte Buchstaben dargestellt werden können, und die bei der Alphabetisierung als getrennte Buchstaben behandelt werden. Beispiel: französisches œ = oe.
IV) Ligaturen mit Status als Sonderbuchstaben: Zusammengeschriebene Buchstaben, die in der jeweiligen Sprache als Sonderbuchstaben angesehen werden, einen eigenen Namen haben und im Alphabet ihren eigenen Platz haben. Orthoepisch gesehen müssen solche Ligaturen zu den Digraphen gerechnet werden, da sie nur einen Laut wiedergeben.
Beispiel: im Dänischen æ nach z im Alphabet.
Das diakritische Zeichen dient zur weiteren Unterscheidung zwischen Buchstaben, meist hinsichtlich der Aussprache (z.B. c/ç, e/é). Einige diakritische Zeichen (z.B. ´ über é) werden auch Akzente genannt. Die meisten mit diakritischen Zeichen versehenen Buchstaben werden mit den Basisbuchstaben zusammensortiert (z.B. é mit e), wogegen andere in den jeweiligen Sprachen eine Sonderstellung einnehmen. Nach obiger Definition würde ich beim Buchstaben å das º nicht als diakritisches Zeichen bezeichnen, da å in den skandinavischen Ländern als selbständiger Buchstabe angesehen wird.
Eine Ligatur ist eine Drucktype mit einer Buchstabenverbindung, z.B. ff zusammengeschrieben. Einige Ligaturen werden jedoch als neue, selbständige Buchstaben angesehen und lassen sich nicht zerlegen. In den skandinavischen Sprachen läßt sich æ nicht durch ae ersetzen.

Festlegung eines Begriffsmodells

Für die weitere Beschäftigung mit den jeweils benötigten Alphabetisierungskriterien möchte ich einige Begriffe zur leichteren Handhabung festlegen.

Primäres Kriterium

Als primäres Kriterium gilt die Feststellung, ob zwei zu vergleichende Zeichen ohne Rücksicht auf etwa diakritische Zeichen demselben Basisbuchstaben (Grundbuchstaben) angehören. So werden E, É, e, é, ê usw. als primär gleich angesehen, weil sie alle aus dem Basisbuchstaben E/e bestehen. Dagegen sind beispielsweise g und k primär unterschiedlich, da die Basisbuchstaben verschieden sind.
Die beiden Zeichenfolgen forêt und forez weisen beim fünften Buchstaben einen primären Unterschied auf und werden deshalb nach den Basisbuchstaben alphabetisiert ohne Rücksicht auf das diakritische Zeichen ˆ.
Die beiden Zeichenfolgen foret und forêt sind primär gleich. Das primäre Kriterium reicht also nicht aus, um die Reihenfolge festzulegen.

Sekundäres Kriterium

Es besteht ein sekundärer Unterschied, wenn zwei zu vergleichende Buchstaben primär gleich sind, sich aber hinsichtlich der diakritischen Zeichen unterscheiden. Beispielsweise sind die Buchstaben e, é, è, ê und ë primär gleich, aber sekundär unterschiedlich.
Beim sekundären Kriterium e vor ê kommt foret vor forêt, indem die beiden Zeichenfolgen primär gleich sind. Weil bei den Zeichenfolgen forêt und forez schon ein primärer Unterschied besteht, hat das sekundäre Kriterium für die Alphabetisierungsreihenfolge keine Bedeutung.

Tertiäres Kriterium

Die beiden ersten Kriterien führen in den meisten Fällen zu einer ausreichend zufriedenstellenden Alphabetisierung. Die gängige Zusammensortiering von Groß- und Kleinbuchstaben (wobei Großbuchstaben vor Kleinbuchstaben Vorrang haben) würde aber mit zweiteiliger Kriterienstufe, wobei der Unterschied zwischen großem und kleinem Buchstaben als sekundäres Kriterium anzusehen wäre, zu Reihenfolgen führen können wie:
Foret Forêt foret forêt
Gómêt Gòmét gómêt gòmét
Dabei wäre Foret von foret und Forêt von forêt getrennt und ebenfalls mit der <gomet>-Reihe. Es besteht also der Bedarf der Einführung eines tertiären Kriteriums, um Zeichenfolgen zusammenhalten zu können, die nach dem primären Kriterium (gleiche Basisbuchstaben), sowie nach dem sekundären Kriterium (gleiche Basisbuchstaben mit gleichen diakritischen Zeichen) sich nur in bezug auf Groß- und Kleinschreibung unterscheiden. So wie das zweite Kriterium erst bei Unzulänglichkeit des ersten Kriterium herangezogen wird, nehme man erst das dritte Kriterium in Betracht, wenn die Sortierfolge nicht durch die beiden ersten Kriterien gegeben ist. Die korrekte Alphabetisierung der obigen Beispielswörter ist auch nach der Auffassung von »Dansk Sprognævn« (dem dänischen Sprachnormenausschuß):
Foret foret Forêt forêt Gómêt gómêt Gòmét gòmét

Look-ahead

Die Einhaltung der stufengeteilten Sortierung erfordert das Look-ahead (Voraussichtsvermögen), indem man beispielsweise beim Antreffen des sekundären Unterschieds zwischen e und ê noch nicht entscheiden kann, welche von zwei Zeichenfolgen zuerst kommt, indem das sekundäre Kriterium erst bei primärer Zeichenfolgengleichheit anzuwenden ist. Einem Sortieralgorithmus, der in der Reihenfolge foret, forez, forêt alphabetisiert, mangelt es an Look-ahead, weil ein sekundärer Unterschied fehlerhaft dem primären vorangegangen ist. Die richtige Reihenfolge ist: foret, forêt, forez.

Alphabetisierungsprobleme

I) Allgemeine Probleme bei manueller und automatischer Sortierung:
Die vorrangige Sprache muß festgelegt werden, da einige Buchstaben nach länderspezifischen Regeln unterschiedlich einsortiert werden. Dies gilt vor allem Sonderbuchstaben und Buchstabenkombinationen mit eigener Einordnung (Digraphe). Wo z.B. ö auf deutsch mit o zusammensortiert wird, ist es der letzte Buchstabe im schwedischen und im isländischen Alphabet, und beim Vorkommen im dänischen Zusammenhang in Eigennamen wird ö mit ø zusammensortiert (bei gleichen Zeichenfolgen hat ø den Vorrang, also Øster vor Öster).
Die Berücksichtigung fremder Zeichen muß festgelegt werden. Zeichen, die nur in einer Fremdsprache vorkommen, können nach den Regeln des betreffenden Landes eingeordnet werden, z.B. ß und œ. Die physikalische Einheit Å (ångström) nach dem schwedischen Physiker Anders Ångström (1814-74) findet man jedoch in einem deutschen Lexikon nicht nach den schwedischen Regeln eingeordnet, sondern unter A, obwohl Å in den Ländern, wo der Buchstabe im Alphabet vorkommt, kein Buchstabe mit diakritischem Zeichen, sondern ein Sonderbuchstabe ist.
Eines der wahlfreien Sortierungskriterien muß gewählt werden. Also streng alphabetisch (das häufigste Prinzip), mit bedeutsamem Leerzeichen (das einfachste beim Computer) oder nach Zusammengehörigkeit (was ein leichtes Wiederfinden der Eintragungen erschwert, da dies Prinzip den meisten Menschen fremdartig vorkommt).
Bei Regelschwankung muß Einheitlichkeit zugestrebt werden. Es können in einer Sprache mehrere Alphabetisierungsregeln gleichberechtigt sein, oder mehrere Regeln werden in der Praxis benutzt. Im Einzelfall und vor allem bei der Computersortierung ist es unerläßlich, sich auf eine Regel festzulegen.
Im Deutschen gibt es die beiden Möglichkeiten, Ä/ä, Ö/ö, Ü/ü entweder als Basisbuchstaben mit diakritischem Zeichen oder als Ligaturen mit der Sortierauflösung Basisbuchstabe + e anzusehen.
Im Dänischen wird beispielsweise in Telefonbüchern aa sowohl als aa als auch å nach z alphabetisiert, obwohl nur die letztere Möglichkeit genormt ist. Die Abweichung von der Normung erfolgt in den Fällen, wo aa nicht ["omega"] wie in å, sondern [a] oder [a:] ausgesprochen wird. (Ein Beispiel aus dem Kopenhagener Telefonbuch 1996-97: Maar, Maardt, Maas, Maass, Mabeck, Møss, Maach Månsson, Maansson Månsson.)

II) Sonderprobleme bei Computersortierung:
Sortierweise nach Aussprache: Im Wiener Telefonbuch von 1970 ist die Buchstabengruppe ue unterschiedlich eingereiht, je nachdem ob dadurch der Umlaut ü oder ein langes u zu sprechen ist. In dänischen Telefonbüchern wird aa mit einer Aussprache wie å unter å eingeordnet im Gegensatz zu aa mit einer Aussprache wie langes a. In einfacher Weise läßt sich dies bei Computeralphabetisierung nicht durchführen. Eine Implementierung dieses Prinzips erfordert zumindest eine Datenbank, in der zum einzelnen Feld eine Auskunft über die zu befolgende Sortierweise vorliegt, beispielsweise eine alternative Schreibweise, die zur richtigen Einordnung führt.
Digraphe: Einige Digraphe bereiten keine Probleme bei der Computersortierung, indem sie auch bei der manuellen Sortierung nicht gesondert berücksichtigt werden, so beispielsweise ph mit der Aussprache [f], das als p-h sortiert wird, aber einige Digraphe sind schwieriger zu handhaben, indem sie in den jeweiligen Sprachen eine Sonderstellung einnehmen. Eine Computersortierung basiert meist auf eine Tabelle, die mit naher Anknüpfung an eine »Computerzeichentabelle« die primäre Sortierreihenfolge darstellt, und diese ist nicht geeignet, das Digraphenproblem zu berücksichtigen. Nehmen wir als Beispiel die Alphabetisierung in WordPerfects dänischer Ausgabe vom Digraph aa, können wir bei einer Sortiereingabe zur entsprechenden Ausgabe aal, ål, aal kommen, welches belegt, daß im benutzten Algorithmus aa mit å ohne Vorrang gleichgesetzt ist. Nach dem dänischen Rechtschreibwörterbuch hat å Vorrang vor aa. Eine Prioritierungsordnung zwischen dem Digraph aa und seiner Entsprechung å ist schon möglich, da der Unterschied maschinell feststellbar ist, aber algorithmen- und implementierungsmäßig etwas aufwendiger. Die spanischen Digraphe ch (alphabetisiert als Sonderbuchstabe zwischen c und d) und ll (zwischen l und m) bereiten auch Schwierigkeiten, und so ist es allgemein üblich, daß bei der Computersortierung von der bei manueller Sortierung berücksichtigten Ordnung weggesehen wird. Ein zusätzliches Problem ist, daß bei manueller Alphabetisierung ch und ll in Fremdwörtern nicht als Digraphe behandelt werden, sondern international als c-h und l-l eingereiht werden, was eine Entscheidungsfähigkeit voraussetzt, die beim Computerprogramm schwer, wenn überhaupt, implementierbar ist.

Feststellung von Alphabetisierungskriterien

Meine Arbeit mit der Ausarbeitung eines neuen Alphabetisierungsverfahrens ist 1993-94 der Feststellung entsprungen, daß zugängliche Softwareprodukte teils unterschiedlich alphabetisieren, teils zu einer anderen Reihenfolge kommen als eine manuelle, lexikographisch basierte Einordnung. Um festzustellen nach welchen Kriterien ein spezifisches Programm sortiert, müssen wir eine Reihe von Zeichenfolgen aufstellen, nach der sich die Kriterien eines Programms entleiten lassen. Für eine solche Untersuchung ist es ohne Bedeutung, ob den untersuchten Zeichenfolgen in irgendwelcher Sprache eine lexikalische Bedeutung zugeschrieben werden kann.

Anzahl der Kriterienstufen

Die Anzahl der Kriterienstufen läßt sich durch folgende Testeingabe ermitteln:
Drei Kriterienstufen:
Zeichenfolgen, die hinsichtlich diakritischer Zeichen gleich sind, werden ohne Rücksicht auf Klein- oder Großschreibung zusammensortiert. Es besteht eine prioritierte Reihenfolge zwischen Zeichen desselben Basisbuchstaben. Der Basisbuchstabe ohne Akzentzeichen kommt vor dem Basisbuchstaben mit Akzentzeichen, wenn die nachfolgenden Zeichen keine schwerwiegendere Unterschiede aufweisen (Look-ahead). Normalerweise hat ein Großbuchstabe den Vorrang vor einem Kleinbuchstaben desselben Basisbuchstaben, welches diese Reihenfolge ergibt: Sollte aber ein Kleinbuchstabe als vorrangig angesehen werden, sind bei folgender Reihenfolge immer noch drei Kriterienstufen da (schwedische Reihenfolge): Das entscheidende ist, daß Programme mit 1 oder 2 Kriterienstufen keinerlei zu den obigen Alphabetisierungsreihenfolgen gelangen können.

Zwei Kriterienstufen:
Der Unterschied zwischen Klein- und Großbuchstaben steht auf derselben Kriterienstufe wie andere Unterschiede eines und desselben Basisbuchstaben. Der zuerst auftretende Unterschied ist für die Alphabetisierungsreihenfolge ausschlaggebend, außer wenn die beiden zu vergleichenden Zeichen als zusammenzusortieren vordefiniert sind, und die Reihenfolge durch nachfolgende primäre Unterschiede gegeben ist (Look-ahead). Mit zwei Kriterienstufen kommt man, je nachdem ob Groß- oder Kleinbuchstaben den Vorrang haben, zu einer der folgenden Reihenfolgen: Die erste Reihe ist für die meisten Sprachen normgerecht (in Schweden aber die zweite Reihe, da da Kleinbuchstaben den Vorrang haben).
Programme mit nur einer Kriterienstufe werden nicht zu den obigen Reihenfolgen kommen können.
Zwei Kriterienstufen gibt es (1994) z.B. bei Paradox, WordPerfect 5.1 und MS-Word.

Eine Kriterienstufe:
Alle Programme, die die unter drei bzw. zwei Kriterienstufen angegebenen Sortierreihenfolgen nicht hervorbringen können, haben nur eine Kriterienstufe. Dies können wir vor allem als fehlendes Look-ahead beschreiben, indem beispielsweise e und ê dieselbe feste Reihenfolge ohne Berücksichtigung der nachfolgenden Zeichen einnehmen. Ein Beispiel einer einkriterienstufige Reihenfolge ist diese einfache ANSI- Reihenfolge: Das besondere bei einer Kriterienstufe ist, daß beim zuerst vorkommenden Unterschied, hier F/f, bzw. e/ê, die Reihenfolge ohne Rücksicht auf nachfolgende Zeichen entschieden wird (fehlendes Look-ahead). Beim Vorkommen einer Sortierfolge wie foret forez forêt ist also nur eine Kriterienstufe vorhanden.
Es könnte wünschenswert sein, zwischen drei Gattungen der Einkriterienstufe zu unterscheiden, und zwar:
  1. der einfachen ANSI-Reihenfolge nach der ANSI-Tabelle,
  2. einer verbesserten einkriterienstufige Sortiering mit Zusammensortierung gewisser Zeichen ohne Prioritierung, und
  3. einer erweitert verbesserten einkriterienstufige Sortierung mit einer prioritierten Ordnung von zusammensortierten Zeichen.
Eine solche Unterscheidung ist aber kaum so einfach wie die Feststellung der Anzahl der Kriterienstufen, und die oben benutzten Zeichenfolgen reichen da nicht aus.
Wenn es festgestellt ist, daß ein Programm nur eine Kriterienstufe hat, und wenn eine Sortierfolge von der Reihenfolge der Zeichen der ANSI-Tabelle (oder einer anderen vorgegebenen Tabelle) abweicht, läßt sich Möglichkeit 1) ausschließen.
Wenn eine Eingabe wie ret ret rét zur Sortierfolge ret rét ret führt, ersieht man, daß e und é als dasselbe Zeichen angesehen werden, und wiederholte Sortiervorgänge mit derselben Eingabe können zu beliebigen anderen Reihenfolgen führen. Das fehlende Look-ahead besagt, daß nur eine Kriterienstufe vorhanden ist, und der Mangel an Prioritierung zwischen e und é zeigt uns, daß hier Möglichkeit 2) vorliegt.
Eine einfache ANSI- oder ASCII-Reihenfolge erhält man durch eine Sortierung, die eigens auf den Vergleichsvorgang der C-Funktion strcmp beruht, was in der untersuchten Version von Oracle festgestellt werden konnte. Die erweitert verbesserte Sortierung fand ich bei Ingres und Danbase vor.

Teilweise Kriterienstufenabweichungen:
Im Regelfall heißt eine undefinierte Reihenfolge von zusammensortierten Zeichen, daß das Sortierprogramm nur über eine Kriterienstufe verfügt, aber bei einigen Programmen tritt dieses Phänomen in Verbindung mit gewissen Buchstaben und Buchstabengruppen auf, obwohl der Hauptteil der Zeichen nach zwei Kriterien einsortiert wird. Es ist also darauf zu achten, daß von einer kleinen Sortiermenge heraus keine übereilten Schlüsse gezogen werden. WordPerfect (V.5.1) hat im allgemeinen zwei Kriterienstufen. In der dänischen Ausgabe wird å mit aa zusammensortiert, jedoch in undefinierter Reihenfolge, indem ein Sortiervorgang schon zur folgenden Reihenfolge führen kann: aal ål aal. Ein Sortiervorgang von der Wortfolge ret rét ret führt aber immer zur Sortierfolge ret ret rét. Mehrere Programme, die sonst über zwei Kriterienstufen verfügen, sortieren ß, Œ und œ fälschlischerweise nach der erweitert verbesserten Einkriterienstufe ein. Diesen Fehler gibt es noch bei WordPerfect 6.1.

Streng alphabetisch oder mit bedeutendem Leerzeichen?

Vom Zusammengehörigkeitsprinzip kann meist weggesehen werden, da eine Computerimplementierung nicht ohne weiteres durchführbar ist, aber wenn angewandt, sind die beiden anderen wahlfreien Kriterien nicht (überall) eingehalten. Die Beispiele lassen sich in Verbindung mit zusammengesetzten Wörtern finden (Finger zusammen mit fingerförmig vor Fingerei in: DUDEN Das große Wörterbuch der deutsche Sprache in 6 Bänden).
Ob das Leerzeichen bei der Alphabetisierung berücksichtigt ist, läßt sich durch die Testeingabe von aba und a ca ermitteln mit folgenden Ausgabemöglichkeiten:
1) Streng alphabetisch: aba, a ca
2) Bedeutendes Leerzeichen: a ca, aba
Alle untersuchten Programme (Danbase, Ingres, MS-Word, Oracle, Paradox, WordPerfect) sortieren mit bedeutendem Leerzeichen.

Einordnung der Sonderzeichen

In den ANSI- und ASCII-Alphabeten findet man Sonderzeichen vor den Ziffern (z.B. &, *), zwischen den Ziffern und den Großbuchstaben (z.B. <, ?), zwischen Groß- und Kleinbuchstaben (z.B. [, ^) und nach den Kleinbuchstaben (z.B. {, ƒ). Einige Sortierprogramme behalten diese Verteilung ganz oder teilweise bei, während andere die Sonderzeichen entweder vor oder nach den alphanumerischen Zeichen kommen lassen. Zu einer Rohfeststellung benutzen wir z.B. die Testeingabe & * < ? [ ^ { ƒ 3 f F. Da aber das Sammeln oder Getrennthalten der Zeichen keine unmittelbare Auskunft über die etwaige Beibehaltung der ursprünglichen Tabellenreihenfolge gibt, wäre es angebracht, sämtliche Zeichen sortieren zu lassen.

Reihenfolge der Akzente

In den meisten Programmen haben die Akzente unabhängig vom Basisbuchstaben eine festgelegte Reihenfolge. Diese läßt sich gegebenenfalls durch diese Testeingabe ermitteln: a á à â ã ä. Um aber eventuelle Abweichungen feststellen zu können, ist es erforderlich, den gesamten Zeichensatz sortieren zu lassen, auch um die Einordnung anderer mit diakritischen Zeichen versehenen Buchstaben festzustellen.

Sprachenspezifische Regeln

Hier läßt sich die Einhaltung der Sonderregeln in beliebig vielen Sprachen untersuchen. Die nachfolgenden Beispiele sind so nicht erschöpfend.

Dänisch, norwegisch und schwedisch:
Wenn aa und å nach dänischen und norwegischen Regeln zusammensortiert werden, erhalten wir die Sortierreihenfolge z ål aal. In den Fällen, wo aa kein Digraph ist, sondern in einem zusammengesetzten Wort vorkommt, erfolgt keine Zusammensortierung. Ein Beispiel hierfür ist das Wort ekstraarbejde (Extraarbeit). Die Feststellung, ob aa im Einzelfall ein Digraph ist, läßt sich aber beim Computer ohne weiteres nicht durchführen.
Der isländische Buchstabe þ wird nicht wie im Isländischen sortiert, sondern wie th.
Nach dänischen und norwegischen Regeln werden Umlautbuchstaben mit den nationalen Buchstaben in folgender Reihenfolge zusammensortiert: Y Ü y ü Z z Æ Ä æ ä Ø Ö ø ö Å å.
Die schwedischen Alphabetisierungsregeln entsprechen dagegen der ANSI-Reihenfolge: å ä ö.

Deutsch:
Es wird ß als ss alphabetisiert, jedoch hat bei sonstiger Gleichheit zweier Zeichenfolgen ss Vorrang vor ß. So ist die folgende Reihe von Wörtern lexikographisch korrekt eingeordnet:
haspeln Haß hassen hassenswert haßerfüllt
Viele Programme nehmen die Zusammensortierung von ss und ß schon wahr, lassen aber fehlerhaft bei vorgehender Gleichheit alle ß-Vorkommen zuletzt kommen.
Bei den Umlautbuchstaben gibt es zwei Möglichkeiten:
1) Die gebräuchlichste Einordnung, bei der die Buchstaben so sortiert werden wie andere Basisbuchstaben mit diakritischen Zeichen, führt zu einer Reihenfolge wie:
ae aeh äg äi vor vör vore vöre
2) Die in alten Wörterbüchern, in Telefonbüchern und in Büchereien gebrauchte Einordnung basiert auf die Auflösung in Basisbuchstaben + e, z.B. ü = ue, was zur folgenden Reihenfolge führt:
ae äg aeh äi vör vöre vor vore

Färöisch und isländisch:
Die Buchstaben Ð, ð (»eth«) und d mit einem Querstrich (hier nicht wiedergebbar) werden als bzw. D und d mit diakritischem Zeichen angesehen. Dies ergibt eine Reihenfolge wie: D Ð d [d mit Querstrich] ð E e.
Das isländische Þ/þ (»thorn«) wird nach y eingeordnet, aber vor anderen nationalen Sonderbuchstaben (z gibt es in isländischen Wörtern nicht). Im reinen isländischen Zusammenhang haben wir die Folge y þ æ, und zusammen mit ausländischen Wörtern, Fremdwörtern und Eigennamen ist folgende Alphabetisierungsreihenfolge gegeben:
Y y Z z Þ þ Æ æ Ö Ø ö ø Å å

Französisch:
Bei genormter Einordnung der französischen Zeichen Œ und œ erhält man folgende alphabetisierte Reihenfolgen:
boea boef bœf boeg boez bof
und
BOEA BOEF BŒF BOEF BOEZ BOF
Abhängig von den Vorrangskriterien des Sortierprogramms können diese beiden Reihen mit Klein- und Großbuchstaben getrennt oder zusammen sortiert werden, was aber mit der französischen Fragestellung nichts zu tun hat. Bei Zusammensortierung werden die beiden obigen Reihen vereint zu entweder:
BOEA boea BOEF boef BŒF bœf BOEG boeg BOEZ boez BOF bof
oder:
boea BOEA boef BOEF bœf BŒF boeg BOEG boez BOEZ bof BOF
Die erste Reihe, wo Großbuchstaben den Vorrang haben, folgt den Normen.

Holländisch/niederländisch:
Die holländischen Ligaturen IJ zusammengeschrieben und ij zusammengeschrieben haben keine Sonderstellung, sondern gelten als IJ/ij und werden auch so alphabetisiert. Es gibt also die Reihenfolge ii [ij zusammengeschrieben] ik.

Spanisch:
In spanischen Wörtern ist der Digraph ch ein selbständiger Buchstabe zwischen c und d, und der Digraph ll wird als selbständiger Buchstabe zwischen l und m gerechnet. Außerdem ist im Spanischen Ñ/ñ kein Buchstabe mit diakritischem Zeichen, sondern ein Sonderbuchstabe zwischen N/n und O/o. Diese Regeln führen zu einer Reihenfolge wie:
czar chabacanada lynchar llaca nz ña o

Voraussetzungen der Computeralphabetisierung

Das Betriebssystem eines Computers stellt einen Zeichenvorrat (native character set) zur Verfügung, der die Grundlage der meisten Sortierverfahren ausmacht. Einige Programme haben darüber hinaus softwareimplementierte Zeichensätze, auf die man nur im betreffenden Programm zurückgreifen kann (z.B. WordPerfect). Grundlegend für jedes Computersortierverfahren ist die Festlegung einer Reihenfolge der zu sortierenden Zeichen. Die Reihenfolge wird in einer Tabelle festgelegt, wobei jedem Zeichen ein Zahlenwert zugeschrieben wird. Bei den einfachsten Sortierverfahren wird von der Reihenfolge des betriebssystemeigenen Zeichensatzes ausgegangen, und sonst wird eine Abänderungstabelle erstellt. Verschiedene Computer haben verschiedene Zeichenvorräte, aber für sie alle gilt, daß für die lexikographisch korrekte Alfabetisierung eine Änderung der Reihenfolge erforderlich ist. Für die grundlegenden Erörterungen in diesem Artikel ist es ohne Bedeutung, welcher Zeichensatz zugrunde gelegt wird. Als Beispielszeichensatz habe ich den ANSI-Zeichensatz gewählt, der auf dem PC unter Windows, auf Prime-Computern und auf VAX-Computern zugrunde gelegt wird (jedoch mit kleinen Abweichungen). Die ersten 128 Zeichen sind den Zeichen des 7-Bit-ASCII-Zeichensatzes und den ersten 128 Zeichen des PC-DOS-Zeichensatzes gleich.

ANSI-Zeichensatz


000     032 [SP] 064 @    096 `    128      160      192 À    224 à

001     033 !    065 A    097 a    129      161 ¡    193 Á    225 á

002     034 "    066 B    098 b    130 ‚    162 ¢    194 Â    226 â

003     035 #    067 C    099 c    131 ƒ    163 £    195 Ã    227 ã

004     036 $    068 D    100 d    132 „    164 ¤    196 Ä    228 ä

005     037 %    069 E    101 e    133 …    165 ¥    197 Å    229 å

006     038 &    070 F    102 f    134 †    166 ¦    198 Æ    230 æ

007     039 '    071 G    103 g    135 ‡    167 §    199 Ç    231 ç

008     040 (    072 H    104 h    136 ˆ    168 ¨    200 È    232 è

009     041 )    073 I    105 i    137 ‰    169 ©    201 É    233 é

010     042 *    074 J    106 j    138 Š    170 ª    202 Ê    234 ê

011     043 +    075 K    107 k    139 ‹    171 «    203 Ë    235 ë

012     044 ,    076 L    108 l    140 Œ    172 ¬    204 Ì    236 ì

013     045 -    077 M    109 m    141      173 ­    205 Í    237 í

014     046 .    078 N    110 n    142      174 ®    206 Î    238 î

015     047 /    079 O    111 o    143      175 ¯    207 Ï    239 ï

016     048 0    080 P    112 p    144      176 °    208 Ð    240 ð

017     049 1    081 Q    113 q    145 ‘    177 ±    209 Ñ    241 ñ

018     050 2    082 R    114 r    146 ’    178 ²    210 Ò    242 ò

019     051 3    083 S    115 s    147 “    179 ³    211 Ó    243 ó

020     052 4    084 T    116 t    148 ”    180 ´    212 Ô    244 ô

021     053 5    085 U    117 u    149 •    181 µ    213 Õ    245 õ

022     054 6    086 V    118 v    150 –    182 ¶    214 Ö    246 ö

023     055 7    087 W    119 w    151 —    183 ·    215 ×/Œ  247 ÷/œ

024     056 8    088 X    120 x    152 ˜    184 ¸    216 Ø    248 ø

025     057 9    089 Y    121 y    153 ™    185 ¹    217 Ù    249 ù

026     058 :    090 Z    122 z    154 š    186 º    218 Ú    250 ú

027     059 ;    091 [    123 {    155 ›    187 »    219 Û    251 û

028     060 <    092 \    124 |    156 œ    188 ¼    220 Ü    252 ü

029     061 =    093 ]    125 }    157      189 ½    221 Ý    253 ý

030     062 >    094 ^    126 ~    158      190 ¾    222 Þ    254 þ

031     063 ?    095 _    127      159 Ÿ    191 ¿    223 ß    255 ÿ

Die ersten 32 Zeichen (0-31) sind Kontroll-/Steuerzeichen, die in der ASCII-Tabelle für die Telekommunikation (z.B. Fernschreiber) festgelegt wurden. Einige dieser Zahlenwerte finden jedoch im PC-DOS-Zeichensatz für Sonderzeichen Anwendung, und die Werte 128-255 sind hier völlig anders belegt. Im VAX-VMS-Zeichensatz sind die Werte 128-159 mit Steuerzeichen belegt, und andere Zeichen mit höheren Werten fehlen. Þ und þ sind nur in einigen Ausgaben des Betriebssystems zugänglich. Œ hat den Wert 215, und œ hat den Wert 247, also korrekt unter O/o gruppiert, aber die meisten Drucker drucken bzw. × und ÷ nach der oben angegebenen ANSI-Norm aus.
Die Alphabetisierung eines Zeichensatzes erfolgt mit einem Kriterium (oder aber mit mehreren Kriterien als erstes Kriterienniveau) in der Reihenfolge der zugrundegelegten Tabelle. In obiger ANSI-Tabelle (und ebenso im ASCII- Alphabet) hat F den Wert 70, und b hat den Wert 98, so sortiert nach dieser Tabelle kommt F vor b, weil 70 kleiner ist als 98.

Prinzipien einiger Sortierverfahren

Bevor die tatsächliche Realisierung von Programmen in der Programmiersprache C gezeigt wird, sollen aus Rücksicht auf Leser, die mit dieser Sprache oder eventuell mit dem Programmieren überhaupt nicht vertraut sind, die Prinzipien der Sortiermethoden möglichst einfach erklärt werden.

Einfache einstufige Sortierung (I)
Die Grundlage einer jeweiligen Alphabetisierung ist ein Zeichensatz. Bei manueller Sortierung wird direkt die in einer Sprache vorkommenden Buchstaben in einer vorgegebenen Reihenfolge (»der alphabetischen Reihenfolge«) zugrunde gelegt. Als Beispiel sei die schwedische alphabetische Reihenfolge angegeben: a b c d e f g h i j k l m n o p q r s t u v w x y z å ä ö. Implizit haben die Großbuchstaben dieselbe Reihenfolge (A B ... Z Å Ä Ö) und werden mit den Kleinbuchstaben zusammensortiert. Über die Einreihung typographischer Zeichen, die keine Buchstaben sind, geben die Rechtschreibwörterbücher kaum Auskunft, aber Veröffentlichungen der Normungsausschüsse können uns da weiterhelfen. Sehen Sie hierzu den Abschnitt Sortierfolge der Sonderzeichen. Die so festgelegten Normen sind aber durchaus nicht computergerecht, indem an einem Computersortierverfahren hohe Ansprüche gestellt werden. Die übliche Computersortierung hat ein »Computeralphabet« als ihre Grundlage wie das in diesem Artikel wiedergegebene ANSI-Alphabet (ANSI-Zeichensatz). Für die Prinzipien ist es ohne Bedeutung, ob der ANSI-Zeichensatz oder ein anderer zugrunde gelegt wird, wie 7-Bit-ASCII, PC-ASCII, EBCDIC, Unicode oder sonst noch etwas. Die Alphabetisierung erfolgt in der Reihenfolge der Tabellenwerte des herangezogenen Zeichensatzes. Die zu sortierenden Eintragungen werden zuerst nach den ersten Buchstaben (von links) eingeordnet. Beim Zusammenfall (d.h. wenn diese ganz gleich sind), wird nach dem zweiten eingeordnet und so fort.
Vergleichen wir die beiden Zeichenfolgen hinten und hinter, finden wir in der sechsten Position von links einen Unterschied, und zwar zwischen n und r. Nach dem allgemeinen Begriff der alphabetischen Reihenfolge kommt n vor r, aber die gleichlautende Entscheidung eines Computers beruht auf die Tabellenwerte. Nach der ANSI-Tabelle hat n den Wert 110, und r hat den Wert 114. Weil n den niedrigeren Tabellenwert hat, kommt n vor r. Auf die Frage, wie ein Computer Zahlenwerte vergleicht, wollen wir nicht näher eingehen, da es dem Laien einleuchtender sein dürfte, daß dies möglich ist, als daß Zeichen, die in den Alphabeten verschiedener Länder unterschiedlich eingereiht sind, sich »größenmäßig« vergleichen ließen.
Sowohl diese als die nachfolgenden Sortiermethoden lassen eine kürzere Zeichenfolge, deren Zeichen den ersten Zeichen einer längeren Folge gleich sind, zuerst kommen, z.B. Blut vor Blutdruck. Dies beruht darauf, daß eine Zeichenfolge mit einem Abschlußzeichen abgeschlossen wird, das den Wert 0 (Null) hat. Man betrachte also Blut als eine Folge von 5 Zeichen, B = 66, l = 108, u = 117, t = 116, Schlußzeichen = 0. Der entscheidende Vergleich ist also zwischen dem Schlußzeichen = 0 und d = 100. (So jedenfalls in der Sprache C. Es gibt andere Methoden der Längenangabe).
Die einfache einstufige Sortierung, die bei mehreren Computerprogrammen, vor allem amerikanischer Herkunft, zu finden ist, genügt auch in Verbindung mit dem einfachen englischen Zeichensatz (A-Z, a-z) den lexikographischen Prinzipien nicht, indem Groß- und Kleinbuchstaben nicht zusammensortiert werden. Wörter mit bzw. Groß- und Kleinschreibung zerfallen also in zwei Gruppen. So kommt Karl vor aber. Alle nationale Zeichen kommen nach Z/z, und auf Französisch kommt z.B. zèbre vor ébat.

Verbesserte einstufige Sortierung (Ia)
Wenn wir die Tabellenwerte zur Angabe der Einordnungsreihenfolge abändern wollen, müssen wir eine Zusatztabelle zur Hilfe nehmen, indem unsere primäre Grundlage die binäre Darstellung der Zeichen im Speicher ist. Geben wir beim PC ein a ein, wird der binäre Wert 01100001 (=97) gespeichert. Um diesen primären Wert abzuändern, läßt man zweckmäßig den Primärwert Index der Zusatztabelle sein. Es wäre schon vonnöten, hier diese Begriffe anhand eines kleinen erstellten Beispiels zu erklären.
Vorgegeben sei dieser betriebssystemeigene Minimalzeichensatz eines gedachten Betriebssystems:

 0  †    1  ~    2  •    3  ®    4  ‰    5  &    6  ¶    7  ¤

Diese Zeichen werden unmittelbar nach den (primären) Tabellenwerten in folgender Reihenfolge sortiert: † ~ • ® ‰ & ¶ ¤ . Wir wollen aber die Reihenfolge abändern zu: † • ¤ & ~ ¶ ‰ ® . Wir definieren hierzu eine Tabelle:
Folge[] = { 0, 2, 7, 5, 1, 6, 4, 3 }

Ein Index gibt die Platznummer in der neuen Tabelle an in der Reihenfolge 0, 1, 2, 3 ... n. Nach diesen beiden Tabellen haben wir also z.B.: Folge['~'] = Folge[1] = 2 und Folge['¤'] = Folge[7] = 3. Folglich: ~ < ¤ (d.h. ~ ist »kleiner als« ¤, oder ~ kommt vor ¤), weil 2 < 3.
Wir können die Tabelle mit alten (alt) und neuen (neu) Reihenfolgennummern zweierlei aufschreiben:

alt 0 †  alt 1 ~  alt 2 •  alt 3 ®  alt 4 ‰  alt 5 &  alt 6 ¶  alt 7 ¤

neu 0    neu 2    neu 7    neu 5    neu 1    neu 6    neu 4    neu 3

und

alt 0 †  alt 4 ‰  alt 1 ~  alt 7 ¤  alt 6 ¶  alt 3 ®  alt 5 &  alt 2 •

neu 0    neu 1    neu 2    neu 3    neu 4    neu 5    neu 6    neu 7

Ein ‰ hat im Beispielszeichensatz den primären Tabellenwert 4 (native character set value) und infolge der Abänderungstabelle den sekundären Tabellenwert 1 (softwareimplementierte Zeichenfolgewert). Im folgenden ist unter Tabellenwert der sekundäre Wert gemäß einer Abänderungstabelle zu verstehen.
In einer Variante der verbesserten einstufigen Sortierung erhalten mehrere Zeichen denselben Tabellenwert, um eine Zusammensortierung der betreffenden Zeichen zu erzielen. Um die Zeichen E É È Ê Ë e é è ê ë zusammenzusortieren, erhalten sie alle z.B. den Tabellenwert 101 (ANSI- und ASCII- Wert von 'e'). Bei einem Zeichenfolgenvergleich nach diesem Prinzip sind aber beispielsweise folgende Zeichenfolgen als gleich anzusehen: Ena ena Éna Énà enâ. Diese Folgen werden nach der eingesetzten Abänderungstabelle zusammensortiert, was anhand der Primärwerte (z.B. ANSI- oder ASCII-Tabelle) nicht der Fall sein würde, aber die Reihenfolge untereinander bleibt undefiniert, so daß bei wiederholter Sortierung durch dieselbe Sortierroutine nach diesem Prinzip 5*4*3*2*1 = 120 verschiedene Sortierfolgen der erwähnten fünf Zeichenfolgen auftreten können, was durchaus unzufriedenstellend erscheint.

Erweiterte, verbesserte, einstufige Sortierung (Ib)
Um den Nachteil der undefinierten Reihenfolge bei Gleichheit eines Basisbuchstaben abzuhelfen, schreiben wir zusammenzusortierenden Zeichen konsekutive Tabellenwerte innerhalb eines abgegrenzten Intervalls zu. Die konkreten Tabellenwerte sind ohne Bedeutung, wenn bloß eingehalten ist, daß Zeichen, die den in Frage kommenden zuvorkommen, einen niedrigeren Wert, und die, die danachkommen, einen höheren haben. Eine von mehreren brauchbaren Lösungen wäre, den primären Wert (ANSI-Wert) des Basisbuchstaben mit 100 zu multiplizieren, und zum Ergebnis einen Gewichtsfaktor zu addieren. Lassen wir einen Kleinbuchstaben den Gewichtsfaktor 10 erhalten, einen Großbuchstaben den Faktor 0 und die Akzente Faktoren wie folgt: ´ = 1, ` = 2, ˆ = 3, ˜ = 4, ¨ = 5. Gewichtsfaktor 6 verwenden wir für andere Varianten eines Basisbuchstaben, z.B. für ç, was sich machen läßt, weil in Verbindung mit den in den in Betracht genommenen Zeichensätzen berücksichtigten Sprachen keine Diskrepanzen entstehen, und ansonsten ließen sich die Gewichtsfaktoren sinngemäß justieren. Nach diesem Prinzip hätten wir Tabellenwerte wie beispielsweise:

D = 10000        E = 10100        Ë = 10105        ê = 10113

Ð = 10006        É = 10101        e = 10110        ë = 10105

d = 10010        È = 10102        é = 10111        F = 10200

ð = 10016        Ê = 10103        è = 10112        f = 10210

Es ist ohne Bedeutung, ob in einer konkreten Implementierung diese oder andere Tabellenwerte gewählt wurden. In der erweiterten, verbesserten, einstufigen Sortierung geht es darum, daß alle Zeichen des Zeichensatzes separate Tabellenwerte haben, und daß das Computerprogramm zur Festlegung der Sortierreihenfolge nur eine Kriterienstufe hat. Die Reihenfolge primär gleicher Zeichenfolgen liegt aber durch diese Erweiterung fest.
Dieses Sortierverfahren führt zu einer Reihenfolge wie: foret forez forêt, indem e vor ê kommt. Der primäre Einwand dagegen ist das fehlende »look ahead«. Diese Sortiermethode finden wir u.a. beim Datenbanksystem Ingres.

Zweikriterienstufige Sortierung (II)
Das eben beschriebene Verfahren der Zuschreibung von Tabellenwerten ist mit zwei Kriterienstufen ohne weiteres nutzbar, wenn bloß die Tabelle andersartig herangezogen wird.
Bei der Untersuchung, ob E, É, È, Ê, Ë, e, é, è, ê und ë primär gleich sind, teilen wir die jeweiligen Tabellenwerte durch 100 (und lassen den Rest außer acht). Das Ergebnis 101 besagt, daß alle Zeichen primär gleich sind. Beim Vergleich der unmodifizierten Tabellenwerte ersehen wir, daß die Zeichen sekundär unterschiedlich sind.
Greifen wir ein weiteres Beispiel auf. Die Tabellenwerte der 'u'-Varianten lassen sich folgendermaßen festlegen:

U = 'u' * 100     = 11700          u = 'u' * 100 + 10 = 11710

Ú = 'u' * 100 + 1 = 11701          ú = 'u' * 100 + 11 = 11711

Ù = 'u' * 100 + 2 = 11702          ù = 'u' * 100 + 12 = 11712

Û = 'u' * 100 + 3 = 11703          û = 'u' * 100 + 13 = 11713

Ü = 'u' * 100 + 5 = 11705          ü = 'u' * 100 + 15 = 11715

Die Untersuchung der primären Gleichheit zweier Zeichen erfolgt durch die Teilung durch 100 unter Weglassung des Teilungsrestes, was mit dem Operator DIV angebbar ist. Nach dem primären Kriterium ist u = ü, weil (11710 DIV 100) = (11715 DIV 100) = 117. Die beiden Zeichen sind jedoch sekundär ungleich, da 11710 != 11715.
Im Falle einer sekundären Differenz vor dem Auftreten einer primären Differenz wird die Stelle durch einen »Zeiger« angezeigt, so daß bei eventueller Zeichenfolgengleichheit nach dem ersten Kriterium auf die betreffende Stelle zurückgegriffen werden kann, indem gegebenenfalls die Reihenfolge durch die Tabellenwerte der sekundären Unterschiede festzulegen ist.
Eine besondere Schwierigkeit entsteht durch die für Alphabetisierungszwecke als getrennte Buchstaben anzusehenden Ligaturen ß, Œ und œ. Das deutsche scharfe s, ß, wird wie ss einalphabetisiert, aber bei sonstiger Zeichenfolgengleichheit kommt ss vor ß, also beispielsweise Strassmann vor Straßmann. Ebenso behandelt man französisches œ wie oe. Aus Rücksicht auf die Computeralphabetisierung sehe ich die Notwendigkeit, die Sortierung nicht auf die Originalzeichenfolgen, sondern auf daraus erstellte Kopien erfolgen zu lassen. Damit Strassmann vor Straßmann komme, genügt es nicht, in der Kopie Straßmann zu Strassmann werden zu lassen, da dadurch die Reihenfolge undefiniert bleiben würde. Das Problem läßt sich aber dadurch lösen, daß wir dem ß denselben primären Gewichtsfaktor zuschreiben wie s, aber einen höheren sekundären Faktor. So bekommt 's' den Wert 's' * 100 + 10 = 11510 (Gewichtsfaktor 10, weil es ein Kleinbuchstabe ist), und 'ß' bekommt den Wert 's' * 100 + 10 + 6 = 11516 (Gewichtsfaktor 6, weil ß eine Sondervariante von s ist). Hierdurch sind 's' und 'ß' primär gleich (da 11510 DIV 100 = 11516 DIV 100), aber sekundär kommt 's' vor 'ß'.
Die Kopie von 'Strassmann' wird so 'Strassmann', und die Kopie von 'Straßmann' wird 'Straßsmann'. Die Kopienzeichenfolgen dienen aber ausschließlich internen Sortierungszwecken, und der Programmbenutzer bekommt sie nicht zu sehen. Es wird aber erreicht, daß die Tabellenwertfolgen der beiden Zeichenfolgen so gestaltet werden:
Strassmann:
<11500> <11610> <11410> <9710> <11510> <11510> <11910> <9710> <11010> <11010>
Straßmann :
<11500> <11610> <11410> <9710> <11516> <11510> <11910> <9710> <11010> <11010>
Die beiden Folgen sind primär gleich, aber einen sekundären Unterschied finden wir beim fünften Zeichen, das nach dem primären Kriterium schon ein primäres 's' darstellt (da 11510 DIV 100 = 11516 DIV 100), aber nach dem sekundären Kriterium kommt Strassmann vor Straßmann, da 11510 < 11516.

Dreikriterienstufige Sortierung (III)
Mit nur zwei Kriterienstufen ist der Unterschied zwischen Groß- und Kleinbuchstaben ein sekundärer Unterschied und also beispeilsweise dem Unterschied zwischen e und é gleichzusetzen. Mit zwei Kriterien haben wir eine Sortierfolge wie: Foret, Forêt, foret, forêt. Wörter, die sich nur in bezug auf Groß- oder Kleinschreibung unterscheiden, aber hinsichtlich der diakritischen Zeichen gleich sind, können bei der zweikriterienstufigen Sortierung voneinander getrennt werden, was unzweckmäßig vorkommt. Meine Auffassung, daß die Reihenfolge Foret, foret, Forêt, forêt sein müßte, wird von Dansk Sprognævn (dem dänischen Sprachnormenausschuß) unterstützt. Dies läßt sich computermäßig implementieren, indem wir den Unterschied zwischen Groß- und Kleinschreibung als ein drittes Kriterium ansehen.
Alle Buchstaben, die nach dem primären Kriterium gleich sind, erhalten dieselbe primäre Gewichtszahl. Alle e-Buchstaben (E, É, È, Ê, Ë, e, é, è, ê, ë) sind primär gleich. Ich teile ihnen als Gewichtszahl den ANSI-/ASCII-Wert von 'e' mal 100 zu, um die niedrigeren Stellenwerte für die Gewichtszahlen der weiteren Kriterien freizuhalten. Die e-Buchstaben erhalten also die primäre Gewichtszahl 'e' * 100 = 101 * 100 = 10100.
Die sekundäre Gewichtszahl legt bei primärer Gleichheit die Reihenfolgen nach den diakritischen Zeichen fest. Den französischen, deutschen, dänischen und anderen Alphabetisierungsregeln (aber nicht beispielsweise den italienischen) genügt folgende Festlegung von sekundären Gewichtszahlen: <Buchstabe ohne diakritisches Zeichen> = 0, ´ = 10, ` = 20, ˆ = 30, ˜ = 40, ¨ = 50, <andere> = 60.
Die tertiäre Gewichtszahl dient zur Unterscheidung zwischen Groß- und Kleinbuchstaben und wird herangezogen, wenn sowohl primäre als sekundäre Gleichheit zweier Zeichenfolgen vorliegt. Da ein Großbuchstabe (außer im Schwedischen) einem Kleinbuchstaben zuvorkommt, erhält der Großbuchstabe das kleinere Gewicht, also Großbuchstabe = 0, Kleinbuchstabe = 1.
Beispiele der Errechnung der totalen Gewichtszahl:

      c           ç            e            E            ê            Ê

  1:  9900    1:  9900    1:  10100    1:  10100    1:  10100    1:  10100

  2:     0    2:    60    2:      0    2:      0    2:     30    2:     30

  3:     1    3:     1    3:      1    3:      0    3:      1    3:      0

total 9901  total 9961  total 10101  total 10100  total 10131  total 10130

Tertiäre Gleichheit entscheiden wir nach der Einer-Stelle der totalen Gewichtszahl, sekundäre Gleichheit nach der Zehner-Stelle, und primäre Gleichheit nach den übrigen Stellen.
Als Beispiel vergleichen wir Ê und ê miteinander:
1) Es besteht primäre Gleichheit, da 10130 DIV 100 = 10131 DIV 100 = 101.
2) Es besteht sekundäre Gleichheit, da 10130 DIV 10 = 10131 DIV 10 = 1013.
3) Es besteht tertiäre Ungleichheit, da 10130 != 10131.
Bei der tatsächlichen Implementierung des Algorithmus ist es zu aufwendig, die Multiplikations- und Divisionsrechenvorgänge wie oben angegeben auszuführen. Die obige Beschreibung dient der besseren Verständlichkeit. In meiner realen Lösung werden die zu vergleichenden binären Zahlen im Register durch Schiebeoperationen verschoben, was mit binärer Multiplikation, bzw. Division gleichbedeutend ist.
Die Vergleichsroutine des Alphabetisierungsprogramms untersucht zwei Zeichenfolgen von links nach rechts, jeweils Zeichen derselben Position. Beim Vorkommen eines primären Unterschiedes ist dadurch die Alphabetisierungsreihenfolge gegeben. Beim Vorkommen eines sekundären Unterschiedes wird die Stelle für späteren Gebrauch angezeigt, aber das Vergleichsverfahren wird weitergeführt. Nachdem die erste Stelle eines sekundären Unterschiedes markiert ist, werden alle weiteren Vorkommnisse sekundärer Unterschiede außer acht gelassen, indem der erste sekundäre Unterschied ausschlaggebend ist, wenn zwei Zeichenfolgen primär gleich sind. Ebenfalls wird die Stelle eines eventuellen tertiären Unterschiedes angegeben, indem diese bei sowohl primärer als sekundärer Gleichheit die Sortierfolge entscheidet.

Vergleichsalgorithmen in C

Einfache einstufige Sortierung (I)
Eine Sortierung, wo der Vergleich zweier Zeichenfolgen direkt auf die durch das Betriebssystem zur Verfügung gestellte Zeichentabelle (z.B. ANSI- oder ASCII-Tabelle) beruht, ist die einfachste. Diese Methode finden wir in der C- Standardbibliothek implementiert (die Funktion strcmp, string-compare):

int strcmp (char *s, char *t) {

  for ( ; *s == *t; s++, t++)

    if (*s == '\0')  return 0;

  return *s - *t;

}

Die beiden eingegebenen Zeichenfolgen werden von vorne Zeichen für Zeichen verglichen, bis ein Unterschied erscheint, oder beide Folgen ohne Unterschiede zu Ende sind (Schlußzeichen '\0' = NULL = Tabellenwert 0). Bei Zeichenfolgengleichheit wird der Wert 0 ausgegeben und sonst die Differenz der Tabellenwerte der zuerst vorkommenden unterschiedlichen Zeichen.
Beispiel: Die erste Zeichenfolge, Hafen, und die zweite Folge, Hagel, weisen beim dritten Buchstaben einen Unterschied auf. Es erfolgt der Ausgabewert 'f' (102) – 'g' (103) = -1. Bei einem Wert kleiner als Null ist die erste Folge »kleiner« (kommt zuerst). Beim Umtauschen der Eingaben (also: Hagel, Hafen) ist der Ausgabewert 'g' (103) – 'f' (102) = 1, welches heißt, daß die erste Zeichenfolge »größer« ist (zuletzt kommt).
Dieser Algorithmus führt zu einer Alphabetisierungsreihenfolge wie beispielsweise: Foret, banan, forez, forêt, Æble, ...

Verbesserte einstufige Sortierung (Ia u. Ib)
Eine veränderte Sortierungsreihenfolge kann durch eine Zusatztabelle festgelegt werden. Eine Beispielstabelle wurde jedoch in diesem Beispiel ausgelassen. Die einzelnen Zeichen bekommen einen Tabellenwert, der der gewünschten Reihenfolge entspricht. Oft werden gleiche Basisbuchstaben zusammensortiert (z.B. e, é, è). Wir können hier zwischen einer unprioritierten (Ia) und einer prioritierten Reihenfolge (Ib) der zusammensortierten Zeichen unterscheiden. Wenn nicht prioritiert wird, erhalten alle zusammenzusortierenden Zeichen denselben Wert, und wenn prioritiert wird, erhalten sie Tabellenwerte direkt nebeneinander.

static const int rf[256];

/* Diese Tabelle ist noch zu initialisieren! */

int strvgl_1 (unsigned char *s, unsigned char *t) {

  for ( ; *s == *t; s++, t++)

    if (*s == '\0')  return 0;

  return rf[*s] - rf[*t];

}

Wie in strcmp wird die erste Stelle eines Unterschiedes der beiden eingegebenen Zeichenfolgen festgestellt. Es wird aber nicht die BS-unterstützte Tabelle mit beispielsweise ANSI- oder ASCII-Werten direkt zugrundegelegt, sondern eine abgeleitete Tabelle mit diesen Werten als Index und die abgeänderte Reihenfolge als Tabellenwerte eingereiht. Bei unprioritierter Reihenfolge fänden wir beispielsweise die Tabellenwerte e = é = è = ê = ë = E = É = È = Ê = Ë = 41. Die Reihenfolge untereinander bleibt undefiniert, und beim mehrmaligen Sortieren mit demselben Programm kann dieselbe Eingabe zu unterschiedlichen Ausgaben führen. Bei prioritierter Reihenfolge geben die Tabellenwerte die Reihenfolge an, z.B. E = 41, É = 42, È = 43, Ê = 44, Ë = 45, e = 46, é = 47, è = 48, ê = 49, ë = 50. Den Tabellenwert von e findet man, indem man den ANSI- oder ASCII-Wert von e als Index setzt (oder den Wert der jeweiligen Ausgangstabelle): rf['e'] = rf[101] = 46.

Sortierung mit zwei Kriterienstufen (II)
Sollen sowohl primäre als sekundäre Kriterien berücksichtigt werden, so daß diakritische Zeichen und die Groß- oder Kleinschreibung erst im Falle von primärer Zeichenfolgengleichheit von Bedeutung sind, wird die Aufgabe ein bißchen komplizierter. Der folgende Entwurf setzt voraus, daß die Tabellenwerte zusammenzusortierender Buchstaben folgendermaßen ausgerichtet werden: Wert der Ausgangstabelle mal hundert plus eine Gewichtszahl zur Reihenfolgenbestimmung bei sekundärem Entscheidungsbedarf. Die Tabelle wurde hier ausgelassen. Das Programm hat seinen Ursprung in dem obigen leichter verständlichen Durchgang der Prinzipien einiger Sortierverfahren und wird deshalb hier abgedruckt; ein besseres Programm wird nachfolgend beschrieben. Aus Rücksicht auf die richtige Sortierung von Ligaturen (ß, Œ) wird eine Kopierfunktion aufgerufen, die eine zweckmäßig abgeänderte »Kopie« einer Eingabezeichenfolge erstellt, worauf später näher eingegangen wird.

static const int rf[256];

/* Diese Tabelle ist noch zu initialisieren! */

int strvgl_2 (unsigned char *s1, unsigned char *s2) {

  unsigned char k1[256], k2[256], *s = k1, *t = k2;

  int p = -1;

  s = kopie (s, s1);   t = kopie (t, s2);

  for ( ; rf[*s]/100 == rf[*t]/100; s++, t++) {

    if (*s == '\0') {

      if (p == -1)  return 0;

      return rf[*(k1+p)] - rf[*(k2+p)];

    }

    if (*s != *t && rf[*s]/100 == rf[*t]/100 && p == -1)

      p = s - k1;

  }

  return rf[*s] - rf[*t];

}

Die vielen Teilungen durch 100 sind rechenmäßig viel zu aufwendig im Verhältnis zu maschinenorientierten, binären Operationen. Um eine Optimierung zu erzielen, ersetzen wir die Teilungen durch Schiebeoperationen.
Ein Zeichen nimmt nur ein Byte auf, wogegen die ganzzahligen Tabellenwerte (integers) implementationsabhängig mindestens zwei Bytes aufnehmen. Es ist also reichlich Platz vorhanden, das Bitmuster eines Zeichens um 5 Stellen nach links zu verschieben, so daß die 5 niederwertigsten Bits für einen Gewichtsfaktor und etwaige Anzeiger (flags) genutzt werden können. Die Wahl von 5 Bitstellen ist fakultativ. Nach Bedarf käme jede andere Zahl innerhalb der gegebenen Grenzen in Frage.
Als Beispiel nehmen wir den Buchstaben e mit dem ANSI- und ASCII-Wert 101 = sedezimal 65 = binär 01100101. In einer 2-Byte-Darstellung haben wir das Bitmuster 0000000001100101. Wenn um 5 Bits nach links verschoben ergibt dies einen Tabellenwert von 0000110010100000. Wenn wir dem Akzent ´ den Gewichtswert 1 zuteilen, bekommt é den Tabellenwert ('e' << 5) ¦ 0x01 = 0000110010100001. Um primäre Gleichheit festzustellen sind die beiden zu vergleichenden Bitmuster vor dem Vergleich um 5 Stellen nach rechts zu verschieben, und ohne Verschiebung läßt sich feststellen, ob zwei Zeichen auch noch sekundär gleich sind.
Nach diesen Voraussetzungen wurde folgender Code erstellt:

static const int rf[256];

/* diese tabelle ist noch zu initialisieren! */

int strvgl_2a (unsigned char *s1, unsigned char *s2) {

  unsigned char k1[256], k2[256], *s = k1, *t = k2;

  int p = -1;

  s = kopie (s, s1);   t = kopie (t, s2);

  for ( ; (rf[*s] >> 5) == (rf[*t] >> 5); s++, t++) {

    if (*s == '\0') {

      if (p == -1)  return 0;

      return rf[*(k1+p)] - rf[*(k2+p)];

    }

    if (*s != *t && (rf[*s] >> 5) == (rf[*t] >> 5) && p == -1)

      p = s - k1;

  }

  return rf[*s] - rf[*t];

}

Programmablaufplan der zweikriterienstufigen Sortierung


   strvgl_2

----------------------------------------------

 Erstellung von [abgeänderten] Arbeitskopien:

 Eingabe 1: Original s1 -> Kopie s

 Eingabe 2: Original s2 -> Kopie t

----------------------------------------------

                 |

  ---------------------------------

     Hole erstes Zeichen a und b

            von s bzw. t

  ---------------------------------

                 |

    --------------

    |            |

    |^    ===============

    ||    |  Primärer   |                    -------------

    |     | Unterschied |      ->   ja       | Returniere|

    |     | zw. a u. b  |--------------------| Differenz |

    |     |     ?       |                    -------------

    |     ===============

    |           | nein          ==============         ----------------

    |     =============  -> ja  | Sekundärer |  nein-> | s=t;

    |     | Kopie s   |---------| Unterschied|---------| returniere 0 |

    |     | zu Ende ? |         | markiert ? |         ----------------

    |     =============         ==============

    |            |                    |ja

    |            | nein    -----------------------------

    |            |         | Returniere Differenz beim |

    |            |         |ersten sekund. Unterschied |

    |            |         -----------------------------

    |     ================

    |     | Sekundärer   |   ja   ===============  nein ------------

    |     | Unterschied  |--------| Stelle schon|-------| Stelle   |

    |     | zw. a u. b ? |  ->    | markiert ?  |  ->   | markieren|

    |     ================        ===============       ------------

    |^           | nein                   |ja                |

    ||    -----------------               |                  |

    |   <-| Nächste beide |<-             |<-                |

    ------| Zeichen holen |-----------------------------------

          -----------------


Sortierung mit drei Kriterienstufen (III)
Zur Verfeinerung der zweikriterienstufigen Sortierung lassen wir als drittes Kriterium die Unterscheidung zwischen Groß- und Kleinbuchstaben hinzukommen. Wenn zwei Zeichenfolgen nach den beiden ersten Kriterien gleich sind, ist das dritte Kriterium entscheidend. Der demnächst folgende Code setzt voraus, daß die Konstantentabelle zur Wiederspiegelung stellenwertabhängiger Feststellung der drei Kriterienstufen angelegt wurde. Die höchstwertigsten Bitstellen belegen wir mit dem ANSI-Wert des Basisbuchstaben, was unser erstes Kriterium ist. Darauf folgen Bitstellen zur Festlegung des zweiten Kriteriums, das durch etwaige diakritischen Zeichen gekennzeichnet ist, und das minderwertigste Bit gibt das dritte Kriterium, Groß- oder Kleinbuchstabe, an.
Beispiele:

      1. Krit.    2. Krit.    3. Krit.  Tabellenwert

 o  = ('o' << 5)              | 1     = 0000110111100001

 ô  = ('o' << 5)  | (3 << 1)  | 1     = 0000110111100111

 O  = ('o' << 5)                      = 0000110111100000

 Ô  = ('o' << 5)  | (3 << 1)          = 0000110111100110



  Bitstellen:

15-13: unbelegt

12 -5: primäres Kriterium:     Basisbuchstabe

 4 -1: sekundäres Kriterium:   Diakritisches Zeichen

    0: tertiäres Kriterium:    Groß-/Kleinbuchstabe



static const unsigned int rf[256];

/* Diese Tabelle ist noch zu initialisieren! */

int strvgl_3 (unsigned char *s1, unsigned char *s2) {

  unsigned char k1[256], k2[256], *s = k1, *t = k2;

  int p = -1, gross = -1;

  s = kopie (s, s1);   t = kopie (t, s2);

  for ( ; rf[*s] >> 5 == rf[*t] >> 5; s++, t++) {

    if (*s == '\0') {

      if (p == -1) {

        if (gross == -1) return 0;

        return rf[*(k1+gross)] - rf[*(k2+gross)];

      }

      return rf[*(k1+p)] - rf[*(k2+p)];

    }

    if (*s != *t && rf[*s] >> 5 == rf[*t] >> 5) {

      if (rf[*s] >> 1 == rf[*t] >> 1) {

        if (gross < 0) gross = s - k1;

      }

      else if (p < 0)  p = s - k1;

    }

  }

  return rf[*s] - rf[*t];

}

Programmablaufplan der dreikriterienstufigen Sortierung


   strvgl_3

-----------------------------------------------

|Erstellung von [abgeänderten] Arbeitskopien: |

|Eingabe 1: Original s1 -> Kopie s            |

|Eingabe 2: Original s2 -> Kopie t            |

-----------------------------------------------

                |

 ---------------------------------

 |  Hole erstes Zeichen a und b  |

 |         von s bzw. t          |

 ---------------------------------

               |

  --------------

  |            |

  |^    ===============

  ||    |  Primärer   |           -------------       ----------------

  |     | Unterschied |  -> ja    | Returniere|       | st=t;        |

  |     | zw. a u. b  |-----------| Differenz |       | returniere 0 |

  |     |     ?       |           -------------       ----------------

  |     ===============                                  nein|^

  |           |                                              ||

  |           | nein          ==============          ===============

  |     =============  -> ja  | Sekundärer |  nein -> | Tertiärer   |

  |     | Kopie s   |---------| Unterschied|----------| Unterschied |

  |     | zu Ende ? |         | markiert ? |          | markiert ?  |

  |     =============         ==============          ===============

  |            |                    |ja                    ja|

  |            | nein   -----------------------  --------------------

  |            |        | Return Differenz b. |  |Return Differenz  |

  |            |        | 1. sek. Unterschied |  |1. tert. U.schieds|

  |            |        -----------------------  --------------------

  |            |

  |     ================

  |     | Sekundärer   |   ja   ===============  nein ------------

  |     | Unterschied  |--------| Stelle schon|-------| Stelle   |

  |     | zw. a u. b ? |   ->   | markiert ?  |   ->  | markieren|

  |     ================        ===============       ------------

  |^           |                 |^     |                  |

  ||           | nein            ||     |ja                |

  |     ================         |      |                  |

  |     | Tertiärer    | ja->    |      |                  |

  |     | Unterschied  |----------      |                  |

  |     | zw. a u. b ? |                |                  |

  |     ================                |                  |

  |            | nein                   |                  |

  |     -----------------               |                  |

  |   <-| Nächste beide |<-             |<-                |

  ------| Zeichen holen |-----------------------------------

        -----------------

Die Konstantentabelle

Die Konstantentabelle und die Kopierfunktion machen das Landes- und Wahlregelspezifische einer konkreten Implementierung aus, wogegen die strvgl- Funktion unverändert bleibt.
Die Werte der Konstantentabelle sind zur Dokumentation als Rechenausdrücke dargestellt. Da sie zum Kompilierzeitpunkt einmal ausgerechnet werden, wird die Durchlaufzeit eines Sortierverfahrens davon nicht beeinflußt.
Das folgende Beispiel einer Konstantentabelle wurde zur primären Berücksichtigung von deutschen Regeln erstellt. Hierbei wurden die Umlautbuchstaben als Basisbuchstaben mit diakritischen Zeichen angesehen (Eine Implementierung mit beispielsweise ä = ae wäre in der Kopierfunktion zu berücksichtigen).
Primäre Reihenfolge:
1) Ziffern: 0 1 2 3 4 5 6 7 8 9
2) Buchstaben: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Þ Æ Ø Å und damit zusammensortierte entsprechende Kleinbuchstaben. Von den im Zeichensatz beinhalteten fremdsprachigen Buchstaben wurde Þ nach isländischen Regeln eingeordnet und Æ Ø Å nach norwegischen und dänischen Regeln.
3) Zeichen, die in der primären und in der sekundären Reihenfolge nicht ausdrücklich erwähnt sind, kommen nach den Ziffern und Buchstaben. Untereinander werden sie nach den jeweiligen ANSI- oder ASCII-Werten eingereiht.
Sekundäre Reihenfolge:
a) ss kommt vor ß (durch Kopierfunktion implementiert)
b) Oe kommt vor Œ; oe kommt vor œ (durch Kopierfunktion implementiert)
c) Diakritische Zeichen haben die Reihenfolge ´ ` ˆ ˜ ¨
Tertiäre Reihenfolge:
Bei primärer und sekundärer Gleichheit zweier Zeichenfolgen kommt ein Großbuchstabe vor einem Kleinbuchstaben.


Diese Implementierung einer Konstantentabelle zur Verwendung zusammen mit der Funktion strvgl_3 ist in folgenden Ausschnitten wiederspiegelt:

/*

         Bitwerte von rechts nach links nummeriert:

         0         Tertiäres Gewicht: 0 für Großbuchstaben, 1 für Kleinbuchstaben

         1-4       Sekundäres Gewicht: Akut (´) = 1, Gravis (`) = 2, Zirkumflex (ˆ) = 3, Tilde (˜) = 4,

                   Umlaut/Trema (¨) = 5,  Andere (z.B. ¸) = 6

         5-12      Primäres Gewicht: Gleich für zusammenzusortierende Zeichen

         13        Gewicht für Sonderzeichen, damit sie nach Ziffern

                   und Buchstaben kommen

         14-…      Unbenutzt

*/





# define UC (unsigned char)

static const unsigned int rf[] = {

         /*   0  NUL */    0,

         /*   1  SOH */    1 ¦ 0x2000,

...

         /*  32  SP  */  UC ' ' << 5,

         /*  33  !   */  UC '!' ¦ 0x2000,

...

         /*  57  9   */  UC '9' << 5,

         /*  58  :   */  UC ':' ¦ 0x2000,

...

         /*  64  @   */  UC '@' ¦ 0x2000,

         /*  65  A   */  UC 'a' << 5,

...

         /*  90  Z   */  UC 'z' << 5,

         /*  91  [   */  UC '[' ¦ 0x2000,

...

         /*  96  `   */  UC '`' ¦ 0x2000,

         /*  97  a   */ (UC 'a' << 5) ¦ 0x01,

...

         /* 162  ç   */ (UC 'c' << 5) ¦ (6 << 1) ¦ 0x01,

         /* 198  Æ   */ (UC '¦' << 5),

         /* 199  Ç   */ (UC 'c' << 5) ¦ (6 << 1),

...

         /* 222  Þ   */ (UC '{' << 5),

...

         /* 230  æ   */ (UC '¦' << 5) ¦ 0x01,

...

         /* 252  ü   */ (UC 'u' << 5) ¦ (5 << 1) ¦ 0x01,

...

         /* 254  þ   */ (UC '{' << 5) ¦ 0x01,

         /* 255      */ 255 ¦ 0x2000

};



Die Kopierfunktion

Die Kopierfunktion dient dazu, eine eingegebene Zeichenfolge entweder ungeändert zu kopieren oder beim Vorkommen im Voraus festgelegter Zeichen oder Zeichenkombinationen eine nach festgelegten Kriterien abgeänderte Kopie zu erstellen, die von der Vergleichsfunktion (strvgl) sinngemäß behandelt wird. In dem folgenden Beispiel ist die regelgenormte Einordnung von ß, Œ und œ berücksichtigt.
Wir kopieren 'ß' zu 'ßs'. 'ß' wird als 'ss' sortiert, aber 'ss' kommt vor 'ß'. Nach dem Tabellenwert sind ß und s primär gleich, aber sekundär kommt s vor ß. Bei Einordnung der Eingaben aßt und asst mit den Kopien bzw. aßst und asst erhalten wir bei Sortierung nach den Kopiezeichenfolgen die genormte Reihenfolge: asst aßt. Ebenso verfahren wir bei den französischen Buchstaben Œ und œ. Aus Œ wird Œe, und aus œ wird œe, wobei Œ und œ dasselbe primäre Gewicht haben wie o, aber größeres sekundäres Gewicht. Wir erhalten dadurch die genormte Reihenfolge dieser Zeichen.

unsigned char *kopie (unsigned char *a, unsigned char *b) {

  unsigned char *start = a;

  int i;

  for (i = 0; *b && i < 255; a++, b++, i++) {

    switch (*b) {

      case 'ß':  *a++ = *b;

                 *a   = 's';

                 i++;

                 break;

      case 'Œ':  case 'œ':

                 *a++ = *b;

                 *a   = 'e';

                 i++;

                 break;

      default:   *a = *b;

                 break;

    }

  }

  *a = '\0';

  return start;

}

Gedanken zur Verfeinerung des Algorithmus

Mein oben dargestelltes Verfahren führt zu einer lexikographisch besseren Alphabetisierung als die herkömmlichen Methoden, die sich bei den bekannten Softwareprodukten feststellen lassen, aber das abgedrucke Programm (strvgl_3) hat keineswegs alle Probleme gelöst. Ich möchte im folgenden darauf eingehen.
In den obigen Programmen ist das Leerzeichen überall bedeutsam, und die Reihenfolge von Digraphen und ihren Entsprechungen (z.B. dän./norw. å und aa) ist unentschieden, indem die eingesetzte Kopierfunktion z.B. aa als å wiedergibt. Die Berücksichtigung des Leerzeichens ist durchaus zufriedenstellend, da dadurch nach einer genormten Wahlmöglichkeit sortiert wird, aber im Falle der dänischen als Digraph angesehenen Buchstabenverbindung aa könnte es wünschenswert sein, normengerecht å vor aa kommen zu lassen. Jede derartige Regel führt zu aufwendigeren Programmen, und so ist vorauszusehen, daß in überschaubarer Zukunft die Regeln vereinfacht werden, was ich aber bedauerlich finde, da ich der Meinung bin, daß eher die Computeralgoritmen angepaßt werden sollten als die Außenwelt. Ein Problembeispiel stellt das dänische Wort ekstraarbejde (Extraarbeit) da. Bei diesem aus ekstra und arbejde zusammengesetzten Wort dürfen die beiden aufeinanderfolgenden a nicht als å angesehen werden. Solche Ausnahmefälle lassen sich nur berücksichtigen, wenn eine große Datenbank zur Verfügung steht, was bei der Sortierung zu aufwendig sein würde.
Eine erste Annäherung der Lösung dieser beiden Probleme wäre durch die Kopierfunktion zu erreichen, indem wir beispielsweise aus der zu sortierenden Zeichenfolge »a conto« die Folge »aconto« erstellen ließen, und ebenso würde aus »aal« die Folge »ål«. Da aber dieses Verfahren nicht zwischen a conto und aconto und zwischen aal und ål unterscheidet, muß man den Vorgang etwas verfeinern, um zu einer einheitlichen Reihenfolge zu gelangen.
Um eine Lösungsmethode zu skizzieren, würde ich eine größere Tabelle anlegen, die aber keineswegs so überschaubar sein würde wie die bisherigen. Wenn nach spanischen Regeln zu sortieren ist, sollte beispielsweise ñ einen Tabellenwert zwischen dem von n und dem von o erhalten, und ll käme, durch die Kopierfunktion implementiert, mit Tabellenwert zwischen l und m (aber in Fremdwörtern wäre es nach den Regeln nicht so! - also das Datenbankproblem schon wieder!), und in einer dänischen Fassung bekäme aa einen Tabellenwert nach å. Der auszulassende Zwischenraum (space) wäre durch einen besonderen vom Programm erkennbaren Tabellenwert zu kennzeichen, so daß zwei sonst gleiche Zeichenfolgen auseinander gehalten werden könnten.
Auf die Implementierung des letzten Modells habe ich bisher verzichtet. Wie ich beschrieben habe, gibt es keine einheitliche überall einsetztbare Methode, die sämtliche Probleme lösen würde. Nicht zu vergessen, würden die heiklen konstruierten Zeichenzusammenstellungen, die die meisten Schwierigkeiten bereiten, in der Praxis sehr selten oder nie vorkommen, so daß es auch eine Frage von Aufwand im Gegensatzt zu Nutzen ist, was aber meiner Meinung nach den theoretischen Überlegungen nicht im Wege stehen darf.

Sortierung einiger kommerzieller Programme

Meine Arbeit mit der Untersuchung von Alphabetisierungsregeln und mit der Implementierung eines verbesserten Computersortierverfahrens entspringt der Feststellung, das handelsübliche Softwareprodukte (1994) teils unterschiedlich, teils unzufriedenstellend sortieren im Verhältnis zum üblichen Ergebnis einer manuellen Alphabetisierung. Deshalb will ich kurz eine kleine Auswahl von sortierfähigen Softwareprodukten rezensieren und auf die Unzulänglichkeit des einzelnen Produktes eingehen. Es sei aber ausdrücklich darauf hingewiesen, daß einige der behandelten Produkte in anderen Ausgaben, auf anderen Computerplattformen oder mit anderen Softwareeinstellungen eventuell zu andersartigen Sortierergebnissen kommen könnten.

Wie sortiert Ingres?

Das weltweit verbreitete Datenbanksystem Ingres wurde in der Version 6.3 auf einem VAX-Computer mit dem Betriebssystem VMS untersucht. Der zur Verfügung stehende Zeichensatz ist der multinationale Satz des VMS, der abgesehen von unbedeutenden Abweichungen dem in diesem Artikel abgedruckten ANSI-Zeichensatz gleich ist. Œ hat den Wert 215 auf dem Platz von × der ANSI-Tabelle, und œ hat den Wert 147. Die benutzte Version wurde zur vorrangigen Handhabung der dänischen Sonderbuchstaben eingestellt. Vor dieser Umstellung hatten wir die schwedische Einordnung von Å und å.
Ingres hat eine Kriterienstufe (Ib) und also kein Look-ahead. Die Großbuchstaben kommen vor den Kleinbuchstaben mit beispielsweise folgendem Sortierergebnis:
Banan, Kælder, Zoologi, Æble, Ångström, citron, jeep, zone, æble.
In einem Lexikon ist es unerläßlich, Groß- und Kleinbuchstaben zusammenzusortieren.
Die Vorkommnisse eines Basisbuchstaben werden zusammensortiert. Wörter mit Wortanfang ó sind also unter o zu suchen. Beim gleichen Basisbuchstaben stimmt die Reihenfolge mit der ANSI-Tabelle überein. Französisches œ wird mit o zusammensortiert, aber wird fehlerhaft bei der Einordnung nicht als o+e angesehen. Sortierbeispiel:
ol, òl, ól, ôl, õ, öl, œl.
Nach dänischen Regeln wäre ö mit ø am Ende des Alphabets zusammenzusortieren, aber die Umlautbuchstaben werden nach deutschen Regeln eingeordnet.
Das fehlende Look-ahead von Ingres ersieht man aus der sortierten Reihenfolge:
et, ez, êt.
Die lexikographisch richtige Reihenfolge ist: et, êt, ez, aber Ingres läßt alle e-Vorkommnisse vor ê-Vorkommnissen kommen.
Ingres reiht deutsches ß nach ss ein, aber ohne Rücksicht darauf, was danachkommt. Dies läßt sich anhand einer Namensliste exemplifizieren, die teils durch Ingres, teils mit der C-Funktion strcmp und teils mit meiner strvgl-Funktion sortiert wurde:

Ingres                   strcmp                   strvgl

Strasrer                 Strasrer                 Strasrer

Strassmann               Strassmann               Strassmann

Strasstmann              Strasstmann              Straßmann

Straßmann                Strastmann               Straßrer

Straßrer                 Stratrer                 Strasstmann

Straßtmann               Strazmann                Straßtmann

Strastmann               Straßmann                Strastmann

Stratrer                 Straßrer                 Stratrer

Strazmann                Straßtmann               Strazmann

Französisches œ ist als oe zu sortieren. Bei Ingres wird œ schon als oe sortiert, aber ohne Look-ahead:

Ingres                   strcmp                   strvgl

BOEF                     BOEF                     boea

BŒF                      BŒF                      BOEF

boea                     boea                     boef

boef                     boef                     BŒF

boeg                     boeg                     bœf

boez                     boez                     boeg

bœf                      bof                      boez

bof                      bœf                      bof

Eine weitere Liste zur Feststellung der Sortierungsunterschiede wäre:

Ingres                   strcmp                   strvgl

ACE                      ACE                      Abe

ACK                      ACK                      abe

AÇE                      Abe                      abé

Abe                      AÇE                      ACE

Zebra                    Zebra                    AÇE

abe                      abe                      ACK

abé                      abé                      vor

vor                      vor                      vör

vore                     vore                     vore

vör                      vör                      vöre

vöre                     vöre                     Zebra

Wie sortiert WordPerfect?

Das Sortierverfahren des Textverarbeitungsprogramms WordPerfect (5.1) wurde in der dänischen Version 5.1 auf einem PC und auf einem VAX- Computer untersucht, und zwar mit unterschiedlichen Ergebnissen. Auf dem PC haben Kleinbuchstaben Vorrang vor den Großbuchstaben; auf dem VAX ist es umgekehrt. Und auf dem VAX sind Buchstaben mit dem Gravis (`) fehlerhaft nach allen anderen Akzenten desselben Basisbuchstaben angebracht.
Die unmittelbar feststellbare Reihenfolge ist:
1) Sonderzeichen aus der niederen Hälfte des ANSI-/ASCII-Zeichensatzes, wie z.B. , . ; + *
2) griechische Buchstaben
3) Ziffern
4) lateinische Buchstaben
5) russische Buchstaben
6) hebräische Buchstaben
7) japanische Buchstaben
8) mathematische Symbole des WP-Zeichensatzes 6
9) Sonderzeichen aus der oberen Hälfte des ANSI-/ASCII-Zeichensatzes
Es scheint unzweckmäßig, daß die Sonderzeichen in zwei Gruppen aufgeteilt sind.
Groß- und Kleinbuchstaben mit und ohne diakritischen Zeichen werden in WP zusammensortiert. Die diakritischen Zeichen scheinen beim PC generell diese Reihenfolge zu haben: ´ (accent aigu, Akut), ` (accent grave, Gravis), breve, Kürzezeichen, ˆ (accent circonflexe, Zirkumflex), caron, Hácek, Hatschek, ¨ (Trema bzw. Umlaut), ˜ (Tilde), ¸ (Cedille), · (Punktakzent), ° (Kreisakzent), Ogonek, ¯ (Macron, Längestrich), " (ungarischer Umlaut).

Es muß als Fehler angesehen werden, daß die beiden Sonderzeichen [ und ] (die bei der vorhergehenden Sortierung nicht mit einbezogen wurden) unter die Buchstaben kommen, und zwar [ zwischen Ø und ö, und ] zwischen Ö und å. Die Sortierung folgt dänischen Regeln, also Ä/ä mit Æ/æ zusammen, Ö/ö mit Ø/ø und Ü/ü mit Y/y zusammen. Den Regeln der dänischen Norm (Dansk Standard Nr. 377) entsprechend wird aa mit å zusammensortiert. Der Flußname Maas ['ma·s] wird also der unterschiedlichen Aussprache zum Trotz mit Mås ['må·'s] zusammensortiert, was den meisten Leuten unsinnig vorkommt, und viele Wörterbücher sehen von dieser Regel weg. Es entsteht ein Fehler bei der Einreihung von ekstraarbejde (Extraarbeit), indem dies Wort nach beispielsweise ekstraudgift (Extraausgabe) einsortiert wird. Die Zusammensortierungsregel gilt nach der Norm nicht bei zusammengesetzten Wörtern.
Im Regelfall benutzt WP Look-ahead (zwei Kriterienstufen). Wir bekommen also die korrekte Reihenfolge: foret, forêt, forez. Wir finden aber nur eine einstufige Sortierung (Ia) in Verbindung mit å/aa. Nach den Regeln hat å den Vorrang vor aa, aber bei WP bleibt die Reihenfolge undefiniert, wie aus folgender Sortierreihenfolge zu ersehen ist: baaf, båf, båk, baak, Ål, Aal, Ål. Wiederholte Sortiervorgänge können zu unterschiedlichen Ergebnissen führen! Der Versuch, ß, Œ und œ richtig einzureihen, ist nur teilweise gelungen, was aus dieser Sortierreihenfolge von WP ersichtlich ist: asst, asstm, aßt, boef, boez, BOEZ, bof, bœf, BŒF, Haß, haßerfüllt, haspeln, hassen, hassenswert. Die lexikographisch richtige Reihenfolge ist: asst, aßt, asstm, boef, BŒF, bœf, BOEZ, boez, bof, haspeln, Haß, hassen, hassenswert, haßerfüllt.
Eine Sortierung mit WordPerfect Version 6.0 in deutscher Ausgabe (mit Option groß vor klein) ergab:

  ae        asst        boef       Foret       haspeln

  aeh       asstm       BOEZ       foret       hassen

  afg       aßt         boez       Forêt       hassenswert

  äg                    bof        forêt       Haß

  äi                    BŒF        forez       haßerfüllt

                        bœf

Wahlweise können auch Kleinbuchstaben den Vorrang haben. Umlaut gilt hier als diakritisches Zeichen.
Der Fehler bei der Einordnung von Wörtern mit ß, Œ, œ ist auch in dieser Ausgabe nicht behoben worden.

Wie sortiert Paradox?

Das Datenbanksystem Paradox von Borland hat ein hervorragendes Sortiervermögen. Die Einwände, die sich machen lassen, sind erheblich kleiner als bei den anderen Programmen, die ich untersucht habe. Die untersuchte PC-Ausgabe bietet vier unterschiedliche Sortierreihenfolgen an: ASCII, International, Dänisch/Norwegisch und Schwedisch/Finnisch.
Die Sortierung erfolgt unabhängig von der benutzten Codepage. Bei Codepage 850 hat Ó den Wert 224, und bei Codepage 865 hat den Wert 224, und in beiden Fällen ist die Alphabetisierungsreihenfolge vom ASCII-Wert abhängig. Dagegen bestimmt die benutzte Sortiertabelle (ASCII, INTL, NORDAN oder SWEDFIN) die Sortierreihenfolge. Das Zeichen ß wird nach der INTL-Tabelle als ss, also nach deutscher Norm, sortiert, aber nach den anderen Tabellen als Sonderzeichen nach allen anderen Buchstaben.
Paradox hat zwei Kriterienstufen (Look-ahead). Mit Ausnahme der ASCII-Sortierung kommt Paradox zur korrekten Reihenfolge: asst, aßt, asstm; foret, forêt, forez. Nach der INTL-Tabelle werden die Umlautbuchstaben mit den Grundbuchstaben zusammensortiert, aber nach der Variante, wo z.B. ä als ae aufgefaßt wird: vad, vaer, vär, vaere, väre, vaf, var, vare.
Groß- und Kleinbuchstaben werden zusammensortiert, wobei ein Kleinbuchstabe als Sekundärkriterium einem Großbuchstaben zuvorkommt (tom, Tom, tomp, Tomp). Daß nur zwei Kriterienstufen vorhanden sind, ersieht man aus der Reihenfolge: foret, forêt, Foret, Forêt.
Sonderzeichen kommen sowohl vor den Buchstaben (z.B. % & *) als danach (z.B. \ £ ½). Sie hätten nur entweder vor oder nach den Buchstaben kommen dürfen. Dafür kommen in der norwegisch/dänischen Ausgabe zwischen Buchstaben keine Sonderzeichen vor, was leider in der internationalen und in der schwedisch/finnischen Ausgabe der Fall ist.
Nach norwegischer und dänischer Norm wäre aa als å zu sortieren, was jedoch nicht geschieht, und ebenso werden Umlautbuchstaben nicht regelgemäß eingereiht, also ä unter æ, ö unter ø, ü unter y. Wir erhalten eine Sortierung wie: æ Æ ø Ø å Å ä Ä ö Ö ü Ü.
Mit schwedisch/finnischer Sortierung werden folgende Zeichen völlig falsch folgendermaßen eingereiht: æ Æ å Å ä Ä ö Ö ü Ü [ \ ] ø £ Ø.
Normengerecht müßte ein Trema-Zeichen nach den übrigen diakritischen Zeichen kommen, also z.B. e é è ê ë, aber bei Paradox kommt das Trema zuerst: e ë é è ê.

Wie sortiert Microsoft Word for Windows?

Word hat zwei Kriterienstufen (Look-ahead), und Großbuchstaben kommen vor Kleinbuchstaben (Foret, Forêt, foret, forêt, forez). Der Umlautbuchstabe ü wird als der Grundbuchstabe mit diakritischem Zeichen angesehen (u, ü, ud), aber ä und ö haben ihren Platz zuletzt im Alphabet (vor, vore, vör, vöre, z, Þ, þ, æ, ø, å, ä, ö) (Der isländische Buchstabe Þ/þ ist dabei nach isländischen Regeln eingereiht, und æ, ø, å nach norwegisch/dänischen Regeln, und so nicht nach den schwedischen). Œ und œ wären als OE/Oe bzw. oe einzureihen. Zwar werden sie unter O/o sortiert, kommen aber nach anderen oe- Vorkommen. Sortierbeispiel: boez, BŒF, bof, bœf. Ebenfalls kommt ß unter ss, aber nach anderen ss-Vorkommen: hassen, hassenswert, Haß, haßerfüllt. Die isländischen Buchstaben Ð und ð kommen unter d, aber zuletzt (D, d, Ð, ð, e).
Das Leerzeichen hat den Wert 32 (also kein Blindzeichen). Alle Sonderzeichen kommen nach dem Leerzeichen und vor den Ziffern und den Buchstaben.

Wie sortiert Oracle?

Das verbreitete Datenbanksystem Oracle RDBMS (V.6) wurde auf einem VAX-Computer getestet. Die betreffende Ausgabe basierte auf dem ANSI-Zeichensatz des VAX mit einer Kriterienstufe, also ohne Änderungen der Zeichenreihenfolge im Verhältnis zur ANSI-Tabelle. Einige Beispiele der Unzweckmäßigkeit dieser Sortierungsweise wären: Alle Großbuchstaben kommen vor den Kleinbuchstaben (z.B. Zebra vor aber); kein Look-ahead (forez vor forêt); alle nationalen Buchstaben kommen nach z.

Wie sortiert Danbase?

Danbase (V.2.2) ist ein dänisches PC-basiertes Datenbanksystem mit folgender Sortierungsreihenfolge:
  1. ASCII-Werte < 'A' (65), d.h. Sonderzeichen und Ziffern.
  2. A-Z, a-z zusammensortiert mit Buchstaben mit diakritischen Zeichen; jedoch werden ª (166) und º (167) unter o eingereiht (als Œ und œ ?)
  3. Æ æ
  4. [ {
  5. Ø ø
  6. \ ¦
  7. Å å
  8. ] }
  9. Sonderzeichen mit ASCII-Werten 168 - 254
  10. £ (156), Pt-Zeichen (158), ƒ (159).
Die Einordnung der Sonderzeichen vor, zwischen und nach den Buchstaben ist unbefriedigend. Die Reihenfolge von Groß- und Kleinbuchstaben bei sonst gleichen Wörtern ist zufällig (ra, Ra, ra). Buchstaben ohne diakritisches Zeichen kommen vor Buchstaben mit diakritischem Zeichen. Die Reihenfolge scheint zufälliger Art zu sein: ä â à á é ê ë è ï î ì í ö ª ô ò ó ü û ù ú. Es ist unklar, warum die Akzentenreihenfolge bei e anders ist als bei den anderen Grundbuchstaben.
Kein Look-ahead: foret, forez, forêt. Daß das ß nicht als ss, sondern als Sonderzeichen 225 eingereiht wird, läßt sich in einem dänischen Programm entschuldigen, aber dafür hätten ä, ö und ü mit bzw. æ, ø und y zusammensortiert werden müssen.

Schlußwort

Wie ich oben dargestellt habe, haben verschiedene Länder unterschiedliche Alphabetisierungsreihenfolgen, die nicht alle gleichzeitig in Anspruch genommen werden können. Die kommerziell erhältlichen Softwareprodukte mit Sortierfähigkeit machen meist eine unzulängliche Sortierung, die den Anforderungen keines einzelnen Landes gewachsen ist. Es bestand deshalb der Bedarf, ein eigenes Sortierprogramm zu schreiben, das für unterschiedliche Ansprüche abgeändert, bzw. ausgebaut werden kann. Der Endbenutzer sollte die Möglichkeit haben, eigene Sortierreihenfolgen und Kriterienstufen festzulegen.
Möge dieser Artikel dazu beitragen, daß die Sortierweisen kommerzieller Produkte verfeinert werden! Und daß Sprachwissenschaftler einen besseren Einblick in das Computersortierverfahren bekommen haben.



Eine Arbeitsgruppe arbeitet zur Zeit (Frühling 1997) an einem Entwurf zum neuen internationalen Standard. Der Entwurf ist erhältlich über ftp://dkuug.dk/JTC1/SC22/WG20/docs/65S14651.doc (MS-Word 6.0-Datei) oder http://www.dkuug.dk/JTC1/SC22/WG20/docs/14651.html.
Siehe auch die Homepage. Nach meiner Beurteilung des Entwurfes liegt die Zukunft des Alphabetisierens hier in guten Händen.


Hans Christophersen

Homepage: http://www.rostra.dk/