{"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\/da\/blog\/administrirovanie\/eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8","title":{"rendered":"Endnu en cykel: vi opbevarer Unicode-strenge 30-60% mere kompakt end UTF-8","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Endnu
\n
\nHvis du er udvikler, og det er tid til at v\u00e6lge en kodning, er det n\u00e6sten altid den rigtige l\u00f8sning at v\u00e6lge Unicode. Den specifikke repr\u00e6sentationsmetode afh\u00e6nger af konteksten, men oftest er svaret ogs\u00e5 her universelt \u2014 UTF-8. Det er godt, fordi det tillader brug af alle Unicode-tegn uden at bruge for mange<\/em> bytes i de fleste tilf\u00e6lde. Sandt nok, for sprog der ikke kun bruger det latinske alfabet, er \u201cikke for mange\u201d mindst to bytes per tegn<\/strong>. Er der en bedre l\u00f8sning, uden at vende tilbage til forhistoriske kodninger, der begr\u00e6nser os til kun 256 tilg\u00e6ngelige tegn?<\/p>\n

Nedenfor vil jeg pr\u00e6sentere mit fors\u00f8g p\u00e5 at besvare dette sp\u00f8rgsm\u00e5l samt implementeringen af en relativt enkel algoritme, der tillader opbevaring af strenge p\u00e5 de fleste verdenes sprog uden at tilf\u00f8je den redundans, der findes i UTF-8.<\/a><\/noindex><\/p>\n

Fraskrivelse.<\/i> Lad mig straks komme med et par vigtige forbehold: den beskrevne l\u00f8sning er ikke ment som en universel erstatning for UTF-8<\/strong>, den er kun velegnet i en sn\u00e6ver liste af tilf\u00e6lde (mere om dette nedenfor), og den m\u00e5 under ingen omst\u00e6ndigheder bruges til at interagere med tredjeparts API'er (som ikke engang kender den). Ofte vil algoritmer til generel komprimering (f.eks. deflate) v\u00e6re passende til kompakt opbevaring af store m\u00e6ngder tekstdata. Desuden fandt jeg allerede under udviklingen af min l\u00f8sning en eksisterende standard inden for selve Unicode, som l\u00f8ser den samme opgave \u2014 den er noget mere kompleks (og ofte v\u00e6rre), men er trods alt et accepteret standard og ikke noget, der er samlet hurtigt. Jeg vil ogs\u00e5 fort\u00e6lle om det.<\/p>\n

Om Unicode og UTF-8<\/h2>\n

\nFor at begynde \u2014 et par ord om, hvad Unicode<\/strong> og UTF-8<\/strong>.<\/p>\n

Som bekendt havde 8-bit kodninger tidligere popularitet. Med dem var alt enkelt: 256 tegn kan nummereres fra 0 til 255, og tallene fra 0 til 255 kan \u00e5benlyst repr\u00e6senteres som \u00e9n byte. Hvis vi ser tilbage til de tidligste dage, er ASCII-kodningen faktisk begr\u00e6nset til 7 bits, s\u00e5 det h\u00f8jeste bit i dens byte-repr\u00e6sentation er lig med nul, og de fleste 8-bit kodninger er kompatible med den (de adskiller sig kun i den \u201c\u00f8verste\u201d del, hvor det h\u00f8jeste bit er \u00e9n).<\/p>\n

Hvordan adskiller Unicode sig fra disse kodninger, og hvorfor knytter der sig mange specifikke repr\u00e6sentationer til den \u2014 UTF-8, UTF-16 (BE og LE), UTF-32? Lad os tage det skridt for skridt.<\/p>\n

Den grundl\u00e6ggende Unicode-standard beskriver kun overensstemmelsen mellem tegn (og i nogle tilf\u00e6lde \u2014 enkelte komponenter af tegn) og deres numre. Og der er mange mulige numre i denne standard \u2014 fra 0x00<\/b><\/code> op til 0x10FFFF<\/b><\/code> (1 114 112 stykker). Hvis vi \u00f8nskede at placere et tal i dette interval i en variabel, ville hverken 1 eller 2 byte v\u00e6re tilstr\u00e6kkeligt. Da vores processorer ikke er meget tilpasset til arbejde med tre-byte tal, ville vi v\u00e6re n\u00f8dt til at bruge hele 4 byte til et enkelt tegn! Dette er UTF-32, men netop af denne \"give\" bruges dette format ikke popul\u00e6rt.<\/p>\n

Heldigvis er tegnene inden for Unicode ikke sorteret tilf\u00e6ldigt. Hele deres m\u00e6ngde er opdelt i 17 \"planer<\/em>\", hvor hver indeholder 65536 (0x10000<\/b><\/code>) \u00abkodepunkter<\/em>\". Begrebet \"kodepunkt\" her er blot nummeret p\u00e5 tegnet<\/em>, tildelt det af Unicode. Men som n\u00e6vnt ovenfor er ikke kun individuelle tegn i Unicode nummereret, men ogs\u00e5 deres komponenter og kontrolm\u00e6rker (og nogle gange svarer et nummer slet ikke til noget \u2014 m\u00e5ske indtil videre, men det er ikke s\u00e5 vigtigt for os), s\u00e5 det er mere korrekt altid at tale om antallet af selve numrene, ikke tegnene. Men for kortheds skyld vil jeg ofte bruge ordet \"tegn\", hvilket refererer til termen \"kodepunkt\".<\/p>\n

\"Endnu
\nUnicode-planer. Som det kan ses, er st\u00f8rstedelen (planer fra 4 til 13) stadig ikke brugt.<\/i><\/p>\n

Det mest fantastiske er, at selve \"k\u00f8det\" ligger i nul-niveauet, som hedder "Basic Multilingual Plane<\/em>". Hvis linjen indeholder tekst p\u00e5 et af de moderne sprog (inklusive kinesisk), vil du ikke komme ud over dette niveau. Men du kan ikke sk\u00e6re den resterende del af Unicode v\u00e6k - for eksempel findes emojis prim\u00e6rt i slutningen af det n\u00e6ste niveau, "Supplementary Multilingual Plane<\/em>" (det str\u00e6kker sig fra 0x10000<\/b><\/code> op til 0x1FFFF<\/b><\/code>). Derfor h\u00e5ndterer UTF-16 det s\u00e5dan: Alle tegn, der falder inden for Basic Multilingual Plane<\/em>, kodes \"som de er\" med det tilsvarende to-byte nummer. Dog betegner nogle tal i dette omr\u00e5de slet ikke specifikke tegn, men angiver, at der efter dette byte-par skal overvejes endnu et \u2014 kombinerer man v\u00e6rdierne af disse fire byte, f\u00e5r man et tal, der d\u00e6kker hele den tilladte r\u00e6kkevidde af Unicode. Denne repr\u00e6sentation kaldes \"surrogatpar\" \u2014 du har m\u00e5ske h\u00f8rt om dem.<\/p>\n

Dermed kr\u00e6ver UTF-16 to eller (i meget sj\u00e6ldne tilf\u00e6lde) fire byte pr. \"kodepunkt\". Det er bedre end konstant at bruge fire byte, men latinske bogstaver (og andre ASCII-tegn) bruger i denne kodning halvdelen af rummet p\u00e5 nuller. UTF-8 er designet til at rette dette: ASCII optager i det kun \u00e9n byte, som f\u00f8r; koder fra 0x80<\/b><\/code> op til 0x7FF<\/b><\/code> \u2014 to byte; fra 0x800<\/b><\/code> op til 0xFFFF<\/b><\/code> \u2014 tre, og fra 0x10000<\/b><\/code> op til 0x10FFFF<\/b><\/code> \u2014 fire. P\u00e5 den ene side er det godt for latin: kompatibilitet med ASCII er tilbage, og fordelingen er mere j\u00e6vnt \"fordelt\" fra 1 til 4 byte. Men alfabetter, der adskiller sig fra det latinske, vinder desv\u00e6rre ikke noget sammenlignet med UTF-16, og mange kr\u00e6ver nu faktisk tre byte i stedet for to \u2014 omr\u00e5det d\u00e6kket af den to-bytede repr\u00e6sentation er blevet indsn\u00e6vret med 32 gange, fra 0xFFFF<\/b><\/code> op til 0x7FF<\/b><\/code>, og det inkluderer hverken kinesisk eller for eksempel georgisk. Kirillisk og yderligere fem alfabetter - hurra - er heldige, 2 byte pr. tegn.<\/p>\n

Hvorfor sker dette? Lad os se p\u00e5, hvordan UTF-8 repr\u00e6senterer koderne for tegnene:
\n\"Endnu
\nHer er bits, der er m\u00e6rket med symbolet x<\/b><\/code>, direkte brugt til at repr\u00e6sentere numre. Det er tydeligt, at der kun er 11 af s\u00e5danne bits i den to-bytede repr\u00e6sentation (ud af 16). De f\u00f8rende bits har kun en servicefunktion. I tilf\u00e6lde af den fire-bytede repr\u00e6sentation er der overhovedet afsat 21 bits ud af 32 til kodepunktsnummeret \u2014 det kunne tilsyneladende have v\u00e6ret tilstr\u00e6kkeligt med tre byte (som giver i alt 24 bits), men service-mark\u00f8rerne spiser for meget.<\/p>\n

Er dette d\u00e5rligt? Faktisk, ikke rigtig. P\u00e5 den ene side \u2014 hvis vi er meget bekymrede for det pladskrav, har vi komprimeringsalgoritmer, der let kan fjerne al overfl\u00f8dig entropi og redundans. P\u00e5 den anden side var m\u00e5let med Unicode at give en s\u00e5 universel kodning som muligt. For eksempel kan vi stole p\u00e5 en tekst, der er kodet i UTF-8, til kode, der tidligere kun arbejdede med ASCII, og vi beh\u00f8ver ikke frygte, at den vil se et tegn fra ASCII-omr\u00e5det, som ikke egentlig er der (for i UTF-8 er alle bytes, der starter med den nulbit, netop ASCII). Og hvis vi pludselig vil sk\u00e6re et lille hale af en stor streng, uden at dekode den fra starten (eller genskabe en del af informationen efter et beskadiget omr\u00e5de) \u2014 er det ikke sv\u00e6rt at finde den forskydning, hvor et bestemt tegn begynder (det er nok at springe over bytes, der har en bitpr\u00e6fiks 10<\/b><\/code>).<\/p>\n

Hvorfor skulle man s\u00e5 finde p\u00e5 noget nyt?<\/h2>\n

\nSamtidig er der lejlighedsvis situationer, hvor kompressionsalgoritmer som deflate er d\u00e5rligt anvendelige, men man \u00f8nsker at opn\u00e5 kompakt lagring af strenge. Personligt har jeg st\u00f8dt p\u00e5 en s\u00e5dan opgave, mens jeg overvejede konstruktionen af et komprimeret pr\u00e6fikstr\u00e6<\/a><\/noindex> til et stort ordforr\u00e5d, der inkluderer ord p\u00e5 vilk\u00e5rlige sprog. P\u00e5 den ene side er hvert ord meget kort, s\u00e5 at komprimere det ville v\u00e6re ineffektivt. P\u00e5 den anden side var implementeringen af tr\u00e6et, som jeg overvejede, beregnet til, at hvert byte af den gemte streng genererede et separat tr\u00e6nod, s\u00e5 det var meget nyttigt at minimere deres antal. I mit bibliotek Az.js<\/a><\/noindex> (ligesom i pymorphy2<\/a><\/noindex>, som det er baseret p\u00e5) l\u00f8ses et lignende problem simpelt \u2014 strenge pakket ind i DAWG<\/a><\/noindex>-ordbogen gemmes der i den gode gamle CP1251<\/a><\/noindex>. Men som det ikke er sv\u00e6rt at forst\u00e5, fungerer det godt kun for et begr\u00e6nset alfabet \u2014 en streng p\u00e5 kinesisk kan ikke indg\u00e5s i en s\u00e5dan ordbog.<\/p>\n

Jeg vil ogs\u00e5 n\u00e6vne en anden ubehagelig nuance, der opst\u00e5r ved brug af UTF-8 i en s\u00e5dan datstruktur. P\u00e5 billedet ovenfor kan man se, at n\u00e5r et tegn er skrevet med to bytes, s\u00e5 ligger bitene vedr\u00f8rende dets nummer ikke frit sammen, men er splittet af et par bit 10<\/b><\/code> i midten: 110xxxxx 10xxxxxx<\/b><\/code>. P\u00e5 grund af dette, n\u00e5r de nederste 6 bit af den anden byte i tegnkoden overfyldes (dvs. n\u00e5r der sker et skift 10111111<\/b><\/code> \u2192 10000000<\/b><\/code>), \u00e6ndres ogs\u00e5 den f\u00f8rste byte. Det viser sig, at bogstavet \u00ab\u043f\u00bb angives med bytes 0xD0 0xBF<\/b><\/code>, og det efterf\u00f8lgende \u00ab\u0440\u00bb \u2014 allerede 0xD1 0x80<\/b><\/code>. I pr\u00e6fikstr\u00e6et f\u00f8rer det til deling af for\u00e6lderknuden i to \u2014 en for pr\u00e6fikset 0xD0<\/b><\/code>, og en anden for 0xD1<\/b><\/code> (selvom hele kyrillisk kunne kodes kun med den anden byte).<\/p>\n

Hvad jeg fik<\/h2>\n

\nSt\u00f8dt p\u00e5 denne opgave besluttede jeg at \u00f8ve mig med bit-manipulation, og til geng\u00e6ld l\u00e6re lidt bedre om strukturen af Unicode generelt. Resultatet blev UTF-C kodningsformatet (\u00abC\u00bb for compact<\/em>), som bruger ikke mere end 3 bytes per code point, og som ofte tillader at bruge kun et ekstra byte for hele den kodede streng<\/strong>. Dette f\u00f8rer til, at p\u00e5 mange ikke-ASCII alfabeter viser s\u00e5dan kodning sig at v\u00e6re 30-60% mere kompakt end UTF-8<\/strong>.<\/p>\n

Jeg har formateret eksempler p\u00e5 implementeringen af kodnings- og dekodingsalgoritmer i form af biblioteker i JavaScript og Go<\/a><\/noindex>, du kan frit bruge dem i din kode. Men jeg vil stadig understrege, at i nogle henseender forbliver dette format en slags \"cykel\", og jeg anbefaler ikke at bruge det uden at forst\u00e5, hvorfor det er n\u00f8dvendigt for dig<\/strong>. Det er trods alt mere et eksperiment end en seri\u00f8s \"forbedring af UTF-8\". Ikke desto mindre er koden der skrevet p\u00e6nt, kortfattet, med mange kommentarer og testd\u00e6kning.<\/p>\n

\"Endnu
\nResultatet af testene og sammenligningen med UTF-8<\/i><\/p>\n

Jeg har ogs\u00e5 lavet en demo-side<\/a><\/noindex>, hvor du kan vurdere algoritmens arbejde, og senere vil jeg fort\u00e6lle mere om dens principper og udviklingsprocessen.<\/p>\n

Vi fjerner overfl\u00f8dige bits<\/h2>\n

\nSom grundlag tog jeg selvf\u00f8lgelig UTF-8. Det f\u00f8rste og mest \u00e5benlyse, man kan \u00e6ndre \u2014 er at reducere antallet af kontrolbits i hver byte. For eksempel starter den f\u00f8rste byte i UTF-8 altid enten med 0<\/b><\/code>, eller med 11<\/b><\/code> \u2014 mens pr\u00e6fikset 10<\/b><\/code> kun findes i de f\u00f8lgende bytes. Lad os erstatte pr\u00e6fikset 11<\/b><\/code> og f\u00e5 en fungerende kommando. 1<\/b><\/code>, og fjerne pr\u00e6fikserne helt fra de f\u00f8lgende bytes. Hvad f\u00e5r vi s\u00e5?<\/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, men hvor er den fire-byte repr\u00e6sentation? Den er ikke l\u00e6ngere n\u00f8dvendig \u2014 med tre bytes har vi nu 21 bits tilg\u00e6ngelige, og det er mere end tilstr\u00e6kkeligt til alle tal op til 0x10FFFF<\/b><\/code>.<\/p>\n

Hvad har vi ofret her? Det vigtigste \u2014 er opdagelsen af gr\u00e6nserne for symboler fra en vilk\u00e5rlig position i bufferen. Vi kan ikke pege p\u00e5 en vilk\u00e5rlig byte og finde starten p\u00e5 det n\u00e6ste symbol derfra. Dette er en begr\u00e6nsning af vores format, men i praksis opst\u00e5r behovet for det ikke ofte. Normalt kan vi l\u00f8be gennem bufferen fra begyndelsen (is\u00e6r n\u00e5r det drejer sig om korte strenge).<\/p>\n

Situationen med d\u00e6kning af sprog med 2 bytes er ogs\u00e5 blevet bedre: nu giver det to-byte format et interval p\u00e5 14 bits, hvilket svarer til koder op til 0x3FFF<\/b><\/code>. Kineserne har ikke held (deres tegn ligger prim\u00e6rt i intervallet fra 0x4E00<\/b><\/code> op til 0x9FFF<\/b><\/code>), men georgierne og mange andre folk har f\u00e5et det sjovere \u2014 deres sprog passer ogs\u00e5 indenfor 2 bytes pr. symbol.<\/p>\n

Vi introducerer encoderens tilstand<\/h2>\n

\nLad os nu t\u00e6nke p\u00e5 egenskaberne ved selve strenge. I ordbogen ligger de fleste ord skrevet med tegn fra samme alfabet, og dette g\u00e6lder ogs\u00e5 for mange andre tekster. Det ville v\u00e6re godt at angive dette alfabet \u00e9n gang og derefter kun angive nummeret p\u00e5 bogstavet inden i det. Lad os se, om placeringen af tegn i Unicode-tabellen hj\u00e6lper os.<\/p>\n

Som n\u00e6vnt tidligere er Unicode opdelt i planer<\/em> op til 65536 koder hver. Men dette er ikke en s\u00e6rlig nyttig opdeling (som allerede sagt, befinder vi os oftest i den nul-planet). En mere interessant opdeling er p\u00e5 blokke.<\/em> Disse intervaller har ikke l\u00e6ngere en fast l\u00e6ngde og b\u00e6rer mere mening - som regel samler hver af dem tegn fra det samme alfabet.<\/p>\n

\"Endnu
\nEn blok, der indeholder tegn fra det bengalske alfabet. Desv\u00e6rre, af historiske grunde, er dette et eksempel p\u00e5 en ikke s\u00e6rlig t\u00e6t pakning - 96 tegn er spredt tilf\u00e6ldigt over 128 kodepunkter i blokken.<\/i><\/p>\n

Startpunkter for blokke og deres st\u00f8rrelser er altid multippel af 16 - dette g\u00f8res bare for bekvemmelighed. Desuden starter og slutter mange blokke p\u00e5 v\u00e6rdier, der er multipler af 128 eller endda 256 - for eksempel optager den grundl\u00e6ggende kyrilliske 256 bytes fra 0x0400<\/b><\/code> op til 0x04FF<\/b><\/code>. Det er ret praktisk: hvis vi en gang gemmer et pr\u00e6fiks 0x04<\/b><\/code>, kan ethvert kyrillisk tegn derefter skrives med \u00e9n byte. Men s\u00e5 mister vi muligheden for at vende tilbage til ASCII (og til alle andre tegn overhovedet). Derfor g\u00f8r vi det s\u00e5dan:<\/p>\n

    \n
  1. To bytes 10yyyyyy yxxxxxxx<\/b><\/code> angiver ikke kun et tegn med nummeret yyyyyy yxxxxxxx<\/b><\/code>, men \u00e6ndrer ogs\u00e5 det aktuelle alfabet<\/em> og f\u00e5 en fungerende kommando. yyyyyy y0000000<\/b><\/code> (dvs. vi gemmer alle bits undtagen de laveste 7 bits<\/strong>);<\/li>\n
  2. En byte 0xxxxxxx<\/b><\/code> er et tegn fra det aktuelle alfabet. Det skal blot l\u00e6gges sammen med det skift, som vi huskede i trin 1. S\u00e5 l\u00e6nge vi ikke har \u00e6ndret alfabetet, er skiftet lig med nul, s\u00e5 vi har bevaret kompatibiliteten med ASCII.<\/li>\n<\/ol>\n

    \nTilsvarende for koder, der kr\u00e6ver 3 bytes:<\/p>\n

      \n
    1. Tre bytes 110yyyyy yxxxxxxx xxxxxxxx<\/b><\/code> angiver et tegn med nummeret yyyyyy yxxxxxxx xxxxxxxx<\/b><\/code>, \u00e6ndrer det aktuelle alfabet<\/em> og f\u00e5 en fungerende kommando. yyyyyy y0000000 00000000<\/b><\/code> (vi huskede alt, undtagen de laveste 15 bits<\/strong>), og s\u00e6tter et flag, at vi nu er i lang<\/em> tilstand (ved tilbageveksling til det to-byte alfabet vil vi nulstille dette flag);<\/li>\n
    2. To bytes 0xxxxxxx xxxxxxxx<\/b><\/code> i lang tilstand er det et tegn fra det aktuelle alfabet. P\u00e5 samme m\u00e5de l\u00e6gger vi det sammen med skiftet fra trin 1. Den eneste forskel er, at nu l\u00e6ser vi to bytes (fordi vi skiftede til denne tilstand).<\/li>\n<\/ol>\n

      \nDet lyder godt: nu, s\u00e5 l\u00e6nge vi skal kodificere tegn fra det samme 7-bit Unicode-omr\u00e5de, bruger vi 1 ekstra byte i starten og kun en byte til hvert tegn.<\/p>\n

      \"Endnu
      \nArbejdet med en af de tidlige versioner. Unders\u00f8ger ofte UTF-8, men der er stadig meget, der kan forbedres.<\/i><\/p>\n

      Hvad er blevet v\u00e6rre? For det f\u00f8rste, er der kommet en tilstand, nemlig det aktuelle alfabet skift<\/em> og flaget lang tilstand<\/em>Dette begr\u00e6nser os yderligere: nu kan de samme tegn kodes forskelligt i forskellige kontekster. S\u00f8gning efter understrenge skal for eksempel g\u00f8res med dette in mente, ikke bare ved at sammenligne bytes. For det andet, s\u00e5 snart vi skiftede alfabet, blev ASCII-tegnkodningen et problem (og det inkluderer ikke kun det latinske alfabet, men ogs\u00e5 grundl\u00e6ggende tegns\u00e6t, herunder mellemrum) \u2014 de kr\u00e6ver en ny alfabet\u00e6ndring ved 0, dvs. endnu en byte (og derefter endnu en for at vende tilbage til vores hoved).<\/p>\n

      \u00c9n alfabet er godt, to er bedre<\/h2>\n

      \nLad os pr\u00f8ve at \u00e6ndre vores bitpr\u00e6fikser lidt ved at presse endnu en ind sammen med de tre ovenfor beskrevne:<\/p>\n

      0xxxxxxx<\/b><\/code> \u2014 1 byte i normal tilstand, 2 i lang tilstand
      \n11xxxxxx<\/b><\/code> \u2014 1 byte
      \n100xxxxx xxxxxxxx<\/b><\/code> \u2014 2 bytes
      \n101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> \u2014 3 bytes<\/p>\n

      \"Endnu
      \n
      \nNu er der blevet en bygbar mindre i den to-byte optagelse \u2014 kodepunkter kan nu rumme op til 0x1FFF<\/b><\/code>, ikke 0x3FFF<\/b><\/code>. Men der er stadig m\u00e6rkbart flere end i to-byte UTF-8 koder; de fleste almindelige sprog kan stadig rummes, den mest m\u00e6rkbare tab er       hiragana<\/a><\/noindex> og katakana<\/a><\/noindex>, japanerne er triste.<\/p>\n

      Hvad er den nye kode 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. N\u00e5r vi skifter det nuv\u00e6rende alfabet, bliver en del af det gamle alfabet til en hj\u00e6lpealfabet. For eksempel, n\u00e5r vi skifter fra ASCII til kyrillisk \u2014 er der nu 64 tegn i \"depotet\", som indeholder det latinske alfabet, cifre, mellemrum og komma<\/strong> (de mest almindelige indsatser i ikke-ASCII tekster). N\u00e5r vi skifter tilbage til ASCII \u2014 vil det hj\u00e6lpe alfabet omfatte hovedparten af det kyrilliske alfabet.<\/p>\n

      Takket v\u00e6re adgangen til to alfabeter kan vi h\u00e5ndtere en st\u00f8rre m\u00e6ngde tekster med minimale omkostninger til alfabet\u00e6ndringer (punktuation vil oftest f\u00f8re tilbage til ASCII, men efter dette kan vi hente mange ikke-ASCII tegn fra det ekstra alfabet uden at skifte tilbage igen).<\/p>\n

      Bonus: ved at definere det ekstra alfabet med et pr\u00e6fiks 11xxxxxx<\/b><\/code> og v\u00e6lge dets initiale forskydning som 0xC0<\/b><\/code>, f\u00e5r vi delvis kompatibilitet med CP1252. Med andre ord, mange (men ikke alle) vesteurop\u00e6iske tekster, der er kodet i CP1252, vil se ens ud i UTF-C.<\/p>\n

      Her opst\u00e5r der dog et problem: hvordan f\u00e5r man det hj\u00e6lpealphabet ud fra det prim\u00e6re alfabet? Man kan lade det samme forskydning blive, men \u2014 desv\u00e6rre \u2014 her spiller Unicode-strukturen allerede imod os. Ofte findes hovedparten af alfabetet ikke i begyndelsen af blokken (for eksempel har det russiske store \"\u0410\" koden 0x0410<\/b><\/code>, selvom det kyrilliske blok starter med 0x0400<\/b><\/code>). S\u00e5ledes, ved at tage de f\u00f8rste 64 tegn i \"reserven\", kan vi muligvis miste adgangen til den afsluttende del af alfabetet.<\/p>\n

      For at l\u00f8se dette problem har jeg manuelt gennemg\u00e5et nogle blokke, der svarer til forskellige sprog, og angivet offset for det hj\u00e6lpealfabet inden for hovedet. Latinske bogstaver har jeg i undtagelsestilf\u00e6lde omorganiseret som base64.<\/p>\n

      \"Endnu<\/p>\n

      De sidste detaljer<\/h2>\n

      \nLad os til sidst overveje, hvor vi stadig kan finjustere noget.<\/p>\n

      Vi bem\u00e6rker, at formatet 101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> giver mulighed for at kode tal op til 0x1FFFFF<\/b><\/code>, mens Unicode slutter tidligere, ved 0x10FFFF<\/b><\/code>. Med andre ord, den sidste kodepunkt vil blive repr\u00e6senteret som 10110000 11111111 11111111<\/b><\/code>. S\u00e5 vi kan sige, at hvis det f\u00f8rste byte har form som 1011xxxx<\/b><\/code> (hvor xxxx<\/b><\/code> st\u00f8rre end 0), betyder det noget andet. For eksempel kan vi tilf\u00f8je yderligere 15 tegn, som konstant er tilg\u00e6ngelige for kodning med \u00e9t byte, men jeg har valgt at g\u00f8re det anderledes.<\/p>\n

      S\u00e5 vi v\u00e6lger nogle udvalgte intervaller, der svarer til emoji, hiragana og katakana, omnummererer dem i en kontinuerlig liste og koder dem med to byte i stedet for tre:<\/p>\n

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

      Perfekt: ovenn\u00e6vnte emoji \u200d\u200d\u200d\"Endnu<\/a><\/noindex>, der best\u00e5r af 7 kodepunkter, fylder 25 byte i UTF-8, men vi fik plads til det i 14<\/strong> (pr\u00e6cis to byte pr. kodepunkt). For \u00f8vrigt n\u00e6gtede Habr at behandle det (b\u00e5de i den gamle og den nye editor), s\u00e5 jeg m\u00e5tte inds\u00e6tte det som et billede.<\/p>\n

      Lad os pr\u00f8ve at l\u00f8se et andet problem. Som vi husker, er hovedalfabetet i f\u00f8rste omgang de h\u00f8jeste 6 bit<\/strong>, som vi har i tankerne, og kl\u00e6ber til koden af hver enkelt dekodet tegn. I tilf\u00e6lde af kinesiske tegn, der befinder sig i blokken 0x4E00<\/b><\/code> \u2013 0x9FFF<\/b><\/code>, er det enten bit 0 eller 1. Det er ikke s\u00e6rlig praktisk: vi skal konstant skifte alfabet mellem disse to v\u00e6rdier (dvs. bruge tre byte). Men lad os bem\u00e6rke, at i lang tilstand kan vi fra selve koden tr\u00e6kke antallet af tegn, som vi koder med den korte tilstand (efter alle de tidligere beskrevne finesser er det 10240) \u2014 s\u00e5 vil omr\u00e5det af tegn flytte sig til 0x2600<\/b><\/code> \u2013 0x77FF<\/b><\/code>, og i dette tilf\u00e6lde vil de \u00f8verste 6 bits (ud af 21) i hele dette omr\u00e5de v\u00e6re lig med 0. S\u00e5ledes vil tegnsekvenserne bruge to byte pr. tegn (hvilket er optimalt for et s\u00e5 stort omr\u00e5de), uden at der opst\u00e5r skift af alfabetet. <\/p>\n

      Alternativ l\u00f8sninger: SCSU, BOCU-1<\/h2>\n

      \nKenderne af Unicode, efter kun at have l\u00e6st titlen p\u00e5 artiklen, vil sandsynligvis hurtigt minde om, at der blandt Unicode-standarderne findes Standard Compression Scheme for Unicode<\/a><\/noindex> (SCSU), som beskriver en kodningsmetode, der ligner den, der er beskrevet i artiklen.<\/p>\n

      Jeg m\u00e5 \u00e6rligt indr\u00f8mme: jeg fandt f\u00f8rst ud af eksistensen af det, da jeg var dybt inde i at skrive min l\u00f8sning. Havde jeg kendt til det fra starten, ville jeg sandsynligvis have fors\u00f8gt at skrive dens implementation i stedet for at finde p\u00e5 min egen tilgang.<\/p>\n

      Det interessante er, at SCSU bruger ideer, der ligner dem, jeg kom frem til selv (i stedet for begrebet 'alfabeter' bruges der 'vinduer', og der er flere tilg\u00e6ngelige end hos mig). Samtidig har dette format ogs\u00e5 ulemper: det ligger lidt t\u00e6ttere p\u00e5 komprimeringsalgoritmer snarere end kodning. Standardet giver mange m\u00e5der at repr\u00e6sentere p\u00e5, men siger ikke noget om, hvordan man v\u00e6lger den optimale \u2014 til det skal encoder bruge nogle heuristikker. S\u00e5ledes vil en SCSU-encoder, der giver god komprimering, v\u00e6re mere kompleks og besv\u00e6rlig end min algoritme.<\/p>\n

      Til sammenligning har jeg overf\u00f8rt en relativt simpel implementering af SCSU til JavaScript \u2014 den viste sig at v\u00e6re sammenlignelig med mit UTF-C i kodevolumen, men i nogle tilf\u00e6lde pr\u00e6sterede den betydeligt d\u00e5rligere (nogle gange kan den dog overg\u00e5 den, men ikke med meget). For eksempel kodede UTF-C tekster p\u00e5 hebraisk og gr\u00e6sk hele 60% bedre end SCSU<\/strong> (sandsynligvis p\u00e5 grund af deres kompakte alfabeter).<\/p>\n

      Jeg vil gerne tilf\u00f8je, at udover SCSU findes der ogs\u00e5 en anden metode til kompakt repr\u00e6sentation af Unicode \u2014 BOCU-1<\/a><\/noindex>, men det sigter mod kompatibilitet med MIME (hvilket ikke var n\u00f8dvendigt for mig), og anvender en lidt anden tilgang til kodning. Jeg har ikke vurderet dens effektivitet, men jeg tror ikke, den vil v\u00e6re h\u00f8jere end SCSU.<\/p>\n

      Mulige forbedringer<\/h2>\n

      \nDen algoritme, jeg har pr\u00e6senteret, er ikke universel by design (heri adskiller mine m\u00e5l sig sandsynligvis mest fra Unicode-konsortiumets m\u00e5l). Jeg har allerede n\u00e6vnt, at den prim\u00e6rt blev udviklet til et specifikt form\u00e5l (opbevaring af flersprogede ordlister i et pr\u00e6fiks-tr\u00e6), og nogle af dens egenskaber kan v\u00e6re mindre velegnede til andre opgaver. Men det faktum, at den ikke er en standard, kan ogs\u00e5 v\u00e6re en fordel \u2014 du kan nemt tilpasse den til dine behov<\/strong>.<\/p>\n

      For eksempel kan man helt klart fjerne tilstedev\u00e6relsen af tilstand, g\u00f8re kodningen stateless \u2014 blot ved ikke at opdatere variablerne afslag<\/b><\/code>, auxOffs<\/b><\/code> og is21Bit<\/b><\/code> i encoder og decoder. I s\u00e5 fald vil det ikke v\u00e6re muligt at pakke sekvenser af tegn fra det samme alfabet effektivt, men der vil v\u00e6re garanti for, at det samme tegn altid kodes med de samme bytes, uanset konteksten.<\/p>\n

      Derudover kan encoderens konfiguration tilpasses til et bestemt sprog ved at \u00e6ndre standardtilstanden \u2014 for eksempel, ved at basere sig p\u00e5 russiske tekster, indstille i starten af encoder og decoder offs = 0x0400<\/b><\/code> og auxOffs = 0<\/b><\/code>. Dette giver is\u00e6r mening i tilf\u00e6lde af stateless-tilstand. Generelt vil det minde om brugen af den gamle ottebiters kodning, men det fjerner ikke muligheden for at inds\u00e6tte tegn fra hele Unicode efter behov.<\/p>\n

      En anden ulempe, som tidligere n\u00e6vnt \u2014 i en omfattende tekst kodet i UTF-C, er der ingen hurtig m\u00e5de at finde gr\u00e6nsen for det tegn, der er t\u00e6ttest p\u00e5 et vilk\u00e5rligt byte. Hvis du sk\u00e6rer de sidste, lad os sige, 100 bytes fra den kodede buffer, risikerer du at f\u00e5 skrammel, som ikke kan bruges til noget. Kodningen er ikke beregnet til opbevaring af multigigabyte logfiler, men generelt kan dette rettes. Et byte 0xBF<\/b><\/code> m\u00e5 aldrig forekomme som det f\u00f8rste byte (men kan v\u00e6re det andet eller tredje). Derfor kan man under kodning inds\u00e6tte en sekvens 0xBF 0xBF 0xBF<\/b><\/code> hvis vi siger 10 KB \u2014 s\u00e5 vil det v\u00e6re tilstr\u00e6kkeligt at scanne det valgte stykke, indtil en lignende mark\u00f8r findes. Efter den sidste 0xBF<\/b><\/code> vil der garanti v\u00e6re begyndelsen af et tegn. (Ved dekodning skal denne sekvens af tre bytes selvf\u00f8lgelig ignoreres.)<\/p>\n

      Sammenfattende<\/h2>\n

      \nHvis du har l\u00e6st dette langt, tillykke! Jeg h\u00e5ber, at du, ligesom jeg, har l\u00e6rt noget nyt (eller genopfrisket det gamle) om Unicode-systemet.<\/p>\n

      \"Endnu
      \nDemonstrationssiden. P\u00e5 eksempel med hebraisk er fordelene b\u00e5de i forhold til UTF-8 og SCSU tydelige.<\/i><\/p>\n

      Det er ikke hensigtsm\u00e6ssigt at betragte de ovenfor beskrevne unders\u00f8gelser som indgreb i standarderne. Men jeg er generelt tilfreds med resultaterne af mit arbejde, s\u00e5 jeg er glad for at de dele<\/a><\/noindex>: for eksempel vejer JS-biblioteket i minimeret form kun 1710 bytes (og har naturligvis ingen afh\u00e6ngigheder). Som jeg n\u00e6vnte f\u00f8r, kan du finde ud af, hvordan det fungerer p\u00e5 demo-siden<\/a><\/noindex> (der er ogs\u00e5 en samling tekster, hvor den kan sammenlignes med UTF-8 og SCSU).<\/p>\n

      Til sidst vil jeg igen p\u00e5pege de situationer, hvor det ikke er v\u00e6rd at bruge UTF-C hvis dine strenge er lange nok (fra 100-200 tegn). I s\u00e5 fald b\u00f8r du overveje at anvende komprimeringsalgoritmer som deflate.<\/b>:<\/p>\n

      Lad os se p\u00e5 de Unicode blokke, der i \u00f8jeblikket kr\u00e6ver tre byte. Hovedsageligt, som allerede n\u00e6vnt, er det kinesiske tegn \u2014 men det er sv\u00e6rt at g\u00f8re noget med, da der er 21 tusinde. Men ogs\u00e5 hiragana og katakana er blevet inkluderet \u2014 og der er ikke s\u00e5 mange, mindre end to hundrede. Og da vi nu har n\u00e6vnt japanerne \u2014 der ligger ogs\u00e5 emoji (faktisk er de spredt mange steder i Unicode, men de vigtigste blokke ligger i omr\u00e5det 0x1F300<\/b><\/code> \u2013 0x1FBFF<\/b><\/code>). Hvis vi t\u00e6nker p\u00e5, at der nu findes emoji, der sammens\u00e6ttes af flere kodepunkter (for eksempel, emoji \u200d\u200d\u200d\"Endnu<\/a><\/noindex> best\u00e5r af hele 7 koder!), s\u00e5 bliver det virkelig trist at bruge tre byte p\u00e5 hver (7\u00d73 = 21 byte for \u00e9n karakter, det er skr\u00e6kkeligt).<\/p>\n