Veel üks jalgratas: salvestame Unicode'i stringid 30-60% kompaktsemalt kui UTF-8

Kui olete arendaja ja silmitsi valikuga kodeeringu osas, siis peaaegu alati on õige lahendus Unicode. Konkreetne esitamise meetod sõltub kontekstist, kuid enamasti on siin samuti universaalne vastus — UTF-8. See on hea seetõttu, et võimaldab kasutada kõiki Unicode'i märke, kulutamata liialt palju baite enamikul juhtudel. Tõsi, keelte puhul, mis ei kasuta ainult ladina tähestikku, tähendab „liialt vähe” vähemalt kaht byte'i sümboli kohta. Kas on võimalik paremini, naasmata eelajaloolistesse kodeeringutesse, mis piiravad meid vaid 256 saadaval sümboliga?

Allpool pakun välja oma katse anda sellele küsimusele vastus ja teostada suhteliselt lihtne algoritm, mis võimaldab salvestada ridu enamikus maailma keeltes, lisamata neid üleliigseid koormusi, mis on omased UTF-8-le.

Äratus. Tõin esile mitmeid olulisi juhtnööre: kirjeldatud lahendust ei pakuta universaalse asendusena UTF-8-le, see sobib vaid kitsas nimekirjas juhtudest (millest kirjutan allpool), ja seda ei tohi mingil juhul kasutada kolmandate osapoolte API-dega suhtlemiseks (kes sellest isegi ei tea). Enamasti sobivad suure hulga tekstiliste andmete kompaktseks hoidmiseks üldotstarbelised tihendamisalgoritmid (näiteks deflate). Lisaks leidsin juba oma lahenduse loomise käigus olemasoleva standardi ise Unicode'is, mis lahendab sama ülesande — see on veidi keerulisem (ja tihti kehvem), kuid siiski vastuvõetud standard, mitte jalgaastatud lahendus. Kannan ka sellest teada.

Unicode ja UTF-8

Alustuseks — paar sõna sellest, mis see üldiselt on Unicode ja UTF-8.

Kuidas on teada, olid varem populaarsed 8-bitised kodeeringud. Nendega oli kõik lihtne: 256 sümbolit saab nummerdada numbritega vahemikus 0 kuni 255, ning numbrid vahemikus 0 kuni 255 on selgelt esitatavad ühe baidina. Kui minna tagasi algusesse, siis ASCII kodeering piirneb isegi 7 bitiga, seega on selle baidiesituses kõige vanem bit null, ja enamik 8-bitisi kodeeringuid on sellega ühilduvad (need erinevad ainult „ülemises” osas, kus vanem bit on üks).

Kuidas eristub Unicode neist kodeeringutest ja miks on sellega seotud korraga mitmed konkreetsed esitused — UTF-8, UTF-16 (BE ja LE), UTF-32? Selgitame järjest.

Peamine Unicode'i standard kirjeldab ainult vastavust tähemärkide (ja mõnel juhul - tähemärkide eraldi komponentide) ja nende numbrite vahel. Ja võimalikke numbreid selles standardis on väga palju - alates 0x00 kuni 0x10FFFF (1 114 112 tükki). Kui me tahaksime sellises vahemikus arvu muutuja sisse panna, ei piisaks meile ei 1 ega 2 baitist. Ja kuna meie protsessorid ei ole kolmbaitsete arvudega väga harjutanud, oleksime sunnitud kasutama terveid 4 baiti ühe tähemärgi jaoks! Just see ongi UTF-32, kuid just selle "rahakulu" tõttu ei ole see formaat populaarne.

