Unicode-Bidi-Algorithmus

Der Unicode-Bidi-Algorithmus (englisch Unicode Bidirectional Algorithm, kurz UBA) ist der vom Unicode-Konsortium veröffentlichte Algorithmus zur Darstellung bidirektionaler Texte, also Texte, die sowohl Zeichen von Schriften enthalten, die von links nach rechts geschrieben werden, als auch von solchen, die von rechts nach links geschrieben werden.

Anforderungen

Während eine Zeichenkette aus Unicode-Zeichen im Speicher immer in der logischen Reihenfolge vorliegt, müssen für die Ausgabe die Teile umgekehrt werden, die aus linksläufigen Schriften stammen. Dabei ist zu beachten, dass Zahlen auch in linksläufigen Texten von links nach rechts geschrieben werden. Ferner müssen einige Zeichen, etwa Klammern, bei einer Umkehrung der Schreibrichtung gespiegelt ausgegeben werden.

Geschichte

Als Autoren der gegenwärtigen Formulierung des Algorithmus werden Mark Davis, Aharon Lanin und Andrew Glass genannt. Ursprünglich wurde der Algorithmus direkt im Unicode-Standard beschrieben, dann aber in einen Anhang ausgelagert. Bis zur ersten offiziellen Version dieses Anhangs am 8. Februar 1999^[1] hatte es immer wieder Korrekturen und weitere Änderungen am Algorithmus gegeben, die folgenden Revisionen enthielten hauptsächlich Klarstellungen von ungenauen Formulierungen. Erst mit der Revision 29 zu Unicode 6.3.0 wurde der Algorithmus durch einige weitere Steuerzeichen und neue Regeln umfassend erweitert. Zuvor konnte es passieren, dass bei Klammern eine der beiden zum Links-nach-Rechts-Text gezählt wurde, die andere zum Rechts-nach-Links-Text, was zu einer unleserlichen Ausgabe führte. Außerdem wurde die maximale Verschachtelungstiefe von 64 auf 128 verdoppelt.

Grundlagen

Zur Beeinflussung des Algorithmus sind mehrere bidirektionale Steuerzeichen definiert, insbesondere das Links-nach-Rechts- und das Rechts-nach-Links-Zeichen.

Außerdem wird jedem Unicode-Zeichen eine Bidi-Klasse (Bidi_Class^[2]) zugewiesen. Diese werden in vier Kategorien unterteilt:

Starke Zeichen besitzen eine eindeutige Schreibrichtung. Hier gibt es folgende Werte:

• L für Zeichen aus von links nach rechts geschriebenen Schriften, also insbesondere alle lateinischen Buchstaben. Auch das Links-nach-rechts-Zeichen hat diesen Wert.
• R für Zeichen aus von rechts nach links geschriebenen Schriften, also etwa Hebräisch. Auch das Rechts-nach-links-Zeichen hat diesen Wert. Zeichen für Arabisch, Syrisch und Thaana erhalten ebenso wie das mit Unicode 6.3 eingeführte arabische Buchstabenzeichen abweichend davon den Wert AL.

Bei den sogenannten schwachen Zeichen treten die folgenden Werte auf:

• EN für die in Europa verwendeten indischen Ziffern, ES für Zeichen, die innerhalb einer Zahl aus diesen Ziffern vorkommen können (Plus- und Minuszeichen) und ET für Zeichen, die am Anfang oder Ende einer Zahl stehen können, etwa Währungssymbole.
• AN für arabisch-indische Ziffern und in solchen Zahlen verwendete Interpunktion.
• CS für Zeichen, die sowohl europäische als auch arabische Ziffern trennen können, etwa Punkt und Komma.
• NSM für kombinierende Zeichen wie Akzente, die mit dem vorhergehenden Zeichen bei der Anzeige vereinigt werden.
• BN für Zeichen wie der bedingte Trennstrich, die in der Ausgabe nicht erscheinen.

Außerdem gibt es noch neutrale Zeichen mit den Werten B, S, WS und ON, diese werden verschiedenen Whitespaces und anderen neutralen Zeichen (Ausrufezeichen etc.) zugewiesen.

Schließlich gibt es noch die expliziten Steuerzeichen, diese werden unterteilt in Steuerzeichen zur Einbettung und zum Überschreiben (LRE, RLE, LRO, RLO, PDF) und die Steuerzeichen zum Isolieren (LRI, RLI, FSI, PDI). Die letzte Gruppe wurde mit Unicode 6.3.0 neu eingeführt. Alle expliziten Steuerzeichen haben einen eigenen Wert für die Bidi-Klasse, der mit ihrem Kurznamen übereinstimmt.

