{"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\/nl\/blog\/administrirovanie\/eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8","title":{"rendered":"Nog een fiets: we slaan Unicode-strings 30-60% compacter op dan UTF-8","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Nog
\n
\nAls je een ontwikkelaar bent en de taak hebt om een codering te kiezen, is Unicode bijna altijd de juiste keuze. De specifieke manier van weergave hangt af van de context, maar meestal is er ook hier een universeel antwoord - UTF-8. Dit is goed omdat het alle Unicode-symbolen toestaat zonder te veel te verspillen. te veel<\/em> bytes in de meeste gevallen. Voor talen die niet alleen het Latijnse alfabet gebruiken, betekent \"niet te veel\" echter minimaal twee bytes per teken<\/strong>. Is er een betere optie zonder terug te keren naar de prehistorische coderingen die ons beperken tot slechts 256 beschikbare symbolen?<\/p>\n

Hieronder bied ik mijn poging aan om deze vraag te beantwoorden en een relatief eenvoudig algoritme te implementeren dat het mogelijk maakt om tekst in de meeste talen ter wereld op te slaan, zonder de overbodigheid die aanwezig is in UTF-8.<\/a><\/noindex><\/p>\n

Disclaimer.<\/i> Ik wil een paar belangrijke opmerkingen maken: de beschreven oplossing wordt niet gepresenteerd als een universele vervanging voor UTF-8<\/strong>, het is alleen geschikt voor een beperkte reeks gevallen (daarover hieronder) en het mag absoluut niet worden gebruikt voor interactie met externe API's (die er helemaal niet van op de hoogte zijn). Vaak zijn generieke compressie-algoritmes (bijvoorbeeld deflate) geschikter voor het compact opslaan van grote hoeveelheden tekstgegevens. Bovendien ontdekte ik tijdens het cre\u00ebren van mijn oplossing een bestaande standaard binnen Unicode die hetzelfde probleem oplost - het is iets ingewikkelder (en vaak slechter), maar het is in ieder geval een geaccepteerde standaard en geen zelfgemaakte oplossing. Daarover zal ik ook vertellen.<\/p>\n

Over Unicode en UTF-8<\/h2>\n

\nLaten we beginnen met een paar woorden over wat Unicode<\/strong> en UTF-8<\/strong>.<\/p>\n

Zoals bekend, waren 8-bits coderingen vroeger populair. Het was eenvoudig: 256 symbolen kunnen genummerd worden van 0 tot 255, en de getallen van 0 tot 255 zijn uiteraard te representeren in \u00e9\u00e9n byte. Terugkerend naar de oorsprong, beperkt de ASCII-codering zich zelfs tot 7 bits, waardoor de meest significante bit in de byte-representatie nul is, en de meeste 8-bits coderingen compatibel zijn (ze verschillen alleen in het 'bovenste' gedeelte, waar de meest significante bit \u00e9\u00e9n is).<\/p>\n

Wat zijn de verschillen tussen Unicode en die coderingen en waarom zijn er zoveel specifieke representaties - UTF-8, UTF-16 (BE en LE), UTF-32? Laten we het systematisch bekijken.<\/p>\n

De belangrijkste Unicode-standaard beschrijft alleen de overeenstemming tussen tekens (en in sommige gevallen - afzonderlijke componenten van tekens) en hun nummers. En er zijn veel mogelijke nummers in deze standaard - van 0x00<\/b><\/code> tot 0x10FFFF<\/b><\/code> (1 114 112 stuks). Als we een nummer in een dergelijk bereik in een variabele wilden plaatsen, zouden we met 1 of 2 bytes niet rondkomen. En omdat onze processors niet goed zijn ingericht voor de behandeling van driefnummers, zouden we 4 bytes per teken moeten gebruiken! Dit is wat UTF-32 is, maar juist vanwege deze 'verspilling' is dit formaat niet populair.<\/p>\n

Gelukkig zijn de tekens binnen Unicode niet willekeurig geordend. Al deze elementen zijn verdeeld in 17 'vlakken<\/em>', elk met 65536 (0x10000<\/b><\/code>) \u00abcodepunten<\/em>). Het begrip 'codepunt' hier is eenvoudigweg het nummer van een teken<\/em>, dat door Unicode is toegewezen. Maar, zoals hierboven vermeld, zijn niet alleen afzonderlijke tekens in Unicode genummerd, maar ook hun componenten en uitvoeringsnotities (en soms komt er helemaal geen nummer aan te pas - misschien tijdelijk, maar dat is voor ons minder belangrijk). Daarom is het nauwkeuriger om altijd over het aantal nummers te praten, en niet over tekens. Echter, voor de kortheid zal ik hierna vaak het woord 'teken' gebruiken, waarmee ik de term 'codepunt' bedoel.<\/p>\n

\"Nog
\nUnicode-vlakken. Zoals te zien is, is het merendeel (de vlakken van 4 tot 13) nog steeds niet in gebruik.<\/i><\/p>\n

Het meest opvallende is dat de hele 'kern' zich in de nul-dimensionale ruimte bevindt, deze wordt genoemd "Basic Multilingual Plane<\/em>". Als de regel tekst in een van de moderne talen staat (inclusief het Chinees), kom je daarbuiten niet. Maar je kunt ook de andere delen van Unicode niet uitsluiten - bijvoorbeeld, emoji's bevinden zich voornamelijk aan het einde van de volgende dimensie, "Supplementary Multilingual Plane<\/em>" (die zich uitstrekt van 0x10000<\/b><\/code> tot 0x1FFFF<\/b><\/code>). Daarom werkt UTF-16 als volgt: alle tekens die in Basic Multilingual Plane<\/em>, worden gecodeerd 'zoals ze zijn', met het bijbehorende tweebitsgetal. Echter, sommige nummers in dit bereik vertegenwoordigen helemaal geen specifieke tekens, maar geven aan dat we na dit paar bytes nog een paar moeten overwegen - door de waarden van deze vier bytes samen te voegen, krijgen we een nummer dat het volledige toegestane bereik van Unicode omvat. Deze weergave wordt 'surrogaatparen' genoemd - mogelijk heeft u daar al van gehoord.<\/p>\n

Zo vereist UTF-16 twee of (in zeer zeldzame gevallen) vier bytes voor \u00e9\u00e9n 'codepunt'. Dit is beter dan continu vier bytes te gebruiken, maar het Latijnse alfabet (en andere ASCII-tekens) verbruikt bij deze codering de helft van de ruimte aan nullen. UTF-8 is bedoeld om dit te verbeteren: ASCII neemt daarin, zoals voorheen, slechts \u00e9\u00e9n byte in beslag; codes van 0x80<\/b><\/code> tot 0x7FF<\/b><\/code> \u2014 twee bytes; van 0x800<\/b><\/code> tot 0xFFFF<\/b><\/code> \u2014 drie, en van 0x10000<\/b><\/code> tot 0x10FFFF<\/b><\/code> \u2014 vier. Enerzijds gaat het goed met het Latijnse alfabet: de compatibiliteit met ASCII is teruggebracht, en de verdeling is meer gelijkmatig 'verspreid' van 1 tot 4 bytes. Maar alfabetten die anders zijn dan het Latijnse, profiteren helaas niet in vergelijking met UTF-16, en vele vereisen nu drie bytes in plaats van twee \u2014 het bereik dat door de tweebyte codering wordt gedekt, is 32 keer kleiner, van 0xFFFF<\/b><\/code> tot 0x7FF<\/b><\/code>, en daarin komt al geen Chinees meer voor, noch bijvoorbeeld Georgisch. Cyrillisch en nog vijf alfabetten - hoera - hebben geluk, 2 bytes per teken.<\/p>\n

Waarom is dat zo? Laten we eens kijken hoe UTF-8 de codes van de tekens voorstelt:
\n\"Nog
\nDirect voor de representatie van de getallen worden hier bits gebruikt, gemarkeerd met het teken x<\/b><\/code>. Het is duidelijk dat er in de tweebyte codering slechts 11 van dergelijke bits (uit 16) zijn. De leidende bits vervullen hier alleen een functie voor beheer. In het geval van de vierbyte codering is er zelfs 21 bit gereserveerd voor het codepunt uit 32 \u2014 het lijkt erop dat drie bytes (die in totaal 24 bits geven) voldoende zouden zijn, maar de beheermarkers slokken te veel op.<\/p>\n

Is dat slecht? Eigenlijk niet echt. Enerzijds \u2014 als we ons veel zorgen maken over de ruimte die beslagen wordt, hebben we compressie-algoritmes die gemakkelijk alle overbodige entropie en redundantie kunnen uitschakelen. Aan de andere kant was het doel van Unicode om de meest universele codering te geven. Bijvoorbeeld, een in UTF-8 gecodeerde string kunnen we toevertrouwen aan een code die voorheen alleen met ASCII werkte, en we hoeven niet bang te zijn dat het daar een teken uit het ASCII-bereik tegenkomt dat er eigenlijk niet is (want in UTF-8 zijn alle bytes die beginnen met de nulbit, inderdaad ASCII). En als we plotseling een klein staartje van een grote string willen afsnijden, zonder deze vanaf het begin te decoderen (of een deel van de informatie willen herstellen na een beschadigd stuk) \u2014 is het niet moeilijk om die offset te vinden waar een teken begint (het is genoeg om bytes over te slaan met een bitprefix 10<\/b><\/code>).<\/p>\n

Waarom dan iets nieuws uitvinden?<\/h2>\n

\nTegelijkertijd zijn er af en toe situaties waarin compressie-algoritmen zoals deflate slecht toepasbaar zijn, maar je toch een compacte opslag van strings wilt bereiken. Persoonlijk heb ik met deze taak te maken gehad terwijl ik nadacht over de constructie van een gecomprimeerde prefixboom<\/a><\/noindex> voor een groot woordenboek dat woorden in willekeurige talen bevat. Enerzijds zijn de woorden heel kort, dus compressie is niet effici\u00ebnt. Anderzijds was de implementatie van de boom die ik overwoog, gericht op het feit dat elke byte van de opgeslagen string een aparte knoop in de boom genereerde, dus het minimaliseren van hun aantal was zeer nuttig. In mijn bibliotheek Az.js<\/a><\/noindex> (net als in pymorphy2<\/a><\/noindex>, waarop deze is gebaseerd) wordt een dergelijk probleem eenvoudig opgelost \u2014 strings verpakt in een DAWG<\/a><\/noindex>-woordenboek worden daar opgeslagen in het oude vertrouwde CP1251<\/a><\/noindex>. Maar zoals je gemakkelijk kunt begrijpen, werkt dit alleen goed voor een beperkte alfabet \u2014 een string in het Chinees kan je al niet meer in zo'n woordenboek plaatsen.<\/p>\n

Daarnaast wil ik nog een vervelend nuancepunt opmerken dat zich voordoet bij het gebruik van UTF-8 in dergelijke datastructuren. Op de afbeelding hierboven is te zien dat bij het opslaan van een teken in de vorm van twee bytes, de bits die betrekking hebben op zijn nummer, niet aaneengeschakeld zijn, maar onderbroken door een paar bits 10<\/b><\/code> in het midden: 110xxxxx 10xxxxxx<\/b><\/code>. Hierdoor, wanneer de lagere 6 bits van de tweede byte van de code van het teken overlopen (dat wil zeggen, er is een overgang 10111111<\/b><\/code> \u2192 10000000<\/b><\/code>), verandert ook de eerste byte. Het resultaat is dat de letter \u201e\u043f\u201d wordt weergegeven door de bytes 0xD0 0xBF<\/b><\/code>, en de volgende \u201e\u0440\u201d \u2014 al door 0xD1 0x80<\/b><\/code>. In de prefixboom leidt dit tot het splitsen van de ouderknop in twee \u2014 \u00e9\u00e9n voor het prefix 0xD0<\/b><\/code>, en de andere voor 0xD1<\/b><\/code> (hoewel de hele Cyrillische tekst alleen met de tweede byte gecodeerd zou kunnen worden).<\/p>\n

Wat ik heb bereikt<\/h2>\n

\nToen ik met deze taak geconfronteerd werd, besloot ik om wat te experimenteren met bits, en tegelijkertijd mezelf iets beter te leren kennen met de Unicode-structuur in het algemeen. Het resultaat was het UTF-C coderingsformaat (de \u201eC\u201d staat voor compact<\/em>), dat niet meer dan 3 bytes per codepunt verbruikt, en vaak slechts \u00e9\u00e9n extra byte vereist voor de hele gecodeerde string<\/strong>. Dit zorgt ervoor dat voor veel niet-ASCII alfabetten deze codering 30-60% compacter is dan UTF-8<\/strong>.<\/p>\n

Ik heb voorbeelden van de implementatie van coderings- en decodering algoritmen gepresenteerd in de vorm van bibliotheken in JavaScript en Go<\/a><\/noindex>, u kunt ze vrij gebruiken in uw code. Maar ik wil toch benadrukken dat dit formaat in zekere zin een 'fiets' blijft, en ik raad aan het niet te gebruiken zonder te beseffen waarom u het nodig heeft<\/strong>. Het is tenslotte meer een experiment dan een serieuze 'verbetering van UTF-8'. Desondanks is de code daar netjes en beknopt geschreven, met veel commentaar en testdekking.<\/p>\n

\"Nog
\nDe resultaten van de tests en de vergelijking met UTF-8<\/i><\/p>\n

Daarnaast heb ik een demo-pagina<\/a><\/noindex>, waar u de werking van het algoritme kunt beoordelen, en verder zal ik meer vertellen over de principes en het ontwikkelingsproces.<\/p>\n

Overbodige bits verwijderen<\/h2>\n

\nIk heb, natuurlijk, UTF-8 als basis genomen. Het eerste en meest voor de hand liggende dat je kunt veranderen, is het aantal controlebits in elke byte verminderen. Bijvoorbeeld, de eerste byte in UTF-8 begint altijd met 0<\/b><\/code>, of met 11<\/b><\/code> \u2014 en het prefix 10<\/b><\/code> is alleen voor de volgende bytes. Laten we het prefix vervangen, 11<\/b><\/code> en een werkende opdracht krijgen. 1<\/b><\/code>en bij de volgende bytes verwijderen we de prefixes helemaal. Wat krijgen we dan?<\/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

Stop, waar is de vierbyte notatie? Die is niet meer nodig \u2014 met de opschrijving over drie bytes hebben we nu 21 bits beschikbaar, en dat is ruim voldoende voor alle getallen tot 0x10FFFF<\/b><\/code>.<\/p>\n

Wat hebben we hier opgeofferd? Het belangrijkste is het ontdekken van de grenzen van symbolen vanuit een willekeurige plek in de buffer. We kunnen niet zomaar naar een willekeurige byte wijzen en vanaf daar het begin van het volgende symbool vinden. Dit is een beperking van ons formaat, maar in de praktijk komt de behoefte eraan niet vaak voor. Gewoonlijk zijn we in staat om de buffer vanaf het begin te doorlopen (vooral als het gaat om korte strings).<\/p>\n

De situatie met de dekking van talen met 2 bytes is ook verbeterd: nu biedt het tweebyteformaat een bereik van 14 bits, wat codes tot 0x3FFF<\/b><\/code>. De Chinezen hebben pech (hun hieroglyphen liggen voornamelijk in het bereik van 0x4E00<\/b><\/code> tot 0x9FFF<\/b><\/code>), maar voor de Georgi\u00ebrs en veel andere volkeren is het nu gemakkelijker \u2014 hun talen passen ook in 2 bytes per symbool.<\/p>\n

We voeren de toestand van de encoder in<\/h2>\n

\nLaten we nu eens nadenken over de eigenschappen van de rijen zelf. In het woordenboek staan meestal woorden die met de symbolen van \u00e9\u00e9n alfabet zijn geschreven, en dat geldt ook voor veel andere teksten. Het zou goed zijn om dit alfabet een keer op te geven, en vervolgens alleen het nummer van de letter binnenin. Laten we bekijken of de indeling van de symbolen in de Unicode-tabel ons helpt.<\/p>\n

Zoals hierboven vermeld, is Unicode verdeeld in vlakken<\/em> per 65536 codes each. However, this division is not very useful (as mentioned, we are mostly in the zero plane). A more interesting division is into blocks.<\/em> These ranges no longer have a fixed length and carry more meaning \u2014 as a rule, each combines characters from one alphabet.<\/p>\n

\"Nog
\nA block containing characters from the Bengali alphabet. Unfortunately, due to historical reasons, this is an example of not very dense packing \u2014 96 characters are scattered chaotically across 128 code points of the block.<\/i><\/p>\n

The beginnings of blocks and their sizes are always multiples of 16 \u2014 this is done simply for convenience. Additionally, many blocks start and end at values that are multiples of 128 or even 256 \u2014 for instance, the primary Cyrillic occupies 256 bytes from 0x0400<\/b><\/code> tot 0x04FF<\/b><\/code>. This is quite convenient: if we save the prefix once 0x04<\/b><\/code>, then any Cyrillic character can be recorded in a single byte. However, this means we lose the ability to revert to ASCII (and any other characters at all). Therefore, we do it like this:<\/p>\n

    \n
  1. Two bytes 10yyyyyy yxxxxxxx<\/b><\/code> not only denote a character with number yyyyyy yxxxxxxx<\/b><\/code>, but also alter the current alphabet<\/em> en een werkende opdracht krijgen. yyyyyy y0000000<\/b><\/code> (i.e., we remember all bits except for the least significant ones, 7 bits.<\/strong>);<\/li>\n
  2. One byte 0xxxxxxx<\/b><\/code> is a symbol from the current alphabet. It simply needs to be added to the offset we remembered in step 1. As long as we haven't changed the alphabet, the offset is zero, so we preserve compatibility with ASCII.<\/li>\n<\/ol>\n

    \nSimilarly for codes that require 3 bytes:<\/p>\n

      \n
    1. Three bytes 110yyyyy yxxxxxxx xxxxxxxx<\/b><\/code> denote a character with number yyyyyy yxxxxxxx xxxxxxxx<\/b><\/code>, change the current alphabet<\/em> en een werkende opdracht krijgen. yyyyyy y0000000 00000000<\/b><\/code> (we remembered everything except for the least significant ones, 15 bits<\/strong>), and set a flag that we are now in long<\/em> mode (when switching the alphabet back to the two-byte one, we will reset this flag);<\/li>\n
    2. Two bytes 0xxxxxxx xxxxxxxx<\/b><\/code> in long mode, this is a symbol from the current alphabet. Similarly, we add it to the offset from step 1. The only difference is that now we read two bytes (because we switched to that mode).<\/li>\n<\/ol>\n

      \nSounds good: as long as we need to encode characters from the same 7-bit range of Unicode, we spend 1 extra byte at the start and only one byte per character.<\/p>\n

      \"Nog
      \nThe work of one of the early versions. It already often surpasses UTF-8, but there's still room for improvement.<\/i><\/p>\n

      What has worsened? Firstly, we have acquired a state, namely the offset of the current alphabet<\/em> and a flag for long mode.<\/em>. Dit beperkt ons verder: nu kunnen dezelfde symbolen op verschillende manieren worden gecodeerd in verschillende contexten. Het zoeken naar substrings zal bijvoorbeeld rekening moeten houden met dit aspect, in plaats van alleen bytes te vergelijken. Ten tweede, zodra we het alfabet veranderden, ontstonden er problemen met de codering van ASCII-tekens (wat niet alleen het Latijnse alfabet is, maar ook basisinterpunctie, inclusief spaties) \u2014 ze vereisen een herhaalde verandering van het alfabet bij 0, dat wil zeggen opnieuw een extra byte (en dan nog een om terug te keren naar ons hoofdalfabet).<\/p>\n

      \u00c9\u00e9n alfabet is goed, twee is beter<\/h2>\n

      \nLaten we onze bitprefixen iets aanpassen door er nog \u00e9\u00e9n aan de drie hierboven beschreven toe te voegen:<\/p>\n

      0xxxxxxx<\/b><\/code> \u2014 1 byte in normale modus, 2 in lange modus
      \n11xxxxxx<\/b><\/code> \u2014 1 byte
      \n100xxxxx xxxxxxxx<\/b><\/code> \u2014 2 bytes
      \n101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> \u2014 3 bytes<\/p>\n

      \"Nog
      \n
      \nNu is er in de tweebyte notatie \u00e9\u00e9n beschikbare bit minder \u2014 coderingstekens tot 0x1FFF<\/b><\/code>, en niet 0x3FFF<\/b><\/code>. Desondanks is dit nog steeds aanzienlijk meer dan bij de tweebyte codes van UTF-8, de meeste gangbare talen passen er nog steeds in, het meest opvallende verlies is de       hiragana<\/a><\/noindex> en katakana<\/a><\/noindex>, de Japanners zijn bedroefd.<\/p>\n

      Wat voor een nieuwe 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>) alfabet. Wanneer we het huidige alfabet wisselen, wordt een deel van het oude alfabet een hulpalfabet. Bijvoorbeeld, als we van ASCII op Cyrillisch schakelen \u2014 in de \"schuilplaats\" staan nu 64 symbolen, waaronder het Latijnse alfabet, cijfers, spatie en komma<\/strong> (de meest voorkomende invoegen in niet-ASCII teksten). Wanneer we terugschakelen naar ASCII \u2014 wordt een groot deel van het Cyrillische alfabet het hulpalfabet.<\/p>\n

      Dankzij de toegang tot twee alfabets, kunnen we omgaan met een grotere hoeveelheid teksten, met minimale kosten voor het schakelen van alfabetten (interpunctie zal meestal leiden tot terugkeer naar ASCII, maar daarna kunnen we veel niet-ASCII symbolen al uit het aanvullende alfabet halen, zonder opnieuw te schakelen).<\/p>\n

      Bonus: door het aanvullende alfabet een prefix te geven 11xxxxxx<\/b><\/code> en de initi\u00eble verschuiving in te stellen op 0xC0<\/b><\/code>, krijgen we gedeeltelijke compatibiliteit met CP1252. Met andere woorden, veel (maar niet allemaal) West-Europese teksten gecodeerd in CP1252 zullen er ook zo uitzien in UTF-C.<\/p>\n

      Hier ontstaat echter een moeilijkheid: hoe krijgen we het hulpalfabet uit het hoofdalfabet? We kunnen dezelfde verschuiving behouden, maar \u2014 helaas \u2014 hier speelt de Unicode-structuur tegen ons. Vaak bevindt het hoofddeel van het alfabet zich niet aan het begin van het blok (bijvoorbeeld, de Russische hoofdletter \"\u0410\" heeft code 0x0410<\/b><\/code>, hoewel het Cyrillische blok begint met 0x0400<\/b><\/code>). Dus door de eerste 64 tekens in de \u2018reserve\u2019 te nemen, verliezen we mogelijk toegang tot het eindgedeelte van het alfabet.<\/p>\n

      Om dit probleem op te lossen, heb ik handmatig enkele blokken doorgenomen die overeenkomen met verschillende talen en heb ik de verschuiving van het hulpalfabet binnen het hoofdalfabet aangegeven. De Latijnse letters heb ik, als uitzondering, helemaal opnieuw gerangschikt, alsof het base64 is.<\/p>\n

      \"Nog<\/p>\n

      Laatste handtekeningen<\/h2>\n

      \nLaten we tenslotte nadenken waar we nog iets kunnen verbeteren.<\/p>\n

      Laten we opmerken dat het formaat 101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> in staat is om cijfers tot 0x1FFFFF<\/b><\/code>, en Unicode eindigt eerder, op 0x10FFFF<\/b><\/code>. Met andere woorden, het laatste codepunt zal worden weergegeven als 10110000 11111111 11111111<\/b><\/code>. Dus kunnen we zeggen dat als de eerste byte eruitziet als 1011xxxx<\/b><\/code> (waar xxxx<\/b><\/code> groter is dan 0), dan betekent dit iets anders. Bijvoorbeeld, we kunnen daar nog eens 15 tekens aan toevoegen, die altijd beschikbaar zijn voor codering met \u00e9\u00e9n byte, maar ik heb besloten het anders te doen.<\/p>\n

      Dus kiezen we enkele geselecteerde bereiken waar de emoji's, hiragana en katakana overeenkomen, hernummeren we deze in \u00e9\u00e9n continue lijst en coderen we deze in twee bytes in plaats van drie:<\/p>\n

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

      Uitstekend: de eerder genoemde emoji \u200d\u200d\u200d\"Nog<\/a><\/noindex>, bestaande uit 7 codepunten, neemt in UTF-8 25 bytes in beslag, maar we hebben deze in gepast 14<\/strong> laten we zeggen twee bytes per codepunt). Trouwens, Habr weigerde het te verwerken (zowel in de oude als in de nieuwe editor), dus ik moest het als afbeelding invoegen.<\/p>\n

      Laten we nog een probleem proberen op te lossen. Zoals we ons herinneren, is het hoofdalfabet in wezen de hogere 6 bits<\/strong>, die we in gedachten houden, en plakken aan de code van elk te decoderen symbool. In het geval van Chinese karakters, die zich in het blok bevinden 0x4E00<\/b><\/code> \u2013 0x9FFF<\/b><\/code>, is dit ofwel bit 0 of 1. Dit is niet erg handig: we moeten voortdurend het alfabet tussen deze twee waarden wisselen (dat wil zeggen, drie bytes verbruiken). Maar laten we opmerken dat we in de lange modus het aantal symbolen dat we coderen met behulp van de korte modus van de code kunnen aftrekken (na alle eerder genoemde trucs is dat 10240) \u2014 dan verschuift het bereik van de karakters naar 0x2600<\/b><\/code> \u2013 0x77FF<\/b><\/code>, en in dat geval zijn de hogere 6 bits (uit 21) in dit hele bereik gelijk aan 0. Op deze manier zullen de reeksen karakters twee bytes per karakter gebruiken (wat optimaal is voor zo'n groot bereik), zonder dat er alfabetswitches optreden. <\/p>\n

      Alternatieve oplossingen: SCSU, BOCU-1<\/h2>\n

      \nKenners van Unicode, die alleen de titel van het artikel hebben gelezen, zullen waarschijnlijk snel herinneren dat er binnen de Unicode-standaarden Standard Compression Scheme for Unicode<\/a><\/noindex> (SCSU) is, dat een methode voor codering beschrijft die veel lijkt op de in dit artikel beschreven.<\/p>\n

      Ik geef eerlijk toe: ik kwam pas diep in het schrijven van mijn oplossing achter het bestaan ervan. Als ik er vanaf het begin van had geweten, zou ik waarschijnlijk geprobeerd hebben een implementatie ervan te schrijven in plaats van mijn eigen benadering te verzinnen.<\/p>\n

      Het is interessant dat SCSU idee\u00ebn gebruikt die zeer vergelijkbaar zijn met de idee\u00ebn die ik zelf heb ontwikkeld (in plaats van het concept van \u2018alfabetten\u2019 worden \u2018vensters\u2019 gebruikt, en er zijn er meer beschikbaar dan bij mij). Tegelijkertijd heeft dit formaat ook nadelen: het ligt iets dichter bij compressie-algoritmes dan bij codering. In het bijzonder biedt de standaard veel representatiemethoden, maar zegt niet hoe je de optimale moet kiezen \u2014 daarvoor moet de encoder enige heuristieken toepassen. Daarom zal een SCSU-encoder die een goede compressie biedt, complexer en omvangrijker zijn dan mijn algoritme.<\/p>\n

      Ter vergelijking heb ik een relatief eenvoudige implementatie van SCSU naar JavaScript overgezet \u2014 qua codevolume blijkt het vergelijkbaar te zijn met mijn UTF-C, maar in een aantal gevallen toonde het resultaten die tientallen procenten slechter waren (soms kan het ook beter presteren, maar niet veel). Bijvoorbeeld, teksten in het Hebreeuws en Grieks codeerde UTF-C met maar liefst 60% beter dan SCSU<\/strong> (waarschijnlijk vanwege hun compacte alfabetten).<\/p>\n

      Daarnaast wil ik toevoegen dat er naast SCSU ook een andere manier van compacte weergave van Unicode bestaat \u2014 BOCU-1<\/a><\/noindex>, maar deze richt zich op compatibiliteit met MIME (wat ik niet nodig had), en gebruikt een iets andere benadering van codering. Ik heb de effici\u00ebntie ervan niet beoordeeld, maar ik denk niet dat deze hoger zal zijn dan die van SCSU.<\/p>\n

      Mogelijke aanpassingen<\/h2>\n

      \nHet algoritme dat ik heb gepresenteerd is niet universeel by design (hierin verschillen mijn doelen waarschijnlijk het meest van die van de Unicode-consortium). Ik heb al vermeld dat het voornamelijk is ontwikkeld voor \u00e9\u00e9n taak (het opslaan van een meertalige woordenlijst in een prefixboom), en sommige van zijn kenmerken zijn misschien niet geschikt voor andere taken. Maar het feit dat het geen standaard is, kan ook een voordeel zijn \u2014 je kunt het gemakkelijk aanpassen aan je behoeften<\/strong>.<\/p>\n

      Bijvoorbeeld, je kunt eenvoudigweg het bestaan van status schrappen, de codering stateless maken \u2014 gewoon de variabelen niet bijwerken uitschakelen<\/b><\/code>, auxOffs<\/b><\/code> en is21Bit<\/b><\/code> in de encoder en decoder. In dat geval is het niet mogelijk om reeksen van symbolen uit \u00e9\u00e9n alfabet effici\u00ebnt in te pakken, maar dat garandeert wel dat hetzelfde symbool altijd op dezelfde manier wordt gecodeerd, ongeacht de context.<\/p>\n

      Daarnaast kan de encoder worden afgestemd op een specifieke taal door de standaardstatus aan te passen \u2014 bijvoorbeeld, gericht op Russische teksten, de instellingen in het begin van de encoder en decoder vaststellen offs = 0x0400<\/b><\/code> en auxOffs = 0<\/b><\/code>. Dit is vooral zinvol in de stateless modus. In het algemeen zal dit lijken op het gebruik van de oude 8-bits codering, maar het biedt nog steeds de mogelijkheid om symbolen uit de hele Unicode indien nodig in te voegen.<\/p>\n

      Een ander tekortkoming, eerder genoemd \u2014 in volumineuze tekst gecodeerd in UTF-C is er geen snelle manier om de grens van een symbool te vinden, dichtbij een willekeurig byte. Door de laatste, laten we zeggen, 100 bytes van de gecodeerde buffer af te snijden, loop je het risico onbruikbare data te krijgen waar je niets mee kunt. Voor het opslaan van meergigabyte logs is de codering niet geschikt, maar in het algemeen kan dit worden opgelost. Een byte 0xBF<\/b><\/code> mag nooit als de eerste byte voorkomen (maar kan als de tweede of derde verschijnen). Daarom kan bij codering een reeks worden ingevoegd 0xBF 0xBF 0xBF<\/b><\/code> Elke, laten we zeggen, 10 KB \u2014 dan is het bij behoefte om de grens te vinden voldoende om het geselecteerde stuk te scannen totdat een vergelijkbare marker wordt gevonden. Direct achter de laatste 0xBF<\/b><\/code> zal het begin van het teken zijn. (Bij decodering moet deze reeks van drie bytes natuurlijk worden genegeerd.)<\/p>\n

      Samenvattend<\/h2>\n

      \nAls je tot hier hebt gelezen \u2014 gefeliciteerd! Hopelijk heb je, net als ik, iets nieuws geleerd (of oude kennis opgefrist) over hoe Unicode werkt.<\/p>\n

      \"Nog
      \nDemonstratiepagina. Aan de hand van het Hebreeuws zijn de voordelen ten opzichte van zowel UTF-8 als SCSU zichtbaar.<\/i><\/p>\n

      Je zou de bovengenoemde overpeinzingen niet moeten beschouwen als een inbreuk op de standaarden. Echter, over het algemeen ben ik tevreden met de resultaten van mijn werkzaamheden, dus ben ik blij om ze te delen<\/a><\/noindex>: bijvoorbeeld, de JS-bibliotheek in geminimaliseerde vorm weegt slechts 1710 bytes (en heeft uiteraard geen afhankelijkheden). Zoals ik eerder noemde, kun je het werken met deze bibliotheek bekijken op de demo-pagina<\/a><\/noindex> (daar is ook een set teksten waarmee je het kunt vergelijken met UTF-8 en SCSU).<\/p>\n

      Tot slot wil ik nog eens de aandacht vestigen op de gevallen waarin het gebruik van UTF-C niet aan te raden is<\/b>:<\/p>\n

      Laten we kijken naar de Unicode-blokken die nu drie bytes vereisen. Over het algemeen zijn dit, zoals al gezegd, Chinese karakters \u2014 maar daar is moeilijk iets mee te doen, ze zijn er 21.000. Daarnaast zijn er ook de hiragana en katakana \u2014 en die zijn er al veel minder, minder dan tweehonderd. En aangezien we de Japanners hebben genoemd \u2014 daar liggen ook emoji's (in werkelijkheid zijn ze overal verspreid in Unicode, maar de belangrijkste blokken zijn in het bereik 0x1F300<\/b><\/code> \u2013 0x1FBFF<\/b><\/code>). Als we denken aan het feit dat er nu emoji's bestaan die uit meerdere codepunten zijn samengesteld (bijvoorbeeld emoji \u200d\u200d\u200d\"Nog<\/a><\/noindex> bestaat uit maar liefst 7 codes!), dan is het droevig om voor elk daarvan drie bytes te besteden (7\u00d73 = 21 bytes voor \u00e9\u00e9n teken, dat is echt problematisch).<\/p>\n