Õnneks ei ole Unicode'i tähemärgid korduvad juhuslikult. Nende suur hulk on jaotatud 17 «tasandisse», millest igaüks sisaldab 65536 (0x10000) «koodipunkti». Mõisted „koodipunkt” tähistab siin lihtsalt tähemärgi numbrit, mille Unicode on talle määranud. Kuid nagu eespool mainitud, on Unicode'is nummerdatud mitte ainult eraldi tähemärgid, vaid ka nende komponendid ja teenindusmärkmed (ja mõnikord ei vasta number üldse millelegi - võib-olla ajutiselt, kuid meile pole see niivõrd oluline), seega on korrektsem alati rääkida just numbrite koguarvust, mitte tähemärkidest. Siiski, edaspidigi kasutan sageli sõna „tähemärk”, silmas pidades mõistet „koodipunkt”.

Unicode'i tasandid. Nagu näha, on suur osa (tasandid 4 kuni 13) endiselt kasutamata.

Ja kõige tähelepanuväärsem on see, et kogu peamine „sisu” asub nulltasandil, mida nimetatakse "Basic Multilingual Plane". Kui rida sisaldab teksti mõnes kaasaegses keeles (sealhulgas hiina keeles), ei pääse te sellele tasandilt välja. Kuid ka teisi Unicode'i osasid ei saa välja jätta - näiteks emoji asuvad peamiselt järgmise tasandi lõpus, "Supplementary Multilingual Plane" (see ulatub alates 0x10000 kuni 0x1FFFF). Seetõttu käitub UTF-16 nii: kõik tähemärgid, mis jäävad Basic Multilingual Plane, kodeeritakse „nagu on”, nende vastav kahekohaline number. Kuid osa numbritest selles vahemikus ei tähista üldse konkreetseid tähemärke, vaid osutavad sellele, et pärast seda kaht baidi paari tuleb vaadata veel ühte - kombineerides nende nelja baidi väärtused, saame numbri, mis katab kogu lubatud Unicode'i vahemiku. Seda esitusviisi nimetatakse „suurte paarideks” - võib-olla olete neist kuulnud.

Seega, UTF-16 nõuab ühe "koodipunkti" jaoks kahte või (väga harvadel juhtudel) neli baiti. See on parem kui pidev nelja baitide kasutamine, kuid ladina tähestiku (ja teiste ASCII-märkide) puhul kulutab see sellise kodeerimisega pool salvestatud ruumist nullidele. UTF-8 on loodud seda parandama: ASCII võtab seal nagu varem ainult ühe bait; koodid alates 0x80 kuni 0x7FF — kahest baitist; alates 0x800 kuni 0xFFFF — kolmest ja alates 0x10000 kuni 0x10FFFF — neljast. Ühelt poolt on ladina tähestikul nüüd hästi: tagasiviidatud ühildus ASCII-ga, ning jaotus on ühtlasemalt "jaotatud" 1 kuni 4 baidi vahel. Kuid ladina tähestikust erinevad tähestikud, kahjuks, ei saa UTF-16-ga võrreldes midagi võita, ja paljud nõuavad nüüd kolmandat bait; kahe baitiga kirje katab vahemiku 32 korda vähenenud, ulatudes 0xFFFF kuni 0x7FF, ja see ei hõlma enam ei hiina ega näiteks gruusia keelt. Kirillitsale ja veel viiele tähestikule – rõõm – on vedanud, 2 baiti sümboli peale.

Kuidas see siis välja tuleb? Vaatame, kuidas UTF-8 esindab sümbolite koode:

Numbrite otseseks esitamiseks on siin kasutatud bitte, tähistatud sümboliga x. On näha, et kahe baitiga kirjes on selliseid bitte vaid 11 (16-st). Esialgsed bitid kannavad siin ainult teeninduslikku funktsiooni. Nelja baitiga kirje puhul on koodipunkti number määratud täielikult 21 bitile 32-st – näiliselt peaks siin piisama kolmest baitist (mis annab kokku 24 bitti), kuid teenindusmärgid võtavad liiga palju ruumi.

