Binary Ordered Compression for Unicode

Binary Ordered Compression for Unicode (englisch für binär geordnete Komprimierung für Unicode, kurz BOCU) ist eine Familie von Kodierungen für Texte aus Unicode-Zeichen, die zum einen auf möglichst kleinen Speicherbedarf ausgerichtet ist, zum anderen darauf, die binäre Ordnung zu erhalten. Der bekannteste Vertreter BOCU-1 ist zudem direkt mit dem MIME-Protokoll kompatibel. Das Verfahren konnte sich allerdings in der Praxis nicht etablieren.

Geschichte

BOCU wurde 2001 von Mark Davis und Markus Scherer für das ICU-Projekt entwickelt. BOCU-1 ist eine Anwendung dieses Prinzips, die in UTN #6 beschrieben wird. Dabei fehlt allerdings eine formale Definition, lediglich der Code eines C-Programms beschreibt die Kodierung. Der BOCU-Algorithmus ist beim United States Patent and Trademark Office patentiert.

Idee

Die Idee von BOCU besteht darin, dass sich die Codepunkte aufeinander folgender Zeichen meist nur wenig unterscheiden. Werden Zeichen also durch die Differenz zum vorherigen Zeichen kodiert und kleine Differenzen mit einem Byte, größere dagegen mit mehr Bytes repräsentiert, so kann damit Speicherplatz gespart werden. Tatsächlich verwendet BOCU statt der Differenz zum letzten Zeichen die Differenz zu einem Grundzeichen, das auf verschiedene Arten bestimmt werden kann. Es kann zum Beispiel das mittlere Zeichen im zuletzt verwendet Unicodeblock als Grundzeichen verwendet werden um so längere Sprünge von einem Ende des Blocks zum anderen zu vermeiden. Auch ist es möglich, das Grundzeichen bei einem Wechsel des Blocks nicht gleich zu ändern, um so bei Leerzeichen oder Satzzeichen aus dem ASCII-Bereich zwischen Zeichen aus einem anderen Block einen langen Rücksprung zu vermeiden.

In BOCU-1 ist die Menge der Bytewerte, die zur Kodierungen der Differenzen genutzt werden, so beschränkt, dass die Kompatibilität mit MIME gewährleistet ist. Zudem werden Steuerzeichen und das Leerzeichen direkt kodiert.

Eigenschaften

Auf Grund ihrer Konstruktion besitzen BOCU und BOCU-1 folgende Eigenschaften:

BOCU erhält die binäre Ordnung. Ist also eine Liste von Zeichenketten binär den Codepunkten entsprechend geordnet, so trifft dies auch auf die BOCU-kodierten Bytefolgen zu.
BOCU ist – im Gegensatz zu SCSU – deterministisch, jeder Text besitzt eine eindeutige Kodierung. Allerdings kann das gleiche Zeichen an unterschiedlichen Stellen verschieden kodiert werden.
BOCU-1 ist MIME-kompatibel: Die ASCII-Steuerzeichen NUL (0x00), LF (0x0A), CR (0x0D), sowie neun weitere werden wie in ASCII kodiert, und diese Bytewerte werden auch nur zur Kodierung dieser Steuerzeichen verwendet.
BOCU-1 erlaubt in begrenztem Maße einen wahlfreien Zugriff.
BOCU benötigt für normale Texte ähnlich viel Speicherplatz wie traditionelle Zeichensätze vor Unicode oder auch wie SCSU.
BOCU-1 benötigt maximal 4 Byte pro Zeichen.

Eine Reihe von Eigenschaften wirken sich negativ auf die praktische Verwendbarkeit aus:

Obwohl der BOCU-Algorithmus ausdrücklich einfacher als SCSU konzipiert wurde, braucht er in der Praxis deutlich länger.
BOCU-1 ist nicht abwärtskompatibel zu ASCII. Zwar benötigen Texte, die ausschließlich aus ASCII-Zeichen bestehen in der BOCU-1-Kodierung den gleichen Speicherplatz, werden aber durch andere Bytewerte dargestellt. Dies ist insbesondere dann ein Problem, wenn die Zeichenkodierung wie in XML im Dokument selbst angegeben werden soll.

Quellen

Markus W. Scherer, Mark Davis: Unicode Technical Note #6: BOCU-1: MIME-compatible Unicode Compression. (Online)
Doug Ewell: Unicode Technical Note #14: A Survey of Unicode Compression. (Online)
Patentanmeldung US6737994: Binary-ordered compression for unicode. Angemeldet am 13. Mai 2002, veröffentlicht am 13. November 2003, Anmelder: IBM, Erfinder: Davis, Mark Edward; Scherer Markus Walter.‌

Weblinks

Mark Davis, Markus Scherer: BOCU: Binary-Ordered Compression for Unicode
ICU User Guide: Compression