Noch ein Bike: Wir speichern Unicode-Strings 30-60 % kompakter als UTF-8

Wenn Sie als Entwickler vor der Aufgabe stehen, eine Kodierung auszuwählen, ist Unicode fast immer die richtige Lösung. Die konkrete Darstellungsmethode hängt vom Kontext ab, aber meistens gibt es auch hier eine universelle Antwort – UTF-8. Das Gute daran ist, dass Sie damit alle Unicode-Zeichen ohne Kosten verwenden können zu viel In den meisten Fällen viele Bytes. Stimmt, für Sprachen, die mehr als nur das lateinische Alphabet verwenden, ist „nicht zu viel“ zumindest der Fall zwei Bytes pro Zeichen. Können wir es besser machen, ohne zu prähistorischen Kodierungen zurückzukehren, die uns auf nur 256 verfügbare Zeichen beschränken?

Im Folgenden schlage ich vor, Sie mit meinem Versuch vertraut zu machen, diese Frage zu beantworten und einen relativ einfachen Algorithmus zu implementieren, der es Ihnen ermöglicht, Zeilen in den meisten Sprachen der Welt zu speichern, ohne die Redundanz von UTF-8 hinzuzufügen.

Haftungsausschluss. Ich werde gleich ein paar wichtige Vorbehalte machen: Die beschriebene Lösung wird nicht als universeller Ersatz für UTF-8 angeboten, ist es nur in einer engen Liste von Fällen geeignet (mehr dazu weiter unten) und sollte auf keinen Fall für die Interaktion mit APIs von Drittanbietern verwendet werden (die nicht einmal davon wissen). Am häufigsten eignen sich allgemeine Komprimierungsalgorithmen (z. B. Deflate) für die kompakte Speicherung großer Textdatenmengen. Darüber hinaus habe ich bereits bei der Erstellung meiner Lösung einen vorhandenen Standard in Unicode selbst gefunden, der das gleiche Problem löst – er ist etwas komplizierter (und oft schlimmer), aber dennoch ein akzeptierter Standard und nicht einfach ausgedrückt zusammen auf dem Knie. Ich werde dir auch von ihm erzählen.

Über Unicode und UTF-8

Zunächst ein paar Worte darüber, was es ist Unicode и UTF-8.

Wie Sie wissen, waren früher 8-Bit-Kodierungen beliebt. Bei ihnen war alles einfach: 256 Zeichen können mit Zahlen von 0 bis 255 nummeriert werden, und Zahlen von 0 bis 255 lassen sich natürlich als ein Byte darstellen. Wenn wir zum Anfang zurückkehren, ist die ASCII-Kodierung vollständig auf 7 Bits beschränkt, sodass das höchstwertige Bit in ihrer Byte-Darstellung Null ist und die meisten 8-Bit-Kodierungen damit kompatibel sind (sie unterscheiden sich nur im „oberen“ Bit). Teil, wobei das höchstwertige Bit eins ist).

Wie unterscheidet sich Unicode von diesen Codierungen und warum sind damit so viele spezifische Darstellungen verbunden – UTF-8, UTF-16 (BE und LE), UTF-32? Lasst es uns der Reihe nach klären.

Der grundlegende Unicode-Standard beschreibt nur die Entsprechung zwischen Zeichen (und in einigen Fällen einzelnen Zeichenbestandteilen) und ihren Zahlen. Und es gibt viele mögliche Zahlen in diesem Standard – von 0x00 auf 0x10FFFF (1 Stück). Wenn wir eine Zahl in einem solchen Bereich in eine Variable einfügen wollten, würden uns weder 114 noch 112 Bytes ausreichen. Und da unsere Prozessoren nicht besonders für die Arbeit mit Drei-Byte-Zahlen ausgelegt sind, wären wir gezwungen, bis zu 1 Bytes pro Zeichen zu verwenden! Das ist UTF-2, aber gerade wegen dieser „Verschwendung“ ist dieses Format nicht beliebt.

Glücklicherweise ist die Reihenfolge der Zeichen in Unicode nicht zufällig. Ihr gesamtes Set ist in 17" unterteilt.Flugzeuge", die jeweils 65536 (0x10000) "Codepunkte" Das Konzept eines „Codepunkts“ ist hier einfach Zeichennummer, ihm von Unicode zugewiesen. Aber wie oben erwähnt, werden in Unicode nicht nur einzelne Zeichen nummeriert, sondern auch deren Bestandteile und Dienstleistungszeichen (und manchmal entspricht überhaupt nichts der Nummer – vielleicht vorerst, aber für uns ist das nicht so wichtig), also Es ist richtiger, immer konkret über die Anzahl der Zahlen selbst zu sprechen und nicht über Symbole. Der Kürze halber werde ich im Folgenden jedoch häufig das Wort „Symbol“ verwenden, was den Begriff „Codepunkt“ impliziert.