Kas see on halb? Tegelikult mitte. Ühelt poolt – kui me hoolime väga salvestusruumist, on meil olemas tihendamisalgoritmid, mis kõrvaldavad kergesti kogu liigse entropia ja üleliigsuse. Teiselt poolt – Unicode eesmärk oli anda võimalikult universaalne kodeerimine. Näiteks võime UTF-8-s kodeeritud stringi usaldada koodile, mis töötas varem ainult ASCII-ga, ja ei muretse, et seal näeb sümbolit ASCII vahemikust, mida seal tegelikult ei ole (sest UTF-8-s on kõik baitid, mis algavad nullbitiga – need ongi ASCII). Ja kui me tahame äkki suurt stringist mõne väikese saba ära lõigata, ilma et me seda algusest peale dekodeeriksime (või taastaksime teavet pärast kahjustatud osa) – ei ole meil keeruline leida seda nihke kohta, kust mõni sümbol algab (piisab, kui mööda minna baitsidest, millel on bittide eellane 10).

Miks siis midagi uut välja mõelda?

Samas ajal esineb harva olukordi, kus kokkusurumisalgoritmid nagu deflate ei ole hästi rakendatavad, kuid soov on saavutada kompaktsed stringide salvestamise vormid. Isiklikult olen sellise ülesande ees seisnud, kui olen mõelnud kokkusurutud prefikspuu suure sõnavara jaoks, mis sisaldab sõnu erinevates keeltes. Ühelt poolt on iga sõna väga lühike, seega on selle kokkusurumine ebaefektiivne. Teiselt poolt - puu realiseerimine, millele ma mõtlesin, eeldas, et iga salvestatud stringi bait genereeris eraldi puu tipu, mistõttu oli nende arvu vähendamine väga kasulik. Minu teegis Az.js (nagu ka pymorphy2, millele see põhineb) selline probleem lahendatakse lihtsalt - stringid, mis on pakitud DAWG-sõnaraam, säilitatakse seal vana hea CP1251. Kuid nagu on lihtne mõista, töötab see hästi ainult piiratud tähestikuga - hiina stringi sellesse sõnaraamatusse ei saa juba paigutada.

Eraldi märgin veel ühe ebameeldiva nüansi, mis tekib UTF-8 kasutamisel sellises andmestruktuuris. Ülaltoodud pildilt on näha, et kui sümbolit salvestatakse kahe baitina, siis selle numbri bitid ei paikne järjestikku, vaid on katkenud paari bitti 10 vahepeal: 110xxxxx 10xxxxxx. Selle tõttu, kui sümboli koodis ületatakse teise baidi madalamad 6 bitti (st toimub üleminek 10111111 → 10000000), muutub ka esimene bait. Tulemuseks on, et täht „п” tähistatakse baitidega 0xD0 0xBF, ja järgmine „р” juba 0xD1 0x80. Prefikspuus põhjustab see vanema tipu jagunemise kaheks - üheks prefiksi 0xD0, ja teiseks 0xD1 (kuigi kogu kirillitsa võiks kodeerida ainult teise baidi kaudu).

Mida ma sain

Selle ülesande ees seistes otsustasin natuke mängida bittidega ja samal ajal tutvuda paremini Unicode'i struktuuriga. Tulemuseks sai koodimisformaat UTF-C („C” tähistab compact), mis kulutab ühe koodipunkti jaoks mitte üle 3 baidi ning sageli võimaldab kulutada vaid ühe lisabait terve kodeeritud stringi peale.See toob kaasa selle, et paljude mitte-ASCII tähestike korral osutub selline kodeering 30-60% kompaktselt kui UTF-8..

Olen vormistatud koodimise ja dekodeerimise algoritmide näidised teekidena JavaScriptis ja Go-s., võite neid oma koodis vabalt kasutada. Kuid tahaksin siiski rõhutada, et teataval määral jääb see formaat „jalgrattaks” ja ma ei soovita seda kasutada ilmse arusaamata, miks see teile vajalik on. See on siiski pigem eksperiment kui tõsine „UTF-8 täiustamine”. Sellegipoolest on sealne kood kirjutatud korralikult, kompaktsetena, koos rohkete kommentaaride ja katsetega.