Die Eigenschaft Bidi_Paired_Bracket_Type kennzeichnet öffnende und schließende Klammern, Bidi_Paired_Bracket gibt das jeweilige Gegenstück an.^[3]

Schließlich sind einige Zeichen (etwa Klammern) als spiegelbar gekennzeichnet (Bidi_Mirrored^[4]), für viele dieser Zeichen existiert auch ein Unicode-Zeichen, das dieses Spiegelbild darstellt (Bidi_Mirroring_Glyph^[5]). Bei den anderen Zeichen muss das darstellende Programm selbst ein Spiegelbild erzeugen. Spiegelbild bedeutet dabei nicht in jedem Fall ein exaktes Spiegelbild, so sollte etwa beim Zeichen für die dritte Wurzel nur die Wurzel, nicht aber die 3 gespiegelt werden.

Algorithmus

Zunächst wird der Text in Absätze zerlegt. Der weitere Algorithmus behandelt die Absätze einzeln.

Als erstes erfolgt eine Einteilung in Ebenen (Level) entsprechend den expliziten Steuerzeichen und es wird für jedes Zeichen seine Bidi_Class-Eigenschaft bestimmt. Anschließend wird dieser Wert schrittweise abgeändert, bis schließlich jedes Zeichen als L, R, EN oder AN gekennzeichnet ist. Dazu werden zunächst die schwachen Zeichen angepasst: Trennzeichen zwischen Ziffern werden als Ziffern behandelt, europäische Ziffern, die auf rechtsläufigen Text folgen, werden wie dieser als L behandelt. Nach den schwachen Zeichen werden schließlich die neutralen Zeichen umgewandelt, diese passen sich in ihrer Schreibrichtung dem umgebenden Text an. Dabei werden Ziffern – sofern sie nicht im vorherigen Schritt den Typ L erhalten haben – als R behandelt.

Auf diesen geänderten Eigenschaften wird aufbauend die Ebeneneinteilung so geändert, dass (ausgehend von Ebene 0) Ebenen mit gerader Ordnungszahl von links nach rechts geschriebenen Text enthalten, während die Schreibrichtung in ungeraden Ebenen von rechts nach links geht.

Schließlich erfolgt die Darstellung: Dazu wird der Absatz in Zeilen aufgeteilt und der Text entsprechend den Ebenen umgeordnet. Dabei werden zunächst alle Blöcke der höchsten Ebene umgekehrt, dann alle der zweithöchsten und höchsten, und so weiter, bis zuletzt alle Blöcke mit einer Nummer größer als 0 umgekehrt werden. Zeichen, die dabei von rechts nach links geschrieben werden und gespiegelt werden können, werden durch ihr Spiegelbild ersetzt.

Details

Absätze

• Zerlege den Text in Absätze und wende die folgenden Schritte auf jeden Absatz einzeln an.
• Ermittle in jedem Absatz das erste Zeichen vom Typ L, R oder AL. Dabei werden Zeichen innerhalb eines isolierten Bereiches ignoriert.
• Falls ein solches Zeichen existiert und es vom Typ R oder AL ist, so ist die Grundschreibrichtung linksläufig, die Ebenenzählung beginnt bei 1. Andernfalls ist der Absatz rechtsläufig, die Ebenenzählung beginnt bei 0.

Explizite Steuerzeichen