Unicode-Flugzeuge. Wie Sie sehen, ist der Großteil davon (Flugzeuge 4 bis 13) noch ungenutzt.

Das Bemerkenswerteste ist, dass der gesamte Haupt-„Zellstoff“ in der Nullebene liegt, man nennt ihn „Grundlegende mehrsprachige Ebene". Wenn eine Zeile Text in einer der modernen Sprachen (einschließlich Chinesisch) enthält, kommen Sie nicht über diese Ebene hinaus. Sie können aber auch den Rest von Unicode nicht abschneiden – Emojis befinden sich beispielsweise hauptsächlich am Ende von das nächste Flugzeug“,Zusätzliche mehrsprachige Ebene"(es erstreckt sich von 0x10000 auf 0x1FFFF). UTF-16 macht also Folgendes: alle Zeichen fallen darunter Grundlegende mehrsprachige Ebenewerden „wie sie sind“ mit einer entsprechenden Zwei-Byte-Zahl codiert. Einige der Zahlen in diesem Bereich geben jedoch überhaupt keine bestimmten Zeichen an, sondern weisen darauf hin, dass wir nach diesem Bytepaar ein weiteres in Betracht ziehen müssen – indem wir die Werte dieser vier Bytes miteinander kombinieren, erhalten wir eine abdeckende Zahl den gesamten gültigen Unicode-Bereich. Diese Idee wird „Ersatzpaare“ genannt – Sie haben vielleicht schon davon gehört.

UTF-16 benötigt also zwei oder (in sehr seltenen Fällen) vier Bytes pro „Codepunkt“. Das ist besser als die ständige Verwendung von vier Bytes, aber lateinische Zeichen (und andere ASCII-Zeichen) verschwenden bei dieser Codierung die Hälfte des Platzes durch Nullen. UTF-8 soll dies beheben: ASCII belegt darin nach wie vor nur ein Byte; Codes von 0x80 auf 0x7FF - zwei Bytes; aus 0x800 auf 0xFFFF - drei, und von 0x10000 auf 0x10FFFF - vier. Einerseits ist das lateinische Alphabet gut geworden: Die Kompatibilität mit ASCII ist zurückgekehrt und die Verteilung ist gleichmäßiger von 1 auf 4 Bytes „verteilt“. Aber andere Alphabete als Latein haben im Vergleich zu UTF-16 leider keinen Vorteil, und viele erfordern jetzt drei statt zwei Bytes – der von einem Zwei-Byte-Datensatz abgedeckte Bereich hat sich mit um das 32-fache verringert 0xFFFF auf 0x7FF, und weder Chinesisch noch beispielsweise Georgisch sind darin enthalten. Kyrillisch und fünf weitere Alphabete – Hurra – Glück gehabt, 2 Bytes pro Zeichen.

Warum passiert das? Sehen wir uns an, wie UTF-8 Zeichencodes darstellt:

Direkt zur Darstellung von Zahlen werden hier mit dem Symbol gekennzeichnete Bits verwendet x. Es ist ersichtlich, dass in einem Zwei-Byte-Datensatz nur 11 solcher Bits (von 16) vorhanden sind. Die führenden Bits haben hier nur eine Hilfsfunktion. Im Fall eines Vier-Byte-Datensatzes werden 21 von 32 Bits für die Codepunktnummer reserviert – es scheint, dass drei Bytes (was insgesamt 24 Bits ergibt) ausreichen würden, aber Service-Marker fressen zu viel.

Ist das schlecht? Nicht wirklich. Wenn uns der Speicherplatz sehr am Herzen liegt, verfügen wir einerseits über Komprimierungsalgorithmen, mit denen sich die zusätzliche Entropie und Redundanz problemlos beseitigen lässt. Andererseits bestand das Ziel von Unicode darin, eine möglichst universelle Codierung bereitzustellen. Beispielsweise können wir eine in UTF-8 codierte Zeile einem Code anvertrauen, der zuvor nur mit ASCII funktionierte, und müssen keine Angst haben, dass er ein Zeichen aus dem ASCII-Bereich sieht, das tatsächlich nicht vorhanden ist (schließlich in UTF-8 alle). Bytes beginnend mit dem Nullbit – genau das ist ASCII). Und wenn wir plötzlich einen kleinen Schwanz von einer langen Zeichenfolge abschneiden möchten, ohne ihn von Anfang an zu dekodieren (oder einen Teil der Informationen nach einem beschädigten Abschnitt wiederherstellen möchten), ist es für uns einfach, den Versatz zu finden, an dem ein Zeichen beginnt (es reicht aus). um Bytes zu überspringen, die ein Bit-Präfix haben 10).