Testide tulemused ja võrdlus UTF-8-ga

Lisaks tegin ma demonstreerimise lehe, kus saab hinnata algoritmi tööd, ja hiljem räägin selle põhimõtetest ja väljatöötamisprotsessist üksikasjalikumalt.

Eemaldame üleliigsed bitid

Aluseks võtsin loomulikult UTF-8. Esimene ja ilmselge asi, mida seal muuta saab — vähendada teenindusbitide arvu igas baitis. Näiteks hakkab esimene bait UTF-8-s alati kas 0, või 11 — ja prefiks 10 on ainult järgnevate baitide jaoks. Asendame prefiksi 11 . Tundub, et 1, ja järgmiste baitide puhul eemaldame prefiksid täielikult. Mis juhtub?

0xxxxxxx — 1 bait
10xxxxxx xxxxxxxx — 2 baiti
110xxxxx xxxxxxxx xxxxxxxx — 3 baiti

Peatus, aga kus on nelja-baitline kirje? See pole enam vajalik — kolme baitiga kirjutamisel on meil nüüd 21 bitti ja seda piisab kuni 0x10FFFF.

Mida me siin ohverdasime? Peamine — sümbolite piiride avastamine juhuslikust buffri kohast. Me ei saa torkida juhuslikku baidi ja leida sealt järgmise sümboli algust. See on meie formaadi piirang, kuid praktikas ei esine sellist vajadust tihti. Üldiselt saame püsida buffri algusest alates (eriti kui on tegemist lühikeste ridadega).

Kaks baitide katvuse olukord on ka paranenud: nüüd annab kaheettevõtmise formaat 14 bitist vahemiku, mis katab koodid kuni 0x3FFF. Hiinlastel ei vea (nende ideogrammid asuvad peamiselt vahemikus 0x4E00 kuni 0x9FFF), kuid gruusia rahvas ja paljud teised on nüüd õnnelikumad — nende keeled mahuvad samuti 2 baiti sümboli kohta.

Sissevõttes oleme dekooder

Nüüd mõtleme ridade omadustele. Sõnaraamatus on sageli sõnad, mis on kirjutatud ühe tähtede alfabeediga, ja paljude teiste tekstide puhul on see samuti tõsi. Oleks hea korra näidata see alfabet, ja seejärel näidata ainult tähtede numbrit selle sees. Vaadakem, kas Unicode'i tabelis olevad sümbolite asukohad aitavad meid.

Nagu ülalpool mainitud, on Unicode jagatud tasanditeks koodide iga 65536. Kuid see ei ole eriti kasulik jaotus (nagu juba mainitud, oleme enamasti nulltasemel). Huvi pakkub jaotus plokkideks. Need vahemikud ei ole enam fikseeritud pikkusega ja omavad rohkem tähendust — reeglina koondavad nad sama tähestiku sümbolid.

Plokk, mis sisaldab bengali tähestiku sümboleid. Kahjuks on ajaloolistel põhjustel see näide üsna ebaühtlasest pakkimisest — 96 sümbolit on juhuslikult hajutatud 128 koodipunkti vahel plokis.

Plokkide algused ja nende suurused on alati 16-kordsed — see on lihtsalt mugavuse tõttu. Lisaks, paljud plokid algavad ja lõppevad väärtustes, mis on 128 või isegi 256 kordne – näiteks, põhikirillika hõivab 256 baiti alates 0x0400 kuni 0x04FF. See on üsna mugav: kui salvestame kordumatu prefiksi 0x04, siis saame igat kirillika sümbolit kirjutada ühe baitiga. Tõsi, me kaotame võimaluse tagasi pöörduda ASCII (ja ükskõik milliste teiste sümbolite) juurde. Seega teeme järgmist:

