Kung ikaw ay isang developer at nahaharap ka sa gawain ng pagpili ng isang encoding, ang Unicode ay halos palaging magiging tamang solusyon. Ang tiyak na paraan ng representasyon ay nakasalalay sa konteksto, ngunit kadalasan mayroong isang unibersal na sagot din dito - UTF-8. Ang magandang bagay tungkol dito ay pinapayagan ka nitong gamitin ang lahat ng mga character na Unicode nang hindi gumagasta masyadong maraming maraming byte sa karamihan ng mga kaso. Totoo, para sa mga wikang gumagamit ng higit pa sa alpabetong Latin, hindi bababa sa "hindi masyadong marami". dalawang byte bawat karakter. Magagawa ba natin ang mas mahusay nang hindi bumabalik sa mga prehistoric encoding na naglilimita sa atin sa 256 na available na character lang?
Sa ibaba ay ipinapanukala kong pamilyar ka sa aking pagtatangka na sagutin ang tanong na ito at ipatupad ang isang medyo simpleng algorithm na nagbibigay-daan sa iyo upang mag-imbak ng mga linya sa karamihan ng mga wika sa mundo nang hindi nagdaragdag ng redundancy na nasa UTF-8.
Disclaimer. Agad akong gagawa ng ilang mahahalagang reserbasyon: ang inilarawang solusyon ay hindi inaalok bilang isang unibersal na kapalit para sa UTF-8, ito ay angkop lamang sa isang makitid na listahan ng mga kaso (higit pa sa mga ito sa ibaba), at sa anumang kaso ay hindi ito dapat gamitin upang makipag-ugnayan sa mga third-party na API (na hindi pa nakakaalam tungkol dito). Kadalasan, ang mga pangkalahatang layunin ng compression algorithm (halimbawa, deflate) ay angkop para sa compact na storage ng malalaking volume ng data ng text. Bilang karagdagan, nasa proseso na ng paglikha ng aking solusyon, natagpuan ko ang isang umiiral na pamantayan sa Unicode mismo, na malulutas ang parehong problema - ito ay medyo mas kumplikado (at madalas na mas masahol pa), ngunit ito ay isang tinatanggap na pamantayan, at hindi lamang ilagay magkasama sa tuhod. Sasabihin ko rin sa iyo ang tungkol sa kanya.
Tungkol sa Unicode at UTF-8
Upang magsimula sa, ilang mga salita tungkol sa kung ano ito Unicode ΠΈ UTF-8.
Tulad ng alam mo, sikat ang 8-bit na pag-encode noon. Sa kanila, ang lahat ay simple: 256 na mga character ay maaaring bilangin na may mga numero mula 0 hanggang 255, at ang mga numero mula 0 hanggang 255 ay malinaw na kinakatawan bilang isang byte. Kung babalik tayo sa pinakasimula, ang pag-encode ng ASCII ay ganap na limitado sa 7 bits, kaya ang pinaka makabuluhang bit sa representasyon ng byte nito ay zero, at karamihan sa 8-bit na pag-encode ay katugma dito (naiiba lamang sila sa "itaas" bahagi, kung saan ang pinaka makabuluhang bit ay isa ).
Paano naiiba ang Unicode sa mga encoding na iyon at bakit napakaraming partikular na representasyon ang nauugnay dito - UTF-8, UTF-16 (BE at LE), UTF-32? Ayusin natin ito sa pagkakasunud-sunod.
Ang pangunahing pamantayan ng Unicode ay naglalarawan lamang ng mga sulat sa pagitan ng mga character (at sa ilang mga kaso, mga indibidwal na bahagi ng mga character) at ang kanilang mga numero. At mayroong maraming posibleng mga numero sa pamantayang ito - mula sa 0x00 sa 0x10FFFF (1 piraso). Kung gusto naming maglagay ng isang numero sa ganoong hanay sa isang variable, alinman sa 114 o 112 byte ay hindi magiging sapat para sa amin. At dahil hindi masyadong idinisenyo ang aming mga processor para sa pagtatrabaho sa tatlong-byte na numero, mapipilitan kaming gumamit ng kasing dami ng 1 byte bawat character! Ito ay UTF-2, ngunit ito ay tiyak na dahil sa "pagkaaksaya" na ito na ang format na ito ay hindi popular.
Sa kabutihang palad, ang pagkakasunud-sunod ng mga character sa loob ng Unicode ay hindi random. Ang kanilang buong set ay nahahati sa 17"mga eroplano", ang bawat isa ay naglalaman ng 65536 (0x10000) Β«mga puntos ng code" Ang konsepto ng isang "code point" dito ay simple numero ng karakter, na itinalaga dito ng Unicode. Ngunit, tulad ng nabanggit sa itaas, sa Unicode hindi lamang ang mga indibidwal na character ay binibilang, kundi pati na rin ang kanilang mga bahagi at mga marka ng serbisyo (at kung minsan ay wala sa lahat na tumutugma sa numero - marahil sa ngayon, ngunit para sa amin ito ay hindi napakahalaga), kaya mas tama laging pag-usapan ang tungkol sa bilang ng mga numero mismo, at hindi mga simbolo. Gayunpaman, sa mga sumusunod, para sa kapakanan ng kaiklian, madalas kong gagamitin ang salitang "simbolo", na nagpapahiwatig ng terminong "punto ng code".
Unicode na eroplano. Tulad ng makikita mo, karamihan sa mga ito (eroplano 4 hanggang 13) ay hindi pa rin ginagamit.
Ang pinaka-kapansin-pansin ay ang lahat ng pangunahing "pulp" ay nasa zero plane, ito ay tinatawag na "Basic Multilingual Plane". Kung ang isang linya ay naglalaman ng teksto sa isa sa mga modernong wika (kabilang ang Chinese), hindi ka lalampas sa eroplanong ito. Ngunit hindi mo rin maaaring putulin ang natitirang bahagi ng Unicode - halimbawa, ang emoji ay pangunahing matatagpuan sa dulo ng ang susunod na eroplano,"Karagdagang Multilingual na Eroplano"(umaabot ito mula sa 0x10000 sa 0x1FFFF). Kaya ginagawa ito ng UTF-16: lahat ng character ay nasa loob Basic Multilingual Plane, ay naka-encode na "as is" na may katumbas na dalawang-byte na numero. Gayunpaman, ang ilan sa mga numero sa hanay na ito ay hindi nagpapahiwatig ng mga partikular na character, ngunit nagpapahiwatig na pagkatapos ng pares na ito ng mga byte kailangan nating isaalang-alang ang isa pa - sa pamamagitan ng pagsasama-sama ng mga halaga ng apat na byte na ito, nakakakuha tayo ng isang numero na sumasaklaw sa ang buong wastong hanay ng Unicode. Ang ideyang ito ay tinatawag na βsurrogate couplesββmaaaring narinig mo na sila.
Kaya ang UTF-16 ay nangangailangan ng dalawa o (sa napakabihirang mga kaso) apat na byte bawat "code point". Ito ay mas mahusay kaysa sa paggamit ng apat na byte sa lahat ng oras, ngunit ang Latin (at iba pang mga ASCII character) kapag na-encode sa paraang ito ay nag-aaksaya ng kalahati ng espasyo sa mga zero. Ang UTF-8 ay idinisenyo upang itama ito: Ang ASCII dito ay sumasakop, tulad ng dati, isang byte lamang; mga code mula sa 0x80 sa 0x7FF - dalawang byte; mula sa 0x800 sa 0xFFFF - tatlo, at mula 0x10000 sa 0x10FFFF - apat. Sa isang banda, ang alpabetong Latin ay naging mabuti: ang pagiging tugma sa ASCII ay bumalik, at ang pamamahagi ay mas pantay na "kumakalat" mula 1 hanggang 4 na byte. Ngunit ang mga alpabeto maliban sa Latin, sayang, ay hindi nakikinabang sa anumang paraan kumpara sa UTF-16, at marami ngayon ay nangangailangan ng tatlong byte sa halip na dalawa - ang saklaw na sakop ng isang two-byte na tala ay lumiit ng 32 beses, na may 0xFFFF sa 0x7FF, at hindi kasama dito ang Chinese o, halimbawa, Georgian. Cyrillic at limang iba pang mga alpabeto - hurray - masuwerteng, 2 byte bawat karakter.
Bakit ito nangyayari? Tingnan natin kung paano kinakatawan ng UTF-8 ang mga code ng character:
Direktang kumakatawan sa mga numero, ang mga bit na may markang simbolo ay ginagamit dito x. Ito ay makikita na sa isang dalawang-byte na talaan mayroon lamang 11 tulad na mga bits (sa 16). Ang mga nangungunang bit dito ay mayroon lamang isang pantulong na function. Sa kaso ng isang four-byte record, 21 sa 32 bits ang inilalaan para sa code point number - mukhang sapat na ang tatlong byte (na nagbibigay ng kabuuang 24 bits), ngunit ang mga service marker ay kumakain ng sobra.
masama ba ito? Hindi naman. Sa isang banda, kung marami tayong pakialam sa espasyo, mayroon tayong mga compression algorithm na madaling maalis ang lahat ng sobrang entropy at redundancy. Sa kabilang banda, ang layunin ng Unicode ay magbigay ng pinaka-unibersal na coding na posible. Halimbawa, maaari nating ipagkatiwala ang isang linyang naka-encode sa UTF-8 upang mag-code na dati ay gumana lamang sa ASCII, at huwag matakot na makakakita ito ng character mula sa hanay ng ASCII na talagang wala doon (pagkatapos ng lahat, sa UTF-8 lahat bytes na nagsisimula sa zero bit - ito ay eksakto kung ano ang ASCII). At kung biglang gusto nating putulin ang isang maliit na buntot mula sa isang malaking string nang hindi nagde-decode nito mula pa sa simula (o ibalik ang bahagi ng impormasyon pagkatapos ng isang nasirang seksyon), madali para sa amin na mahanap ang offset kung saan nagsisimula ang isang character (ito ay sapat na upang laktawan ang mga byte na may medyo prefix 10).
Bakit nag-imbento ng bago?
Kasabay nito, paminsan-minsan ay may mga sitwasyon kung kailan hindi naaangkop ang mga algorithm ng compression tulad ng deflate, ngunit gusto mong makamit ang compact na storage ng mga string. Sa personal, nakatagpo ako ng problemang ito kapag nag-iisip tungkol sa pagtatayo para sa isang malaking diksyunaryo kasama ang mga salita sa mga arbitrary na wika. Sa isang banda, ang bawat salita ay napakaikli, kaya ang pag-compress nito ay hindi magiging epektibo. Sa kabilang banda, ang pagpapatupad ng puno na isinasaalang-alang ko ay idinisenyo upang ang bawat byte ng nakaimbak na string ay nakabuo ng isang hiwalay na tuktok ng puno, kaya ang pagliit ng kanilang bilang ay lubhang kapaki-pakinabang. Sa library ko (Tulad ng sa , kung saan ito nakabatay) ang isang katulad na problema ay maaaring malutas nang simple - mga string na naka-pack sa -diksyonaryo, nakaimbak doon sa . Ngunit, tulad ng madaling maunawaan, ito ay gumagana nang maayos para lamang sa isang limitadong alpabeto - isang linya sa Chinese ay hindi maaaring idagdag sa naturang diksyunaryo.
Hiwalay, nais kong tandaan ang isa pang hindi kasiya-siyang nuance na lumitaw kapag gumagamit ng UTF-8 sa naturang istraktura ng data. Ang larawan sa itaas ay nagpapakita na kapag ang isang character ay isinulat bilang dalawang byte, ang mga bit na nauugnay sa numero nito ay hindi darating sa isang hilera, ngunit pinaghihiwalay ng isang pares ng mga bit. 10 nasa gitna: 110xxxxx 10xxxxxx. Dahil dito, kapag ang mas mababang 6 na bits ng pangalawang byte ay umapaw sa code ng character (ibig sabihin, may nagaganap na paglipat 10111111 β 10000000), pagkatapos ay nagbabago rin ang unang byte. Lumalabas na ang titik na "p" ay tinutukoy ng mga byte 0xD0 0xBF, at ang susunod na "r" ay na 0xD1 0x80. Sa isang prefix tree, humahantong ito sa paghahati ng parent node sa dalawa - isa para sa prefix 0xD0, at isa pa para sa 0xD1 (bagama't ang buong Cyrillic alphabet ay maaaring ma-encode lamang ng pangalawang byte).
Ano ang nakuha ko
Nahaharap sa problemang ito, nagpasya akong magsanay sa paglalaro ng mga laro na may mga bits, at sa parehong oras ay mas makilala ang istraktura ng Unicode sa kabuuan. Ang resulta ay ang format ng pag-encode ng UTF-C ("C" para sa siksik), na gumagastos ng hindi hihigit sa 3 byte sa bawat code point, at kadalasang nagbibigay-daan sa iyong gumastos lamang isang dagdag na byte para sa buong naka-encode na linya. Ito ay humahantong sa katotohanan na sa maraming hindi ASCII na mga alpabeto ang gayong pag-encode ay lumalabas na 30-60% mas compact kaysa sa UTF-8.
Nagpakita ako ng mga halimbawa ng pagpapatupad ng encoding at decoding algorithm sa form , malaya mong magagamit ang mga ito sa iyong code. Ngunit idiin ko pa rin na sa isang kahulugan ang format na ito ay nananatiling isang "bisikleta", at hindi ko inirerekomenda ang paggamit nito nang hindi nalalaman kung bakit kailangan mo ito. Ito ay higit pa sa isang eksperimento kaysa sa isang seryosong "pagpapabuti ng UTF-8". Gayunpaman, ang code doon ay nakasulat nang maayos, maigsi, na may malaking bilang ng mga komento at saklaw ng pagsubok.
Mga resulta ng pagsubok at paghahambing sa UTF-8
ginawa ko rin , kung saan maaari mong suriin ang pagganap ng algorithm, at pagkatapos ay sasabihin ko sa iyo ang higit pa tungkol sa mga prinsipyo at proseso ng pag-unlad nito.
Pag-aalis ng mga kalabisan na piraso
Kinuha ko ang UTF-8 bilang batayan, siyempre. Ang una at pinaka-halatang bagay na maaaring baguhin dito ay upang bawasan ang bilang ng mga bit ng serbisyo sa bawat byte. Halimbawa, ang unang byte sa UTF-8 ay palaging nagsisimula sa alinman 0, o kasama 11 - isang prefix 10 Tanging ang mga sumusunod na byte ang mayroon nito. Palitan natin ang prefix 11 sa 1, at para sa mga susunod na byte ay ganap naming aalisin ang mga prefix. Ano ang mangyayari?
0xxxxxxx β 1 byte
10xxxxxx xxxxxxxx - 2 byte
110xxxxx xxxxxxxx xxxxxxxx - 3 byte
Teka, nasaan ang four-byte record? Ngunit hindi na ito kailangan - kapag nagsusulat sa tatlong byte, mayroon na tayong 21 bits na magagamit at ito ay sapat na para sa lahat ng mga numero hanggang sa 0x10FFFF.
Ano ang isinakripisyo natin dito? Ang pinakamahalagang bagay ay ang pagtuklas ng mga hangganan ng character mula sa isang arbitrary na lokasyon sa buffer. Hindi namin maaaring ituro ang isang di-makatwirang byte at mahanap ang simula ng susunod na character mula dito. Ito ay isang limitasyon ng aming format, ngunit sa pagsasanay ito ay bihirang kinakailangan. Karaniwan kaming nagagawang tumakbo sa buffer mula pa sa simula (lalo na pagdating sa mga maikling linya).
Ang sitwasyon na sumasaklaw sa mga wika na may 2 byte ay naging mas mahusay din: ngayon ang two-byte na format ay nagbibigay ng isang hanay ng 14 bits, at ito ay mga code hanggang sa 0x3FFF. Ang mga Intsik ay hindi pinalad (ang kanilang mga karakter ay kadalasang mula sa 0x4E00 sa 0x9FFF), ngunit ang mga Georgian at marami pang ibang mga tao ay mas masaya - ang kanilang mga wika ay umaangkop din sa 2 byte bawat karakter.
Ipasok ang estado ng encoder
Pag-isipan natin ngayon ang tungkol sa mga katangian ng mga linya mismo. Ang diksyunaryo ay kadalasang naglalaman ng mga salitang nakasulat sa mga character ng parehong alpabeto, at totoo rin ito para sa maraming iba pang mga teksto. Mainam na ipahiwatig ang alpabetong ito nang isang beses, at pagkatapos ay ipahiwatig lamang ang numero ng titik sa loob nito. Tingnan natin kung makakatulong sa atin ang pag-aayos ng mga character sa Unicode table.
Tulad ng nabanggit sa itaas, ang Unicode ay nahahati sa eroplano 65536 code bawat isa. Ngunit hindi ito isang napaka-kapaki-pakinabang na dibisyon (tulad ng nasabi na, kadalasan ay nasa zero plane tayo). Mas kawili-wili ang paghahati ni mga bloke. Wala nang nakapirming haba ang mga hanay na ito, at mas makabuluhan - bilang panuntunan, pinagsasama ng bawat isa ang mga character mula sa parehong alpabeto.
Isang bloke na naglalaman ng mga character ng alpabetong Bengali. Sa kasamaang-palad, para sa mga makasaysayang dahilan, ito ay isang halimbawa ng hindi masyadong siksik na packaging - 96 na character ang nakakalat sa 128 block code point.
Ang mga simula ng mga bloke at ang kanilang mga sukat ay palaging multiple ng 16 - ito ay ginagawa para lamang sa kaginhawahan. Bilang karagdagan, maraming mga bloke ang nagsisimula at nagtatapos sa mga halaga na multiple ng 128 o kahit na 256 - halimbawa, ang pangunahing Cyrillic alphabet ay tumatagal ng 256 byte mula 0x0400 sa 0x04FF. Ito ay medyo maginhawa: kung i-save natin ang prefix nang isang beses 0x04, pagkatapos ay anumang Cyrillic character ay maaaring isulat sa isang byte. Totoo, sa ganitong paraan mawawalan tayo ng pagkakataong bumalik sa ASCII (at sa anumang iba pang mga character sa pangkalahatan). Samakatuwid ginagawa namin ito:
- Dalawang byte
10yyyyyy yxxxxxxxhindi lamang nagsasaad ng simbolo na may numeroyyyyyy yxxxxxxx, ngunit baguhin din kasalukuyang alpabeto sayyyyyy y0000000(ibig sabihin, naaalala namin ang lahat ng mga piraso maliban sa mga hindi gaanong mahalaga 7 bit); - Isang byte
0xxxxxxxito ang katangian ng kasalukuyang alpabeto. Kailangan lang itong idagdag sa offset na naalala namin sa hakbang 1. Bagama't hindi namin binago ang alpabeto, zero ang offset, kaya napanatili namin ang pagiging tugma sa ASCII.
Gayundin para sa mga code na nangangailangan ng 3 byte:
- Tatlong byte
110yyyyy yxxxxxxx xxxxxxxxmagpahiwatig ng simbolo na may numeroyyyyyy yxxxxxxx xxxxxxxx, pagbabago kasalukuyang alpabeto sayyyyyy y0000000 00000000(naalala ang lahat maliban sa mga nakababata 15 bit), at lagyan ng tsek ang kahon kung saan tayo naroroon mahaba mode (kapag binago ang alpabeto pabalik sa isang double-byte, ire-reset namin ang flag na ito); - Dalawang byte
0xxxxxxx xxxxxxxxsa long mode ito ang karakter ng kasalukuyang alpabeto. Katulad nito, idinagdag namin ito sa offset mula sa hakbang 1. Ang pagkakaiba lang ay nabasa namin ngayon ang dalawang byte (dahil lumipat kami sa mode na ito).
Mukhang maganda: ngayon habang kailangan naming mag-encode ng mga character mula sa parehong 7-bit na hanay ng Unicode, gumugugol kami ng 1 dagdag na byte sa simula at isang kabuuang isang byte bawat character.
Gumagana mula sa isa sa mga naunang bersyon. Madalas na nitong matalo ang UTF-8, ngunit mayroon pa ring puwang para sa pagpapabuti.
Kung ano ang mas masahol pa? Una, mayroon tayong kondisyon, ibig sabihin kasalukuyang alphabet offset at checkbox mahabang mode. Ito ay higit pang naglilimita sa amin: ngayon ang parehong mga character ay maaaring ma-encode nang iba sa iba't ibang konteksto. Ang paghahanap para sa mga substring, halimbawa, ay kailangang gawin na isinasaalang-alang ito, at hindi lamang sa pamamagitan ng paghahambing ng mga byte. Pangalawa, sa sandaling binago namin ang alpabeto, naging masama ito sa pag-encode ng mga character na ASCII (at hindi lamang ito ang alpabetong Latin, kundi pati na rin ang pangunahing bantas, kabilang ang mga puwang) - kailangan nilang baguhin muli ang alpabeto sa 0, iyon ay, muli ng dagdag na byte (at pagkatapos ay isa pa upang makabalik sa aming pangunahing punto).
Ang isang alpabeto ay mabuti, ang dalawa ay mas mahusay
Subukan nating palitan ng kaunti ang ating mga bit na prefix, na ipasok ang isa pa sa tatlong inilarawan sa itaas:
0xxxxxxx β 1 byte sa normal na mode, 2 sa long mode
11xxxxxx β 1 byte
100xxxxx xxxxxxxx - 2 byte
101xxxxx xxxxxxxx xxxxxxxx - 3 byte
Ngayon sa isang dalawang-byte na tala ay mayroong isang mas kaunting magagamit na bit - ang mga puntos ng code hanggang sa 0x1FFFAt hindi 0x3FFF. Gayunpaman, kapansin-pansing mas malaki pa rin ito kaysa sa mga double-byte na UTF-8 code, ang karamihan sa mga karaniwang wika ay nababagay pa rin, ang pinaka-kapansin-pansing pagkawala ay nawala. ΠΈ , malungkot ang mga Hapon.
Ano ang bagong code na ito? 11xxxxxx? Ito ay isang maliit na "stash" na may sukat na 64 na mga character, pinupunan nito ang aming pangunahing alpabeto, kaya tinawag ko itong pantulong (pantulong) alpabeto. Kapag inilipat natin ang kasalukuyang alpabeto, ang isang piraso ng lumang alpabeto ay nagiging auxiliary. Halimbawa, lumipat kami mula sa ASCII patungong Cyrillic - ang itago ay naglalaman na ngayon ng 64 na character na naglalaman Latin na alpabeto, mga numero, espasyo at kuwit (pinaka madalas na pagsingit sa mga hindi ASCII na teksto). Bumalik sa ASCII - at ang pangunahing bahagi ng Cyrillic alphabet ay magiging pantulong na alpabeto.
Salamat sa pag-access sa dalawang alpabeto, maaari naming hawakan ang isang malaking bilang ng mga teksto na may kaunting gastos para sa paglipat ng mga alpabeto (ang bantas ay kadalasang hahantong sa pagbabalik sa ASCII, ngunit pagkatapos nito ay makakakuha tayo ng maraming hindi ASCII na mga character mula sa karagdagang alpabeto, nang walang lumipat muli).
Bonus: prefixing ang sub-alphabet 11xxxxxx at pagpili ng paunang offset nito 0xC0, nakakakuha kami ng bahagyang compatibility sa CP1252. Sa madaling salita, marami (ngunit hindi lahat) ang mga tekstong Western European na naka-encode sa CP1252 ay magiging pareho sa UTF-C.
Dito, gayunpaman, isang kahirapan ang lumitaw: kung paano makakuha ng isang pantulong na isa mula sa pangunahing alpabeto? Maaari mong iwanan ang parehong offset, ngunit - sayang - dito naglalaro na ang istraktura ng Unicode laban sa amin. Kadalasan ang pangunahing bahagi ng alpabeto ay wala sa simula ng bloke (halimbawa, ang kabisera ng Russia na "A" ay may code 0x0410, kahit na ang Cyrillic block ay nagsisimula sa 0x0400). Kaya, kapag kinuha ang unang 64 na character sa itago, maaari tayong mawalan ng access sa buntot na bahagi ng alpabeto.
Upang ayusin ang problemang ito, mano-mano akong dumaan sa ilang mga bloke na nauugnay sa iba't ibang wika, at tinukoy ang offset ng pantulong na alpabeto sa loob ng pangunahing isa para sa kanila. Ang alpabetong Latin, bilang isang pagbubukod, ay karaniwang muling inayos tulad ng base64.
Mga huling pagpindot
Sa wakas, isipin natin kung saan pa natin mapapabuti ang isang bagay.
Tandaan na ang format 101xxxxx xxxxxxxx xxxxxxxx nagbibigay-daan sa iyong mag-encode ng mga numero hanggang sa 0x1FFFFF, at ang Unicode ay nagtatapos nang mas maaga, sa 0x10FFFF. Sa madaling salita, ang huling code point ay kakatawanin bilang 10110000 11111111 11111111. Samakatuwid, maaari nating sabihin na kung ang unang byte ay nasa anyo 1011xxxx (Saan xxxx mas malaki sa 0), kung gayon iba ang ibig sabihin nito. Halimbawa, maaari kang magdagdag ng isa pang 15 character doon na patuloy na magagamit para sa pag-encode sa isang byte, ngunit nagpasya akong gawin ito nang iba.
Tingnan natin ang mga bloke ng Unicode na nangangailangan ng tatlong byte ngayon. Karaniwan, tulad ng nabanggit na, ito ay mga character na Tsino - ngunit mahirap gawin ang anumang bagay sa kanila, mayroong 21 libo sa kanila. Ngunit ang hiragana at katakana ay lumipad din doon - at hindi na gaanong marami sa kanila, wala pang dalawang daan. At, dahil naalala natin ang mga Hapon, mayroon ding mga emojis (sa katunayan, nakakalat sila sa maraming lugar sa Unicode, ngunit ang mga pangunahing bloke ay nasa hanay. 0x1F300 - 0x1FBFF). Kung iniisip mo ang katotohanan na ngayon ay may mga emoji na pinagsama-sama mula sa ilang mga code point nang sabay-sabay (halimbawa, ang emoji βββ Binubuo ng kasing dami ng 7 code!), pagkatapos ay nagiging isang kumpletong kahihiyan na gumastos ng tatlong byte sa bawat isa (7Γ3 = 21 byte para sa kapakanan ng isang icon, isang bangungot).
Samakatuwid, pumili kami ng ilang napiling hanay na tumutugma sa emoji, hiragana at katakana, muling binibilang ang mga ito sa isang tuloy-tuloy na listahan at i-encode ang mga ito bilang dalawang byte sa halip na tatlo:
1011xxxx xxxxxxxx
Mahusay: ang nabanggit na emoji, na binubuo ng 7 code point, ay tumatagal ng 8 byte sa UTF-25, at pinagkakasya namin ito 14 (eksaktong dalawang byte para sa bawat code point). Siyanga pala, tumanggi si Habr na tunawin ito (kapwa sa luma at sa bagong editor), kaya kinailangan kong ipasok ito ng isang larawan.
Subukan nating ayusin ang isa pang problema. Tulad ng naaalala natin, ang pangunahing alpabeto ay mahalagang mataas na 6 bits, na inilalagay namin sa isip at nakadikit sa code ng bawat susunod na na-decode na simbolo. Sa kaso ng mga Chinese character na nasa block 0x4E00 - 0x9FFF, ito ay alinman sa bit 0 o 1. Ito ay hindi masyadong maginhawa: kakailanganin nating patuloy na ilipat ang alpabeto sa pagitan ng dalawang value na ito (ibig sabihin, gumastos ng tatlong byte). Ngunit tandaan na sa mahabang mode, mula sa code mismo maaari nating ibawas ang bilang ng mga character na na-encode namin gamit ang maikling mode (pagkatapos ng lahat ng mga trick na inilarawan sa itaas, ito ay 10240) - pagkatapos ay ang hanay ng mga hieroglyph ay lilipat sa 0x2600 - 0x77FF, at sa kasong ito, sa buong hanay na ito, ang pinakamahalagang 6 bits (sa 21) ay magiging katumbas ng 0. Kaya, ang mga pagkakasunud-sunod ng hieroglyph ay gagamit ng dalawang byte bawat hieroglyph (na pinakamainam para sa ganoong malaking hanay), nang walang nagiging sanhi ng pagpapalit ng alpabeto.
Mga alternatibong solusyon: SCSU, BOCU-1
Ang mga eksperto sa Unicode, na nabasa pa lang ang pamagat ng artikulo, ay malamang na magmadali upang ipaalala sa iyo na direkta sa mga pamantayan ng Unicode ay mayroong (SCSU), na naglalarawan ng paraan ng pag-encode na halos kapareho ng inilarawan sa artikulo.
Tapat kong inaamin: Nalaman ko lamang ang tungkol sa pagkakaroon nito pagkatapos kong malalim na isawsaw ang aking desisyon. Kung alam ko ang tungkol dito sa simula, malamang na sinubukan kong magsulat ng isang pagpapatupad sa halip na gumawa ng sarili kong diskarte.
Ang kawili-wili ay ang SCSU ay gumagamit ng mga ideya na halos kapareho sa mga naisip ko sa aking sarili (sa halip na ang konsepto ng "mga alpabeto" ay gumagamit sila ng "mga bintana", at mas marami sa kanila ang magagamit kaysa sa akin). Kasabay nito, ang format na ito ay mayroon ding mga disadvantages: mas malapit ito sa mga algorithm ng compression kaysa sa pag-encode. Sa partikular, ang pamantayan ay nagbibigay ng maraming mga pamamaraan ng representasyon, ngunit hindi sinasabi kung paano pipiliin ang pinakamainam - para dito, ang encoder ay dapat gumamit ng ilang uri ng heuristics. Kaya, ang isang SCSU encoder na gumagawa ng magandang packaging ay magiging mas kumplikado at mas mahirap kaysa sa aking algorithm.
Para sa paghahambing, inilipat ko ang isang medyo simpleng pagpapatupad ng SCSU sa JavaScript - sa mga tuntunin ng dami ng code ito ay naging maihahambing sa aking UTF-C, ngunit sa ilang mga kaso ang resulta ay sampu-sampung porsyento na mas masahol pa (minsan ay maaaring lumampas ito, ngunit hindi masyado). Halimbawa, ang mga teksto sa Hebrew at Greek ay na-encode ng UTF-C 60% mas mahusay kaysa sa SCSU (marahil dahil sa kanilang mga compact na alpabeto).
Hiwalay, idaragdag ko na bukod sa SCSU ay mayroon ding isa pang paraan para siksikang kumatawan sa Unicode - , ngunit nilalayon nito ang pagiging tugma ng MIME (na hindi ko kailangan) at tumatagal ng bahagyang naiibang diskarte sa pag-encode. Hindi ko nasuri ang pagiging epektibo nito, ngunit tila sa akin ay malamang na hindi ito mas mataas kaysa sa SCSU.
Mga posibleng pagpapabuti
Ang algorithm na ipinakita ko ay hindi unibersal sa pamamagitan ng disenyo (ito ay marahil kung saan ang aking mga layunin ay higit na nag-iiba mula sa mga layunin ng Unicode Consortium). Nabanggit ko na na ito ay pangunahing binuo para sa isang gawain (pag-iimbak ng isang multilingual na diksyunaryo sa isang prefix tree), at ang ilan sa mga tampok nito ay maaaring hindi angkop para sa iba pang mga gawain. Ngunit ang katotohanan na ito ay hindi isang pamantayan ay maaaring maging isang plus - madali mo itong mababago upang umangkop sa iyong mga pangangailangan.
Halimbawa, sa malinaw na paraan maaari mong alisin ang pagkakaroon ng estado, gumawa ng stateless coding - huwag lang mag-update ng mga variable offs, auxOffs ΠΈ is21Bit sa encoder at decoder. Sa kasong ito, hindi posible na epektibong mag-pack ng mga pagkakasunud-sunod ng mga character ng parehong alpabeto, ngunit magkakaroon ng garantiya na ang parehong character ay palaging naka-encode na may parehong mga byte, anuman ang konteksto.
Bilang karagdagan, maaari mong iangkop ang encoder sa isang partikular na wika sa pamamagitan ng pagbabago ng default na estado - halimbawa, tumuon sa mga tekstong Ruso, itakda ang encoder at decoder sa simula offs = 0x0400 ΠΈ auxOffs = 0. Ito ay may katuturan lalo na sa kaso ng stateless mode. Sa pangkalahatan, ito ay magiging katulad ng paggamit ng lumang eight-bit encoding, ngunit nang hindi inaalis ang kakayahang magpasok ng mga character mula sa lahat ng Unicode kung kinakailangan.
Ang isa pang disbentaha na binanggit kanina ay na sa malaking text na naka-encode sa UTF-C ay walang mabilis na paraan upang mahanap ang hangganan ng character na pinakamalapit sa isang arbitrary na byte. Kung pinutol mo ang huli, sabihin nating, 100 byte mula sa naka-encode na buffer, nanganganib kang makakuha ng basura na wala kang magagawa. Ang pag-encode ay hindi idinisenyo para sa pag-iimbak ng mga multi-gigabyte na log, ngunit sa pangkalahatan ito ay maaaring itama. Byte 0xBF hindi dapat lumitaw bilang unang byte (ngunit maaaring pangalawa o pangatlo). Samakatuwid, kapag nag-encode, maaari mong ipasok ang pagkakasunud-sunod 0xBF 0xBF 0xBF bawat, sabihin nating, 10 KB - pagkatapos, kung kailangan mong makahanap ng hangganan, sapat na upang i-scan ang napiling piraso hanggang sa makita ang isang katulad na marker. Kasunod ng huli 0xBF ay garantisadong simula ng isang karakter. (Kapag nagde-decode, ang sequence na ito ng tatlong byte, siyempre, ay kailangang balewalain.)
Lagom
Kung nabasa mo na ito, congratulations! Sana, tulad ko, may natutunan kang bago (o na-refresh ang iyong memorya) tungkol sa istruktura ng Unicode.
Pahina ng demo. Ang halimbawa ng Hebrew ay nagpapakita ng mga pakinabang sa parehong UTF-8 at SCSU.
Ang inilarawan sa itaas na pananaliksik ay hindi dapat ituring na isang pagsalakay sa mga pamantayan. Gayunpaman, sa pangkalahatan ay nasisiyahan ako sa mga resulta ng aking trabaho, kaya masaya ako sa kanila : halimbawa, ang isang minified JS library ay tumitimbang lamang ng 1710 bytes (at walang mga dependency, siyempre). Tulad ng nabanggit ko sa itaas, ang kanyang trabaho ay matatagpuan sa (mayroon ding hanay ng mga teksto kung saan maihahambing ito sa UTF-8 at SCSU).
Sa wakas, bibigyan ko muli ng pansin ang mga kaso kung saan ginagamit ang UTF-C hindi nagkakahalaga ito:
- Kung sapat ang haba ng iyong mga linya (mula sa 100-200 character). Sa kasong ito, dapat mong isipin ang tungkol sa paggamit ng mga compression algorithm tulad ng deflate.
- Kung kailangan mo Transparency ng ASCII, ibig sabihin, mahalaga para sa iyo na ang mga naka-encode na sequence ay hindi naglalaman ng mga ASCII code na wala sa orihinal na string. Ang pangangailangan para dito ay maiiwasan kung, kapag nakikipag-ugnayan sa mga third-party na API (halimbawa, nagtatrabaho sa isang database), ipapasa mo ang resulta ng pag-encode bilang abstract na hanay ng mga byte, at hindi bilang mga string. Kung hindi, nanganganib kang makakuha ng mga hindi inaasahang kahinaan.
- Kung gusto mong mabilis na mahanap ang mga hangganan ng character sa isang arbitrary na offset (halimbawa, kapag nasira ang bahagi ng isang linya). Magagawa ito, ngunit sa pamamagitan lamang ng pag-scan sa linya mula sa simula (o paglalapat ng pagbabagong inilarawan sa nakaraang seksyon).
- Kung kailangan mong mabilis na magsagawa ng mga operasyon sa mga nilalaman ng mga string (pagbukud-bukurin ang mga ito, maghanap ng mga substring sa kanila, pagdugtungin). Nangangailangan ito ng mga string na ma-decode muna, kaya ang UTF-C ay magiging mas mabagal kaysa sa UTF-8 sa mga kasong ito (ngunit mas mabilis kaysa sa mga compression algorithm). Dahil ang parehong string ay palaging naka-encode sa parehong paraan, ang eksaktong paghahambing ng pag-decode ay hindi kinakailangan at maaaring gawin sa isang byte-by-byte na batayan.
I-update: gumagamit nag-post ng graph na nagha-highlight sa mga limitasyon sa pagkakalapat ng UTF-C. Ipinapakita nito na ang UTF-C ay mas mahusay kaysa sa isang pangkalahatang layunin na compression algorithm (isang variation ng LZW) hangga't ang naka-pack na string ay mas maikli. ~140 character (gayunpaman, tandaan ko na ang paghahambing ay isinagawa sa isang teksto; para sa iba pang mga wika ang resulta ay maaaring magkakaiba).
Pinagmulan: www.habr.com