Warum dann etwas Neues erfinden?

Gleichzeitig gibt es gelegentlich Situationen, in denen Komprimierungsalgorithmen wie Deflate schlecht anwendbar sind, Sie aber eine kompakte Speicherung von Zeichenfolgen erreichen möchten. Persönlich bin ich auf dieses Problem gestoßen, als ich über das Bauen nachdachte komprimierter Präfixbaum für ein großes Wörterbuch mit Wörtern in beliebigen Sprachen. Einerseits ist jedes Wort sehr kurz, sodass eine Komprimierung wirkungslos ist. Andererseits war die von mir in Betracht gezogene Baumimplementierung so konzipiert, dass jedes Byte der gespeicherten Zeichenfolge einen separaten Baumscheitelpunkt generierte, sodass die Minimierung ihrer Anzahl sehr nützlich war. In meiner Bibliothek Az.js (Wie in pymorphy2, auf dem es basiert) kann ein ähnliches Problem einfach gelöst werden – in Strings gepackt DAWG-Wörterbuch, dort gespeichert guter alter CP1251. Dies funktioniert jedoch, wie leicht zu verstehen ist, nur für ein begrenztes Alphabet gut – eine Zeile auf Chinesisch kann einem solchen Wörterbuch nicht hinzugefügt werden.

Unabhängig davon möchte ich auf eine weitere unangenehme Nuance hinweisen, die bei der Verwendung von UTF-8 in einer solchen Datenstruktur auftritt. Das Bild oben zeigt, dass, wenn ein Zeichen als zwei Bytes geschrieben wird, die Bits, die sich auf seine Nummer beziehen, nicht in einer Reihe stehen, sondern durch ein Bitpaar getrennt sind 10 mitten drin: 110xxxxx 10xxxxxx. Aus diesem Grund kommt es zu einem Überlauf der unteren 6 Bits des zweiten Bytes im Zeichencode (d. h. es kommt zu einem Übergang). 10111111 → 10000000), dann ändert sich auch das erste Byte. Es stellt sich heraus, dass der Buchstabe „p“ durch Bytes bezeichnet wird 0xD0 0xBF, und das nächste „r“ ist schon 0xD1 0x80. In einem Präfixbaum führt dies zur Aufteilung des übergeordneten Knotens in zwei Knoten – einen für das Präfix 0xD0, und noch eins für 0xD1 (obwohl das gesamte kyrillische Alphabet nur durch das zweite Byte kodiert werden konnte).

Was habe ich bekommen

Angesichts dieses Problems beschloss ich, das Spielen mit Bits zu üben und mich gleichzeitig etwas besser mit der Struktur von Unicode als Ganzes vertraut zu machen. Das Ergebnis war das UTF-C-Kodierungsformat („C“ für kompakt), der nicht mehr als 3 Bytes pro Codepunkt ausgibt und sehr oft nur Ausgaben ermöglicht ein zusätzliches Byte für die gesamte codierte Zeile. Dies führt dazu, dass sich bei vielen Nicht-ASCII-Alphabeten eine solche Kodierung herausstellt 30–60 % kompakter als UTF-8.

Ich habe Beispiele für die Implementierung von Kodierungs- und Dekodierungsalgorithmen im Formular vorgestellt JavaScript- und Go-Bibliotheken, Sie können sie frei in Ihrem Code verwenden. Ich möchte jedoch dennoch betonen, dass dieses Format in gewisser Weise ein „Fahrrad“ bleibt und ich die Verwendung nicht empfehle ohne zu wissen, warum Sie es brauchen. Dies ist immer noch eher ein Experiment als eine ernsthafte „Verbesserung von UTF-8“. Dennoch ist der Code dort sauber und prägnant geschrieben, mit vielen Kommentaren und Testabdeckungen.

Testergebnisse und Vergleich mit UTF-8

Das habe ich auch getan Demoseite, wo Sie die Leistung des Algorithmus bewerten können, und dann werde ich Ihnen mehr über seine Prinzipien und den Entwicklungsprozess erzählen.