• Speichere in einem Stapelspeicher, der bis zu 128 Einträge enthalten kann, zunächst die ermittelte Grundebene, als Überschreibstatus den Wert „neutral“ und als Isolationsstatus den Wert „falsch“. In den folgenden Schritten werden immer wieder Einträge in diesem Stapelspeicher gespeichert. Sollte dieser voll, oder die Ebenenzählung größer als 125 sein, so wird der Eintrag verworfen.
• Bei einem RLE bestimme die nächstgrößere ungerade Ebene und speichere sie zusammen mit dem Überschreibstatus „neutral“ und dem Isolationsstatus „falsch“.
• Bei einem LRE bestimme die nächstgrößere gerade Ebene und speichere sie zusammen mit dem Überschreibstatus „neutral“ und dem Isolationsstatus „falsch“.
• Bei einem RLO bestimme die nächstgrößere ungerade Ebene und speichere sie zusammen mit dem Überschreibstatus „rechts-nach-links“ und dem Isolationsstatus „falsch“.
• Bei einem LRO bestimme die nächstgrößere gerade Ebene und speichere sie zusammen mit dem Überschreibstatus „links-nach-rechts“ und dem Isolationsstatus „falsch“.
• Bei einem RLI bestimme die nächstgrößere ungerade Ebene und speichere sie zusammen mit dem Überschreibstatus „neutral“ und dem Isolationsstatus „wahr“.
• Bei einem LRI bestimme die nächstgrößere gerade Ebene und speichere sie zusammen mit dem Überschreibstatus „neutral“ und dem Isolationsstatus „wahr“.
• Ein FSI wird wie ein RLI oder ein LRI behandelt, je nach Art des ersten starken Zeichens, das wie bei Absätzen bestimmt wird.
• Bei einem PDI oder PDF setze Ebene, Überschreibstatus und Isolationsstatus auf die Werte zurück, die vor dem zugehörigen Steuerzeichen (RLI, LRI oder FSI für PDI und RLE, LRE, RLO oder LRO für PDF) galten. Sollte es kein solches Zeichen geben, wird das PDI oder PDF ignoriert.
• Weise jedem anderen Zeichen, das nicht vom Typ BN oder B ist, die aktuelle Ebene und seine Bidi-Klasse zu. Sofern der Überschreibstatus nicht neutral ist, bestimmt dieser die Bidi-Klasse (L oder R). Auch die Steuerzeichen RLI, LRI, FSI und PDI erhalten auf diese Art eine Ebenenzählung, wobei die drei einleitenden Steuerzeichen zur vorherigen Ebene gehören, das beendende PDI zur folgenden. Die anderen expliziten Steuerzeichen werden zusammen mit den Zeichen vom Typ BN entfernt.
• Zerlege den Absatz in Folgen aufeinanderfolgenden oder nur durch isolierte Texte getrennte Zeichen gleicher Ebene und wende die folgenden Schritte auf diese Folgen an. Dabei werden Anfang und Ende der Folgen so behandelt, als stünde dort jeweils ein Zeichen in der Schreibrichtung der höheren der beiden angrenzenden Ebenen. Am Anfang und am Ende des Absatzes übernimmt die Grundebene die Rolle der anderen Ebene.

Schwache Zeichen

• Ändere NSM auf den Wert des vorhergehenden Zeichen oder – am Anfang einer Ebene oder Isolierung, wo sie sich nicht mit dem vorhergehenden Zeichen verbinden können – zu ON
• Bestimme zu jeder europäischen Ziffer (EN) das vorhergehende starke Zeichen. Ist dieses vom Typ AL, so ändere EN zu AN.
• Ändere AL zu R.
• Ändere EN-ES-EN zu EN-EN-EN, EN-CS-EN zu EN-EN-EN und AN-CS-AN zu AN-AN-AN.
• Ändere jede Folge von ET, die an ein EN grenzen, zu EN.
• Ändere alle verbliebenen ES, ET und CS zu ON.
• Bestimme zu jedem EN das vorhergehende starke Zeichen. Ist dieses vom Typ L, so ändere EN zu L.

Neutrale Zeichen

• Seit Unicode 6.3 werden zunächst Klammern angepasst. Zusammengehörende öffnende und schließende Klammern werden dabei einheitlich zu R oder L umgewandelt. Dabei wird im Normalfall die Schreibrichtung der aktuellen Ebene gewählt, nur wenn der Inhalt und mindestens ein benachbartes Zeichen außerhalb der anderen Richtung entspricht, nehmen die beiden Klammern diese Richtung an. Neutrale Zeichen werden dabei übersprungen, EN und AN werden wie R behandelt. Ist gar kein starkes Zeichen innerhalb der Klammer vorhanden, so werden zunächst keine Änderungen vorgenommen.
• Ändere jede Folge neutraler Zeichen, die auf beiden Seiten von Zeichen desselben Typs begrenzt werden, in diesen. Dabei werden EN und AN wie R behandelt.
• Ändere alle verbliebenen neutralen Zeichen in die Grundschreibrichtung ab.

Korrigierte Ebeneneinteilung

• Erhöhe in geraden Ebenen für Zeichen vom Typ R die Ebene um 1, für Zeichen vom Typ EN und AN um 2.
• Erhöhe in ungeraden Ebenen für Zeichen vom Typ L, EN und AN die Ebene um 1.

Umordnung