1. Kaks baiti 10yyyyyy yxxxxxxx ei tähista mitte ainult sümbolit numbriga yyyyyy yxxxxxxx, vaid muudavad kehtivat tähestikku . Tundub, et yyyyyy y0000000 (st me salvestame kõik bitid, välja arvatud madalamad 7 bitti);
2. Üks bait 0xxxxxxx on kehtiva tähestiku sümbol. Selle tuleb lihtsalt liita selle nihkega, mille me salvestasime sammul 1. Seni, kuni me tähestikku ei muuda, on nihke väärtus null, seega oleme ASCII-ga ühilduvad.

Sarnaselt koodide puhul, mis nõuavad 3 bait:

1. Kolm baiti 110yyyyy yxxxxxxx xxxxxxxx tähistavad sümbolit numbriga yyyyyy yxxxxxxx xxxxxxxx, muudab kehtivat tähestikku . Tundub, et yyyyyy y0000000 00000000 (salvestame kõik, välja arvatud madalamad 15 bitti), ja seab märkeruumi, et oleme nüüd pikamas režiimis (tähestiku tagasi keeramisel kahekaupa, me tühistame selle märkeruumi);
2. Kaks baiti 0xxxxxxx xxxxxxxx pikamas režiimis on see kehtiva tähestiku sümbol. Samuti liidame selle sammul 1 saadud nihkega. Kõik erinevused on vaid selles, et nüüd me loeme kahte baiti (sest me oleme sellesse režiimi üle läinud).

Tundub hea: nüüd, seni kuni peame kodeerima sümboleid samas 7-bitises Unicode’i vahemikus, kulutame ühe lisabaiti alguses ja vaid ühe baidi igas sümbolis.

Ühe varase versiooni töö. Juba sageli ületab UTF-8, kuid veel on täiustamiseks ruumi.

Mis on halvenenud? Esiteks, meil on nüüd olek, nimelt kehtiva tähestiku nihke ja märkeruumi pikamas režiimis. See, this additionally restricts us: now the same characters can be encoded differently in different contexts. For example, substring searches will have to take this into account, rather than just comparing bytes. Secondly, once we switched the alphabet, we faced issues with the encoding of ASCII characters (which include not only the Latin alphabet but also basic punctuation, including spaces)—they require a re-switch of the alphabet at 0, meaning an extra byte again (and then another to return to our main one).

One alphabet is good, two is better

Let's try to slightly change our bit prefixes by squeezing in one more alongside the three described above:

0xxxxxxx — 1 byte in normal mode, 2 in long mode
11xxxxxx — 1 bait
100xxxxx xxxxxxxx — 2 baiti
101xxxxx xxxxxxxx xxxxxxxx — 3 baiti

Now with two-byte encoding, there's one less available bit—code points fit up to 0x1FFF, mitte 0x3FFF. However, it's still significantly more than in two-byte UTF-8 codes; the majority of common languages still fit in, the most noticeable loss is from hiragana ja katakana, the Japanese are in sadness.

So what is the new code 11xxxxxx? Это небольшой «загашник» размером в 64 символа, он дополняет наш основной алфавит, поэтому я назвал его вспомогательным (auxiliary) alphabet. When we switch the current alphabet, a piece of the old alphabet becomes auxiliary. For example, switching from ASCII to Cyrillic means we now have 64 characters in the 'warehouse' containing the Latin alphabet, digits, a space, and a comma (the most common insertions in non-ASCII texts). Switching back to ASCII will make the main part of Cyrillic the auxiliary alphabet.

Thanks to access to two alphabets, we can handle a larger amount of text with minimal switching costs (punctuation will often lead to a return to ASCII, but after that, many non-ASCII characters will be retrieved from the additional alphabet, without re-switching).

Bonus: by designating the additional alphabet with a prefix 11xxxxxx and setting its initial offset to 0xC0, we achieve partial compatibility with CP1252. In other words, many (but not all) Western European texts encoded in CP1252 will appear the same in UTF-C.

