{"id":95911,"date":"2020-10-05T01:42:09","date_gmt":"2020-10-04T23:42:09","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8"},"modified":"2020-10-05T01:42:09","modified_gmt":"2020-10-04T23:42:09","slug":"eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8","status":"publish","type":"post","link":"https:\/\/prohoster.info\/de\/blog\/administrirovanie\/eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8","title":{"rendered":"Noch ein Rad: Wir speichern Unicode-Zeichenfolgen 30-60 % kompakter als UTF-8","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Noch
\n
\nWenn Sie ein Entwickler sind und die Aufgabe haben, eine Kodierung auszuw\u00e4hlen, ist Unicode fast immer die richtige Wahl. Die spezifische Darstellung h\u00e4ngt vom Kontext ab, aber oft gibt es auch hier eine universelle Antwort: UTF-8. Es hat den Vorteil, dass es alle Unicode-Zeichen verwenden kann, ohne zu viele Bytes zu verschwenden.<\/em> F\u00fcr die meisten F\u00e4lle sind das \u00fcbrigens nicht mehr als zwei Bytes pro Zeichen.<\/strong>Gibt es eine bessere M\u00f6glichkeit, ohne zu den pr\u00e4historischen Kodierungen zur\u00fcckzukehren, die uns auf nur 256 verf\u00fcgbare Zeichen beschr\u00e4nken?<\/p>\n

Im Folgenden finden Sie meinen Versuch, auf diese Frage zu antworten und eine relativ einfache Algorithmus-Implementierung zu pr\u00e4sentieren, die es erm\u00f6glicht, Zeichenfolgen in den meisten Sprachen der Welt zu speichern, ohne die \u00dcberfl\u00fcssigkeit hinzuzuf\u00fcgen, die mit UTF-8 einhergeht.<\/a><\/noindex><\/p>\n

Haftungsausschluss.<\/i> Ich m\u00f6chte gleich einige wichtige Vorbehalte anbringen: Die beschriebene L\u00f6sung wird nicht als universeller Ersatz f\u00fcr UTF-8 angeboten.<\/strong>, es passt nur in einer engen Liste von F\u00e4llen (dar\u00fcber sp\u00e4ter), und es darf auf keinen Fall f\u00fcr die Interaktion mit externen APIs verwendet werden (die davon nicht einmal erfahren). Am h\u00e4ufigsten sind Algorithmen zur allgemeinen Datenkompression (wie deflate) f\u00fcr die kompakte Speicherung gro\u00dfer Textdatenmengen geeignet. Au\u00dferdem habe ich bereits w\u00e4hrend der Erstellung meiner L\u00f6sung einen bestehenden Standard im Unicode gefunden, der dasselbe Problem l\u00f6st \u2013 er ist etwas komplizierter (und oft schlechter), aber immer noch ein anerkannter Standard und nicht etwas, das improvisiert wurde. Auch dar\u00fcber werde ich sprechen.<\/p>\n

\u00dcber Unicode und UTF-8<\/h2>\n

\nZun\u00e4chst einige Worte zu dem, was das \u00fcberhaupt ist Unicode<\/strong> und UTF-8<\/strong>.<\/p>\n

Wie bekannt, waren fr\u00fcher 8-Bit-Codierungen popul\u00e4r. Damit war alles einfach: 256 Symbole k\u00f6nnen mit Zahlen von 0 bis 255 nummeriert werden, und die Zahlen von 0 bis 255 sind offensichtlich als ein Byte darstellbar. Wenn man zu den Urspr\u00fcngen zur\u00fcckkehrt, beschr\u00e4nkt sich die ASCII-Codierung auf 7 Bits, weshalb das h\u00f6chste Bit in ihrer Byte-Darstellung null ist, und die meisten 8-Bit-Codierungen sind damit kompatibel (sie unterscheiden sich nur im \u201eobersten\u201c Teil, wo das h\u00f6chste Bit eins ist).<\/p>\n

Was unterscheidet Unicode von anderen Codierungen und warum sind damit gleich mehrere spezifische Darstellungen verbunden \u2013 UTF-8, UTF-16 (BE und LE), UTF-32? Lassen Sie uns der Reihe nach kl\u00e4ren.<\/p>\n

Der Hauptstandard von Unicode beschreibt nur die Zuordnung zwischen Zeichen (und in einigen F\u00e4llen \u2013 einzelnen Komponenten von Zeichen) und ihren Nummern. Es gibt eine Vielzahl m\u00f6glicher Nummern in diesem Standard \u2013 von 0x00<\/b><\/code> bis zu 0x10FFFF<\/b><\/code> (1.114.112 St\u00fcck). Wenn wir eine Zahl in einem solchen Bereich in einer Variablen speichern wollten, w\u00e4ren 1 oder 2 Byte nicht ausreichend. Und da unsere Prozessoren nicht f\u00fcr die Arbeit mit dreibyteigen Zahlen ausgelegt sind, m\u00fcssten wir ganze 4 Byte f\u00fcr ein Zeichen verwenden! Das ist UTF-32, aber genau wegen dieser \u201eVerschwendung\u201c wird dieses Format nicht oft verwendet.<\/p>\n

Gl\u00fccklicherweise sind die Zeichen innerhalb von Unicode nicht zuf\u00e4llig angeordnet. Ihre Vielzahl ist in 17 \u201eEbenen<\/em>\u201c unterteilt, von denen jede 65.536 (\u201e0x10000<\/b><\/code>) \u00abCodepunkte<\/em>\u201c enth\u00e4lt. Der Begriff \u201eCodepunkt\u201c hier ist einfach die Nummer eines Zeichens.<\/em>, das ihm von Unicode zugewiesen wurde. Wie bereits erw\u00e4hnt, werden im Unicode nicht nur einzelne Zeichen nummeriert, sondern auch deren Komponenten und Steuerzeichen (manchmal wird der Nummer sogar nichts zugeordnet \u2014 vielleicht vor\u00fcbergehend, aber das ist f\u00fcr uns nicht so wichtig), daher ist es korrekter, immer \u00fcber die Anzahl der Nummern zu sprechen, nicht \u00fcber die Zeichen. Im Folgenden werde ich jedoch aus Gr\u00fcnden der K\u00fcrze oft das Wort \u201eZeichen\u201c verwenden, wobei ich den Begriff \u201eCodepunkt\u201c meine.<\/p>\n

\"Noch
\nUnicode-Ebenen. Wie zu sehen ist, ist der gr\u00f6\u00dfte Teil (Ebenen 4 bis 13) noch ungenutzt.<\/i><\/p>\n

Das Erstaunlichste ist, dass der gesamte Kern in der nullten Ebene liegt, die \"Basic Multilingual Plane<\/em>\" genannt wird. Wenn die Zeile Text in einer der modernen Sprachen (einschlie\u00dflich Chinesisch) enth\u00e4lt, werden Sie diese Ebene nicht verlassen. Aber auch der Rest des Unicode darf nicht abgeschnitten werden \u2013 zum Beispiel befinden sich Emojis haupts\u00e4chlich am Ende der n\u00e4chsten Ebene, \"Supplementary Multilingual Plane<\/em>\" (die sich erstreckt von 0x10000<\/b><\/code> bis zu 0x1FFFF<\/b><\/code>). Daher funktioniert UTF-16 so: Alle Zeichen, die in Basic Multilingual Plane<\/em>, wird \"wie ist\" kodiert, entsprechend ihrer zweibyter Zahl. Aber ein Teil der Zahlen in diesem Bereich repr\u00e4sentiert \u00fcberhaupt keine spezifischen Symbole, sondern weist darauf hin, dass nach diesem Byte-Paar ein weiteres betrachtet werden muss \u2014 kombiniert man die Werte dieser vier Bytes, erh\u00e4lt man eine Zahl, die den gesamten zul\u00e4ssigen Unicode-Bereich abdeckt. Diese Darstellung wird als \"surrogates Paare\" bezeichnet \u2014 vielleicht haben Sie schon von ihnen geh\u00f6rt.<\/p>\n

Daher ben\u00f6tigt UTF-16 zwei oder (in sehr seltenen F\u00e4llen) vier Bytes f\u00fcr einen \"Codepunkt\". Das ist besser, als st\u00e4ndig vier Bytes zu verwenden, aber f\u00fcr lateinische Buchstaben (und andere ASCII-Zeichen) verbraucht diese Kodierung die H\u00e4lfte des belegten Raums f\u00fcr Nullen. UTF-8 wurde entwickelt, um dies zu beheben: ASCII belegt darin wie zuvor nur ein Byte; Codes von 0x80<\/b><\/code> bis zu 0x7FF<\/b><\/code> \u2014 zwei Bytes; von 0x800<\/b><\/code> bis zu 0xFFFF<\/b><\/code> \u2014 drei, und von 0x10000<\/b><\/code> bis zu 0x10FFFF<\/b><\/code> \u2014 vier. Auf der einen Seite ist es f\u00fcr das Lateinische gut geworden: Es gibt wieder Kompatibilit\u00e4t mit ASCII, und die Verteilung ist gleichm\u00e4\u00dfiger \"verteilt\" von 1 bis 4 Byte. Aber die Alphabete, die sich vom Lateinischen unterscheiden, gewinnen leider \u00fcberhaupt nicht im Vergleich zu UTF-16, und viele verlangen nun sogar drei Byte statt zwei \u2014 der Bereich, der durch die zweibyte Kodierung abgedeckt wird, hat sich um das 32-fache verengt, 0xFFFF<\/b><\/code> bis zu 0x7FF<\/b><\/code>, und darin sind weder Chinesisch noch zum Beispiel Georgisch enthalten. Der Kyrillischen und f\u00fcnf weiteren Alphabeten \u2013 hurra \u2013 ist es gelungen, 2 Byte pro Zeichen zu nutzen.<\/p>\n

Warum ist das so? Lassen Sie uns betrachten, wie UTF-8 Symbolcodes darstellt:
\n\"Noch
\nDirekt zur Darstellung der Zahlen werden hier Bits verwendet, die mit dem Symbol x<\/b><\/code>markiert sind. Es ist zu sehen, dass es in der zweibyte Kodierung nur 11 solcher Bits (von 16) gibt. Die f\u00fchrenden Bits haben hier nur eine Hilfsfunktion. Im Fall der vierbyte Kodierung werden sogar 21 Bits von 32 f\u00fcr die Nummer des Codepunkts reserviert \u2014 es scheint, dass drei Bytes (die insgesamt 24 Bits ergeben) ausreichen w\u00fcrden, aber die Dienstmarkierungen verbrauchen zu viel.<\/p>\n

Ist das schlecht? Eigentlich nicht. Einerseits \u2014 wenn wir gro\u00dfen Wert auf den ben\u00f6tigten Speicherplatz legen, gibt es Kompressionsalgorithmen, die einfach \u00fcberfl\u00fcssige Entropie und Redundanz beseitigen. Andererseits war das Ziel von Unicode, eine m\u00f6glichst universelle Kodierung bereitzustellen. Zum Beispiel k\u00f6nnen wir eine in UTF-8 kodierte Zeichenkette einem Code anvertrauen, der zuvor nur mit ASCII gearbeitet hat, und m\u00fcssen nicht bef\u00fcrchten, dass er ein Zeichen aus dem ASCII-Bereich sieht, das dort tats\u00e4chlich nicht vorhanden ist (denn in UTF-8 sind alle Bytes, die mit einem Nullbit beginnen, genau das ASCII). Und wenn wir pl\u00f6tzlich den kleinen Schwanz von einer gro\u00dfen Zeichenkette abschneiden m\u00f6chten, ohne sie von Anfang an zu dekodieren (oder einen Teil der Informationen nach einem besch\u00e4digten Abschnitt wiederherzustellen) \u2014 ist es nicht schwierig, die Verschiebung zu finden, an der ein Zeichen beginnt (es reicht, die Bytes zu \u00fcberspringen, die ein bit Pr\u00e4fix haben. 10<\/b><\/code>).<\/p>\n

Warum also etwas Neues erfinden?<\/h2>\n

\nGleichzeitig gibt es gelegentlich Situationen, in denen Kompressionsalgorithmen wie deflate schwer anwendbar sind, aber man m\u00f6chte eine kompakte Speicherung von Zeichenketten erreichen. Ich pers\u00f6nlich bin mit einer solchen Aufgabe konfrontiert worden, als ich \u00fcber den Aufbau nachgedacht habe. eines komprimierten Pr\u00e4fixbaums.<\/a><\/noindex> f\u00fcr ein gro\u00dfes W\u00f6rterbuch, das W\u00f6rter in beliebigen Sprachen umfasst. Einerseits sind alle W\u00f6rter sehr kurz, sodass eine Kompression ineffektiv w\u00e4re. Andererseits wurde die Baumstruktur, die ich in Betracht gezogen habe, darauf ausgelegt, dass jedes Byte der gespeicherten Zeichenfolge einen separaten Knoten im Baum erzeugt, weshalb es sehr n\u00fctzlich war, ihre Anzahl zu minimieren. In meiner Bibliothek Az.js<\/a><\/noindex> (wie in pymorphy2<\/a><\/noindex>, auf dem sie basiert) wird dieses Problem einfach gel\u00f6st \u2014 die in DAWG<\/a><\/noindex>-W\u00f6rterb\u00fcchern gespeicherten Zeichenfolgen werden dort in dem alten guten CP1251<\/a><\/noindex>. Aber wie man leicht erkennen kann, funktioniert das nur f\u00fcr ein eingeschr\u00e4nktes Alphabet \u2013 eine Zeile auf Chinesisch l\u00e4sst sich nicht in ein solches W\u00f6rterbuch einf\u00fcgen.<\/p>\n

Ich m\u00f6chte auch einen weiteren unangenehmen Aspekt hervorheben, der bei der Verwendung von UTF-8 in dieser Datenstruktur auftritt. Auf dem Bild oben ist zu sehen, dass die Bits, die zu seiner Nummer geh\u00f6ren, bei der Speicherung eines Zeichens in Form von zwei Bytes nicht aufeinander folgen, sondern durch ein paar Bits 10<\/b><\/code> in der Mitte unterbrochen sind: 110xxxxx 10xxxxxx<\/b><\/code>. Dadurch \u00e4ndert sich auch das erste Byte, wenn die unteren 6 Bits des zweiten Bytes im Codesymbol \u00fcberlaufen (d.h. ein \u00dcbergang 10111111<\/b><\/code> \u2192 10000000<\/b><\/code>). Das bedeutet, dass der Buchstabe \u201e\u043f\u201c durch Bytes dargestellt wird 0xD0 0xBF<\/b><\/code>, und das n\u00e4chste Zeichen \u201er\u201c ist bereits 0xD1 0x80<\/b><\/code>. Im Pr\u00e4fixbaum f\u00fchrt dies zur Spaltung des Elternknotens in zwei \u2014 einen f\u00fcr das Pr\u00e4fix 0xD0<\/b><\/code>, und den anderen f\u00fcr 0xD1<\/b><\/code> (obwohl das gesamte Kyrillisch durchaus nur mit dem zweiten Byte codiert werden k\u00f6nnte).<\/p>\n

Was ich erreicht habe<\/h2>\n

\nAngesichts dieser Aufgabe beschloss ich, ein wenig mit Bits zu spielen und dabei die Unicode-Struktur besser zu verstehen. Das Ergebnis war das Codierungsformat UTF-C (\u201eC\u201c f\u00fcr kompakt<\/em>), das nicht mehr als 3 Bytes f\u00fcr einen Codepunkt verbraucht, h\u00e4ufig jedoch nur ein zus\u00e4tzliches Byte f\u00fcr die gesamte kodierte Zeile<\/strong>. Das f\u00fchrt dazu, dass bei vielen Nicht-ASCII-Alphabets diese Kodierung 30-60% kompakter ist als UTF-8<\/strong>.<\/p>\n

Ich habe Beispiele zur Implementierung von Codierungs- und Dekodierungsalgorithmen in Form von Bibliotheken in JavaScript und Go<\/a><\/noindex>, die Sie in Ihrem Code frei verwenden k\u00f6nnen. Ich m\u00f6chte jedoch betonen, dass dieses Format in gewisser Weise ein \u201eFahrrad\u201c bleibt, und ich empfehle nicht, es zu verwenden ohne zu verstehen, wof\u00fcr es ben\u00f6tigt wird<\/strong>. Es ist letztlich mehr ein Experiment als eine ernsthafte \"Verbesserung von UTF-8\". Dennoch ist der Code sauber, pr\u00e4gnant geschrieben, mit vielen Kommentaren und Tests.<\/p>\n

\"Noch
\nTestergebnisse und Vergleich mit UTF-8<\/i><\/p>\n

Au\u00dferdem habe ich eine Demo-Seite<\/a><\/noindex>, auf der man die Funktionsweise des Algorithmus bewerten kann. Weiter unten werde ich die Prinzipien und den Entwicklungsprozess n\u00e4her erl\u00e4utern.<\/p>\n

\u00dcberfl\u00fcssige Bits entfernen<\/h2>\n

\nIch habe nat\u00fcrlich UTF-8 als Grundlage genommen. Das erste und offensichtlichste, was man \u00e4ndern kann, ist die Reduzierung der Kontrollbits in jedem Byte. Zum Beispiel beginnt das erste Byte in UTF-8 immer entweder mit 0<\/b><\/code>, oder mit 11<\/b><\/code> \u2014 der Pr\u00e4fix 10<\/b><\/code> gibt es nur bei den folgenden Bytes. Ersetzen wir den Pr\u00e4fix 11<\/b><\/code> findet man 1<\/b><\/code>, und entfernen wir die Pr\u00e4fixe ganz bei den folgenden Bytes. Was kommt dabei heraus?<\/p>\n

0xxxxxxx<\/b><\/code> \u2014 1 Byte
\n10xxxxxx xxxxxxxx<\/b><\/code> \u2014 2 Bytes
\n110xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> \u2014 3 Bytes<\/p>\n

Halt, wo bleibt die vier-Byte-Darstellung? Die ist nicht mehr n\u00f6tig \u2014 mit dreibyteiger Darstellung stehen uns jetzt 21 Bits zur Verf\u00fcgung, was mehr als ausreichend ist f\u00fcr alle Zahlen bis 0x10FFFF<\/b><\/code>.<\/p>\n

Was haben wir hier geopfert? Das Wichtigste ist die Erkennung von Symbolgrenzen an einer beliebigen Stelle des Puffers. Wir k\u00f6nnen nicht einfach in ein beliebiges Byte greifen und von dort aus den Anfang des n\u00e4chsten Symbols finden. Das ist eine Einschr\u00e4nkung unseres Formats, aber in der Praxis tritt die Notwendigkeit daf\u00fcr nicht oft auf. Normalerweise k\u00f6nnen wir den Puffer von ganz vorne durchlaufen (besonders bei kurzen Zeichenfolgen).<\/p>\n

Die Situation mit der Abdeckung von Sprachen in 2 Bytes hat sich ebenfalls verbessert: Jetzt bietet das zweibyte Format einen Bereich von 14 Bit, was Codes bis 0x3FFF<\/b><\/code>. Die Chinesen haben Pech (ihre Schriftzeichen liegen haupts\u00e4chlich im Bereich von 0x4E00<\/b><\/code> bis zu 0x9FFF<\/b><\/code>), aber f\u00fcr die Georgier und viele andere V\u00f6lker ist es erfreulicher geworden \u2013 ihre Sprachen passen ebenfalls in 2 Bytes pro Zeichen.<\/p>\n

Wir f\u00fchren den Zustand des Encoders ein.<\/h2>\n

\nLassen Sie uns nun \u00fcber die Eigenschaften der Zeichenfolgen selbst nachdenken. Im W\u00f6rterbuch sind h\u00e4ufig Worte zu finden, die mit Symbolen eines Alphabets geschrieben sind, und das gilt auch f\u00fcr viele andere Texte. Es w\u00e4re gut, einmal dieses Alphabet anzugeben und dann nur die Nummer des Buchstabens innerhalb davon zu nennen. Mal sehen, ob uns die Anordnung der Zeichen in der Unicode-Tabelle hilft.<\/p>\n

Wie oben erw\u00e4hnt, ist Unicode in Ebenen unterteilt.<\/em> jeweils 65536 Codes. Aber diese Einteilung ist nicht sehr hilfreich (wie bereits erw\u00e4hnt, befinden wir uns meistens in der Nullebene). Interessanter ist die Unterteilung in Bl\u00f6cke.<\/em> Diese Bereiche haben keine feste L\u00e4nge mehr und sind bedeutungsvoller \u2014 in der Regel vereint jeder von ihnen Zeichen eines Alphabets.<\/p>\n

\"Noch
\nEin Block, der Zeichen des bengalischen Alphabets enth\u00e4lt. Leider ist dies aus historischen Gr\u00fcnden ein Beispiel f\u00fcr eine nicht sehr dichte Verpackung \u2014 96 Zeichen sind chaotisch \u00fcber 128 Codepunkte des Blocks verteilt.<\/i><\/p>\n

Die Anfangspositionen der Bl\u00f6cke und deren Gr\u00f6\u00dfen sind stets ein Vielfaches von 16 \u2014 dies erleichtert die Handhabung. Dar\u00fcber hinaus beginnen und enden viele Bl\u00f6cke auf Werten, die ein Vielfaches von 128 oder sogar 256 sind \u2014 zum Beispiel nimmt die Basis-Kyrillik 256 Byte von 0x0400<\/b><\/code> bis zu 0x04FF<\/b><\/code>. Das ist ziemlich praktisch: Wenn wir einmal das Pr\u00e4fix speichern, 0x04<\/b><\/code>, kann jedes kyrillische Zeichen mit einem Byte geschrieben werden. Allerdings verlieren wir dadurch die M\u00f6glichkeit, zu ASCII (und zu allen anderen Zeichen \u00fcberhaupt) zur\u00fcckzukehren. Daher machen wir es so:<\/p>\n

    \n
  1. Zwei Bytes 10yyyyyy yxxxxxxx<\/b><\/code> bezeichnen nicht nur das Zeichen mit der Nummer yyyyyy yxxxxxxx<\/b><\/code>, sondern \u00e4ndern auch das aktuelle Alphabet<\/em> findet man yyyyyy y0000000<\/b><\/code> d.h. wir merken uns alle Bits, au\u00dfer den niedrigsten 7 Bits<\/strong>);<\/li>\n
  2. Ein Byte 0xxxxxxx<\/b><\/code> dies ist das Symbol des aktuellen Alphabets. Es muss einfach mit der Verschiebung addiert werden, die wir in Schritt 1 gespeichert haben. Da wir das Alphabet bisher nicht ge\u00e4ndert haben, ist die Verschiebung null, sodass wir mit ASCII kompatibel geblieben sind.<\/li>\n<\/ol>\n

    \n\u00c4hnlich f\u00fcr Codes, die 3 Byte ben\u00f6tigen:<\/p>\n

      \n
    1. Drei Bytes 110yyyyy yxxxxxxx xxxxxxxx<\/b><\/code> bezeichnen ein Zeichen mit der Nummer yyyyyy yxxxxxxx xxxxxxxx<\/b><\/code>, ver\u00e4ndert das aktuelle Alphabet<\/em> findet man yyyyyy y0000000 00000000<\/b><\/code> (wir haben alles au\u00dfer den niederwertigen 15 Bit<\/strong>), und setzen ein Flag, dass wir uns jetzt im langen<\/em> Modus befinden (bei einem Wechsel des Alphabets zur\u00fcck in den zweibyteiger Modus setzen wir dieses Flag zur\u00fcck);<\/li>\n
    2. Zwei Bytes 0xxxxxxx xxxxxxxx<\/b><\/code> im langen Modus ist dies das Zeichen des aktuellen Alphabets. \u00c4hnlich addieren wir es zur Verschiebung aus Schritt 1. Der einzige Unterschied besteht darin, dass wir jetzt zwei Bytes lesen (weil wir in diesen Modus gewechselt haben).<\/li>\n<\/ol>\n

      \nKlingt gut: Solange wir Zeichen aus dem gleichen 7-Bit-Bereich von Unicode kodieren m\u00fcssen, verwenden wir 1 zus\u00e4tzliches Byte am Anfang und nur 1 Byte pro Zeichen.<\/p>\n

      \"Noch
      \nArbeit einer der fr\u00fcheren Versionen. \u00dcberholt oft UTF-8, aber es gibt noch Verbesserungsbedarf.<\/i><\/p>\n

      Was ist schlimmer geworden? Erstens haben wir jetzt einen Zustand, n\u00e4mlich die Verschiebung des aktuellen Alphabets<\/em> und das Flag des langen Modus<\/em>. Das schr\u00e4nkt uns zus\u00e4tzlich ein: Nun k\u00f6nnen dieselben Zeichen in verschiedenen Kontexten unterschiedlich kodiert werden. Beispielsweise m\u00fcssen wir beim Suchen nach Teilstrings dies ber\u00fccksichtigen und nicht einfach Bytes vergleichen. Zweitens, sobald wir das Alphabet gewechselt haben, gibt es Probleme mit der Kodierung von ASCII-Zeichen (und das umfasst nicht nur das lateinische Alphabet, sondern auch die grundlegende Interpunktion, einschlie\u00dflich Leerzeichen) \u2014 sie erfordern einen erneuten Alphabetwechsel in 0, also wieder ein zus\u00e4tzliches Byte (und dann noch eines, um zu unserem Hauptalphabet zur\u00fcckzukehren).<\/p>\n

      Ein Alphabet ist gut, zwei sind besser.<\/h2>\n

      \nLassen Sie uns versuchen, unsere Bit-Pr\u00e4fixe ein wenig zu \u00e4ndern, indem wir noch einen zu den drei oben beschriebenen hinzuf\u00fcgen:<\/p>\n

      0xxxxxxx<\/b><\/code> \u2014 1 Byte im Normalmodus, 2 im langen Modus.
      \n11xxxxxx<\/b><\/code> \u2014 1 Byte
      \n100xxxxx xxxxxxxx<\/b><\/code> \u2014 2 Bytes
      \n101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> \u2014 3 Bytes<\/p>\n

      \"Noch
      \n
      \nJetzt gibt es in der zweibyte Kodierung ein verf\u00fcgbares Bit weniger \u2014 es werden Codepunkte bis zu 0x1FFF<\/b><\/code>, und nicht 0x3FFF<\/b><\/code>. Dennoch ist das immer noch sp\u00fcrbar mehr als in zweibyte UTF-8-Codes, die meisten verbreiteten Sprachen passen immer noch hinein, der auff\u00e4lligste Verlust \u2014 ist weggefallen.       Hiragana<\/a><\/noindex> und Katakana<\/a><\/noindex>, die Japaner sind traurig.<\/p>\n

      Was ist der neue Code 11xxxxxx<\/b><\/code>? \u042d\u0442\u043e \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u00ab\u0437\u0430\u0433\u0430\u0448\u043d\u0438\u043a\u00bb \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u0432 64 \u0441\u0438\u043c\u0432\u043e\u043b\u0430, \u043e\u043d \u0434\u043e\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043d\u0430\u0448 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0430\u043b\u0444\u0430\u0432\u0438\u0442, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u043d\u0430\u0437\u0432\u0430\u043b \u0435\u0433\u043e \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c (auxiliary<\/em>) Alphabet. Wenn wir das aktuelle Alphabet umschalten, wird ein St\u00fcck des alten Alphabets zum Hilfsalphabet. Zum Beispiel, wenn wir von ASCII auf Kyrillisch umschalten, haben wir nun 64 Zeichen im \u201eCache\u201c, die enthalten sind Latein, Ziffern, Leerzeichen und Komma<\/strong> (die h\u00e4ufigsten Einf\u00fcgungen in Nicht-ASCII-Texten). Wenn wir wieder auf ASCII umschalten, wird der Hauptteil des Kyrillischen zum Hilfsalphabet.<\/p>\n

      Dank des Zugriffs auf zwei Alphabete k\u00f6nnen wir mit einer gro\u00dfen Anzahl von Texten umgehen, ohne nennenswerte Kosten f\u00fcr das Umschalten der Alphabete (die Interpunktion f\u00fchrt meist dazu, dass wir zu ASCII zur\u00fcckkehren, aber danach ziehen wir viele Nicht-ASCII-Zeichen bereits aus dem zus\u00e4tzlichen Alphabet, ohne erneut umzuschalten).<\/p>\n

      Bonus: Wenn wir das Hilfsalphabet mit einem Pr\u00e4fix kennzeichnen 11xxxxxx<\/b><\/code> und seinen Anfangsversatz auf 0xC0<\/b><\/code>setzen, erhalten wir teilweise Kompatibilit\u00e4t mit CP1252. Mit anderen Worten, viele (aber nicht alle) westeurop\u00e4ische Texte, die in CP1252 kodiert sind, werden auch in UTF-C gleich aussehen.<\/p>\n

      Hier stellt sich tats\u00e4chlich die Frage: Wie erh\u00e4lt man aus dem Hauptalphabet ein Hilfsalphabet? Man k\u00f6nnte die gleiche Verschiebung beibehalten, aber leider spielt hier die Unicode-Struktur gegen uns. H\u00e4ufig befindet sich der Hauptteil des Alphabets nicht am Anfang des Blocks (zum Beispiel hat der russische Gro\u00dfbuchstabe \u201e\u0410\u201c den Code 0x0410<\/b><\/code>, w\u00e4hrend der kyrillische Block mit 0x0400<\/b><\/code>beginnt). Wenn wir also die ersten 64 Zeichen in den \u201eSpeicher\u201c nehmen, k\u00f6nnten wir m\u00f6glicherweise den Zugang zum Schwanzteil des Alphabets verlieren.<\/p>\n

      Um dieses Problem zu beheben, habe ich manuell einige Bl\u00f6cke durchgearbeitet, die verschiedenen Sprachen entsprechen, und f\u00fcr sie die Verschiebung des Hilfsalphabets innerhalb des Hauptalphabets angegeben. Die lateinischen Buchstaben habe ich ausnahmsweise ganz umsortiert, \u00e4hnlich wie bei base64.<\/p>\n

      \"Noch<\/p>\n

      Letzte Anpassungen<\/h2>\n

      \nLass uns zum Schluss \u00fcberlegen, wo wir noch etwas verbessern k\u00f6nnen.<\/p>\n

      Beachten wir, dass das Format 101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> es erm\u00f6glicht, Zahlen bis zu 0x1FFFFF<\/b><\/code>zu kodieren, w\u00e4hrend Unicode fr\u00fcher endet, bei 0x10FFFF<\/b><\/code>. Mit anderen Worten, der letzte Codepunkt wird dargestellt als 10110000 11111111 11111111<\/b><\/code>. Das hei\u00dft, wir k\u00f6nnen sagen, dass, wenn das erste Byte wie folgt aussieht 1011xxxx<\/b><\/code> (wo xxxx<\/b><\/code> mehr als 0), was etwas anderes bedeutet. Zum Beispiel k\u00f6nnte man dort noch 15 Zeichen hinzuf\u00fcgen, die st\u00e4ndig mit einem Byte kodiert werden k\u00f6nnen, aber ich habe mich entschieden, es anders zu machen.<\/p>\n

      Deshalb w\u00e4hlen wir einige ausgew\u00e4hlte Bereiche, die den Emojis, Hiragana und Katakana entsprechen, nummerieren sie in eine durchgehende Liste um und kodieren sie in zwei Bytes statt drei:<\/p>\n

      1011xxxx xxxxxxxx<\/b><\/code> <\/p>\n

      Super: das oben genannte Emoji \u200d\u200d\u200d\"Noch<\/a><\/noindex>, das aus 7 Codepunkten besteht, ben\u00f6tigt in UTF-8 25 Bytes, und wir haben es untergebracht in 14<\/strong> (genau zwei Bytes f\u00fcr jedes Codepunkt). \u00dcbrigens hat Habr sich geweigert, es zu verarbeiten (weder im alten noch im neuen Editor), also musste ich es als Bild einf\u00fcgen.<\/p>\n

      Lassen Sie uns ein weiteres Problem versuchen zu beheben. Wie wir wissen, ist das Hauptalphabet im Grunde die oberen 6 Bit<\/strong>, die wir im Kopf behalten und an den Code jedes n\u00e4chsten decodierten Zeichens anheften. Im Fall von chinesischen Schriftzeichen, die sich im Block 0x4E00<\/b><\/code> \u2013 0x9FFF<\/b><\/code>, handelt es sich entweder um Bit 0 oder 1. Das ist nicht sehr praktisch: Wir m\u00fcssen das Alphabet st\u00e4ndig zwischen diesen beiden Werten umschalten (d.h. jeweils drei Bytes verbrauchen). Aber wir beachten, dass wir im langen Modus aus dem Code die Anzahl der Zeichen abziehen k\u00f6nnen, die wir im kurzen Modus codieren (nach all den oben beschriebenen Tricks sind das 10240) \u2014 dann verschiebt sich der Bereich der Schriftzeichen zu 0x2600<\/b><\/code> \u2013 0x77FF<\/b><\/code>, und in diesem Fall werden in diesem gesamten Bereich die oberen 6 Bits (von 21) 0 sein. Somit werden die Sequenzen der Schriftzeichen zwei Bytes pro Schriftzeichen verwenden (was f\u00fcr einen so gro\u00dfen Bereich optimal ist), ohne dass ein Wechsel des Alphabets erforderlich ist. <\/p>\n

      Alternative L\u00f6sungen: SCSU, BOCU-1<\/h2>\n

      \nUnicode-Experten werden, allein beim Lesen des Titels des Artikels, wahrscheinlich schnell daran erinnern, dass es unter den Unicode-Standards Standard-Kompressionsschema f\u00fcr Unicode<\/a><\/noindex> (SCSU) gibt, das beschreibt, wie Daten kodiert werden, was dem in diesem Artikel beschriebenen Ansatz sehr \u00e4hnlich ist.<\/p>\n

      Ich muss ehrlich zugeben: Ich habe erst sehr sp\u00e4t, als ich schon tief in die Entwicklung meiner eigenen L\u00f6sung eingetaucht war, von seiner Existenz erfahren. H\u00e4tte ich von ihm zu Beginn gewusst, h\u00e4tte ich wahrscheinlich versucht, seine Implementierung statt meiner eigenen Herangehensweise zu entwickeln.<\/p>\n

      Was interessant ist, SCSU nutzt Ideen, die sehr \u00e4hnlich sind wie die, zu denen ich selbst gekommen bin (statt des Begriffs \u201eAlphabete\u201d spricht man dort von \u201eFenstern\u201d, und es gibt mehr davon als bei mir). Gleichzeitig hat dieses Format jedoch auch Nachteile: Es ist n\u00e4her an Kompressionsalgorithmen als an Kodierungsalgorithmen. Insbesondere bietet der Standard viele Darstellungsm\u00f6glichkeiten, sagt aber nicht, wie man die beste ausw\u00e4hlt \u2014 daf\u00fcr muss der Encoder einige Heuristiken anwenden. Ein SCSU-Encoder, der eine gute Komprimierung erzielt, wird komplexer und schwerf\u00e4lliger sein als mein Algorithmus.<\/p>\n

      Zum Vergleich habe ich eine relativ einfache SCSU-Implementierung in JavaScript \u00fcbertragen \u2014 der Codeumfang ist mit meinem UTF-C vergleichbar, aber in einigen F\u00e4llen fiel das Ergebnis um mehrere Prozentpunkte schlechter aus (manchmal kann es auch leicht besser abschneiden, aber nicht viel). Beispielsweise hat mein UTF-C Texte in Hebr\u00e4isch und Griechisch um 60 % besser kodiert als SCSU<\/strong> (wahrscheinlich wegen ihrer kompakten Alphabete).<\/p>\n

      Ich f\u00fcge hinzu, dass es neben SCSU auch eine andere Methode zur kompakten Darstellung von Unicode gibt \u2014 BOCU-1<\/a><\/noindex>, die jedoch die Kompatibilit\u00e4t mit MIME (was mir nicht erforderlich war) zum Ziel hat und einen etwas anderen Ansatz zur Kodierung verwendet. Ich habe seine Effektivit\u00e4t nicht bewertet, aber ich denke, dass sie wahrscheinlich nicht h\u00f6her als die von SCSU sein wird.<\/p>\n

      M\u00f6gliche Verbesserungen<\/h2>\n

      \nDer Algorithmus, den ich angegeben habe, ist von Design aus nicht universell (in dieser Hinsicht divergieren meine Ziele wahrscheinlich am st\u00e4rksten von den Zielen des Unicode-Konsortiums). Ich habe bereits erw\u00e4hnt, dass er haupts\u00e4chlich f\u00fcr eine Aufgabe (das Speichern eines mehrsprachigen W\u00f6rterbuchs in einem Pr\u00e4fixbaum) entwickelt wurde, und einige seiner Eigenschaften m\u00f6glicherweise f\u00fcr andere Aufgaben nicht gut geeignet sind. Aber die Tatsache, dass er kein Standard ist, k\u00f6nnte auch ein Vorteil sein \u2014 Sie k\u00f6nnen ihn leicht an Ihre Bed\u00fcrfnisse anpassen.<\/strong>.<\/p>\n

      Zum Beispiel kann offensichtlich der Zustand entfernt und die Kodierung stateless gemacht werden \u2014 einfach die Variablen nicht aktualisieren. Aus<\/b><\/code>, off<\/b><\/code> und ist21Bit<\/b><\/code> Im Encoder und Decoder. In diesem Fall wird es nicht m\u00f6glich sein, effektive Packungen von Symbolfolgen eines Alphabets zu erstellen, w\u00e4hrend die Garantie besteht, dass dasselbe Zeichen immer mit denselben Bytes codiert wird, unabh\u00e4ngig vom Kontext.<\/p>\n

      Dar\u00fcber hinaus kann der Encoder auf eine bestimmte Sprache abgestimmt werden, indem der Standardzustand ge\u00e4ndert wird \u2014 beispielsweise, indem man sich auf russische Texte orientiert und zu Beginn des Encoders und Decoders einrichtet. offs = 0x0400<\/b><\/code> und auxOffs = 0<\/b><\/code>. Dies macht insbesondere im stateless Modus Sinn. Insgesamt wird es \u00e4hnlich sein wie die Verwendung einer alten 8-Bit-Kodierung, jedoch ohne die M\u00f6glichkeit, bei Bedarf Zeichen aus dem gesamten Unicode einzuf\u00fcgen.<\/p>\n

      Ein weiterer Nachteil, der bereits erw\u00e4hnt wurde, ist, dass es im umfangreichen Text, der in UTF-C codiert ist, keine schnelle M\u00f6glichkeit gibt, die Grenzmarkierung eines Zeichens zu finden, das sich am n\u00e4chsten zu einem beliebigen Byte befindet. Wenn Sie die letzten, sagen wir, 100 Bytes aus dem codierten Puffer abschneiden, riskieren Sie, M\u00fcll zu erhalten, mit dem nichts anzufangen ist. Die Kodierung ist nicht f\u00fcr die Speicherung mehrgigagro\u00dfer Protokolldateien ausgelegt, aber insgesamt kann dies behoben werden. Byte 0xBF<\/b><\/code> sollte niemals als erstes Byte auftreten (kann aber das zweite oder dritte sein). Daher kann beim Kodieren eine Sequenz eingef\u00fcgt werden. 0xBF 0xBF 0xBF<\/b><\/code> alle, sagen wir, 10 Kb \u2014 dann reicht es aus, einen gew\u00e4hlten Abschnitt zu scannen, um die Grenze zu finden, bis ein solcher Marker gefunden wird. Hinter dem letzten 0xBF<\/b><\/code> wird garantiert der Beginn des Zeichens sein. (Beim Dekodieren muss diese Sequenz aus drei Bytes nat\u00fcrlich ignoriert werden.)<\/p>\n

      Zusammenfassend<\/h2>\n

      \nWenn Sie es bis hierher gelesen haben \u2014 herzlichen Gl\u00fcckwunsch! Ich hoffe, Sie haben, wie ich, etwas Neues gelernt (oder Erinnerungen an altes Wissen aufgefrischt) \u00fcber den Aufbau von Unicode.<\/p>\n

      \"Noch
      \nDemonstrationsseite. Am Beispiel Hebr\u00e4isch sind die Vorteile sowohl gegen\u00fcber UTF-8 als auch gegen\u00fcber SCSU zu erkennen.<\/i><\/p>\n

      Die oben beschriebenen \u00dcberlegungen sollten nicht als Eingriff in Standards angesehen werden. Insgesamt bin ich jedoch mit den Ergebnissen meiner Arbeit zufrieden und teile sie gerne. teilen<\/a><\/noindex>: Beispielsweise hat die JS-Bibliothek in minifizierter Form nur 1710 Bytes (und nat\u00fcrlich keine Abh\u00e4ngigkeiten). Wie bereits erw\u00e4hnt, kann ihre Funktionsweise auf der Demo-Seite<\/a><\/noindex> eingesehen werden (dort gibt es auch eine Sammlung von Texten, mit denen sie mit UTF-8 und SCSU verglichen werden kann).<\/p>\n

      Zum Schluss m\u00f6chte ich noch einmal auf die F\u00e4lle hinweisen, in denen UTF-C verwendet werden sollte. nicht<\/b>:<\/p>\n

      Schauen wir uns die Unicode-Bl\u00f6cke an, die jetzt drei Bytes erfordern. In erster Linie sind dies, wie bereits erw\u00e4hnt, chinesische Schriftzeichen \u2014 aber damit l\u00e4sst sich schwer etwas machen, es gibt 21.000. Aber auch Hiragana und Katakana haben es dorthin geschafft \u2014 und davon gibt es nicht mehr so viele, weniger als zweihundert. Und da wir gerade die Japaner erw\u00e4hnt haben \u2014 dort liegen auch Emojis (tats\u00e4chlich sind sie \u00fcberall im Unicode verteilt, aber die Hauptbl\u00f6cke liegen im Bereich 0x1F300<\/b><\/code> \u2013 0x1FBFF<\/b><\/code>). Wenn man bedenkt, dass es jetzt Emojis gibt, die aus mehreren Codepunkten bestehen (zum Beispiel das Emoji \u200d\u200d\u200d\"Noch<\/a><\/noindex> besteht aus insgesamt 7 Codes!), dann wird es wirklich schade, f\u00fcr jedes drei Bytes auszugeben (7\u00d73 = 21 Bytes f\u00fcr ein Symbol, das ist der Wahnsinn).<\/p>\n