Eliminierung redundanter Bits

Als Basis habe ich natürlich UTF-8 genommen. Die erste und offensichtlichste Sache, die daran geändert werden kann, besteht darin, die Anzahl der Dienstbits in jedem Byte zu reduzieren. Beispielsweise beginnt das erste Byte in UTF-8 immer mit entweder 0, oder mit 11 - ein Präfix 10 Nur die folgenden Bytes haben es. Ersetzen wir das Präfix 11 auf 1, und für die nächsten Bytes werden wir die Präfixe vollständig entfernen. Was wird passieren?

0xxxxxxx — 1 Byte
10xxxxxx xxxxxxxx - 2 Bytes
110xxxxx xxxxxxxx xxxxxxxx - 3 Bytes

Moment, wo ist der Vier-Byte-Datensatz? Aber es wird nicht mehr benötigt – beim Schreiben in drei Bytes stehen uns jetzt 21 Bit zur Verfügung und das reicht für alle Zahlen bis 0x10FFFF.

Was haben wir hier geopfert? Das Wichtigste ist die Erkennung von Zeichengrenzen an einer beliebigen Stelle im Puffer. Wir können nicht auf ein beliebiges Byte zeigen und daraus den Anfang des nächsten Zeichens finden. Dies ist eine Einschränkung unseres Formats, in der Praxis ist dies jedoch selten erforderlich. Normalerweise können wir den Puffer von Anfang an durchfahren (besonders wenn es um kurze Leitungen geht).

Auch die Situation bei der Abdeckung von Sprachen mit 2 Bytes hat sich verbessert: Das Zwei-Byte-Format ergibt nun einen Bereich von 14 Bits, und das sind Codes bis zu 0x3FFF. Die Chinesen haben Pech (ihre Schriftzeichen reichen meist von 0x4E00 auf 0x9FFF), aber Georgier und viele andere Völker haben mehr Spaß – ihre Sprachen passen auch in 2 Bytes pro Zeichen.

Geben Sie den Encoder-Status ein

Denken wir nun über die Eigenschaften der Linien selbst nach. Das Wörterbuch enthält am häufigsten Wörter, die mit Buchstaben desselben Alphabets geschrieben sind, und das gilt auch für viele andere Texte. Es wäre gut, dieses Alphabet einmal anzugeben und dann nur die Nummer des darin enthaltenen Buchstabens anzugeben. Mal sehen, ob uns die Anordnung der Zeichen in der Unicode-Tabelle hilft.

Wie oben erwähnt, ist Unicode unterteilt in das Flugzeug Jeweils 65536 Codes. Dies ist jedoch keine sehr nützliche Unterteilung (wie bereits gesagt, meistens befinden wir uns in der Nullebene). Interessanter ist die Division durch Blöcke. Diese Bereiche haben keine feste Länge mehr und sind aussagekräftiger – in der Regel fassen sie jeweils Zeichen aus demselben Alphabet zusammen.

Ein 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 chaotisch über 128 Blockcodepunkte verteilt.

Die Anfänge von Blöcken und ihre Größe sind immer ein Vielfaches von 16 – dies dient lediglich der Bequemlichkeit. Darüber hinaus beginnen und enden viele Blöcke mit Werten, die ein Vielfaches von 128 oder sogar 256 sind – das grundlegende kyrillische Alphabet nimmt beispielsweise 256 Bytes ein 0x0400 auf 0x04FF. Das ist ganz praktisch: Wenn wir das Präfix einmal speichern 0x04, dann kann jedes kyrillische Zeichen in ein Byte geschrieben werden. Auf diese Weise verlieren wir zwar die Möglichkeit, zu ASCII (und zu allen anderen Zeichen im Allgemeinen) zurückzukehren. Deshalb machen wir Folgendes:

1. Zwei Bytes 10yyyyyy yxxxxxxx Bezeichnen Sie ein Symbol nicht nur mit einer Zahl yyyyyy yxxxxxxx, sondern auch ändern aktuelles Alphabet auf yyyyyy y0000000 (d. h. wir merken uns alle Bits außer den niedrigstwertigen 7-Bit);
2. Ein Byte 0xxxxxxx Dies ist das Zeichen des aktuellen Alphabets. Es muss lediglich zu dem Offset hinzugefügt werden, den wir uns in Schritt 1 gemerkt haben. Obwohl wir das Alphabet nicht geändert haben, ist der Offset Null, sodass wir die Kompatibilität mit ASCII beibehalten haben.