Here, however, arises the challenge: how to derive an auxiliary alphabet from the main one? You can keep the same offset, but—unfortunately—Unicode structure plays against us here. Very often the main part of the alphabet is not at the beginning of the block (for example, the uppercase 'A' in Russian has code 0x0410, kuigi tsüroliitne blokk algab 0x0400). Nii et, võttes „varustusse“ esimesed 64 sümbolit, võime kaotada ligipääsu tähestiku lõpupoolele.

Selle probleemi lahendamiseks käisin ma käsitsi läbi mõned plokid, mis vastavad erinevatele keeltele, ja märkisin neile põhiallika sees abialfabeedi nihke. Ladina tähestikku, erandina, ümber järjestasin hoopis base64 sarnaselt.

Viimased puudutused

Mõelgem lõpetuseks, kus me saame veel midagi täiustada.

Pane tähele, et formaat 101xxxxx xxxxxxxx xxxxxxxx lubab kodeerida numbreid kuni 0x1FFFFF, kuid Unicode lõpeb varem, number 0x10FFFF. Teisisõnu, viimane koodipunkt esindatakse kui 10110000 11111111 11111111. Nii et, me võime öelda, et kui esimene bait on kujul 1011xxxx kui xxxx suurem kui 0), siis see tähistab midagi muud. Näiteks võib sinna juurde lisada veel 15 sümbolit, mis on pidevalt koodimiseks ühe baidi jagu, kuid ma otsustasin käituda teisiti.

Vaadakem neid Unicode'i plokke, mis praegu nõuavad kolme bait: enamasti, nagu mainitud, on need hiina ideogrammid – aga nendega on raske midagi teha, neid on 21 tuhat. Kuid sinna on juhtunud ka hiragana ja katakana – neid on juba vähem, alla kahesaja. Ja kuna me juba jaapanlastest rääkisime – seal on ka emotikonid (tegelikult on neid palju jaotatud Unicode'is, kuid põhiplokid on vahemikus 0x1F300 – 0x1FBFF). Kui mõelda, et praegu on olemas emotikonid, mis koosnevad mitmest koodipunktist (näiteks emotikon ‍‍‍ koosneb lausa 7 koodist!), siis hakkab tõeliselt kurb olema raisata igaühele kolm bait (7×3 = 21 bait ühe sümboli eest, see on õudne).

Seetõttu valime välja mõned valitud vahemikud, mis vastavad emotikonidele, hiraganale ja katakanale, nummerdame need ühte pidevasse loetellu ja kodeerime kahena baidina kolmest:

1011xxxx xxxxxxxx

Suurepärane: eelmainitud emotikon ‍‍‍, mis koosneb 7 koodipunktist, kasutab UTF-8-s 25 baidi, kuid mahutasime selle 14 kahe baitiga igale koodipunktile). Muide, Habra keeldus seda töötlema (nii vanas kui ka uues toimetajas), nii et tuli see pildina sisestada.

Proovime parandada veel ühte probleemi. Kuidas me mäletame, et põhialfabeet on sisuliselt ülemised 6 bitti, mida me peame meeles ja kinnitame iga dekooditava sümboli koodi. Hiina hieroglüüfide puhul, mis asuvad plokis 0x4E00 – 0x9FFF, on see kas bit 0 või 1. See pole väga mugav: meil tuleb pidevalt vahetada tähestikku nende kahe väärtuse vahel (st kasutada kolm bitti). Kuid märkame, et pikemas režiimis saame koodist lahutada sümbolite arvu, mida kodeerime lühikeses režiimis (aine eelneva kirjeldatud nipi järgi 10240) — siis nihkub hieroglüüfide vahemik 0x2600 – 0x77FF, ja sel juhul on kogu selle vahemiku ülemised 6 bitti (21-st) võrdsed 0-ga. Seega kasutavad hieroglüüfide järjestused iga hieroglüüfi jaoks kahte bitti (mis on suurte vahemike jaoks optimaalselt), põhjustamata tähestiku vahetust.