• Zerlege den Text in Zeilen.
• Kehre in jeder Zeile zunächst alle Zeichenfolgen auf der höchsten Ebene um, dann alle auf der höchsten und zweithöchsten und so weiter, bis zum Schluss alle Zeichenfolgen auf den Ebenen ab 1 umgekehrt werden.
• Setzte kombinierende Zeichen in ungeraden Ebenen wieder hinter ihr zugehöriges Zeichen.
• Stelle Zeichen in ungeraden Ebenen, die gespiegelt werden sollen, durch ihr entsprechendes Spiegelbild dar.

Höhere Protokolle

Der Algorithmus erlaubt die Beeinflussung durch höhere Protokolle. Ein Beispiel hierfür ist das dir-Attribut und das <bdo>-Tag in HTML ebenso wie die unicode-bidi- und die direction-Eigenschaften in CSS, mit denen die Grundschreibrichtung festgelegt werden können oder auch dieselbe Wirkung wie mit den expliziten Steuerzeichen erreicht werden können.^[6]

Implementierung

Der Algorithmus schreibt keine spezielle Implementierung vor, solange das Ergebnis mit dem übereinstimmt, das man erhält, wenn man den Algorithmus streng befolgt. So ist es etwa möglich zunächst zu überprüfen, ob im Text überhaupt Zeichen aus linksläufigen Schreibsystemen vorkommen, und andernfalls den Algorithmus gar nicht erst durchzuführen. Diese Variante ist unter anderem im Webbrowser Firefox implementiert.^[7]

Ein Unicode-kompatibles Programm muss den Unicode-Bidi-Algorithmus nicht unbedingt vollständig implementieren. So könnte eine integrierte Entwicklungsumgebung für Programmiersprachen allen Text grundsätzlich von links nach rechts ausgeben und den UBA somit ganz ignorieren. Auch ist es möglich, nicht alle expliziten Steuerzeichen zu beachten. Die Änderungen mit Unicode 6.3 führten dazu, dass ältere Programme den Algorithmus nicht mehr korrekt umsetzten.

Beispiele

Beispiel 1

(c) צילום:ד"ר אבישי טייכר, CC BY 2.5

Oben rechts steht: „דניאל (ראובן) קזין נפל בעמק הירדן ז׳ אייר תש״ח 16.5.1948 בן 22 במותו“

Betrachtet wird folgende Bildbeschreibung:

Oben rechts steht: „דניאל (ראובן) קזין נפל בעמק הירדן ז׳ אייר תש״ח 16.5.1948 בן 22 במותו“

Die Grundschreibrichtung des Absatzes wird aus dem ersten Zeichen bestimmt und läuft von links nach rechts, ohne explizite Steuerzeichen werden alle Zeichen vorläufig der Ebene 0 zugeordnet. Zunächst bestimmt man die Bidi-Werte der einzelnen Zeichen (zweite Zeile der folgenden Tabelle, N steht dabei für ein beliebiges neutrales Zeichen).

Nun werden die schwachen Zeichen, also die Ziffern behandelt (dritte Zeile). Die Punkte direkt zwischen den Ziffern werden dabei in den Typ EN verwandelt, also im weiteren Verlauf wie die Ziffern selbst behandelt. Den Ziffern geht als erstes starkes Zeichen eines vom Typ R voraus, sodass sie so belassen werden.

Anschließend kommen die neutralen Zeichen an die Reihe (vierte Zeile). Dort wo L und R zusammentreffen, werden – ebenso wie am Ende des Textes – die neutralen Zeichen zu L umgewandelt, da dies der Hauptschreibrichtung entspricht. Da Ziffern für die Behandlung neutraler Zeichen wie R betrachtet wird, werden die neutralen Zeichen zwischen R und EN zu R umgewandelt werden.

Hieraus ergibt sich schließlich die angepasste Ebenenzählung (fünfte Zeile). Ausgehend von der Ebene 0 wird Zeichen vom Typ R die Ebene 1 zugewiesen, Zeichen vom Typ EN die Ebene 2.

Für die Darstellung wird nun zunächst die Ebene 2 in ihrer Richtung umgekehrt:

Anschließend werden die Ebenen 1 und 2 gespiegelt:

Zuletzt werden die beiden Klammern im linksläufigen Text durch ihr jeweiliges Spiegelbild ersetzt:

Auf diese Weise ergibt sich die Darstellung:

Oben rechts steht דניאל (ראובן) קזין נפל בעמק הירדן ז׳ אייר תש״ח 16.5.1948 בן 22 במותו

Kommen noch wie in der Bildunterschrift Zeilenumbrüche innerhalb des Textes vor, so wird zuerst der Umbruch vorgenommen, anschließend die Richtung umgekehrt.

Beispiel 2

Ein biographischer Text über Reuven Rivlin könnte anfangen mit:

Reuven Rivlin (Name in Hebräischer Schrift; geboren 1939 in Jerusalem) ist seit 2014 Staatspräsident von Israel.

Reuven Rivlin (ראובן ריבלין; * 1939 in Jerusalem) ist seit 2014 Staatspräsident von Israel.

Dies führt offenbar zu einer fehlerhaften Darstellung: Das Geburtsjahr steht vor der hebräischen Schreibweise des Namens statt dahinter. Um zu verstehen, wo das Problem liegt, kann man den Algorithmus von Hand durchführen.

Wie im ersten Beispiel läuft die Grundschreibrichtung des Absatzes von links nach rechts und man bestimmt wieder die Bidi-Werte der einzelnen Zeichen (zweite Zeile). Da das nächste starke Zeichen vor dem Geburtsjahr den Wert R hat, wird hier EN nicht in L umgewandelt, im Gegensatz zu den anderen Ziffern in diesem Satz (dritte Zeile). Daher werden diese Ziffern im nächsten Schritt, in dem die neutralen Zeichen aufgelöst werden, daher wie R behandelt (vierte Zeile). Hieraus ergibt sich die angepasste Ebenenzählung (fünfte Zeile). Da die Zeichen zwischen dem hebräischen Namen und dem Geburtsjahr nun in einer ungeraden Ebene liegen, ergibt sich die fehlerhafte Darstellung.

Um dieses Problem zu lösen, fügt man direkt hinter dem hebräischen Namen ein Links-nach-rechts-Zeichen (LRM) ein. So geht den Ziffern ein Zeichen vom Typ L voraus, statt wie bisher eines vom Typ R. Daher wird der Typ der Ziffern auf L geändert und auch die Zeichen zwischen dem Namen und dem Jahr damit korrekt behandelt.

Reuven Rivlin (ראובן ריבלין‎; * 1939 in Jerusalem) ist seit 2014 Staatspräsident von Israel.

Beispiel 3

Bildschirmfoto des Beispiels, einmal nach der aktuellen Form des Algorithmus (oben, Firefox), einmal nach der alten Version (unten, Google Chrome)

Als Beispiel für die mit Unicode 6.3 neu eingeführte Regelung für Paare von Klammern soll folgender Text dienen, der ein Zeichen mitsamt Codepunkt angibt:

Alif (Zeichen: ا): 0627

Eigentlich sollte der deutschen Bezeichnung Alif der arabische Buchstabe in Klammern folgen, dahinter der Codepunkt. In Browsern, die noch den alten Algorithmus verwenden ergibt sich aber ein unleserliches Bild: Beide Klammern sehen wie öffnende aus, die Reihenfolge der einzelnen Elemente ist chaotisch.

Auch hier gibt es nur eine Ebene mit Ebenenzählung 0. Die Bidi-Werte sind in der zweiten Zeile angegeben. Da den europäischen Ziffern ein arabischer Buchstabe vorausgeht, werden sie wie arabische Ziffern behandelt und dem arabischen Buchstaben anschließend der Wert R zugewiesen (Zeile 3). Nach der alten Regelung wären die neutralen Zeichen zwischen dem arabischen Buchstaben und den Ziffern als R behandelt worden, die anderen als L (Zeile 4). Nach der neuen Regel werden aber zunächst die Klammern separat betrachtet. Ihr Inhalt ist zwar einheitlich linksläufig, aber keiner der Nachbarn hat diese Richtung. Damit werden beide Klammern als L behandelt und damit auch die restlichen neutralen Zeichen (Zeile 5). Die sich daraus ergebenden angepassten Ebenenzählung sind in den Zeilen 6 und 7 angegeben.

Nach dem alten Algorithmus ergibt sich durch die wiederholten Umkehrungen und Spiegelungen dieses Bild:

Nach dem neuen Verfahren kommt das erwünschte Ergebnis heraus, Klammern müssen keine gespiegelt werden:

Weblinks

• Demonstration des Algorithmus (englisch)
• Offizielle Formulierung des Algorithmus (englisch)

Einzelnachweise

1. ↑ Dritte Revision des UBA
2. ↑ Fünftes Feld in UnicodeData.txt
3. ↑ BidiBrackets.txt
4. ↑ Zehntes Feld in UnicodeData.txt
5. ↑ BidiMirroring.txt
6. ↑ CSS vs. Markup für bidirektionale Dokumente, abgerufen am 28. Januar 2012
7. ↑ Documentation for BiDi Mozilla, abgerufen am 28. Januar 2012