Jos olet kehittäjä ja joudut valitsemaan koodauksen, Unicode on melkein aina oikea ratkaisu. Erityinen esitystapa riippuu kontekstista, mutta useimmiten tässäkin on universaali vastaus - UTF-8. Hyvä puoli siinä on, että sen avulla voit käyttää kaikkia Unicode-merkkejä ilman kuluja liikaa paljon tavuja useimmissa tapauksissa. Totta, kielille, jotka käyttävät enemmän kuin vain latinalaisia aakkosia, "ei liikaa" on vähintään kaksi tavua per merkki. Pystymmekö paremmin palaamatta esihistoriallisiin koodauksiin, jotka rajoittavat meidät vain 256 merkkiin?
Alla ehdotan tutustumista yritykseeni vastata tähän kysymykseen ja toteuttaa suhteellisen yksinkertainen algoritmi, jonka avulla voit tallentaa rivejä useimmilla maailman kielillä lisäämättä UTF-8:ssa olevaa redundanssia.
Vastuuvapauslauseke. Teen välittömästi muutaman tärkeän varauksen: kuvattua ratkaisua ei tarjota UTF-8:n yleiseksi korvaajaksi, se sopii vain kapeaan luetteloon tapauksista (lisätietoja alla), eikä sitä missään tapauksessa saa käyttää vuorovaikutukseen kolmansien osapuolien API:iden kanssa (jotka eivät edes tiedä siitä). Useimmiten yleiskäyttöiset pakkausalgoritmit (esimerkiksi deflate) soveltuvat suurten tekstidatamäärien kompaktiin tallentamiseen. Lisäksi jo ratkaisuni luomisen aikana löysin itse Unicodesta olemassa olevan standardin, joka ratkaisee saman ongelman - se on hieman monimutkaisempi (ja usein huonompi), mutta silti se on hyväksytty standardi, eikä vain laitettu. yhdessä polvessa. Kerron sinulle myös hänestä.
Tietoja Unicodesta ja UTF-8:sta
Aluksi muutama sana siitä, mitä se on Unicode и UTF-8.
Kuten tiedät, 8-bittiset koodaukset olivat aiemmin suosittuja. Niiden kanssa kaikki oli yksinkertaista: 256 merkkiä voidaan numeroida numeroilla 0-255, ja numerot 0-255 voidaan ilmeisesti esittää yhtenä tavuna. Jos palataan aivan alkuun, ASCII-koodaus on täysin rajoitettu 7 bittiin, joten sen tavuesityksen merkittävin bitti on nolla, ja useimmat 8-bittiset koodaukset ovat yhteensopivia sen kanssa (ne eroavat vain "ylemmästä" osa, jossa merkittävin bitti on yksi ).
Miten Unicode eroaa näistä koodauksista ja miksi siihen liittyy niin monia erityisiä esityksiä - UTF-8, UTF-16 (BE ja LE), UTF-32? Selvitetään se järjestyksessä.
Unicoden perusstandardi kuvaa vain merkkien (ja joissakin tapauksissa merkkien yksittäisten komponenttien) ja niiden numeroiden välistä vastaavuutta. Ja tässä standardissa on paljon mahdollisia numeroita - alkaen 0x00 до 0x10FFFF (1 114 112 kappaletta). Jos haluaisimme laittaa muuttujaan luvun sellaisella alueella, ei 1 eikä 2 tavua riittäisi meille. Ja koska prosessorimme eivät ole kovin suunniteltuja työskentelemään kolmitavuisten numeroiden kanssa, meidän on pakko käyttää jopa 4 tavua merkkiä kohden! Tämä on UTF-32, mutta juuri tämän "tuhlikantaisuuden" vuoksi tämä muoto ei ole suosittu.
Onneksi merkkien järjestys Unicodessa ei ole satunnainen. Heidän koko settinsä on jaettu 17"lentokoneita", joista jokainen sisältää 65536 (0x10000) "koodipisteitä" "Koodipisteen" käsite tässä on yksinkertainen merkin numero, jonka Unicode on määrittänyt sille. Mutta kuten edellä mainittiin, Unicodessa ei vain numeroitu yksittäisiä merkkejä, vaan myös niiden komponentteja ja palvelumerkkejä (ja joskus mikään ei vastaa numeroa - ehkä toistaiseksi, mutta meille tämä ei ole niin tärkeää), joten On oikein puhua aina nimenomaan itse numeroiden lukumäärästä, ei symboleista. Kuitenkin seuraavassa käytän lyhyyden vuoksi usein sanaa "symboli", joka viittaa termiin "koodipiste".
Unicode lentokoneet. Kuten näette, suurin osa siitä (koneet 4-13) on edelleen käyttämättä.
Merkittävintä on, että kaikki tärkein "massa" on nollatasossa, sitä kutsutaan "Monikielinen perustaso". Jos rivi sisältää tekstiä jollakin nykykielellä (mukaan lukien kiina), et mene tämän tason pidemmälle. Mutta et voi myöskään leikata loput Unicodesta - esimerkiksi emojit sijaitsevat pääosin kielen lopussa seuraava kone"Täydentävä monikielinen taso"(se ulottuu alkaen 0x10000 до 0x1FFFF). Joten UTF-16 tekee tämän: kaikki sisällä olevat merkit Monikielinen perustaso, on koodattu "sellaisenaan" vastaavalla kaksitavuisella numerolla. Jotkut tämän alueen numerot eivät kuitenkaan osoita tiettyjä merkkejä, vaan osoittavat, että tämän tavuparin jälkeen meidän on harkittava toista - yhdistämällä näiden neljän tavun arvot yhteen, saadaan numero, joka kattaa koko kelvollinen Unicode-alue. Tätä ideaa kutsutaan "korjauspariksi" – olet ehkä kuullut heistä.
Joten UTF-16 vaatii kaksi tai (erittäin harvoissa tapauksissa) neljä tavua "koodipistettä" kohden. Tämä on parempi kuin neljän tavun käyttäminen koko ajan, mutta latina (ja muut ASCII-merkit) tällä tavalla koodattuina tuhlaa puolet tilasta nollien päälle. UTF-8 on suunniteltu korjaamaan tämä: siinä oleva ASCII vie, kuten ennenkin, vain yhden tavun; koodit alkaen 0x80 до 0x7FF - kaksi tavua; alkaen 0x800 до 0xFFFF - kolme ja alkaen 0x10000 до 0x10FFFF - neljä. Toisaalta latinalaisista aakkosista on tullut hyvä: yhteensopivuus ASCII:n kanssa on palannut ja jakelu on "hajautunut" tasaisemmin 1 - 4 tavua. Mutta muut kuin latinalaiset aakkoset eivät valitettavasti hyödy millään tavalla UTF-16:een verrattuna, ja monet vaativat nyt kolme tavua kahden sijasta – kaksitavuisen tietueen kattama alue on kaventunut 32-kertaiseksi. 0xFFFF до 0x7FF, eikä siihen sisälly kiinaa eikä esimerkiksi georgiaa. Kyrillinen ja viisi muuta aakkosta - hurraa - onnekas, 2 tavua per merkki.
Miksi näin tapahtuu? Katsotaanpa, kuinka UTF-8 edustaa merkkikoodeja:
Tässä käytetään suoraan numeroiden esittämiseen symbolilla merkittyjä bittejä x. Voidaan nähdä, että kaksitavuisessa tietueessa on vain 11 tällaista bittiä (16:sta). Johtavilla biteillä on tässä vain aputoiminto. Nelitavuisen tietueen tapauksessa 21 bitistä 32:sta on varattu koodipistenumerolle - näyttäisi siltä, että kolme tavua (jotka antavat yhteensä 24 bittiä) riittäisi, mutta palvelumerkit syövät liikaa.
Onko tämä huono? Ei oikeastaan. Toisaalta, jos välitämme paljon tilasta, meillä on pakkausalgoritmeja, jotka voivat helposti poistaa kaiken ylimääräisen entropian ja redundanssin. Toisaalta Unicoden tavoitteena oli tarjota mahdollisimman universaali koodaus. Voimme esimerkiksi uskoa UTF-8:lla koodatun rivin koodille, joka on aiemmin toiminut vain ASCII:n kanssa, emmekä pelkää, että se näkee ASCII-alueen merkin, jota ei todellisuudessa ole olemassa (UTF-8:ssa kaikki tavua alkaen nollabitistä - tämä on juuri sitä ASCII). Ja jos haluamme yhtäkkiä leikata pienen hännän pois suuresta merkkijonosta purkamatta sitä heti alusta alkaen (tai palauttaa osan tiedoista vaurioituneen osan jälkeen), meidän on helppo löytää siirtymä, josta merkki alkaa (se riittää ohittaaksesi tavut, joissa on bitti etuliite 10).
Miksi sitten keksiä jotain uutta?
Samaan aikaan on joskus tilanteita, joissa pakkausalgoritmit, kuten deflate, ovat huonosti sovellettavissa, mutta haluat saavuttaa kompaktin merkkijonojen tallennuksen. Itse törmäsin tähän ongelmaan, kun ajattelin rakentamista suurelle sanakirjalle, joka sisältää sanoja mielivaltaisilla kielillä. Toisaalta jokainen sana on hyvin lyhyt, joten sen pakkaaminen on tehotonta. Toisaalta tarkastelemani puutoteutus oli suunniteltu niin, että tallennetun merkkijonon jokainen tavu loi erillisen puupisteen, joten niiden lukumäärän minimointi oli erittäin hyödyllistä. kirjastossani (Kuten , johon se perustuu) samanlainen ongelma voidaan ratkaista yksinkertaisesti - merkkijonot pakataan -sanakirja, tallennettu sinne . Mutta kuten on helppo ymmärtää, tämä toimii hyvin vain rajoitetulle aakkoselle - kiinankielistä riviä ei voi lisätä tällaiseen sanakirjaan.
Haluaisin erikseen mainita vielä yhden epämiellyttävän vivahteen, joka syntyy, kun UTF-8:aa käytetään tällaisessa tietorakenteessa. Yllä olevasta kuvasta näkyy, että kun merkki kirjoitetaan kahdella tavulla, sen numeroon liittyvät bitit eivät tule peräkkäin, vaan ne erotetaan bittiparilla 10 keskellä: 110xxxxx 10xxxxxx. Tästä johtuen, kun toisen tavun alemmat 6 bittiä vuotaa yli merkkikoodissa (eli tapahtuu siirtymä 10111111 → 10000000), myös ensimmäinen tavu muuttuu. Osoittautuu, että kirjain "p" on merkitty tavuilla 0xD0 0xBF, ja seuraava "r" on jo 0xD1 0x80. Etuliitepuussa tämä johtaa pääsolmun jakamiseen kahdeksi - yhdeksi etuliitettä varten 0xD0, ja toinen varten 0xD1 (vaikka koko kyrilliset aakkoset voitiin koodata vain toisella tavulla).
Mitä sain
Tämän ongelman edessä päätin harjoitella pelien pelaamista biteillä ja samalla tutustua hieman paremmin Unicoden rakenteeseen kokonaisuutena. Tuloksena oli UTF-C-koodausmuoto ("C" for kompakti), joka käyttää enintään 3 tavua koodipistettä kohti ja sallii usein vain kulutuksen yksi ylimääräinen tavu koko koodatulle riville. Tämä johtaa siihen, että monissa ei-ASCII-aakkosissa tällainen koodaus osoittautuu 30-60 % kompaktimpi kuin UTF-8.
Olen esittänyt esimerkkejä koodaus- ja dekoodausalgoritmien toteutuksesta muodossa , voit käyttää niitä vapaasti koodissasi. Mutta korostan silti, että tämä muoto on tietyssä mielessä "polkupyörä", enkä suosittele sen käyttöä ymmärtämättä miksi tarvitset sitä. Tämä on edelleen enemmän kokeilu kuin vakava "UTF-8:n parannus". Siitä huolimatta koodi siellä on kirjoitettu siististi, ytimekkäästi, runsaasti kommentteja ja testikattavuutta sisältävänä.
Testitulokset ja vertailu UTF-8:aan
Tein myös , jossa voit arvioida algoritmin suorituskykyä, ja sitten kerron sinulle lisää sen periaatteista ja kehitysprosessista.
Ylimääräisten bittien poistaminen
Otin tietysti perustaksi UTF-8:n. Ensimmäinen ja ilmeisin asia, jota siinä voidaan muuttaa, on vähentää palvelubittien määrää jokaisessa tavussa. Esimerkiksi UTF-8:n ensimmäinen tavu alkaa aina jommallakummalla 0tai 11 -etuliite 10 Vain seuraavilla tavuilla on se. Korvataan etuliite 11 päälle 1, ja seuraavien tavujen etuliitteet poistetaan kokonaan. Mitä tapahtuu?
0xxxxxxx - 1 tavu
10xxxxxx xxxxxxxx - 2 tavua
110xxxxx xxxxxxxx xxxxxxxx - 3 tavua
Odota, missä on neljän tavun tietue? Mutta sitä ei enää tarvita - kun kirjoitat kolmella tavulla, meillä on nyt käytettävissä 21 bittiä ja tämä riittää kaikille numeroille aina 0x10FFFF.
Mitä olemme tässä uhraaneet? Tärkeintä on merkkirajojen havaitseminen mielivaltaisesta paikasta puskurissa. Emme voi osoittaa mielivaltaista tavua ja löytää siitä seuraavan merkin alkua. Tämä on muodomme rajoitus, mutta käytännössä tämä on harvoin välttämätöntä. Pystymme yleensä käymään puskurin läpi alusta alkaen (varsinkin kun on kyse lyhyistä linjoista).
Myös 2-tavuisten kielten peittämisen tilanne on parantunut: nyt kaksitavuinen muoto antaa 14 bitin alueen, ja nämä ovat koodeja aina 0x3FFF. Kiinalaiset ovat epäonnisia (heidän hahmonsa vaihtelevat enimmäkseen 0x4E00 до 0x9FFF), mutta georgialaisilla ja monilla muilla kansoilla on hauskempaa - heidän kielensä mahtuu myös 2 tavuun per merkki.
Anna kooderin tila
Ajatellaan nyt itse linjojen ominaisuuksia. Sanakirja sisältää useimmiten saman aakkoston kirjaimilla kirjoitettuja sanoja, ja tämä pätee myös moniin muihin teksteihin. Tämä aakkosto olisi hyvä ilmoittaa kerran ja sitten vain sen sisällä olevan kirjaimen numero. Katsotaan auttaako Unicode-taulukon merkkien järjestely meitä.
Kuten edellä mainittiin, Unicode on jaettu kone 65536 koodia kukin. Mutta tämä ei ole kovin hyödyllinen jako (kuten jo sanottiin, useimmiten olemme nollatasolla). Mielenkiintoisempi on jako lohkot. Näillä alueilla ei ole enää kiinteää pituutta, ja ne ovat merkityksellisempiä - yleensä jokainen yhdistää merkkejä samasta aakkosesta.
Lohko, joka sisältää bengali-aakkosten merkkejä. Valitettavasti historiallisista syistä tämä on esimerkki ei kovin tiheästä pakkauksesta - 96 merkkiä on kaoottisesti hajallaan 128 lohkokoodipisteen yli.
Lohkojen alkukohdat ja niiden koot ovat aina 16:n kerrannaisia - tämä tehdään yksinkertaisesti mukavuuden vuoksi. Lisäksi monet lohkot alkavat ja päättyvät arvoihin, jotka ovat 128 tai jopa 256 kerrannaisia - esimerkiksi kyrilliset perusaakkoset vievät 256 tavua 0x0400 до 0x04FF. Tämä on varsin kätevää: jos tallennamme etuliitteen kerran 0x04, niin mikä tahansa kyrillinen merkki voidaan kirjoittaa yhteen tavuun. Totta, tällä tavalla menetämme mahdollisuuden palata ASCII:hen (ja muihin hahmoihin yleensä). Siksi teemme näin:
- Kaksi tavua
10yyyyyy yxxxxxxxei vain merkitse symbolia numerollayyyyyy yxxxxxxx, mutta myös muuttaa nykyinen aakkoset päälleyyyyyy y0000000(ts. muistamme kaikki bitit paitsi vähiten merkitsevät 7-bitti); - Yksi tavu
0xxxxxxxtämä on nykyisen aakkoston merkki. Se on vain lisättävä siirtymään, jonka muistimme vaiheessa 1. Vaikka emme vaihtaneet aakkostoa, siirtymä on nolla, joten säilytimme yhteensopivuuden ASCII:n kanssa.
Samoin koodit, jotka vaativat 3 tavua:
- Kolme tavua
110yyyyy yxxxxxxx xxxxxxxxosoittaa symbolin numerollayyyyyy yxxxxxxx xxxxxxxx, muuta nykyinen aakkoset päälleyyyyyy y0000000 00000000(muistan kaiken paitsi nuoremmat 15-bitti) ja valitse ruutu, jossa olemme nyt pitkä tila (kun vaihdat aakkoset takaisin kaksitavuisiksi, nollaamme tämän lipun); - Kaksi tavua
0xxxxxxx xxxxxxxxpitkässä tilassa se on nykyisen aakkoston merkki. Samalla tavalla lisäämme sen siirtymällä vaiheesta 1. Ainoa ero on, että nyt luemme kaksi tavua (koska olemme siirtyneet tähän tilaan).
Kuulostaa hyvältä: nyt kun meidän on koodattava merkkejä samalta 7-bittisellä Unicode-alueella, käytämme alussa yhden ylimääräisen tavun ja yhteensä yhden tavun per merkki.
Toimii jostain aiemmista versioista. Se voittaa jo usein UTF-8:n, mutta parantamisen varaa on vielä.
Mikä on pahempaa? Ensinnäkin meillä on ehto, nimittäin nykyinen aakkosten siirtymä ja valintaruutu pitkä tila. Tämä rajoittaa meitä entisestään: nyt samat merkit voidaan koodata eri tavalla eri yhteyksissä. Esimerkiksi alimerkkijonojen etsiminen on tehtävä ottaen tämä huomioon, eikä vain vertaamalla tavuja. Toiseksi, heti kun muutimme aakkosia, siitä tuli huono ASCII-merkkien koodauksella (ja tämä ei ole vain latinalaisia aakkosia, vaan myös perusvälimerkkejä, mukaan lukien välilyönnit) - ne vaativat aakkosten vaihtamisen uudelleen nollaan, eli jälleen ylimääräinen tavu (ja sitten toinen palataksesi pääkohtaamme).
Yksi aakkosto on hyvä, kaksi on parempi
Yritetään muuttaa hieman bittietuliitteiämme puristaen vielä yksi kolmeen yllä kuvattuun:
0xxxxxxx — 1 tavu normaalitilassa, 2 pitkässä tilassa
11xxxxxx - 1 tavu
100xxxxx xxxxxxxx - 2 tavua
101xxxxx xxxxxxxx xxxxxxxx - 3 tavua
Nyt kaksitavuisessa tietueessa on yksi bitti vähemmän käytettävissä - koodi osoittaa ylöspäin 0x1FFFEikä 0x3FFF. Se on kuitenkin edelleen huomattavasti suurempi kuin kaksitavuisissa UTF-8-koodeissa, yleisimmät kielet mahtuvat edelleen, havaittavin menetys on pudonnut и , japanilaiset ovat surullisia.
Mikä tämä uusi koodi on? 11xxxxxx? Tämä on pieni 64 merkin kokoinen "varasto", se täydentää pääaakkostoamme, joten kutsuin sitä apukirjaimeksi (apu-) aakkoset. Kun vaihdamme nykyistä aakkosta, pala vanhasta aakkosesta tulee apuvälineeksi. Esimerkiksi siirryimme ASCII:stä kyrilliseen - kätkössä on nyt 64 merkkiä, jotka sisältävät Latinalaiset aakkoset, numerot, välilyönti ja pilkku (yleisimmät lisäykset ei-ASCII-teksteihin). Vaihda takaisin ASCII-tilaan - ja kyrillisten aakkosten pääosasta tulee apuaakkosto.
Kahden aakkoston käytön ansiosta pystymme käsittelemään suuren määrän tekstejä minimaalisilla aakkosten vaihtamiskustannuksilla (välimerkit johtavat useimmiten ASCII:een palaamiseen, mutta sen jälkeen saamme lisäaakkosista monia ei-ASCII-merkkejä ilman vaihtaa uudelleen).
Bonus: alaaakkosten etuliite 11xxxxxx ja valita sen alkupoikkeama 0xC0, saamme osittaisen yhteensopivuuden CP1252:n kanssa. Toisin sanoen monet (mutta eivät kaikki) Länsi-Euroopan tekstit, jotka on koodattu CP1252:lla, näyttävät samalta UTF-C:ssä.
Tässä syntyy kuitenkin vaikeus: kuinka saada lisäaakkosesta? Voit jättää saman offsetin, mutta - valitettavasti - täällä Unicode-rakenne pelaa jo meitä vastaan. Hyvin usein aakkosten pääosa ei ole lohkon alussa (esimerkiksi venäjän isolla "A" on koodi 0x0410, vaikka kyrillinen lohko alkaa 0x0400). Siten, kun ensimmäiset 64 merkkiä on tallennettu säilytykseen, saatamme menettää pääsyn aakkosten loppuosaan.
Tämän ongelman korjaamiseksi kävin manuaalisesti läpi joitakin eri kieliä vastaavia lohkoja ja määritin niille apuaakkosten siirtymän pääaakkosten sisällä. Latinalaiset aakkoset järjestettiin poikkeuksena yleensä uudelleen kuten base64.
Viimeiset silaukset
Mietitään vihdoin, missä muualla voisimme parantaa jotain.
Huomaa, että muoto 101xxxxx xxxxxxxx xxxxxxxx voit koodata numeroita aina 0x1FFFFF, ja Unicode päättyy aikaisemmin, klo 0x10FFFF. Toisin sanoen viimeinen koodipiste esitetään muodossa 10110000 11111111 11111111. Siksi voimme sanoa, että jos ensimmäinen tavu on muotoa 1011xxxx (Missä xxxx suurempi kuin 0), se tarkoittaa jotain muuta. Voit esimerkiksi lisätä sinne vielä 15 merkkiä, jotka ovat jatkuvasti käytettävissä koodattavaksi yhdessä tavussa, mutta päätin tehdä sen toisin.
Katsotaan nyt niitä Unicode-lohkoja, jotka vaativat kolme tavua. Periaatteessa, kuten jo mainittiin, nämä ovat kiinalaisia merkkejä - mutta niillä on vaikea tehdä mitään, niitä on 21 tuhatta. Mutta sinne lensi myös hiragana ja katakana - eikä niitä ole enää niin paljon, alle kaksisataa. Ja koska muistimme japanilaiset, siellä on myös emojit (itse asiassa ne ovat hajallaan monissa paikoissa Unicodessa, mutta päälohkot ovat alueella 0x1F300 - 0x1FBFF). Jos ajattelet sitä, että nyt on olemassa hymiöitä, jotka on koottu useista koodipisteistä kerralla (esimerkiksi emoji koostuu jopa 7 koodista!), silloin on täysin sääli kuluttaa kolme tavua jokaiseen (7 × 3 = 21 tavua yhden kuvakkeen vuoksi, painajainen).
Siksi valitsemme muutaman valitun alueen, jotka vastaavat emojia, hiraganaa ja katakanaa, numeroimme ne uudelleen yhdeksi jatkuvaksi luetteloksi ja koodaamme ne kahdeksi tavuksi kolmen sijasta:
1011xxxx xxxxxxxx
Hienoa: edellä mainittu emoji, joka koostuu 7 koodipisteestä, vie 8 tavua UTF-25:ssa ja sovitamme sen sisään 14 (täsmälleen kaksi tavua kutakin koodipistettä kohti). Muuten, Habr kieltäytyi sulattamasta sitä (sekä vanhassa että uudessa editorissa), joten minun piti lisätä se kuvan kanssa.
Yritetään korjata vielä yksi ongelma. Kuten muistamme, perusaakkoset ovat pohjimmiltaan korkea 6 bittiä, jonka pidämme mielessä ja liimaamme jokaisen seuraavan dekoodatun symbolin koodiin. Jos kyseessä ovat kiinalaiset merkit, jotka ovat lohkossa 0x4E00 - 0x9FFF, tämä on joko bitti 0 tai 1. Tämä ei ole kovin kätevää: meidän on jatkuvasti vaihdettava aakkosia näiden kahden arvon välillä (eli kulutettava kolme tavua). Mutta huomaa, että pitkässä tilassa itse koodista voimme vähentää merkkien määrän, jotka koodaamme käyttämällä lyhyttä tilaa (kaikkien yllä kuvattujen temppujen jälkeen tämä on 10240) - sitten hieroglyfien alue siirtyy 0x2600 - 0x77FF, ja tässä tapauksessa koko tällä alueella merkittävin 6 bittiä (21:stä) on yhtä suuri kuin 0. Siten hieroglyfisekvenssit käyttävät kahta tavua hieroglyfiä kohden (mikä on optimaalinen näin suurelle alueelle), ilman aiheuttaa aakkosten vaihtamista.
Vaihtoehtoiset ratkaisut: SCSU, BOCU-1
Unicode-asiantuntijat, jotka ovat juuri lukeneet artikkelin otsikon, kiirehtivät todennäköisesti muistuttamaan, että Unicode-standardien joukossa on (SCSU), joka kuvaa koodausmenetelmää, joka on hyvin samanlainen kuin artikkelissa kuvattu.
Myönnän rehellisesti: sain tietää sen olemassaolosta vasta, kun olin syvästi uppoutunut päätökseni kirjoittamiseen. Jos olisin tiennyt siitä alusta alkaen, olisin todennäköisesti yrittänyt kirjoittaa toteutuksen sen sijaan, että olisin keksinyt oman lähestymistapani.
Mielenkiintoista on, että SCSU käyttää ideoita, jotka ovat hyvin samankaltaisia kuin ne, jotka itse keksin ("aakkosten" sijaan he käyttävät "ikkunoita", ja niitä on enemmän saatavilla kuin minulla). Samaan aikaan tällä formaatilla on myös haittoja: se on hieman lähempänä pakkausalgoritmeja kuin koodausalgoritmeja. Erityisesti standardi antaa monia esitysmenetelmiä, mutta ei kerro kuinka valita optimaalinen - tätä varten kooderin on käytettävä jonkinlaista heuristiikkaa. Näin ollen SCSU-enkooderi, joka tuottaa hyviä pakkauksia, on monimutkaisempi ja hankalampi kuin minun algoritmini.
Vertailun vuoksi siirsin JavaScriptiin suhteellisen yksinkertaisen SCSU-toteutuksen - koodimäärän suhteen se osoittautui UTF-C:heni verrattavissa, mutta joissain tapauksissa tulos oli kymmeniä prosentteja huonompi (joskus voi ylittää sen, mutta ei paljoa). Esimerkiksi heprean ja kreikan tekstit koodattiin UTF-C:llä 60% parempi kuin SCSU (luultavasti heidän kompakteista aakkosistaan).
Lisään erikseen, että SCSU:n lisäksi on myös toinen tapa esittää Unicodea kompaktisti - , mutta se tähtää MIME-yhteensopivuuteen (jota en tarvinnut) ja ottaa hieman erilaisen lähestymistavan koodaukseen. En ole arvioinut sen tehokkuutta, mutta minusta näyttää siltä, että se ei todennäköisesti ole korkeampi kuin SCSU.
Mahdollisia parannuksia
Esittämäni algoritmi ei ole suunnittelultaan universaali (tässä tavoitteeni poikkeavat todennäköisesti eniten Unicode-konsortion tavoitteista). Olen jo maininnut, että se on kehitetty ensisijaisesti yhtä tehtävää varten (monikielisen sanakirjan tallentaminen etuliitepuuhun), ja jotkin sen ominaisuudet eivät välttämättä sovellu muihin tehtäviin. Mutta se, että se ei ole standardi, voi olla plussaa - voit helposti muokata sitä tarpeidesi mukaan.
Esimerkiksi ilmeisellä tavalla voit päästä eroon tilan läsnäolosta, tehdä tilatonta koodausta - älä vain päivitä muuttujia offs, auxOffs и is21Bit kooderissa ja dekooderissa. Tässä tapauksessa ei ole mahdollista pakata tehokkaasti saman aakkoston merkkijonoja, mutta on takuu, että sama merkki on aina koodattu samoilla tavuilla kontekstista riippumatta.
Lisäksi voit räätälöidä kooderin tietylle kielelle muuttamalla oletustilaa - esimerkiksi keskittymällä venäjänkielisiin teksteihin, aseta enkooderi ja dekooderi alussa offs = 0x0400 и auxOffs = 0. Tämä on erityisen järkevää valtiottoman tilan tapauksessa. Yleensä tämä on samanlainen kuin vanhan kahdeksanbittisen koodauksen käyttäminen, mutta poistamatta mahdollisuutta lisätä merkkejä kaikesta Unicodesta tarpeen mukaan.
Toinen aiemmin mainittu haittapuoli on, että suuressa UTF-C-koodatussa tekstissä ei ole nopeaa tapaa löytää mielivaltaista tavua lähinnä olevaa merkkirajaa. Jos katkaiset esimerkiksi viimeiset 100 tavua koodatusta puskurista, voit saada roskia, jolle et voi tehdä mitään. Koodausta ei ole suunniteltu usean gigatavun lokien tallentamiseen, mutta yleensä tämä voidaan korjata. Tavu 0xBF ei saa koskaan esiintyä ensimmäisenä tavuna (mutta se voi olla toinen tai kolmas). Siksi voit lisätä sekvenssin koodattaessa 0xBF 0xBF 0xBF joka, vaikkapa 10 kilotavua - sitten, jos sinun on löydettävä raja, riittää, että skannaat valitun kappaleen, kunnes vastaava merkki löytyy. Viimeisen jälkeen 0xBF on taatusti hahmon alku. (Dekoodattaessa tämä kolmen tavun sarja on tietysti jätettävä huomiotta.)
Yhteenvetona
Jos olet lukenut tähän asti, onnittelut! Toivottavasti sinä, kuten minä, opit jotain uutta (tai virkisit muistisi) Unicoden rakenteesta.
Esittelysivu. Heprean esimerkki osoittaa edut sekä UTF-8:aan että SCSU:han verrattuna.
Yllä kuvattua tutkimusta ei tule pitää standardien loukkauksena. Olen kuitenkin yleisesti ottaen tyytyväinen työni tuloksiin, joten olen tyytyväinen niihin : esimerkiksi pienennetty JS-kirjasto painaa vain 1710 tavua (eikä siinä tietenkään ole riippuvuuksia). Kuten edellä mainitsin, hänen työnsä löytyvät osoitteesta (on myös joukko tekstejä, joiden perusteella sitä voidaan verrata UTF-8:aan ja SCSU:han).
Lopuksi kiinnitän vielä kerran huomion tapauksiin, joissa UTF-C:tä käytetään ei sen arvoista:
- Jos rivisi ovat riittävän pitkiä (100-200 merkkiä). Tässä tapauksessa sinun tulee harkita pakkausalgoritmien, kuten deflate, käyttöä.
- Jos tarvitset ASCII-läpinäkyvyys, eli sinulle on tärkeää, että koodatut sekvenssit eivät sisällä ASCII-koodeja, jotka eivät olleet alkuperäisessä merkkijonossa. Tämän tarve voidaan välttää, jos välität koodaustuloksen abstraktina tavujoukona, etkä merkkijonoina, kun olet vuorovaikutuksessa kolmannen osapuolen API:iden kanssa (esimerkiksi tietokannan kanssa työskennellessäsi). Muuten voit saada odottamattomia haavoittuvuuksia.
- Jos haluat löytää nopeasti merkkien rajat mielivaltaisella siirtymällä (esimerkiksi kun osa rivistä on vaurioitunut). Tämä voidaan tehdä, mutta vain skannaamalla rivi alusta (tai käyttämällä edellisessä osiossa kuvattua muutosta).
- Jos sinun on suoritettava nopeasti toimintoja merkkijonojen sisällölle (lajitella ne, etsiä niistä osamerkkijonoja, ketjuttaa). Tämä edellyttää merkkijonojen dekoodaamista ensin, joten UTF-C on näissä tapauksissa hitaampi kuin UTF-8 (mutta nopeampi kuin pakkausalgoritmit). Koska sama merkkijono koodataan aina samalla tavalla, dekoodauksen tarkkaa vertailua ei tarvita, ja se voidaan tehdä tavu kerrallaan.
Päivitys: käyttäjä julkaisi kaavion, joka korostaa UTF-C:n sovellettavuusrajoja. Se osoittaa, että UTF-C on tehokkaampi kuin yleiskäyttöinen pakkausalgoritmi (LZW:n muunnelma) niin kauan kuin pakattu merkkijono on lyhyempi ~140 merkkiä (Huomaa kuitenkin, että vertailu tehtiin yhdelle tekstille; muilla kielillä tulos voi poiketa).
Lähde: will.com