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:
1) ´ (accent aigu, Akut)
2) ` (accent grave, Gravis)
3) ^ (accent circonflexe, Zirkumflex)
4) ¨ (tréma, Trema)
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:
forêt Foret Forêt forez foret
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:
III-1) Foret foret Forêt forêt forez
Sollte aber ein Kleinbuchstabe als vorrangig angesehen werden, sind bei folgender Reihenfolge immer noch drei
Kriterienstufen da (schwedische Reihenfolge):
III-2) foret Foret forêt Forêt forez
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:
II-1) Foret Forêt foret forêt forez
II-2) foret forêt forez Foret Forêt
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:
I Foret Forêt foret forez forêt
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:
- der einfachen ANSI-Reihenfolge nach der ANSI-Tabelle,
- einer verbesserten einkriterienstufige Sortiering mit Zusammensortierung gewisser Zeichen ohne
Prioritierung, und
- 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:
- ASCII-Werte < 'A' (65), d.h. Sonderzeichen und Ziffern.
- A-Z, a-z zusammensortiert mit Buchstaben mit diakritischen Zeichen; jedoch werden ª (166) und º (167) unter o eingereiht (als Œ und
œ ?)
- Æ æ
- [ {
- Ø ø
- \ ¦
- Å å
- ] }
- Sonderzeichen mit ASCII-Werten 168 - 254
- £ (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/