Wenn Sie ein Entwickler sind und vor der Wahl einer Codierung stehen, ist Unicode fast immer die richtige Wahl. Die spezifische Darstellungsweise hängt vom Kontext ab, aber meistens gibt es auch hier eine universelle Antwort – UTF-8. Es ist gut, weil es alle Unicode-Zeichen verwendet, ohne zu viel Byte in den meisten Fällen zu verschwenden. Allerdings bedeutet „nicht zu viel“ für Sprachen, die nicht nur das lateinische Alphabet verwenden, mindestens zwei Byte pro Zeichen. Gibt es eine bessere Lösung, ohne auf prähistorische Codierungen zurückzugreifen, die uns auf nur 256 verfügbare Zeichen beschränken?
Im Folgenden möchte ich meine Versuche vorstellen, diese Frage zu beantworten und eine relativ einfache Algorithmus-Implementierung zu entwickeln, die es ermöglicht, Zeichenfolgen in den meisten Sprachen der Welt zu speichern, ohne die Überflüssigkeit hinzuzufügen, die in UTF-8 vorhanden ist.
Haftungsausschluss. Zunächst einige wichtige Vorbemerkungen: Die beschriebene Lösung wird nicht als universeller Ersatz für UTF-8 angeboten, sie eignet sich nur für eine enge Liste von Fällen (darüber später), und sie darf auf keinen Fall für die Kommunikation mit externen APIs verwendet werden (die davon nichts wissen). In den meisten Fällen sind Algorithmen zur verlustfreien Kompression (z. B. deflate) besser geeignet, um große Mengen an Textdaten kompakt zu speichern. Darüber hinaus habe ich während der Erstellung meiner Lösung einen bestehenden Standard im Unicode gefunden, der dasselbe Problem löst – er ist etwas komplexer (und oft schlechter), aber er ist dennoch ein akzeptierter Standard und kein zusammengezimmerter Notbehelf. Darüber werde ich ebenfalls berichten.
Über Unicode und UTF-8
Zuerst ein paar Worte darüber, was Unicode und UTF-8.
Wie bekannt ist, waren früher 8-Bit-Codierungen beliebt. Mit ihnen war alles einfach: 256 Zeichen lassen sich durch die Zahlen von 0 bis 255 nummerieren, und die Zahlen von 0 bis 255 lassen sich offensichtlich in einem Byte darstellen. Wenn wir zu den Wurzeln zurückkehren, wird die ASCII-Codierung sogar auf 7 Bits beschränkt, sodass das höchstwertige Bit in ihrer Byte-Darstellung null ist und die meisten 8-Bit-Codierungen mit ihr kompatibel sind (sie unterscheiden sich nur im „oberen“ Bereich, wo das höchstwertige Bit eins ist).
Wie unterscheidet sich Unicode von den anderen Kodierungen und warum sind damit sofort viele spezifische Darstellungen verbunden – UTF-8, UTF-16 (BE und LE), UTF-32? Lassen Sie uns der Reihe nach klären.
Der Hauptstandard von Unicode beschreibt nur die Entsprechung zwischen Zeichen (und in einigen Fällen – einzelnen Komponenten von Zeichen) und ihren Nummern. Und die möglichen Nummern in diesem Standard sind sehr zahlreich – von 0x00 bis 0x10FFFF (1 114 112 Stück). Wenn wir eine Zahl in diesem Bereich einer Variablen zuweisen wollten, würden uns weder 1 noch 2 Bytes ausreichen. Und da unsere Prozessoren für die Arbeit mit dreibyteigen Zahlen nicht ausgelegt sind, wären wir gezwungen, ganze 4 Bytes für ein Zeichen zu verwenden! Das ist UTF-32, aber gerade wegen dieser „Verschwendung“ erfreut sich dieses Format nicht großer Beliebtheit.
Glücklicherweise sind die Zeichen in Unicode nicht zufällig angeordnet. Ihre Menge ist in 17 „Ebenen“ unterteilt, von denen jede 65536 („0x10000) «Codepunkte“ enthält. Der Begriff „Codepunkt“ bedeutet hier einfach die Nummer eines Zeichens, die ihm von Unicode zugewiesen wurde. Aber, wie bereits erwähnt, sind in Unicode nicht nur einzelne Zeichen durchnummeriert, sondern auch deren Komponenten und Steuerzeichen (und manchmal entspricht dem Nummer gar nichts – möglicherweise nur vorübergehend, aber das ist für uns nicht so wichtig), daher ist es genauer, immer von der Anzahl der Nummern und nicht von den Zeichen zu sprechen. Um der Kürze willen werde ich jedoch im Folgenden häufig das Wort „Zeichen“ verwenden, wobei ich den Begriff „Codepunkt“ meine.
Ebenen von Unicode. Wie zu sehen ist, ist der größte Teil (die Ebenen von 4 bis 13) noch ungenutzt.
Das Bemerkenswerteste ist, dass der gesamte wesentliche „Kern“ in der nullten Ebene liegt, die "Basic Multilingual Plane" genannt wird. Wenn eine Zeile Text in einer der modernen Sprachen (einschließlich Chinesisch) enthält, werden Sie diese Ebene nicht verlassen. Aber man kann auch den Rest von Unicode nicht abschneiden – zum Beispiel befinden sich Emojis hauptsächlich am Ende der nächstfolgenden Ebene, „Supplementary Multilingual Plane" (sie erstreckt sich von 0x10000 bis 0x1FFFF). Daher funktioniert UTF-16 so: Alle Zeichen, die in Basic Multilingual Plane, werden „wie sie sind“ kodiert, mit der entsprechenden zweibyte-Zahl. Einige Zahlen in diesem Bereich stellen jedoch überhaupt keine konkreten Symbole dar, sondern weisen darauf hin, dass nach diesem Byte-Paar ein weiteres betrachtet werden muss – kombiniert man die Werte dieser vier Bytes, ergibt sich eine Zahl, die den gesamten zulässigen Unicode-Bereich abdeckt. Diese Darstellung wird „Surrogatpaare“ genannt – vielleicht haben Sie schon darüber gehört.
Somit benötigt UTF-16 zwei oder (in sehr seltenen Fällen) vier Bytes für einen „Codepunkt“. Das ist besser, als ständig vier Bytes zu verwenden, aber die lateinischen Buchstaben (und andere ASCII-Symbole) verbrauchen bei dieser Kodierung die Hälfte des benötigten Raums für Nullen. UTF-8 soll das verbessern: In ihm belegt ASCII wie früher nur ein Byte; die Codes von 0x80 bis 0x7FF – zwei Bytes; von 0x800 bis 0xFFFF – drei, und von 0x10000 bis 0x10FFFF – vier. Einerseits hat es sich für das Lateinische gut entwickelt: Die Kompatibilität mit ASCII ist zurückgekehrt, und die Verteilung ist gleichmäßiger „verteilt“ von 1 bis 4 Bytes. Aber Alphabete, die vom Lateinischen abweichen, haben leider keinen Vorteil im Vergleich zu UTF-16, und viele benötigen nun sogar drei Bytes anstelle von zwei – der von der zweibyte-Darstellung abgedeckte Bereich hat sich um das 32-Fache verkleinert, von 0xFFFF bis 0x7FF, und umfasst jetzt weder das Chinesische noch beispielsweise das Georgische. Das Kyrillische sowie fünf weitere Alphabete – hurrah – haben Glück gehabt, 2 Bytes pro Zeichen.
Wie kommt das zustande? Lassen Sie uns ansehen, wie UTF-8 die Codes der Zeichen darstellt:
Direkt zur Darstellung der Zahlen werden hier die Bits verwendet, die durch das Zeichen xgekennzeichnet sind. Es ist zu erkennen, dass in der zweibyte-Darstellung nur 11 dieser Bits (von 16) vorhanden sind. Die führenden Bits haben hier nur eine Dienstfunktion. Im Fall der vierbyte-Darstellung sind ganze 21 Bits aus 32 für die Codierungspunkte reserviert – hier hätten eigentlich auch drei Bytes (die insgesamt 24 Bits ergeben) ausgereicht, aber die Dienstmarker verbrauchen zu viel.
Ist das schlecht? Eigentlich nicht. Einerseits — wenn wir großen Wert auf den benötigten Speicherplatz legen, haben wir Komprimierungsalgorithmen, die leicht alle überflüssige Entropie und Redundanz beseitigen können. Andererseits war das Ziel von Unicode, eine möglichst universelle Kodierung bereitzustellen. Zum Beispiel können wir eine in UTF-8 kodierte Zeichenkette einem Code anvertrauen, der zuvor nur mit ASCII gearbeitet hat, und wir brauchen uns keine Sorgen zu machen, dass er ein Zeichen aus dem ASCII-Bereich sieht, das dort eigentlich nicht vorhanden ist (denn in UTF-8 sind alle Bytes, die mit dem Nullbit beginnen, genau ASCII). Und wenn wir plötzlich ein kleines Ende von einer großen Zeichenkette abschneiden wollen, ohne sie von Anfang an zu dekodieren (oder einen Teil der Information nach einem beschädigten Abschnitt wiederherzustellen) — ist es nicht schwierig, die Verschiebung zu finden, an der ein Zeichen beginnt (es reicht aus, Bytes mit einem bitweisen Präfix zu überspringen. 10).
Warum also etwas Neues erfinden?
Gleichzeitig gibt es gelegentlich Situationen, in denen Komprimierungsalgorithmen wie deflate schlecht anwendbar sind und man möchte eine kompakte Speicherung von Zeichenketten erreichen. Ich persönlich bin auf ein solches Problem gestoßen, als ich über den Aufbau nachdachte für ein großes Wörterbuch, das Wörter in beliebigen Sprachen umfasst. Einerseits — jedes Wort ist sehr kurz, daher wäre es ineffektiv, es zu komprimieren. Andererseits — die Baumimplementierung, die ich in Betracht zog, war darauf ausgelegt, dass jedes Byte der gespeicherten Zeichenkette eine separate Baumspitze erzeugt, sodass es sehr nützlich war, ihre Anzahl zu minimieren. In meiner Bibliothek (wie auch in , auf dem sie basiert) wird ein solches Problem einfach gelöst — die in -Wörterbuch verpackten Zeichenketten werden dort in gespeichert. Aber wie man leicht verstehen kann, funktioniert das gut nur für ein begrenztes Alphabet — eine Zeichenkette auf Chinesisch kann in ein solches Wörterbuch nicht eingegeben werden.
Ich möchte auch einen weiteren unangenehmen Punkt erwähnen, der beim Einsatz von UTF-8 in einer solchen Datenstruktur auftritt. Auf dem obigen Bild ist zu sehen, dass beim Schreiben eines Zeichens in Form von zwei Bytes die Bits, die zu seiner Nummer gehören, nicht aufeinander folgen, sondern durch ein paar Bits 10 dazwischen unterbrochen sind: 110xxxxx 10xxxxxx. Deshalb, wenn die unteren 6 Bits des zweiten Bytes (d.h. ein Überlauf auftritt, 10111111 → 10000000) überlaufen, ändert sich auch das erste Byte. Es stellt sich heraus, dass der Buchstabe „п“ durch Bytes dargestellt wird. 0xD0 0xBF, und der folgende „r“ — ist bereits 0xD1 0x80. Im Präfixbaum führt dies zur Teilung des Elternknotens in zwei — eine für das Präfix 0xD0, und eine andere für 0xD1 (obwohl das gesamte Kyrillisch nur im zweiten Byte kodiert werden könnte).
Was ich erreicht habe
Mit dieser Aufgabe konfrontiert, beschloss ich, ein wenig mit Bits zu üben und mich gleichzeitig besser mit der Struktur von Unicode vertraut zu machen. Das Ergebnis war das Kodierungsformat UTF-C („C“ steht für compact), das nicht mehr als 3 Byte für einen Codepunkt verwendet und sehr oft nur ein zusätzliches Byte für die gesamte kodierte Zeile. Dies führt dazu, dass dieses Kodierungsverfahren in vielen nicht-ASCII-Alphabets 30-60% kompakter ist als UTF-8.
Ich habe Beispiele zur Implementierung der Kodierungs- und Dekodierungsalgorithmen in Form von , die Sie frei in Ihrem Code verwenden können. Aber ich möchte dennoch betonen, dass dieses Format in gewisser Hinsicht ein „Fahrrad“ bleibt, und ich empfehle nicht, es zu verwenden , ohne zu verstehen, wofür Sie es benötigen. Es handelt sich schließlich mehr um ein Experiment als um eine ernsthafte „Verbesserung von UTF-8“. Dennoch ist der Code dort sauber, prägnant, mit vielen Kommentaren und Tests abgedeckt.
Ergebnisse der Testausführung und Vergleich mit UTF-8
Ich habe auch , auf der die Funktionsweise des Algorithmus bewertet werden kann, und danach werde ich genauer auf seine Prinzipien und den Entwicklungsprozess eingehen.
Überflüssige Bits beseitigen
Als Grundlage habe ich natürlich UTF-8 genommen. Das erste und offensichtlichste, was man darin ändern kann, ist die Anzahl der Steuerbits in jedem Byte zu reduzieren. Zum Beispiel beginnt das erste Byte in UTF-8 immer entweder mit 0, oder mit 11 — und das Präfix 10 gibt es nur bei den folgenden Bytes. Lassen Sie uns das Präfix ersetzen 11 auf 1, und bei den folgenden Bytes entfernen wir die Präfixe ganz. Was kommt heraus?
0xxxxxxx — 1 Byte
10xxxxxx xxxxxxxx — 2 Bytes
110xxxxx xxxxxxxx xxxxxxxx — 3 Bytes
Stopp, und wo ist die vier-Byte-Darstellung geblieben? Diese ist nicht mehr notwendig — bei der Verwendung von drei Bytes haben wir jetzt 21 Bit zur Verfügung, und das reicht für alle Zahlen bis 0x10FFFF.
Wofür haben wir hier bezahlt? Das Wichtigste — die Erkennung der Grenzwerte von Zeichen an beliebiger Stelle im Puffer. Wir können nicht auf ein beliebiges Byte zeigen und von dort den Beginn des nächsten Zeichens finden. Das ist eine Einschränkung unseres Formats, aber in der Praxis tritt diese Notwendigkeit nicht häufig auf. Normalerweise sind wir in der Lage, den Puffer von Anfang an zu durchlaufen (insbesondere wenn es um kurze Zeilen geht).
Die Situation mit der Abdeckung von Sprachen mit 2 Byte hat sich ebenfalls verbessert: Jetzt bietet das zweibyte Format einen Bereich von 14 Bit, was Codes bis 0x3FFF. Die Chinesen haben Pech (ihre Schriftzeichen liegen hauptsächlich im Bereich von 0x4E00 bis 0x9FFF), aber den Georgiern und vielen anderen Völkern geht es fröhlicher — ihre Sprachen passen ebenfalls in 2 Byte pro Zeichen.
Wir aktivieren den Encoder.
Lass uns jetzt über die Eigenschaften der Zeichenfolgen selbst nachdenken. Im Wörterbuch befinden sich meistens Wörter, die mit Zeichen eines Alphabets geschrieben sind, und das gilt auch für viele andere Texte. Es wäre gut, dieses Alphabet einmal festzulegen und dann nur noch die Nummer des Buchstabens darin anzugeben. Schauen wir, ob uns die Anordnung der Zeichen in der Unicode-Tabelle dabei helfen kann.
Wie bereits erwähnt, ist Unicode in Ebenen unterteilt, die jeweils 65536 Codes haben. Aber diese Unterteilung ist nicht besonders nützlich (wie bereits gesagt, befinden wir uns meistens in der nullten Ebene). Interessanter ist die Unterteilung in Blöcke. Diese Bereiche haben bereits keine feste Länge mehr und sind bedeutungsvoller — in der Regel vereint jeder von ihnen Zeichen eines Alphabets.
Block, der Zeichen des bengalischen Alphabets enthält. Leider ist dies aus historischen Gründen ein Beispiel für eine nicht sehr dichte Verpackung — 96 Zeichen sind über 128 Codepunkte des Blocks verstreut.
Die Anfangswerte der Blöcke und deren Größen sind immer Vielfache von 16 — dies wurde einfach der Praktikabilität halber gemacht. Zudem beginnen viele Blöcke bei Werten, die Vielfache von 128 oder sogar 256 sind — zum Beispiel belegt das Grundmodul der kyrillischen Schrift 256 Byte ab 0x0400 bis 0x04FF. Das ist ziemlich praktisch: Wenn wir einmal das Präfix 0x04gespeichert haben, kann jedes kyrillische Zeichen mit einem Byte codiert werden. Allerdings verlieren wir dadurch die Möglichkeit, zu ASCII (und zu allen anderen Zeichen überhaupt) zurückzukehren. Daher machen wir Folgendes:
- Zwei Byte
10yyyyyy yxxxxxxxbezeichnen nicht nur ein Zeichen mit der Nummeryyyyyy yxxxxxxx, sondern ändern auch das aktuelle Alphabet aufyyyyyy y0000000(d.h. wir merken uns alle Bits außer den niederwertigsten 7 Bit.); - Ein Byte
0xxxxxxxstellt ein Zeichen des aktuellen Alphabets dar. Dieses muss einfach mit dem Versatz addiert werden, den wir in Schritt 1 gespeichert haben. Solange wir das Alphabet nicht geändert haben, beträgt der Versatz null, sodass wir die Kompatibilität mit ASCII beibehalten haben.
Analog für Codes, die 3 Byte benötigen:
- Drei Byte
110yyyyy yxxxxxxx xxxxxxxxbezeichnen ein Zeichen mit der Nummeryyyyyy yxxxxxxx xxxxxxxx, ändern das aktuelle Alphabet aufyyyyyy y0000000 00000000(wir merken uns alles, außer den niederwertigsten 15 Bit), und setzen ein Flag, dass wir uns jetzt in der langen Im Modus (bei der Rückwechsel zum zwei Byte-Code setzen wir dieses Flag zurück); - Zwei Byte
0xxxxxxx xxxxxxxxIm langen Modus ist dies das Zeichen des aktuellen Alphabets. Analog dazu addieren wir es mit der Verschiebung aus Schritt 1. Der einzige Unterschied besteht darin, dass wir jetzt zwei Bytes lesen (da wir in diesen Modus gewechselt sind).
Klingt gut: Solange wir Zeichen aus dem gleichen 7-Bit-Bereich des Unicode codieren müssen, verwenden wir 1 zusätzliches Byte am Anfang und nur ein Byte für jedes Zeichen.
Arbeit einer der frühen Versionen. Überholt bereits häufig UTF-8, hat aber noch Verbesserungsbedarf.
Was hat sich verschlechtert? Erstens haben wir jetzt einen Zustand, nämlich die Verschiebung des aktuellen Alphabets und das Flag des langen Modus. Dies schränkt uns zusätzlich ein: Jetzt können dieselben Zeichen in verschiedenen Kontexten unterschiedlich kodiert werden. Beispielsweise muss die Suche nach Teilstrings bereits unter Berücksichtigung dessen erfolgen und nicht nur durch Byte-Vergleich. Zweitens, sobald wir das Alphabet gewechselt haben, wird die Kodierung von ASCII-Zeichen schlecht (und das umfasst nicht nur das Lateinische, sondern auch die grundlegende Zeichensetzung, einschließlich Leerzeichen) — sie erfordert einen weiteren Wechsel des Alphabets zu 0, also wieder ein zusätzliches Byte (und dann noch eines, um zu unserem Hauptalphabet zurückzukehren).
Ein Alphabet ist gut, zwei sind besser
Lassen Sie uns etwas mit unseren Bit-Präfixen ändern, indem wir noch eins zu den drei oben beschriebenen hinzufügen:
0xxxxxxx — 1 Byte im normalen Modus, 2 im langen
11xxxxxx — 1 Byte
100xxxxx xxxxxxxx — 2 Bytes
101xxxxx xxxxxxxx xxxxxxxx — 3 Bytes
Nun hat es in der Zwei-Byte-Darstellung ein verfügbares Bit weniger — es passen Codepunkte bis zu 0x1FFF, nicht 0x3FFF. Dennoch ist es immer noch deutlich mehr als in den zwei Byte-Codes von UTF-8, die meisten verbreiteten Sprachen passen immer noch hinein, der auffälligste Verlust — ist weggefallen und , die Japaner sind traurig.
Was ist also der neue Code 11xxxxxx? Это небольшой «загашник» размером в 64 символа, он дополняет наш основной алфавит, поэтому я назвал его вспомогательным (auxiliary) Alphabet. Wenn wir das aktuelle Alphabet wechseln, wird ein Teil des alten Alphabets zum Hilfsalphabet. Zum Beispiel, wenn wir von ASCII zu Kyrillisch wechseln — nun sind im „Vorrat“ 64 Zeichen enthalten, die Latein, Ziffern, Leerzeichen und Komma die häufigsten Einfügungen in nicht-ASCII-Texten sind. Gehen wir zurück zu ASCII — wird der Hauptteil des Kyrillischen zum Hilfsalphabet.
Durch den Zugang zu zwei Alphabeten können wir mit einer großen Menge von Texten umgehen, ohne die Kosten für das Umschalten der Alphabete zu erhöhen (Interpunktion führt meist dazu, dass wir wieder in ASCII zurückkehren, aber danach können wir viele nicht-ASCII-Zeichen bereits aus dem zusätzlichen Alphabet beziehen, ohne erneut umzuschalten).
Bonus: Den Zusatzalphabet mit einem Präfix kennzeichnen 11xxxxxx und seinen Anfangsversatz gleich 0xC0, erhalten wir eine teilweise Kompatibilität mit CP1252. Mit anderen Worten, viele (aber nicht alle) westeuropäischen Texte, die in CP1252 kodiert sind, werden auch in UTF-C gleich aussehen.
Hier entsteht jedoch ein Problem: Wie erhält man das Hilfsalphabet aus dem Hauptalphabet? Man könnte den gleichen Versatz beibehalten, aber leider spielt hier die Struktur von Unicode schon gegen uns. Sehr oft befindet sich der Hauptteil des Alphabets nicht am Anfang des Blocks (zum Beispiel hat der russische Großbuchstabe „А“ den Code 0x0410, während der kyrillische Block bei 0x0400beginnt). Daher könnte es sein, dass wir beim Auswählen der ersten 64 Zeichen möglicherweise den Zugang zum hinteren Teil des Alphabets verlieren.
Um dieses Problem zu lösen, habe ich manuell einige Blöcke durchlaufen, die verschiedenen Sprachen entsprechen, und für sie den Versatz des Hilfsalphabets innerhalb des Hauptalphabets angegeben. Die Lateinbuchstaben habe ich ausnahmsweise in einer Weise umsortiert, die ähnlich wie base64 ist.
Letzte Schliffe
Lass uns abschließend überlegen, wo wir noch etwas verbessern können.
Wir stellen fest, dass das Format 101xxxxx xxxxxxxx xxxxxxxx es ermöglicht, Zahlen bis zu 0x1FFFFF, und Unicode endet früher, bei 0x10FFFF. Mit anderen Worten, der letzte Codepunkt wird als 10110000 11111111 11111111dargestellt. Daher können wir sagen, dass, wenn das erste Byte wie folgt aussieht 1011xxxx (wo xxxx größer als 0 ist), es etwas anderes bedeutet. Zum Beispiel könnte man dort noch 15 Zeichen hinzufügen, die ständig mit einem Byte kodiert werden können, aber ich habe mich entschieden, es anders zu handhaben.
Schauen wir uns nun die Unicode-Blöcke an, die derzeit drei Bytes benötigen. Im Allgemeinen sind das, wie bereits erwähnt, chinesische Schriftzeichen — aber damit ist es schwierig, etwas zu machen, es sind 21.000. Aber auch Hiragana und Katakana sind dort gelandet — und von denen gibt es schon weniger, weniger als zweihundert. Und da wir gerade die Japaner erwähnt haben — dort liegen auch Emojis (tatsächlich sind sie überall in Unicode verstreut, aber die Hauptblöcke befinden sich im Bereich 0x1F300 – 0x1FBFF). Wenn man bedenkt, dass es jetzt Emojis gibt, die aus mehreren Codepunkten bestehen (zum Beispiel Emoji besteht aus 7 Codes!), dann ist es wirklich schade, für jeden drei Byte zu verschwenden (7×3 = 21 Byte für ein Zeichen, das ist ein Albtraum).
Deshalb wählen wir einige ausgewählte Bereiche aus, die Emojis, Hiragana und Katakana entsprechen, nummerieren sie in einer fortlaufenden Liste um und kodieren sie in zwei Byte statt drei:
1011xxxx xxxxxxxx
Gut: Das oben genannte Emoji , das aus 7 Codepunkten besteht, benötigt in UTF-8 25 Byte, und wir haben es in 14 untergebracht (genau zwei Byte für jeden Codepunkt). Übrigens hat Habr sich geweigert, es zu verarbeiten (weder im alten noch im neuen Editor), daher mussten wir es als Bild einfügen.
Versuchen wir, ein weiteres Problem zu beheben. Wie wir uns erinnern, ist das Hauptalphabet im Grunde genommen die oberen 6 Bits, die wir im Kopf behalten und an den Code jedes weiteren zu dekodierenden Zeichens anhängen. Bei den chinesischen Schriftzeichen, die sich im Block 0x4E00 – 0x9FFF, ist es entweder Bit 0 oder 1. Das ist nicht sehr praktisch: Wir müssen das Alphabet ständig zwischen diesen beiden Werten wechseln (d.h. drei Byte verbrauchen). Aber wir stellen fest, dass wir im langen Modus von dem Code die Anzahl der Zeichen abziehen können, die wir im kurzen Modus kodieren (nach all den oben beschriebenen Tricks sind das 10240) — dann verschiebt sich der Bereich der Schriftzeichen zu 0x2600 – 0x77FF, und in diesem Fall werden in diesem gesamten Bereich die oberen 6 Bits (von 21) gleich 0 sein. Somit werden die Sequenzen der Schriftzeichen je zwei Byte pro Zeichen verwenden (was optimal für so einen großen Bereich ist), ohne dass ein Wechsel des Alphabets erforderlich ist.
Alternative Lösungen: SCSU, BOCU-1
Kenner von Unicode werden wahrscheinlich, noch bevor sie den Titel des Artikels gelesen haben, hastig daran erinnern, dass es unter den Unicode-Standards (SCSU) gibt, das einen Kodierungsansatz beschreibt, der dem in diesem Artikel beschriebenen sehr ähnlich ist.
Ich gestehe ehrlich: Von seiner Existenz habe ich erst erfahren, als ich bereits tief in das Schreiben meiner Lösung eingetaucht war. Wüsste ich von ihm gleich zu Beginn, hätte ich wahrscheinlich versucht, seine Implementierung statt meiner eigenen Herangehensweise zu schreiben.
Interessanterweise verwendet SCSU Ideen, die sehr ähnlich sind denjenigen, zu denen ich selbst gekommen bin (anstatt des Begriffs „Alphabete“ werden dort „Fenster“ verwendet, und es sind mehr verfügbar als bei mir). Gleichzeitig hat dieses Format auch Nachteile: Es ist etwas näher an Komprimierungsalgorithmen als an Kodierung. Insbesondere bietet der Standard viele Darstellungsformen, sagt aber nicht, wie man die optimale auswählt – hierzu muss der Encoder einige Heuristiken anwenden. Somit wird der SCSU-Encoder, der eine gute Packung bietet, komplexer und umständlicher sein als mein Algorithmus.
Zum Vergleich habe ich eine relativ einfache Implementierung von SCSU in JavaScript portiert – in Bezug auf den Codeumfang war sie vergleichbar mit meinem UTF-C, zeigte aber in einigen Fällen Ergebnisse, die um mehrere Prozentsätze schlechter waren (manchmal kann sie auch etwas besser sein, aber nicht viel). Zum Beispiel kodierte UTF-C Texte in Hebräisch und Griechisch um 60 % besser als SCSU (wahrscheinlich wegen ihrer kompakten Alphabete).
Ich möchte zusätzlich erwähnen, dass es neben SCSU auch eine andere Möglichkeit zur kompakten Darstellung von Unicode gibt – , aber sie zielt auf die Kompatibilität mit MIME ab (was ich nicht benötigte) und verwendet einen etwas anderen Ansatz zur Kodierung. Ich habe ihre Effizienz nicht bewertet, aber ich glaube nicht, dass sie höher sein wird als die von SCSU.
Mögliche Verbesserungen
Mein Algorithmus ist von Natur aus nicht universell (in dieser Hinsicht weichen meine Ziele wahrscheinlich am stärksten von den Zielen des Unicode-Konsortiums ab). Ich habe bereits erwähnt, dass er hauptsächlich für eine Aufgabe entwickelt wurde (Speicherung eines mehrsprachigen Wörterbuchs in einem Präfixbaum), und einige seiner Eigenschaften könnten für andere Aufgaben weniger geeignet sein. Aber die Tatsache, dass er kein Standard ist, könnte auch ein Vorteil sein – Sie können ihn leicht an Ihre Bedürfnisse anpassen.
Zum Beispiel kann man offensichtlich den Zustand eliminieren und die Kodierung statuslos machen – einfach die Variablen im Encoder und Decoder nicht aktualisieren. In diesem Fall wird es nicht möglich sein, Folgen von Zeichen eines Alphabets effizient zu verpacken, dafür gibt es jedoch die Garantie, dass dasselbe Zeichen immer mit denselben Bytes kodiert wird, unabhängig vom Kontext. Abgänge, auxOffs und is21Bit Darüber hinaus kann man den Encoder auf eine bestimmte Sprache zuschneiden, indem man den Standardzustand ändert – zum Beispiel, orientiert an russischen Texten, den Anfang des Encoders und Decoders entsprechend einstellen.
Darüber hinaus kann der Encoder für eine bestimmte Sprache angepasst werden, indem der Standardstatus geändert wird – zum Beispiel kann man, orientiert an russischen Texten, zu Beginn des Encoders und Decoders eine entsprechende Einstellung vornehmen. offs = 0x0400 und auxOffs = 0. Dies macht insbesondere im stateless Modus Sinn. Im Großen und Ganzen wird es der Verwendung des alten achtbitigen Codes ähnlich sein, nur dass es nicht die Möglichkeit ausschließt, nach Bedarf Zeichen aus dem gesamten Unicode einzufügen.
Ein weiterer Nachteil, den ich zuvor erwähnt habe – im umfangreichen Text, der in UTF-C codiert ist, gibt es keinen schnellen Weg, um die Grenze des Zeichens zu finden, das dem beliebigen Byte am nächsten ist. Wenn Sie die letzten, sagen wir, 100 Bytes vom codierten Puffer abschneiden, riskieren Sie, Müll zu erhalten, mit dem Sie nichts anfangen können. Die Kodierung ist nicht für die Speicherung von mehreren Gigabyte an Logs ausgelegt, aber grundsätzlich kann das behoben werden. Byte 0xBF sollte niemals als erstes Byte auftreten (kann jedoch als zweites oder drittes auftreten). Daher kann bei der Codierung eine Sequenz eingefügt werden 0xBF 0xBF 0xBF alle, sagen wir, 10 KB – dann reicht es, den gewünschten Abschnitt zu scannen, um einen ähnlichen Marker zu finden, wenn nötig. Nach dem letzten 0xBF wird garantiert der Anfang eines Zeichens folgen. (Beim Dekodieren muss diese Sequenz von drei Bytes selbstverständlich ignoriert werden.)
Zusammenfassend
Wenn Sie bis hierher gelesen haben – herzlichen Glückwunsch! Ich hoffe, Sie haben wie ich etwas Neues gelernt (oder Altes aufgefrischt) über die Funktionsweise von Unicode.
Demonstrationsseite. Am Beispiel von Hebräisch sind die Vorteile sowohl gegenüber UTF-8 als auch gegenüber SCSU sichtbar.
Man sollte die oben beschriebenen Überlegungen nicht als Angriff auf die Standards betrachten. Allerdings bin ich insgesamt mit den Ergebnissen meiner Arbeiten zufrieden, deshalb freue ich mich, sie : zum Beispiel wiegt die JS-Bibliothek in minimierter Form nur 1710 Bytes (und hat natürlich keine Abhängigkeiten). Wie ich oben erwähnt habe, kann man sich mit ihrer Funktionalität auf der vertraut machen (dort gibt es auch eine Reihe von Texten, mit denen man sie mit UTF-8 und SCSU vergleichen kann).
Zum Schluss möchte ich noch einmal auf die Fälle hinweisen, in denen die Verwendung von UTF-C nicht ratsam ist:
- Wenn Ihre Zeichenfolgen lang genug sind (ab 100-200 Zeichen). In diesem Fall sollte man über die Anwendung von Komprimierungsalgorithmen wie Deflate nachdenken.
- Wenn Sie eine ASCII-Transparenz benötigen, das heißt, es ist Ihnen wichtig, dass in den kodierten Sequenzen keine ASCII-Codes auftreten, die nicht im ursprünglichen String waren. Diese Anforderungen können vermieden werden, wenn Sie bei der Interaktion mit externen APIs (zum Beispiel bei der Arbeit mit Datenbanken) das Ergebnis der Kodierung als abstrakte Bytefolge und nicht als Strings übergeben. Andernfalls laufen Sie Gefahr, unvorhergesehene Schwachstellen zu erhalten.
- Wenn Sie die Möglichkeit haben möchten, die Grenzen von Zeichen nach beliebiger Verschiebung schnell zu finden (z.B. bei einer Beschädigung eines Teils des Strings). Dies ist möglich, jedoch nur, wenn Sie den String vom Anfang her scannen (oder eine Modifikation anwenden, die im vorherigen Abschnitt beschrieben wurde).
- Wenn Sie schnell Operationen mit den Inhalten von Strings durchführen müssen (sie sortieren, Substrings darin suchen, verketten). Dafür müssen die Strings zuerst dekodiert werden, weshalb UTF-C in diesen Fällen langsamer als UTF-8 ist (aber schneller als Komprimierungsalgorithmen). Da derselbe String immer gleich kodiert wird, erfordert der genaue Vergleich der Dekodierung kein Abgleich, dieser kann byteweise erfolgen.
Update: Nutzer habe ich ein Diagramm veröffentlicht, das die Anwendbarkeitsgrenze von UTF-C hervorhebt. Darauf ist zu sehen, dass UTF-C effizienter als allgemeine Komprimierungsalgorithmen (Variationen von LZW) ist, solange der zu packende String kürzer ist ~140 Zeichen (ich möchte anmerken, dass der Vergleich mit einem Text durchgeführt wurde; für andere Sprachen kann das Ergebnis abweichen).
Quelle: habr.com