Ebenso für Codes, die 3 Bytes erfordern:

1. Drei Bytes 110yyyyy yxxxxxxx xxxxxxxx Geben Sie ein Symbol mit einer Zahl an yyyyyy yxxxxxxx xxxxxxxx, ändern aktuelles Alphabet auf yyyyyy y0000000 00000000 (erinnerte sich an alles außer an die Jüngeren 15-Bit) und aktivieren Sie das Kontrollkästchen, in dem wir uns gerade befinden lang Modus (wenn wir das Alphabet wieder in ein Doppelbyte-Alphabet ändern, setzen wir dieses Flag zurück);
2. Zwei Bytes 0xxxxxxx xxxxxxxx im Langmodus ist es das Zeichen des aktuellen Alphabets. Ebenso fügen wir es mit dem Offset aus Schritt 1 hinzu. Der einzige Unterschied besteht darin, dass wir jetzt zwei Bytes lesen (da wir in diesen Modus gewechselt sind).

Hört sich gut an: Während wir jetzt Zeichen aus demselben 7-Bit-Unicode-Bereich codieren müssen, geben wir am Anfang 1 zusätzliches Byte und insgesamt ein Byte pro Zeichen aus.

Arbeitet mit einer der früheren Versionen. Es schlägt UTF-8 bereits oft, aber es gibt noch Raum für Verbesserungen.

Was ist schlimmer? Erstens haben wir eine Bedingung, nämlich aktueller Alphabet-Offset und Kontrollkästchen Langer Modus. Dies schränkt uns noch weiter ein: Jetzt können dieselben Zeichen in verschiedenen Kontexten unterschiedlich codiert werden. Die Suche nach Teilzeichenfolgen muss beispielsweise unter Berücksichtigung dieser Tatsache erfolgen und nicht nur durch den Vergleich von Bytes. Zweitens, sobald wir das Alphabet geändert haben, wurde es mit der Kodierung von ASCII-Zeichen schlecht (und das ist nicht nur das lateinische Alphabet, sondern auch grundlegende Zeichensetzung, einschließlich Leerzeichen) – sie erfordern eine erneute Änderung des Alphabets auf 0, d. h. noch einmal ein zusätzliches Byte (und dann noch eines, um zu unserem Hauptpunkt zurückzukommen).

Ein Alphabet ist gut, zwei sind besser

Versuchen wir, unsere Bit-Präfixe ein wenig zu ändern, indem wir zu den drei oben beschriebenen noch eines hinzufügen:

0xxxxxxx — 1 Byte im Normalmodus, 2 im Langmodus
11xxxxxx — 1 Byte
100xxxxx xxxxxxxx - 2 Bytes
101xxxxx xxxxxxxx xxxxxxxx - 3 Bytes

Jetzt ist in einem Zwei-Byte-Datensatz ein Bit weniger verfügbar – Code zeigt bis zu 0x1FFFUnd nicht 0x3FFF. Allerdings ist er immer noch merklich größer als bei Doppelbyte-UTF-8-Codes, die meisten gängigen Sprachen passen noch rein, der auffälligste Verlust ist ausgefallen Hiragana и Katakana, die Japaner sind traurig.

Was ist dieser neue Code? 11xxxxxx? Dies ist ein kleiner „Vorrat“ mit einer Größe von 64 Zeichen. Er ergänzt unser Hauptalphabet, daher habe ich ihn Hilfsalphabet genannt (Hilfs-) Alphabet. Wenn wir das aktuelle Alphabet wechseln, wird ein Teil des alten Alphabets zum Hilfsalphabet. Wir haben zum Beispiel von ASCII auf Kyrillisch umgestellt – der Stash enthält jetzt 64 Zeichen Lateinisches Alphabet, Zahlen, Leerzeichen und Komma (häufigste Einfügungen in Nicht-ASCII-Texten). Wechseln Sie zurück zu ASCII – und der Hauptteil des kyrillischen Alphabets wird zum Hilfsalphabet.

Dank des Zugriffs auf zwei Alphabete können wir eine große Anzahl von Texten mit minimalen Kosten für den Wechsel des Alphabets verarbeiten (Interpunktion führt meistens zu einer Rückkehr zu ASCII, aber danach erhalten wir viele Nicht-ASCII-Zeichen aus dem zusätzlichen Alphabet, ohne). erneut umschalten).