Alternatiivsed lahendused: SCSU, BOCU-1

Unicode'i asjatundjad, lugedes ainult artikli nime, kiirustavad tõenäoliselt meelde tuletama, et Unicode'i standardite seas on Standard Compression Scheme for Unicode (SCSU), mis kirjeldab kodeerimise meetodit, mis on väga sarnane artiklis kirjeldatuga.

Tunnistan ausalt: tema olemasolust sain ma teada alles pärast seda, kui olin sügavalt oma lahenduse kirjutamisega sisse elanud. Kui oleksin sellest alguses teada, oleksin ilmselt proovinud kirjutada tema rakenduse, mitte välja mõelda oma lähenemist.

Huvitav on see, et SCSU kasutab ideid, mis on väga sarnased sellele, milleni ma ise jõudsin (seal, kus kasutatakse „aknaid“ tähestiku asemel, on neid rohkem, kui mul on). Samas on sellel formaadil ka miinuseid: see on veidi lähemal pakkimisalgoritmidele, mitte kodeerimisele. Eelkõige annab standard palju esitlusviise, kuid ei ütle, kuidas neist parimat valida — selleks peab kodeerija kasutama mingeid heuristikume. Seega on SCSU kodeerija, mis pakub head pakkimist, keerulisem ja mahukam kui minu algoritm.

Võrdluseks tõin suhteliselt lihtsa SCSU rakenduse JavaScriptis — koodi mahult oli see võrreldav minu UTF-C-lahendusega, kuid mõnel juhul näitas see tulemusi, mis olid kümnete protsentide võrra halvemad (mõnikord võib see ka ületada, kuid mitte palju). Näiteks heebrea ja kreeka tekstid kodeeris UTF-C lausa 60% paremini kui SCSU (tõenäoliselt tänu nende kompaktsetele tähestikele).

Lisaks mainin, et lisaks SCSU-le on olemas ka teine kompaktne Unicode'i esitusviis — BOCU-1, kuid selle eesmärk on saavutada ühilduvus MIME-iga (mida mul ei olnud vaja) ning see kasutab veidi teistsugust kodeerimise lähenemist. Ma ei ole selle tõhusust hinnanud, kuid mulle tundub, et see ei saa olla efektiivsem kui SCSU.

Võimalikud täiustused

