{"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":"Ein weiteres Fahrrad: Wir speichern Unicode-Zeichenfolgen 30-60 % kompakter als UTF-8.","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Ein
\n
\nWenn Sie ein Entwickler sind und vor der Wahl einer Codierung stehen, ist Unicode fast immer die richtige Wahl. Die spezifische Darstellungsweise h\u00e4ngt vom Kontext ab, aber meistens gibt es auch hier eine universelle Antwort \u2013 UTF-8. Es ist gut, weil es alle Unicode-Zeichen verwendet, ohne zu viel<\/em> Byte in den meisten F\u00e4llen zu verschwenden. Allerdings bedeutet \u201enicht zu viel\u201c f\u00fcr Sprachen, die nicht nur das lateinische Alphabet verwenden, mindestens zwei Byte pro Zeichen<\/strong>. Gibt es eine bessere L\u00f6sung, ohne auf pr\u00e4historische Codierungen zur\u00fcckzugreifen, die uns auf nur 256 verf\u00fcgbare Zeichen beschr\u00e4nken?<\/p>\n

Im Folgenden m\u00f6chte ich meine Versuche vorstellen, diese Frage zu beantworten und eine relativ einfache Algorithmus-Implementierung zu entwickeln, die es erm\u00f6glicht, Zeichenfolgen in den meisten Sprachen der Welt zu speichern, ohne die \u00dcberfl\u00fcssigkeit hinzuzuf\u00fcgen, die in UTF-8 vorhanden ist.<\/a><\/noindex><\/p>\n

Haftungsausschluss.<\/i> Zun\u00e4chst einige wichtige Vorbemerkungen: Die beschriebene L\u00f6sung wird nicht als universeller Ersatz f\u00fcr UTF-8 angeboten<\/strong>, sie eignet sich nur f\u00fcr eine enge Liste von F\u00e4llen (dar\u00fcber sp\u00e4ter), und sie darf auf keinen Fall f\u00fcr die Kommunikation mit externen APIs verwendet werden (die davon nichts wissen). In den meisten F\u00e4llen sind Algorithmen zur verlustfreien Kompression (z. B. deflate) besser geeignet, um gro\u00dfe Mengen an Textdaten kompakt zu speichern. Dar\u00fcber hinaus habe ich w\u00e4hrend der Erstellung meiner L\u00f6sung einen bestehenden Standard im Unicode gefunden, der dasselbe Problem l\u00f6st \u2013 er ist etwas komplexer (und oft schlechter), aber er ist dennoch ein akzeptierter Standard und kein zusammengezimmerter Notbehelf. Dar\u00fcber werde ich ebenfalls berichten.<\/p>\n

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

\nZuerst ein paar Worte dar\u00fcber, was Unicode<\/strong> und UTF-8<\/strong>.<\/p>\n

Wie bekannt ist, waren fr\u00fcher 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\u00fcckkehren, wird die ASCII-Codierung sogar auf 7 Bits beschr\u00e4nkt, sodass das h\u00f6chstwertige Bit in ihrer Byte-Darstellung null ist und die meisten 8-Bit-Codierungen mit ihr kompatibel sind (sie unterscheiden sich nur im \u201eoberen\u201c Bereich, wo das h\u00f6chstwertige Bit eins ist).<\/p>\n

Wie unterscheidet sich Unicode von den anderen Kodierungen und warum sind damit sofort viele 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 Entsprechung zwischen Zeichen (und in einigen F\u00e4llen \u2013 einzelnen Komponenten von Zeichen) und ihren Nummern. Und die m\u00f6glichen Nummern in diesem Standard sind sehr zahlreich \u2013 von 0x00<\/b><\/code> bis 0x10FFFF<\/b><\/code> (1 114 112 St\u00fcck). Wenn wir eine Zahl in diesem Bereich einer Variablen zuweisen wollten, w\u00fcrden uns weder 1 noch 2 Bytes ausreichen. Und da unsere Prozessoren f\u00fcr die Arbeit mit dreibyteigen Zahlen nicht ausgelegt sind, w\u00e4ren wir gezwungen, ganze 4 Bytes f\u00fcr ein Zeichen zu verwenden! Das ist UTF-32, aber gerade wegen dieser \u201eVerschwendung\u201c erfreut sich dieses Format nicht gro\u00dfer Beliebtheit.<\/p>\n

Gl\u00fccklicherweise sind die Zeichen in Unicode nicht zuf\u00e4llig angeordnet. Ihre Menge ist in 17 \u201eEbenen<\/em>\u201c unterteilt, von denen jede 65536 (\u201e0x10000<\/b><\/code>) \u00abCodepunkte<\/em>\u201c enth\u00e4lt. Der Begriff \u201eCodepunkt\u201c bedeutet hier einfach die Nummer eines Zeichens<\/em>, die ihm von Unicode zugewiesen wurde. Aber, wie bereits erw\u00e4hnt, sind in Unicode nicht nur einzelne Zeichen durchnummeriert, sondern auch deren Komponenten und Steuerzeichen (und manchmal entspricht dem Nummer gar nichts \u2013 m\u00f6glicherweise nur vor\u00fcbergehend, aber das ist f\u00fcr uns nicht so wichtig), daher ist es genauer, immer von der Anzahl der Nummern und nicht von den Zeichen zu sprechen. Um der K\u00fcrze willen werde ich jedoch im Folgenden h\u00e4ufig das Wort \u201eZeichen\u201c verwenden, wobei ich den Begriff \u201eCodepunkt\u201c meine.<\/p>\n

\"Ein
\nEbenen von Unicode. Wie zu sehen ist, ist der gr\u00f6\u00dfte Teil (die Ebenen von 4 bis 13) noch ungenutzt.<\/i><\/p>\n

Das Bemerkenswerteste ist, dass der gesamte wesentliche \"Kern\" in der Null-Ebene liegt, die \"Basic Multilingual Plane<\/em>\" genannt wird. Wenn die Zeile Text in einer der modernen Sprachen (einschlie\u00dflich Chinesisch) enth\u00e4lt, wird diese Ebene nicht \u00fcberschritten. Aber man kann auch den Rest von Unicode nicht abschneiden \u2013 zum Beispiel befinden sich Emojis haupts\u00e4chlich am Ende der n\u00e4chsten Ebene, \"Supplementary Multilingual Plane<\/em>\" (sie erstreckt sich von 0x10000<\/b><\/code> bis 0x1FFFF<\/b><\/code>). Daher funktioniert UTF-16 so: Alle Zeichen, die in Basic Multilingual Plane<\/em>, werden \u201ewie sie sind\u201c kodiert, mit der entsprechenden zweibyte-Zahl. Einige Zahlen in diesem Bereich stellen jedoch \u00fcberhaupt keine konkreten Symbole dar, sondern weisen darauf hin, dass nach diesem Byte-Paar ein weiteres betrachtet werden muss \u2013 kombiniert man die Werte dieser vier Bytes, ergibt sich eine Zahl, die den gesamten zul\u00e4ssigen Unicode-Bereich abdeckt. Diese Darstellung wird \u201eSurrogatpaare\u201c genannt \u2013 vielleicht haben Sie schon dar\u00fcber geh\u00f6rt.<\/p>\n

Somit ben\u00f6tigt UTF-16 zwei oder (in sehr seltenen F\u00e4llen) vier Bytes f\u00fcr einen \u201eCodepunkt\u201c. Das ist besser, als st\u00e4ndig vier Bytes zu verwenden, aber die lateinischen Buchstaben (und andere ASCII-Symbole) verbrauchen bei dieser Kodierung die H\u00e4lfte des ben\u00f6tigten Raums f\u00fcr Nullen. UTF-8 soll das verbessern: In ihm belegt ASCII wie fr\u00fcher nur ein Byte; die Codes von 0x80<\/b><\/code> bis 0x7FF<\/b><\/code> \u2013 zwei Bytes; von 0x800<\/b><\/code> bis 0xFFFF<\/b><\/code> \u2013 drei, und von 0x10000<\/b><\/code> bis 0x10FFFF<\/b><\/code> \u2013 vier. Einerseits hat es sich f\u00fcr das Lateinische gut entwickelt: Die Kompatibilit\u00e4t mit ASCII ist zur\u00fcckgekehrt, und die Verteilung ist gleichm\u00e4\u00dfiger \u201everteilt\u201c von 1 bis 4 Bytes. Aber Alphabete, die vom Lateinischen abweichen, haben leider keinen Vorteil im Vergleich zu UTF-16, und viele ben\u00f6tigen nun sogar drei Bytes anstelle von zwei \u2013 der von der zweibyte-Darstellung abgedeckte Bereich hat sich um das 32-Fache verkleinert, von 0xFFFF<\/b><\/code> bis 0x7FF<\/b><\/code>, und darin sind weder Chinesisch noch zum Beispiel Georgisch enthalten. Kyrillisch und f\u00fcnf weitere Alphabete \u2013 hurra \u2013 haben Gl\u00fcck, 2 Byte pro Zeichen.<\/p>\n

Wie kommt das zustande? Lassen Sie uns ansehen, wie UTF-8 die Codes der Zeichen darstellt:
\n\"Ein
\nDirekt zur Darstellung der Zahlen werden hier die Bits verwendet, die durch das Zeichen x<\/b><\/code>gekennzeichnet sind. Es ist zu erkennen, dass in der zweibyte-Darstellung nur 11 dieser Bits (von 16) vorhanden sind. Die f\u00fchrenden Bits haben hier nur eine Dienstfunktion. Im Fall der vierbyte-Darstellung sind ganze 21 Bits aus 32 f\u00fcr die Codierungspunkte reserviert \u2013 hier h\u00e4tten eigentlich auch drei Bytes (die insgesamt 24 Bits ergeben) ausgereicht, aber die Dienstmarker verbrauchen zu viel.<\/p>\n

Ist das schlecht? Eigentlich nicht. Einerseits \u2014 wenn wir gro\u00dfen Wert auf den ben\u00f6tigten Speicherplatz legen, haben wir Komprimierungsalgorithmen, die leicht alle \u00fcberfl\u00fcssige Entropie und Redundanz beseitigen k\u00f6nnen. 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 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\u00f6tzlich ein kleines Ende von einer gro\u00dfen Zeichenkette abschneiden wollen, ohne sie von Anfang an zu dekodieren (oder einen Teil der Information nach einem besch\u00e4digten Abschnitt wiederherzustellen) \u2014 ist es nicht schwierig, die Verschiebung zu finden, an der ein Zeichen beginnt (es reicht aus, Bytes mit einem bitweisen Pr\u00e4fix zu \u00fcberspringen. 10<\/b><\/code>).<\/p>\n

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

\nGleichzeitig gibt es gelegentlich Situationen, in denen Komprimierungsalgorithmen wie deflate schlecht anwendbar sind und man m\u00f6chte eine kompakte Speicherung von Zeichenketten erreichen. Ich pers\u00f6nlich bin auf ein solches Problem gesto\u00dfen, als ich \u00fcber den Aufbau nachdachte eines komprimierten Pr\u00e4fixbaums<\/a><\/noindex> f\u00fcr ein gro\u00dfes W\u00f6rterbuch, das W\u00f6rter in beliebigen Sprachen umfasst. Einerseits \u2014 jedes Wort ist sehr kurz, daher w\u00e4re es ineffektiv, es zu komprimieren. Andererseits \u2014 die Baumimplementierung, die ich in Betracht zog, war darauf ausgelegt, dass jedes Byte der gespeicherten Zeichenkette eine separate Baumspitze erzeugt, sodass es sehr n\u00fctzlich war, ihre Anzahl zu minimieren. In meiner Bibliothek Az.js<\/a><\/noindex> (wie auch in pymorphy2<\/a><\/noindex>, auf dem sie basiert) wird ein solches Problem einfach gel\u00f6st \u2014 die in DAWG<\/a><\/noindex>-W\u00f6rterbuch verpackten Zeichenketten werden dort in guter alter CP1251<\/a><\/noindex>gespeichert. Aber wie man leicht verstehen kann, funktioniert das gut nur f\u00fcr ein begrenztes Alphabet \u2014 eine Zeichenkette auf Chinesisch kann in ein solches W\u00f6rterbuch nicht eingegeben werden.<\/p>\n

Ich m\u00f6chte auch einen weiteren unangenehmen Punkt erw\u00e4hnen, 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\u00f6ren, nicht aufeinander folgen, sondern durch ein paar Bits 10<\/b><\/code> dazwischen unterbrochen sind: 110xxxxx 10xxxxxx<\/b><\/code>. Deshalb, wenn die unteren 6 Bits des zweiten Bytes (d.h. ein \u00dcberlauf auftritt, 10111111<\/b><\/code> \u2192 10000000<\/b><\/code>) \u00fcberlaufen, \u00e4ndert sich auch das erste Byte. Es stellt sich heraus, dass der Buchstabe \u201e\u043f\u201c durch Bytes dargestellt wird. 0xD0 0xBF<\/b><\/code>, und der folgende \u201er\u201c \u2014 ist bereits 0xD1 0x80<\/b><\/code>. Im Pr\u00e4fixbaum f\u00fchrt dies zur Teilung des Elternknotens in zwei \u2014 eine f\u00fcr das Pr\u00e4fix 0xD0<\/b><\/code>, und eine andere f\u00fcr 0xD1<\/b><\/code> (obwohl das gesamte Kyrillisch nur im zweiten Byte kodiert werden k\u00f6nnte).<\/p>\n

Was ich erreicht habe<\/h2>\n

\nMit dieser Aufgabe konfrontiert, beschloss ich, ein wenig mit Bits zu \u00fcben und mich gleichzeitig besser mit der Struktur von Unicode vertraut zu machen. Das Ergebnis war das Kodierungsformat UTF-C (\u201eC\u201c steht f\u00fcr compact<\/em>), das nicht mehr als 3 Byte f\u00fcr einen Codepunkt verwendet und sehr oft nur ein zus\u00e4tzliches Byte f\u00fcr die gesamte kodierte Zeile<\/strong>. Dies f\u00fchrt dazu, dass dieses Kodierungsverfahren in vielen nicht-ASCII-Alphabets 30-60% kompakter ist als UTF-8<\/strong>.<\/p>\n

Ich habe Beispiele zur Implementierung der Kodierungs- und Dekodierungsalgorithmen in Form von Bibliotheken in JavaScript und Go<\/a><\/noindex>, die Sie frei in Ihrem Code verwenden k\u00f6nnen. Aber ich m\u00f6chte dennoch betonen, dass dieses Format in gewisser Hinsicht ein \u201eFahrrad\u201c bleibt, und ich empfehle nicht, es zu verwenden , ohne zu verstehen, wof\u00fcr Sie es ben\u00f6tigen<\/strong>. Es handelt sich schlie\u00dflich mehr um ein Experiment als um eine ernsthafte \u201eVerbesserung von UTF-8\u201c. Dennoch ist der Code dort sauber, pr\u00e4gnant, mit vielen Kommentaren und Tests abgedeckt.<\/p>\n

\"Ein
\nErgebnisse der Testausf\u00fchrung und Vergleich mit UTF-8<\/i><\/p>\n

Ich habe auch eine Demo-Seite<\/a><\/noindex>, auf der die Funktionsweise des Algorithmus bewertet werden kann, und danach werde ich genauer auf seine Prinzipien und den Entwicklungsprozess eingehen.<\/p>\n

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

\nAls Grundlage habe ich nat\u00fcrlich UTF-8 genommen. Das erste und offensichtlichste, was man darin \u00e4ndern kann, ist die Anzahl der Steuerbits in jedem Byte zu reduzieren. Zum Beispiel beginnt das erste Byte in UTF-8 immer entweder mit 0<\/b><\/code>, oder mit 11<\/b><\/code> \u2014 und das Pr\u00e4fix 10<\/b><\/code> gibt es nur bei den folgenden Bytes. Lassen Sie uns das Pr\u00e4fix ersetzen 11<\/b><\/code> auf 1<\/b><\/code>, und bei den folgenden Bytes entfernen wir die Pr\u00e4fixe ganz. Was kommt 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

Stopp, und wo ist die vier-Byte-Darstellung geblieben? Diese ist nicht mehr notwendig \u2014 bei der Verwendung von drei Bytes haben wir jetzt 21 Bit zur Verf\u00fcgung, und das reicht f\u00fcr alle Zahlen bis 0x10FFFF<\/b><\/code>.<\/p>\n

Wof\u00fcr haben wir hier bezahlt? Das Wichtigste \u2014 die Erkennung der Grenzwerte von Zeichen an beliebiger Stelle im Puffer. Wir k\u00f6nnen nicht auf ein beliebiges Byte zeigen und von dort den Beginn des n\u00e4chsten Zeichens finden. Das ist eine Einschr\u00e4nkung unseres Formats, aber in der Praxis tritt diese Notwendigkeit nicht h\u00e4ufig auf. Normalerweise sind wir in der Lage, den Puffer von Anfang an zu durchlaufen (insbesondere wenn es um kurze Zeilen geht).<\/p>\n

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<\/b><\/code>. Die Chinesen haben Pech (ihre Schriftzeichen liegen haupts\u00e4chlich im Bereich von 0x4E00<\/b><\/code> bis 0x9FFF<\/b><\/code>), aber den Georgiern und vielen anderen V\u00f6lkern geht es fr\u00f6hlicher \u2014 ihre Sprachen passen ebenfalls in 2 Byte pro Zeichen.<\/p>\n

Wir aktivieren den Encoder.<\/h2>\n

\nLass uns jetzt \u00fcber die Eigenschaften der Zeichenfolgen selbst nachdenken. Im W\u00f6rterbuch befinden sich meistens W\u00f6rter, die mit Zeichen eines Alphabets geschrieben sind, und das gilt auch f\u00fcr viele andere Texte. Es w\u00e4re 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.<\/p>\n

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

\"Ein
\nBlock, 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 \u00fcber 128 Codepunkte des Blocks verstreut.<\/i><\/p>\n

Die Anfangswerte der Bl\u00f6cke und deren Gr\u00f6\u00dfen sind immer Vielfache von 16 \u2014 dies wurde einfach der Praktikabilit\u00e4t halber gemacht. Zudem beginnen viele Bl\u00f6cke bei Werten, die Vielfache von 128 oder sogar 256 sind \u2014 zum Beispiel belegt das Grundmodul der kyrillischen Schrift 256 Byte ab 0x0400<\/b><\/code> bis 0x04FF<\/b><\/code>. Das ist ziemlich praktisch: Wenn wir einmal das Pr\u00e4fix 0x04<\/b><\/code>gespeichert haben, kann jedes kyrillische Zeichen mit einem Byte codiert werden. Allerdings verlieren wir dadurch die M\u00f6glichkeit, zu ASCII (und zu allen anderen Zeichen \u00fcberhaupt) zur\u00fcckzukehren. Daher machen wir Folgendes:<\/p>\n

    \n
  1. Zwei Byte 10yyyyyy yxxxxxxx<\/b><\/code> bezeichnen nicht nur ein Zeichen mit der Nummer yyyyyy yxxxxxxx<\/b><\/code>, sondern \u00e4ndern auch das aktuelle Alphabet<\/em> auf yyyyyy y0000000<\/b><\/code> (d.h. wir merken uns alle Bits au\u00dfer den niederwertigsten 7 Bit.<\/strong>);<\/li>\n
  2. Ein Byte 0xxxxxxx<\/b><\/code> stellt 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\u00e4ndert haben, betr\u00e4gt der Versatz null, sodass wir die Kompatibilit\u00e4t mit ASCII beibehalten haben.<\/li>\n<\/ol>\n

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

      \n
    1. Drei Byte 110yyyyy yxxxxxxx xxxxxxxx<\/b><\/code> bezeichnen ein Zeichen mit der Nummer yyyyyy yxxxxxxx xxxxxxxx<\/b><\/code>, \u00e4ndern das aktuelle Alphabet<\/em> auf yyyyyy y0000000 00000000<\/b><\/code> (wir merken uns alles, au\u00dfer den niederwertigsten 15 Bit<\/strong>), und setzen ein Flag, dass wir uns jetzt in der langen<\/em> Im Modus (bei der R\u00fcckwechsel zum zwei Byte-Code setzen wir dieses Flag zur\u00fcck);<\/li>\n
    2. Zwei Byte 0xxxxxxx xxxxxxxx<\/b><\/code> Im 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).<\/li>\n<\/ol>\n

      \nKlingt gut: Solange wir Zeichen aus dem gleichen 7-Bit-Bereich des Unicode codieren m\u00fcssen, verwenden wir 1 zus\u00e4tzliches Byte am Anfang und nur ein Byte f\u00fcr jedes Zeichen.<\/p>\n

      \"Ein
      \nArbeit einer der fr\u00fchen Versionen. \u00dcberholt bereits h\u00e4ufig UTF-8, hat aber noch Verbesserungsbedarf.<\/i><\/p>\n

      Was hat sich verschlechtert? Erstens haben wir jetzt einen Zustand, n\u00e4mlich die Verschiebung des aktuellen Alphabets<\/em> und das Flag des langen Modus<\/em>. Dies schr\u00e4nkt uns zus\u00e4tzlich ein: Jetzt k\u00f6nnen dieselben Zeichen in verschiedenen Kontexten unterschiedlich kodiert werden. Beispielsweise muss die Suche nach Teilstrings bereits unter Ber\u00fccksichtigung 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\u00dflich Leerzeichen) \u2014 sie erfordert einen weiteren Wechsel des Alphabets zu 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 etwas mit unseren Bit-Pr\u00e4fixen \u00e4ndern, indem wir noch eins zu den drei oben beschriebenen hinzuf\u00fcgen:<\/p>\n

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

      \"Ein
      \n
      \nNun hat es in der Zwei-Byte-Darstellung ein verf\u00fcgbares Bit weniger \u2014 es passen Codepunkte bis zu 0x1FFF<\/b><\/code>, nicht 0x3FFF<\/b><\/code>. 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\u00e4lligste Verlust \u2014 ist weggefallen       Hiragana<\/a><\/noindex> und Katakana<\/a><\/noindex>, die Japaner sind traurig.<\/p>\n

      Was ist also 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 wechseln, wird ein Teil des alten Alphabets zum Hilfsalphabet. Zum Beispiel, wenn wir von ASCII zu Kyrillisch wechseln \u2014 nun sind im \u201eVorrat\u201c 64 Zeichen enthalten, die Latein, Ziffern, Leerzeichen und Komma<\/strong> die h\u00e4ufigsten Einf\u00fcgungen in nicht-ASCII-Texten sind. Gehen wir zur\u00fcck zu ASCII \u2014 wird der Hauptteil des Kyrillischen zum Hilfsalphabet.<\/p>\n

      Durch den Zugang zu zwei Alphabeten k\u00f6nnen wir mit einer gro\u00dfen Menge von Texten umgehen, ohne die Kosten f\u00fcr das Umschalten der Alphabete zu erh\u00f6hen (Interpunktion f\u00fchrt meist dazu, dass wir wieder in ASCII zur\u00fcckkehren, aber danach k\u00f6nnen wir viele nicht-ASCII-Zeichen bereits aus dem zus\u00e4tzlichen Alphabet beziehen, ohne erneut umzuschalten).<\/p>\n

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

      Hier entsteht jedoch ein Problem: Wie erh\u00e4lt man das Hilfsalphabet aus dem Hauptalphabet? Man k\u00f6nnte 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\u00dfbuchstabe \u201e\u0410\u201c den Code 0x0410<\/b><\/code>, w\u00e4hrend der kyrillische Block bei 0x0400<\/b><\/code>beginnt). Daher k\u00f6nnte es sein, dass wir beim Ausw\u00e4hlen der ersten 64 Zeichen m\u00f6glicherweise den Zugang zum hinteren Teil des Alphabets verlieren.<\/p>\n

      Um dieses Problem zu l\u00f6sen, habe ich manuell einige Bl\u00f6cke durchlaufen, die verschiedenen Sprachen entsprechen, und f\u00fcr sie den Versatz des Hilfsalphabets innerhalb des Hauptalphabets angegeben. Die Lateinbuchstaben habe ich ausnahmsweise in einer Weise umsortiert, die \u00e4hnlich wie base64 ist.<\/p>\n

      \"Ein<\/p>\n

      Letzte Schliffe<\/h2>\n

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

      Wir stellen fest, dass das Format 101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> es erm\u00f6glicht, Zahlen bis zu 0x1FFFFF<\/b><\/code>, und Unicode endet fr\u00fcher, bei 0x10FFFF<\/b><\/code>. Mit anderen Worten, der letzte Codepunkt wird als 10110000 11111111 11111111<\/b><\/code>dargestellt. Daher k\u00f6nnen wir sagen, dass, wenn das erste Byte wie folgt aussieht 1011xxxx<\/b><\/code> (wo xxxx<\/b><\/code> gr\u00f6\u00dfer als 0 ist), es 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 handhaben.<\/p>\n

      Deshalb w\u00e4hlen wir einige ausgew\u00e4hlte Bereiche aus, die Emojis, Hiragana und Katakana entsprechen, nummerieren sie in einer fortlaufenden Liste um und kodieren sie in zwei Byte statt drei:<\/p>\n

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

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

      Versuchen wir, ein weiteres Problem zu beheben. Wie wir uns erinnern, ist das Hauptalphabet im Grunde genommen die oberen 6 Bits<\/strong>, die wir im Kopf behalten und an den Code jedes weiteren zu dekodierenden Zeichens anh\u00e4ngen. Bei den chinesischen Schriftzeichen, die sich im Block 0x4E00<\/b><\/code> \u2013 0x9FFF<\/b><\/code>, ist es entweder Bit 0 oder 1. Das ist nicht sehr praktisch: Wir m\u00fcssen das Alphabet st\u00e4ndig 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\u00f6nnen, die wir im kurzen Modus kodieren (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) gleich 0 sein. Somit werden die Sequenzen der Schriftzeichen je zwei Byte pro Zeichen verwenden (was optimal f\u00fcr so einen gro\u00dfen Bereich ist), ohne dass ein Wechsel des Alphabets erforderlich ist. <\/p>\n

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

      \nKenner von Unicode werden wahrscheinlich, noch bevor sie den Titel des Artikels gelesen haben, hastig daran erinnern, dass es unter den Unicode-Standards Standard Compression Scheme for Unicode<\/a><\/noindex> (SCSU) gibt, das einen Kodierungsansatz beschreibt, der dem in diesem Artikel beschriebenen sehr \u00e4hnlich ist.<\/p>\n

      Ich gestehe ehrlich: Von seiner Existenz habe ich erst erfahren, als ich bereits tief in das Schreiben meiner L\u00f6sung eingetaucht war. W\u00fcsste ich von ihm gleich zu Beginn, h\u00e4tte ich wahrscheinlich versucht, seine Implementierung statt meiner eigenen Herangehensweise zu schreiben.<\/p>\n

      Interessanterweise verwendet SCSU Ideen, die sehr \u00e4hnlich sind denjenigen, zu denen ich selbst gekommen bin (anstatt des Begriffs \u201eAlphabete\u201c werden dort \u201eFenster\u201c verwendet, und es sind mehr verf\u00fcgbar als bei mir). Gleichzeitig hat dieses Format auch Nachteile: Es ist etwas n\u00e4her an Komprimierungsalgorithmen als an Kodierung. Insbesondere bietet der Standard viele Darstellungsformen, sagt aber nicht, wie man die optimale ausw\u00e4hlt \u2013 hierzu muss der Encoder einige Heuristiken anwenden. Somit wird der SCSU-Encoder, der eine gute Packung bietet, komplexer und umst\u00e4ndlicher sein als mein Algorithmus.<\/p>\n

      Zum Vergleich habe ich eine relativ einfache Implementierung von SCSU in JavaScript portiert \u2013 in Bezug auf den Codeumfang war sie vergleichbar mit meinem UTF-C, zeigte aber in einigen F\u00e4llen Ergebnisse, die um mehrere Prozents\u00e4tze schlechter waren (manchmal kann sie auch etwas besser sein, aber nicht viel). Zum Beispiel kodierte UTF-C Texte in Hebr\u00e4isch und Griechisch um 60 % besser als SCSU<\/strong> (wahrscheinlich wegen ihrer kompakten Alphabete).<\/p>\n

      Ich m\u00f6chte zus\u00e4tzlich erw\u00e4hnen, dass es neben SCSU auch eine andere M\u00f6glichkeit zur kompakten Darstellung von Unicode gibt \u2013 BOCU-1<\/a><\/noindex>, aber sie zielt auf die Kompatibilit\u00e4t mit MIME ab (was ich nicht ben\u00f6tigte) und verwendet einen etwas anderen Ansatz zur Kodierung. Ich habe ihre Effizienz nicht bewertet, aber ich glaube nicht, dass sie h\u00f6her sein wird als die von SCSU.<\/p>\n

      M\u00f6gliche Verbesserungen<\/h2>\n

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

      Zum Beispiel kann man offensichtlich den Zustand eliminieren und die Kodierung statuslos machen \u2013 einfach die Variablen im Encoder und Decoder nicht aktualisieren. In diesem Fall wird es nicht m\u00f6glich sein, Folgen von Zeichen eines Alphabets effizient zu verpacken, daf\u00fcr gibt es jedoch die Garantie, dass dasselbe Zeichen immer mit denselben Bytes kodiert wird, unabh\u00e4ngig vom Kontext. Abg\u00e4nge<\/b><\/code>, auxOffs<\/b><\/code> und is21Bit<\/b><\/code> Dar\u00fcber hinaus kann man den Encoder auf eine bestimmte Sprache zuschneiden, indem man den Standardzustand \u00e4ndert \u2013 zum Beispiel, orientiert an russischen Texten, den Anfang des Encoders und Decoders entsprechend einstellen.<\/p>\n

      Dar\u00fcber hinaus kann der Encoder f\u00fcr eine bestimmte Sprache angepasst werden, indem der Standardstatus ge\u00e4ndert wird \u2013 zum Beispiel kann man, orientiert an russischen Texten, zu Beginn des Encoders und Decoders eine entsprechende Einstellung vornehmen. offs = 0x0400<\/b><\/code> und auxOffs = 0<\/b><\/code>. Dies macht insbesondere im stateless Modus Sinn. Im Gro\u00dfen und Ganzen wird es der Verwendung des alten achtbitigen Codes \u00e4hnlich sein, nur dass es nicht die M\u00f6glichkeit ausschlie\u00dft, nach Bedarf Zeichen aus dem gesamten Unicode einzuf\u00fcgen.<\/p>\n

      Ein weiterer Nachteil, den ich zuvor erw\u00e4hnt habe \u2013 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\u00e4chsten ist. Wenn Sie die letzten, sagen wir, 100 Bytes vom codierten Puffer abschneiden, riskieren Sie, M\u00fcll zu erhalten, mit dem Sie nichts anfangen k\u00f6nnen. Die Kodierung ist nicht f\u00fcr die Speicherung von mehreren Gigabyte an Logs ausgelegt, aber grunds\u00e4tzlich kann das behoben werden. Byte 0xBF<\/b><\/code> sollte niemals als erstes Byte auftreten (kann jedoch als zweites oder drittes auftreten). Daher kann bei der Codierung eine Sequenz eingef\u00fcgt werden 0xBF 0xBF 0xBF<\/b><\/code> alle, sagen wir, 10 KB \u2013 dann reicht es, den gew\u00fcnschten Abschnitt zu scannen, um einen \u00e4hnlichen Marker zu finden, wenn n\u00f6tig. Nach dem letzten 0xBF<\/b><\/code> wird garantiert der Anfang eines Zeichens folgen. (Beim Dekodieren muss diese Sequenz von drei Bytes selbstverst\u00e4ndlich ignoriert werden.)<\/p>\n

      Zusammenfassend<\/h2>\n

      \nWenn Sie bis hierher gelesen haben \u2013 herzlichen Gl\u00fcckwunsch! Ich hoffe, Sie haben wie ich etwas Neues gelernt (oder Altes aufgefrischt) \u00fcber die Funktionsweise von Unicode.<\/p>\n

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

      Man sollte die oben beschriebenen \u00dcberlegungen nicht als Angriff auf die Standards betrachten. Allerdings bin ich insgesamt mit den Ergebnissen meiner Arbeiten zufrieden, deshalb freue ich mich, sie zu teilen<\/a><\/noindex>: zum Beispiel wiegt die JS-Bibliothek in minimierter Form nur 1710 Bytes (und hat nat\u00fcrlich keine Abh\u00e4ngigkeiten). Wie ich oben erw\u00e4hnt habe, kann man sich mit ihrer Funktionalit\u00e4t auf der Demo-Seite<\/a><\/noindex> vertraut machen (dort gibt es auch eine Reihe von Texten, mit denen man sie mit UTF-8 und SCSU vergleichen kann).<\/p>\n

      Zum Schluss m\u00f6chte ich noch einmal auf die F\u00e4lle hinweisen, in denen die Verwendung von UTF-C nicht ratsam ist<\/b>:<\/p>\n

      Schauen wir uns nun die Unicode-Bl\u00f6cke an, die derzeit drei Bytes ben\u00f6tigen. Im Allgemeinen sind das, wie bereits erw\u00e4hnt, chinesische Schriftzeichen \u2014 aber damit ist es schwierig, etwas zu machen, es sind 21.000. Aber auch Hiragana und Katakana sind dort gelandet \u2014 und von denen gibt es schon weniger, weniger als zweihundert. Und da wir gerade die Japaner erw\u00e4hnt haben \u2014 dort liegen auch Emojis (tats\u00e4chlich sind sie \u00fcberall in Unicode verstreut, aber die Hauptbl\u00f6cke befinden sich im Bereich 0x1F300<\/b><\/code> \u2013 0x1FBFF<\/b><\/code>). Wenn man bedenkt, dass es jetzt Emojis gibt, die aus mehreren Codepunkten bestehen (zum Beispiel Emoji \u200d\u200d\u200d\"Ein<\/a><\/noindex> besteht aus 7 Codes!), dann ist es wirklich schade, f\u00fcr jeden drei Byte zu verschwenden (7\u00d73 = 21 Byte f\u00fcr ein Zeichen, das ist ein Albtraum).<\/p>\n