Bonus: Voranstellen des Unteralphabets 11xxxxxx und die Wahl seines anfänglichen Offsets 0xC0erhalten wir teilweise Kompatibilität mit CP1252. Mit anderen Worten: Viele (aber nicht alle) in CP1252 kodierte westeuropäische Texte sehen in UTF-C gleich aus.

Hier entsteht jedoch eine Schwierigkeit: Wie erhält man ein Hilfsalphabet aus dem Hauptalphabet? Sie können den gleichen Offset belassen, aber leider spielt hier die Unicode-Struktur bereits gegen uns. Sehr oft steht der Hauptteil des Alphabets nicht am Anfang des Blocks (zum Beispiel steht der Code im russischen Großbuchstaben „A“) 0x0410, obwohl der kyrillische Block mit beginnt 0x0400). Nachdem wir also die ersten 64 Zeichen in den Vorrat aufgenommen haben, verlieren wir möglicherweise den Zugriff auf den hinteren Teil des Alphabets.

Um dieses Problem zu beheben, habe ich einige Blöcke, die verschiedenen Sprachen entsprechen, manuell durchgegangen und für sie den Versatz des Hilfsalphabets innerhalb des Hauptalphabets angegeben. Ausnahmsweise wurde das lateinische Alphabet generell wie base64 neu geordnet.

Letzter Schliff

Lasst uns endlich darüber nachdenken, wo wir sonst noch etwas verbessern können.

Beachten Sie, dass das Format 101xxxxx xxxxxxxx xxxxxxxx ermöglicht die Kodierung von Zahlen bis zu 0x1FFFFF, und Unicode endet früher, um 0x10FFFF. Mit anderen Worten, der letzte Codepunkt wird dargestellt als 10110000 11111111 11111111. Daher können wir sagen, dass das erste Byte die Form hat 1011xxxx (wo xxxx größer als 0), dann bedeutet es etwas anderes. Dort kann man zum Beispiel weitere 15 Zeichen hinzufügen, die ständig in einem Byte zum Kodieren zur Verfügung stehen, aber ich habe mich entschieden, es anders zu machen.

Schauen wir uns jetzt die Unicode-Blöcke an, die drei Bytes benötigen. Im Grunde handelt es sich, wie bereits erwähnt, um chinesische Schriftzeichen – aber mit ihnen lässt sich kaum etwas anfangen, es gibt 21 davon. Aber auch Hiragana und Katakana flogen dorthin – und davon gibt es nicht mehr so ​​viele, weniger als zweihundert. Und da wir uns an die Japaner erinnern, gibt es auch Emojis (tatsächlich sind sie in Unicode an vielen Stellen verstreut, aber die Hauptblöcke liegen im Bereich 0x1F300 - 0x1FBFF). Wenn Sie darüber nachdenken, dass es mittlerweile Emojis gibt, die aus mehreren Codepunkten gleichzeitig zusammengesetzt sind (zum Beispiel das Emoji ‍‍‍ besteht aus bis zu 7 Codes!), dann ist es eine absolute Schande, für jeden drei Bytes auszugeben (7×3 = 21 Bytes für ein Symbol, ein Albtraum).

Daher wählen wir einige ausgewählte Bereiche aus, die Emoji, Hiragana und Katakana entsprechen, nummerieren sie in einer fortlaufenden Liste neu und kodieren sie als zwei statt drei Bytes:

1011xxxx xxxxxxxx

Toll: das oben erwähnte ‍‍‍-Emoji, bestehend aus 7 Codepunkten, benötigt 8 Bytes in UTF-25, und wir passen es ein 14 (genau zwei Bytes für jeden Codepunkt). Habr weigerte sich übrigens, es zu verdauen (sowohl im alten als auch im neuen Editor), also musste ich es mit einem Bild einfügen.

Versuchen wir, ein weiteres Problem zu beheben. Wie wir uns erinnern, besteht das Grundalphabet im Wesentlichen aus hohe 6 Bit, die wir uns merken und an den Code jedes nächsten dekodierten Symbols kleben. Bei chinesischen Schriftzeichen, die im Block stehen 0x4E00 - 0x9FFF, das ist 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 Bytes ausgeben). Beachten Sie jedoch, dass wir im langen Modus vom Code selbst die Anzahl der Zeichen abziehen können, die wir im kurzen Modus codieren (nach all den oben beschriebenen Tricks sind dies 10240) – dann verschiebt sich der Bereich der Hieroglyphen 0x2600 - 0x77FF, und in diesem Fall sind im gesamten Bereich die höchstwertigen 6 Bits (von 21) gleich 0. Somit verwenden Hieroglyphensequenzen zwei Bytes pro Hieroglyphe (was für einen so großen Bereich optimal ist), ohne was zu Alphabetwechseln führt.