Kasutatud algoritm ei ole disaini poolest universaalne (selle tõttu lahknevad mu eesmärgid kõige rohkem Unicode'i konsortsiumi eesmärkidest). Olen juba maininud, et see töötati välja peamiselt ühe ülesande jaoks (mitmekeelse sõnaraamatu salvestamine prefiksipuu kujul), ja mõned selle omadused võivad teiste ülesannete jaoks mitte sobida. Kuid fakt, et see ei ole standard, võib olla ka positiivne — saate seda hõlpsasti oma vajadustele kohandada.

Näiteks on ilmne, et võimalik on eemaldada oleku olemasolu, muuta kodeerimine riistadesse mitteoluliseks — lihtsalt mitte värskendada muutujaid kingad, auxOffs ja is21Bit kodeerijas ja dekodeerijas. Sellisel juhul ei saa efektiivselt pakkida sümboolsete järjestusi, kuid on garantii, et sama sümbol kodeeritakse alati samade baitidega, sõltumata kontekstist.

Lisaks võib kodeerijat kohandada konkreetse keele järgi, muutes vaikeseisundi — näiteks, suunates Venemaa tekstide peale, seadistada alguses kodeerijat ja dekodeerijat offs = 0x0400 ja auxOffs = 0. See on eriti mõistlik just staatiliste režiimide korral. Üldiselt sarnaneb see vana 8-bitise kodeerimise kasutamisega, kuid ei välista võimalust vajadusel lisada sümboleid kogu Unicode'ist.

Veel üks varem mainitud puudus — mahukas tekstis, mis on kodeeritud UTF-C-s, ei ole kiiret viisi, kuidas leida sümboli piir, mis asub juhusliku baidi lähedal. Kui lõikate kodeeritud puhverdamist viimased, ütleme, 100 baidi, riskite saada prügi, millega ei saa midagi teha. Suurte logide hoidmiseks ei ole kodeerimine mõeldud, kuid seda on võimalik parandada. Bait 0xBF ei tohi kunagi esimesena esineda (aga see võib olla teine või kolmas). Seetõttu saab kodeerimise käigus lisada järjestuse 0xBF 0xBF 0xBF iga, ütleme, 10 Kb — siis piisab valitud osa skaneerimisest, et leida piir, kuni sarnane marker on leitud. Viimane 0xBF garantereeritult on sümboli algus. (Dekodeerimisel tuleb see kolmest baitist koosnev järjestus muidugi ignoreerida.)

Kokkuvõtteks

Kui olete siiani lugenud — õnnitleme! Loodan, et olete nagu mina midagi uut õppinud (või värskendanud mälu) Unicode'i seadistusest.

Demonstratsioonileht. Heebrea näitel on näha eelistusi nii UTF-8 kui ka SCSU ees.

Ärge käsitlege eespool toodud uurimusi standardite rikkumisena. Siiski olen üldiselt tulemuste üle rahul ja seetõttu olen rõõmuga valmis neid: näiteks JS-raamatukogu minimeeritud kujul kaalub vaid 1710 baiti (ja loomulikult ei ole tal sõltuvusi). Nagu ma enne mainisin, on selle tööga võimalik tutvuda demonstreerimislehe (seal on ka tekstide komplekt, millega seda saab võrrelda UTF-8 ja SCSU-ga).

Lõpetuseks tuletan veel kord meelde olukordi, kus UTF-C-d ei tohiks kasutada:

• Kui teie stringid on piisavalt pikad (100–200 sümbolit). Sel juhul tasub mõelda, kas rakendada kompressioonialgoritme nagu deflate.
• Kui teil on vajalik ASCII läbitavus, see tähendab, et teie jaoks on oluline, et kodeeritud järjestustes ei oleks ASCII-koode, mis ei olnud algses stringis. Selle vajaduse saab vältida, kui edastate kodeerimise tulemuse kui abstraktset baitide kogumit, mitte stringidena, kui suhtlete välistest API-dest (nt töötades andmebaasidega). Vastasel juhul riskite ettenägematute haavatavuste ilmnemisega.
• Kui soovite olla suuteline kiiresti leidma sümbolite piire suvalise nihkega (näiteks kui osa stringist on kahjustatud). Seda saab teha, kuid ainult skaneerides stringi algusest (või rakendades eelmises jaotises kirjeldatud täiustust).
• Kui teil on vaja kiiresti teha toiminguid stringide sisus (sorteerida neid, otsida alamstringe, konkateerida). Sel juhul tuleb stringid esmalt dekodeerida, seega on UTF-C nendes olukordades aeglasem kui UTF-8 (aga kiirem kompressioonialgoritmidest). Kuna sama string kodeeritakse alati ühtemoodi, ei nõua täpne dekodeerimise võrdlemine selle tegemist baitide kaupa.

Uuendus: kasutaja tyomitch allpoolt kommentaarides Jagasin graafiku, mis rõhutab UTF-C rakenduse piire. Näha on, et UTF-C on efektiivsem kui üldotstarbelise tihendamise algoritm (LZW variatsioonid), seni kuni tihendatav tekst on lühem ~140 sümbolit (kuigi pean märkima, et võrdlus viidi läbi ühe teksti põhjal; teiste keelte puhul võib tulemus erineda).


Allikas: habr.com