Alternative Lösungen: SCSU, BOCU-1

Unicode-Experten, die gerade den Titel des Artikels gelesen haben, werden Sie höchstwahrscheinlich daran erinnern, dass es direkt unter den Unicode-Standards gibt Standardkomprimierungsschema für Unicode (SCSU), das eine Codierungsmethode beschreibt, die der im Artikel beschriebenen sehr ähnlich ist.

Ich gebe ehrlich zu: Ich habe von seiner Existenz erst erfahren, als ich tief in die Niederschrift meiner Entscheidung vertieft war. Hätte ich es von Anfang an gewusst, hätte ich wahrscheinlich versucht, eine Implementierung zu schreiben, anstatt einen eigenen Ansatz zu entwickeln.

Interessant ist, dass SCSU Ideen verwendet, die denen sehr ähnlich sind, die ich mir selbst ausgedacht habe (anstelle des Konzepts der „Alphabete“ verwenden sie „Fenster“, und davon sind mehr verfügbar als ich). Gleichzeitig hat dieses Format auch Nachteile: Es ähnelt Komprimierungsalgorithmen etwas näher als Kodierungsalgorithmen. Insbesondere gibt der Standard viele Darstellungsmethoden an, sagt aber nicht, wie man die optimale auswählt – dafür muss der Encoder eine Art Heuristik verwenden. Daher ist ein SCSU-Encoder, der eine gute Verpackung erzeugt, komplexer und umständlicher als mein Algorithmus.

Zum Vergleich habe ich eine relativ einfache SCSU-Implementierung auf JavaScript übertragen – in Bezug auf das Codevolumen erwies es sich als vergleichbar mit meinem UTF-C, aber in einigen Fällen war das Ergebnis um Dutzende Prozent schlechter (manchmal kann es sogar darüber hinausgehen, aber nicht viel). Beispielsweise wurden Texte in Hebräisch und Griechisch mit UTF-C kodiert 60 % besser als SCSU (wahrscheinlich aufgrund ihrer kompakten Alphabete).

Unabhängig davon möchte ich hinzufügen, dass es neben SCSU auch eine andere Möglichkeit gibt, Unicode kompakt darzustellen: BOCU-1, aber es zielt auf MIME-Kompatibilität ab (die ich nicht brauchte) und verfolgt einen etwas anderen Ansatz bei der Kodierung. Ich habe die Wirksamkeit nicht beurteilt, aber es scheint mir, dass sie wahrscheinlich nicht höher sein wird als die von SCSU.

Mögliche Verbesserungen

Der von mir vorgestellte Algorithmus ist von Natur aus nicht universell (hier weichen meine Ziele wahrscheinlich am meisten von den Zielen des Unicode-Konsortiums ab). Ich habe bereits erwähnt, dass es hauptsächlich für eine Aufgabe entwickelt wurde (Speichern eines mehrsprachigen Wörterbuchs in einem Präfixbaum) und dass einige seiner Funktionen für andere Aufgaben möglicherweise nicht gut geeignet sind. Aber die Tatsache, dass es sich nicht um einen Standard handelt, kann ein Pluspunkt sein – Sie können es ganz einfach an Ihre Bedürfnisse anpassen.

Auf die offensichtliche Weise können Sie beispielsweise das Vorhandensein von Zuständen beseitigen und eine zustandslose Codierung durchführen – nur Variablen nicht aktualisieren offs, auxOffs и is21Bit im Encoder und Decoder. In diesem Fall ist es nicht möglich, Zeichenfolgen desselben Alphabets effektiv zu packen, aber es besteht die Garantie, dass dasselbe Zeichen unabhängig vom Kontext immer mit denselben Bytes codiert wird.

Darüber hinaus können Sie den Encoder an eine bestimmte Sprache anpassen, indem Sie den Standardstatus ändern. Wenn Sie sich beispielsweise auf russische Texte konzentrieren, stellen Sie den Encoder und Decoder am Anfang ein offs = 0x0400 и auxOffs = 0. Dies ist insbesondere im Stateless-Modus sinnvoll. Im Allgemeinen ähnelt dies der Verwendung der alten XNUMX-Bit-Kodierung, ohne dass jedoch die Möglichkeit entfernt wird, bei Bedarf Zeichen aus dem gesamten Unicode einzufügen.

Ein weiterer bereits erwähnter Nachteil besteht darin, dass es in großen, in UTF-C codierten Texten keine schnelle Möglichkeit gibt, die Zeichengrenze zu finden, die einem beliebigen Byte am nächsten liegt. Wenn Sie beispielsweise die letzten 100 Bytes aus dem codierten Puffer abschneiden, besteht die Gefahr, dass Sie Müll erhalten, mit dem Sie nichts anfangen können. Die Kodierung ist nicht für die Speicherung von Multi-Gigabyte-Protokollen ausgelegt, aber im Allgemeinen kann dies korrigiert werden. Byte 0xBF darf niemals als erstes Byte erscheinen (kann aber das zweite oder dritte sein). Daher können Sie beim Codieren die Sequenz einfügen 0xBF 0xBF 0xBF alle, sagen wir, 10 KB – wenn Sie dann eine Grenze finden müssen, reicht es aus, das ausgewählte Stück zu scannen, bis eine ähnliche Markierung gefunden wird. Im Anschluss an den letzten 0xBF ist garantiert der Anfang eines Zeichens. (Beim Dekodieren muss diese Folge von drei Bytes natürlich ignoriert werden.)

Zusammenfassend

Wenn Sie bis hierhin gelesen haben, herzlichen Glückwunsch! Ich hoffe, dass Sie, wie ich, etwas Neues über die Struktur von Unicode gelernt (oder Ihr Gedächtnis aufgefrischt) haben.

Demoseite. Das Beispiel Hebräisch zeigt die Vorteile gegenüber UTF-8 und SCSU.

Die oben beschriebene Forschung sollte nicht als Eingriff in die Standards angesehen werden. Generell bin ich jedoch mit den Ergebnissen meiner Arbeit zufrieden und daher zufrieden teilen: Beispielsweise wiegt eine minimierte JS-Bibliothek nur 1710 Bytes (und hat natürlich keine Abhängigkeiten). Wie ich oben erwähnt habe, ist ihre Arbeit unter zu finden Demoseite (Es gibt auch eine Reihe von Texten, anhand derer es mit UTF-8 und SCSU verglichen werden kann).

Abschließend möchte ich noch einmal auf Fälle hinweisen, in denen UTF-C verwendet wird lohnt sich nicht:

• Wenn Ihre Zeilen lang genug sind (von 100 bis 200 Zeichen). In diesem Fall sollten Sie über die Verwendung von Komprimierungsalgorithmen wie Deflate nachdenken.
• Wenn Sie brauchen ASCII-Transparenz, das heißt, es ist für Sie wichtig, dass die codierten Sequenzen keine ASCII-Codes enthalten, die nicht im Originalstring enthalten waren. Dies kann vermieden werden, wenn Sie bei der Interaktion mit APIs von Drittanbietern (z. B. beim Arbeiten mit einer Datenbank) das Codierungsergebnis als abstrakte Menge von Bytes und nicht als Zeichenfolgen übergeben. Andernfalls besteht die Gefahr unerwarteter Sicherheitslücken.
• Wenn Sie in der Lage sein möchten, Zeichengrenzen mit einem beliebigen Versatz schnell zu finden (z. B. wenn ein Teil einer Zeile beschädigt ist). Dies ist möglich, jedoch nur durch Scannen der Zeile von Anfang an (oder durch Anwenden der im vorherigen Abschnitt beschriebenen Änderung).
• Wenn Sie schnell Operationen am Inhalt von Zeichenfolgen durchführen müssen (sortieren, nach Teilzeichenfolgen darin suchen, verketten). Dies erfordert, dass Zeichenfolgen zuerst dekodiert werden, sodass UTF-C in diesen Fällen langsamer als UTF-8 ist (aber schneller als Komprimierungsalgorithmen). Da die gleiche Zeichenfolge immer auf die gleiche Weise codiert wird, ist ein genauer Vergleich der Decodierung nicht erforderlich und kann byteweise erfolgen.

Update: Benutzer Tyomitsch in den Kommentaren unten hat eine Grafik gepostet, die die Anwendbarkeitsgrenzen von UTF-C hervorhebt. Es zeigt, dass UTF-C effizienter ist als ein Allzweck-Komprimierungsalgorithmus (eine Variation von LZW), solange die gepackte Zeichenfolge kürzer ist ~140 Zeichen (Ich stelle jedoch fest, dass der Vergleich an einem Text durchgeführt wurde; bei anderen Sprachen kann das Ergebnis abweichen).


Source: habr.com