Bir tərtibatçısınızsa və kodlaşdırma seçmək vəzifəsi ilə qarşılaşırsınızsa, Unicode demək olar ki, həmişə düzgün həll olacaqdır. Xüsusi təmsil üsulu kontekstdən asılıdır, lakin çox vaxt burada universal bir cavab var - UTF-8. Bunun yaxşı tərəfi, xərcləmədən bütün Unicode simvollarından istifadə etməyə imkan verməsidir çoxdur əksər hallarda çox bayt. Düzdür, latın əlifbasından daha çox istifadə edən dillər üçün “çox deyil” ən azı simvol başına iki bayt. Bizi yalnız 256 mövcud simvolla məhdudlaşdıran tarixdən əvvəlki kodlaşdırmalara qayıtmadan daha yaxşısını edə bilərikmi?
Aşağıda bu suala cavab vermək cəhdimlə tanış olmağı və UTF-8-də olan artıqlığı əlavə etmədən dünyanın əksər dillərində sətirləri saxlamağa imkan verən nisbətən sadə bir alqoritmi həyata keçirməyi təklif edirəm.
İmtina. Dərhal bir neçə vacib qeyd edəcəyəm: təsvir olunan həll UTF-8 üçün universal bir əvəz kimi təklif edilmir, o, yalnız işlərin dar siyahısına uyğundur (aşağıda daha ətraflı) və heç bir halda üçüncü tərəf API-ləri ilə qarşılıqlı əlaqə üçün istifadə edilməməlidir (hətta bunu bilmir). Çox vaxt ümumi təyinatlı sıxılma alqoritmləri (məsələn, deflate) böyük həcmli mətn məlumatlarının yığcam saxlanması üçün uyğundur. Bundan əlavə, artıq öz həllimi yaratma prosesində mən Unicode-un özündə eyni problemi həll edən mövcud bir standart tapdım - bu, bir qədər daha mürəkkəbdir (və tez-tez daha pisdir), lakin yenə də qəbul edilmiş standartdır və sadəcə qoymaq deyil. diz üstə birlikdə. Mən də sizə onun haqqında danışacağam.
Unicode və UTF-8 haqqında
Başlamaq üçün bunun nə olduğu haqqında bir neçə kəlmə Unicode и UTF-8.
Bildiyiniz kimi, əvvəllər 8 bitlik kodlaşdırmalar məşhur idi. Onlarla hər şey sadə idi: 256 simvol 0-dan 255-ə qədər rəqəmlərlə nömrələnə bilər və 0-dan 255-ə qədər rəqəmlər açıq şəkildə bir bayt kimi göstərilə bilər. Ən əvvəlinə qayıtsaq, ASCII kodlaşdırması tamamilə 7 bitlə məhdudlaşır, ona görə də onun bayt təmsilindəki ən əhəmiyyətli bit sıfırdır və əksər 8 bitlik kodlaşdırmalar onunla uyğun gəlir (onlar yalnız "yuxarı" ilə fərqlənirlər. hissə, burada ən əhəmiyyətli bit birdir).
Unicode bu kodlaşdırmalardan nə ilə fərqlənir və nə üçün bu qədər spesifik təqdimatlar onunla əlaqələndirilir - UTF-8, UTF-16 (BE və LE), UTF-32? Gəlin bunu ardıcıllıqla sıralayaq.
Əsas Unicode standartı yalnız simvollar (və bəzi hallarda simvolların fərdi komponentləri) və onların nömrələri arasındakı yazışmaları təsvir edir. Və bu standartda çox sayda mümkün rəqəm var - dən 0x00 üzrə 0x10FFFF (1 ədəd). Belə diapazonda olan rəqəmi dəyişənə daxil etmək istəsək, bizə nə 114, nə də 112 bayt kifayət edərdi. Prosessorlarımız üç baytlıq nömrələrlə işləmək üçün o qədər də nəzərdə tutulmadığından, hər bir simvol üçün 1 bayt istifadə etmək məcburiyyətində qalacağıq! Bu UTF-2-dir, lakin məhz bu “israfçılıq” səbəbindən bu format populyar deyil.
Xoşbəxtlikdən, Unicode daxilində simvolların sırası təsadüfi deyil. Onların bütün dəsti 17 "ə bölünür.təyyarələr", hər birində 65536 (0x10000) «kod nöqtələri" Burada “kod nöqtəsi” anlayışı sadədir simvol nömrəsi, ona Unicode tərəfindən təyin edilmişdir. Lakin, yuxarıda qeyd edildiyi kimi, Unicode-da təkcə fərdi simvollar deyil, həm də onların komponentləri və xidmət nişanları nömrələnir (və bəzən heç bir şey nömrəyə uyğun gəlmir - bəlkə də hələlik, amma bizim üçün bu o qədər də vacib deyil), buna görə də daha düzgündür, həmişə simvolların deyil, rəqəmlərin sayının özləri haqqında danışın. Bununla belə, aşağıda qısalıq üçün mən tez-tez “kod nöqtəsi” ifadəsini nəzərdə tutan “simvol” sözündən istifadə edəcəyəm.
Unicode təyyarələri. Gördüyünüz kimi, onun çox hissəsi (4-dən 13-ə qədər olan təyyarələr) hələ də istifadə olunmur.
Ən diqqətəlayiq odur ki, bütün əsas "pulpa" sıfır müstəvisində yerləşir, buna "Əsas Çoxdilli Təyyarə". Əgər sətirdə müasir dillərdən birində (Çin də daxil olmaqla) mətn varsa, siz bu müstəvidən kənara çıxmayacaqsınız. Ancaq Unicode-un qalan hissəsini də kəsə bilməzsiniz - məsələn, emoji əsasən sonunda yerləşir. növbəti təyyarə"Əlavə çoxdilli təyyarə"(dan uzanır 0x10000 üzrə 0x1FFFF). Beləliklə, UTF-16 bunu edir: daxil olan bütün simvollar Əsas Çoxdilli Təyyarə, müvafiq iki baytlıq nömrə ilə “olduğu kimi” kodlanır. Bununla birlikdə, bu diapazondakı bəzi nömrələr ümumiyyətlə xüsusi simvolları göstərmir, lakin bu cüt baytdan sonra başqa birini nəzərdən keçirməli olduğumuzu göstərir - bu dörd baytın dəyərlərini birləşdirərək, əhatə edən bir nömrə alırıq. bütün etibarlı Unicode diapazonu. Bu ideya "surroqat cütlər" adlanır - siz onlar haqqında eşitmisiniz.
Beləliklə, UTF-16 "kod nöqtəsi" üçün iki və ya (çox nadir hallarda) dörd bayt tələb edir. Bu, hər zaman dörd baytdan istifadə etməkdən daha yaxşıdır, lakin Latın dili (və digər ASCII simvolları) bu şəkildə kodlandıqda boş yerin yarısını sıfırlara sərf edir. UTF-8 bunu düzəltmək üçün nəzərdə tutulmuşdur: ASCII, əvvəlki kimi, yalnız bir bayt tutur; -dən kodlar 0x80 üzrə 0x7FF - iki bayt; -dan 0x800 üzrə 0xFFFF - üç və dən 0x10000 üzrə 0x10FFFF - dörd. Bir tərəfdən, Latın əlifbası yaxşı oldu: ASCII ilə uyğunluq qayıtdı və paylama 1-dən 4 bayta qədər daha bərabər şəkildə "yayıldı". Ancaq Latın dilindən başqa əlifbalar, təəssüf ki, UTF-16 ilə müqayisədə heç bir fayda vermir və bir çoxları indi iki əvəzinə üç bayt tələb edir - iki baytlıq rekordun əhatə etdiyi diapazon 32 dəfə daraldı. 0xFFFF üzrə 0x7FF, və nə Çin, nə də məsələn, gürcü bura daxil deyil. Kiril və digər beş əlifba - hurray - şanslı, hər simvol üçün 2 bayt.
Bu niyə baş verir? UTF-8-in simvol kodlarını necə təmsil etdiyinə baxaq:
Birbaşa rəqəmləri təmsil etmək üçün burada simvolla işarələnmiş bitlərdən istifadə olunur x. Görünür ki, iki baytlıq qeyddə yalnız 11 belə bit var (16-dan). Buradakı aparıcı bitlər yalnız köməkçi funksiyaya malikdir. Dörd baytlıq qeyd vəziyyətində, kod nöqtəsi nömrəsi üçün 21 bitdən 32-i ayrılır - üç bayt (ümumi 24 bit verən) kifayət edər, lakin xidmət markerləri çox yeyir.
Bu pisdir? Həqiqətən yox. Bir tərəfdən, kosmosa çox əhəmiyyət veririksə, bütün əlavə entropiya və artıqlığı asanlıqla aradan qaldıra bilən sıxılma alqoritmlərimiz var. Digər tərəfdən, Unicode-un məqsədi mümkün olan ən universal kodlaşdırmanı təmin etmək idi. Məsələn, UTF-8-də kodlanmış sətri əvvəllər yalnız ASCII ilə işləyən koda həvalə edə bilərik və onun ASCII diapazonundan əslində orada olmayan simvolu görəcəyindən qorxmayaq (axı UTF-8-də hamısı sıfır bitdən başlayan baytlar - ASCII məhz budur). Və əgər birdən böyük bir sətirdən kiçik quyruğu lap əvvəldən deşifrə etmədən kəsmək istəsək (və ya zədələnmiş hissədən sonra məlumatın bir hissəsini bərpa etsək), simvolun başladığı yerdə ofset tapmaq bizim üçün asandır (bu kifayətdir). bir az prefiksi olan baytları atlamaq üçün 10).
Bəs niyə yeni bir şey icad?
Eyni zamanda, deflate kimi sıxılma alqoritmlərinin zəif tətbiq olunduğu hallar olur, lakin siz sətirlərin yığcam saxlanmasına nail olmaq istəyirsiniz. Şəxsən mən tikinti haqqında düşünəndə bu problemlə qarşılaşdım ixtiyari dillərdə sözlər daxil olmaqla böyük lüğət üçün. Bir tərəfdən, hər bir söz çox qısadır, ona görə də onu sıxışdırmaq təsirsiz olacaq. Digər tərəfdən, hesab etdiyim ağac tətbiqi elə qurulmuşdu ki, saxlanılan sətirin hər bir baytı ayrı bir ağac təpəsi yaratdı, buna görə də onların sayını minimuma endirmək çox faydalı oldu. Kitabxanamda (olduğu kimi , onun əsaslandığı) oxşar problem sadəcə həll edilə bilər - strings daxil doludur -Lüğət, orada saxlanılır . Ancaq başa düşmək asan olduğu kimi, bu, yalnız məhdud əlifba üçün yaxşı işləyir - Çin dilində bir xətt belə bir lüğətə əlavə edilə bilməz.
Ayrı-ayrılıqda, belə bir məlumat strukturunda UTF-8 istifadə edərkən ortaya çıxan daha bir xoşagəlməz nüansı qeyd etmək istərdim. Yuxarıdakı şəkil göstərir ki, simvol iki bayt olaraq yazıldıqda onun nömrəsinə aid olan bitlər ard-arda gəlmir, bir cüt bitlə ayrılır. 10 ortasında: 110xxxxx 10xxxxxx. Buna görə, simvol kodunda ikinci baytın aşağı 6 biti daşdıqda (yəni keçid baş verir) 10111111 → 10000000), onda birinci bayt da dəyişir. Belə çıxır ki, “p” hərfi baytla işarələnir 0xD0 0xBF, və növbəti “r” artıqdır 0xD1 0x80. Prefiks ağacında bu, ana düyünün ikiyə bölünməsinə gətirib çıxarır - biri prefiks üçün 0xD0, və digəri üçün 0xD1 (baxmayaraq ki, bütün kiril əlifbası yalnız ikinci baytla kodlana bilərdi).
Mən nə aldım
Bu problemlə qarşılaşaraq, bitlərlə oyun oynamağı məşq etmək və eyni zamanda bütövlükdə Unicode-un strukturu ilə bir az daha yaxından tanış olmaq qərarına gəldim. Nəticə UTF-C kodlaşdırma formatı oldu ("C" üçün yığcam), kod nöqtəsi üçün 3 baytdan çox olmayan və çox vaxt yalnız xərcləməyə imkan verir bütün kodlanmış xətt üçün əlavə bir bayt. Bu, bir çox qeyri-ASCII əlifbalarında belə kodlaşdırmanın olduğu ortaya çıxır UTF-30-dən 60-8% daha yığcam.
Kodlaşdırma və deşifrə alqoritmlərinin həyata keçirilməsinə dair nümunələri formada təqdim etmişəm , siz onları kodunuzda sərbəst istifadə edə bilərsiniz. Amma yenə də vurğulayacağam ki, müəyyən mənada bu format “velosiped” olaraq qalır və mən ondan istifadə etməyi məsləhət görmürəm. niyə lazım olduğunu başa düşmədən. Bu, ciddi "UTF-8-in təkmilləşdirilməsindən" daha çox təcrübədir. Bununla belə, oradakı kod səliqəli, yığcam, çoxlu sayda şərh və test əhatəsi ilə yazılmışdır.
Test nəticələri və UTF-8 ilə müqayisə
Mən də etdim , burada alqoritmin performansını qiymətləndirə bilərsiniz, sonra onun prinsipləri və inkişaf prosesi haqqında sizə daha ətraflı məlumat verəcəyəm.
Lazımsız bitlərin aradan qaldırılması
Mən UTF-8-i əsas götürdüm, əlbəttə. Onda dəyişdirilə bilən ilk və ən açıq şey hər baytda xidmət bitlərinin sayını azaltmaqdır. Məsələn, UTF-8-də ilk bayt həmişə hər ikisi ilə başlayır 0, və ya ilə 11 - prefiks 10 Yalnız aşağıdakı baytlarda var. Prefiksi əvəz edək 11 haqqında 1, və növbəti baytlar üçün biz prefiksləri tamamilə siləcəyik. Nə olacaq?
0xxxxxxx — 1 bayt
10xxxxxx xxxxxxxx - 2 bayt
110xxxxx xxxxxxxx xxxxxxxx - 3 bayt
Gözləyin, dörd baytlıq rekord haradadır? Ancaq buna artıq ehtiyac yoxdur - üç baytda yazarkən, indi bizdə 21 bit mövcuddur və bu, bütün rəqəmlər üçün kifayətdir. 0x10FFFF.
Biz burada nəyi qurban vermişik? Ən vacibi, buferdəki ixtiyari bir yerdən xarakter sərhədlərinin aşkarlanmasıdır. Biz ixtiyari bayta işarə edib ondan sonrakı simvolun başlanğıcını tapa bilmərik. Bu, bizim formatımızın məhdudlaşdırılmasıdır, lakin praktikada buna nadir hallarda ehtiyac duyulur. Biz adətən lap əvvəldən buferdən keçə bilirik (xüsusilə də qısa sətirlərə gəldikdə).
Dillərin 2 baytla əhatə olunması ilə bağlı vəziyyət də yaxşılaşıb: indi iki baytlıq format 14 bit diapazonu verir və bunlar daha çox kodlardır. 0x3FFF. Çinlilər bəxtsizdirlər (xarakterləri əsasən aşağıdakılardan fərqlənir 0x4E00 üzrə 0x9FFF), lakin gürcülər və bir çox başqa xalqlar daha çox əylənirlər - dilləri də hər simvol üçün 2 bayta uyğun gəlir.
Kodlayıcı vəziyyətini daxil edin
İndi xətlərin özlərinin xüsusiyyətləri haqqında düşünək. Lüğətdə ən çox eyni əlifbanın simvolları ilə yazılmış sözlər var və bu, bir çox başqa mətnlərə də aiddir. Yaxşı olardı ki, bu əlifbanı bir dəfə qeyd edək, sonra isə yalnız onun içindəki hərfin nömrəsini göstərək. Görək Unicode cədvəlindəki simvolların düzülüşü bizə kömək edəcəkmi?
Yuxarıda qeyd edildiyi kimi, Unicode bölünür təyyarə Hər biri 65536 kod. Ancaq bu, çox faydalı bir bölmə deyil (əvvəlcədən deyildiyi kimi, çox vaxt sıfır müstəvisindəyik). Daha maraqlısı bölgüdür bloklar. Bu diapazonlar artıq sabit uzunluğa malik deyil və daha mənalıdır - bir qayda olaraq, hər biri eyni əlifbadan olan simvolları birləşdirir.
Benqal əlifbasının simvollarını ehtiva edən blok. Təəssüf ki, tarixi səbəblərə görə bu, çox sıx olmayan qablaşdırma nümunəsidir - 96 simvol 128 blok kodu nöqtəsinə xaotik şəkildə səpələnmişdir.
Blokların başlanğıcı və onların ölçüləri həmişə 16-nın qatıdır - bu, sadəcə rahatlıq üçün edilir. Bundan əlavə, bir çox bloklar 128 və ya hətta 256-nın qatları olan dəyərlərlə başlayır və bitir - məsələn, əsas kiril əlifbası 256 bayt tutur. 0x0400 üzrə 0x04FF. Bu olduqca rahatdır: əgər prefiksi bir dəfə yadda saxlasaq 0x04, onda hər hansı kiril simvolu bir baytda yazıla bilər. Doğrudur, bu yolla biz ASCII-yə (və ümumiyyətlə hər hansı digər simvola) qayıtmaq imkanını itirəcəyik. Buna görə də bunu edirik:
- İki bayt
10yyyyyy yxxxxxxxyalnız simvolu rəqəmlə ifadə etmiryyyyyy yxxxxxxx, həm də dəyişir cari əlifba haqqındayyyyyy y0000000(yəni, ən az əhəmiyyətli olanlar istisna olmaqla, bütün bitləri xatırlayırıq 7 bit); - Bir bayt
0xxxxxxxbu, indiki əlifbanın xarakteridir. Sadəcə onu 1-ci addımda xatırladığımız ofsete əlavə etmək lazımdır. Əlifbanı dəyişməsək də, ofset sıfırdır, ona görə də ASCII ilə uyğunluğu qoruyub saxladıq.
Eyni şəkildə 3 bayt tələb edən kodlar üçün:
- Üç bayt
110yyyyy yxxxxxxx xxxxxxxxrəqəmlə simvolu göstərinyyyyyy yxxxxxxx xxxxxxxx, dəyişdirin cari əlifba haqqındayyyyyy y0000000 00000000(kiçiklərdən başqa hər şeyi xatırladım 15 bit) və indi daxil olduğumuz qutuyu yoxlayın uzun rejim (əlifbanı iki baytlıq bir hala dəyişdirərkən, biz bu bayrağı sıfırlayacağıq); - İki bayt
0xxxxxxx xxxxxxxxuzun rejimdə cari əlifbanın xarakteridir. Eynilə, biz onu 1-ci addımdan ofsetlə əlavə edirik. Yeganə fərq ondadır ki, indi iki bayt oxuyuruq (çünki biz bu rejimə keçdik).
Yaxşı səslənir: indi eyni 7-bit Unicode diapazonundan simvolları kodlaşdırmalı olduğumuz halda, başlanğıcda 1 əlavə bayt və hər simvol üçün cəmi bir bayt sərf edirik.
Əvvəlki versiyalardan birindən işləyir. Artıq tez-tez UTF-8-i məğlub edir, lakin hələ də təkmilləşdirmə üçün yer var.
Daha pisi nədir? Birincisi, bir şərtimiz var, yəni cari əlifba ofset və qeyd qutusu uzun rejim. Bu, bizi daha da məhdudlaşdırır: indi eyni simvollar müxtəlif kontekstlərdə fərqli şəkildə kodlaşdırıla bilər. Məsələn, alt sətirlərin axtarışı yalnız baytları müqayisə etməklə deyil, bunu nəzərə alaraq aparılmalı olacaq. İkincisi, biz əlifbanı dəyişdirən kimi ASCII simvollarının kodlaşdırılması ilə pisləşdi (və bu, təkcə Latın əlifbası deyil, həm də əsas durğu işarələri, o cümlədən boşluqlardır) - onlar əlifbanı yenidən 0-a dəyişdirməyi tələb edirlər, yəni, yenidən əlavə bayt (və sonra əsas fikrimizə qayıtmaq üçün başqa bir bayt).
Bir əlifba yaxşıdır, ikisi daha yaxşıdır
Yuxarıda təsvir edilən üçünə daha birini sıxaraq, bit prefikslərimizi bir az dəyişdirməyə çalışaq:
0xxxxxxx — Normal rejimdə 1 bayt, uzun rejimdə 2 bayt
11xxxxxx — 1 bayt
100xxxxx xxxxxxxx - 2 bayt
101xxxxx xxxxxxxx xxxxxxxx - 3 bayt
İndi iki baytlıq qeyddə daha az əlçatan bit var - kod işarəsinə qədər 0x1FFFVə 0x3FFF. Bununla belə, o, hələ də iki baytlıq UTF-8 kodlarından nəzərəçarpacaq dərəcədə böyükdür, ən çox yayılmış dillər hələ də uyğun gəlir, ən nəzərəçarpacaq itki azalıb. и , yaponlar kədərlidirlər.
Bu yeni kod nədir? 11xxxxxx? Bu, 64 simvoldan ibarət kiçik bir "saklama"dır, əsas əlifbamızı tamamlayır, ona görə də onu köməkçi adlandırdım (köməkçi) əlifbası. Cari əlifbanı dəyişdikdə köhnə əlifbanın bir parçası köməkçi olur. Məsələn, biz ASCII-dən kiril əlifbasına keçdik - saklama indi 64 simvoldan ibarətdir. Latın əlifbası, rəqəmlər, boşluq və vergül (ASCII olmayan mətnlərdə ən çox əlavələr). ASCII-yə qayıdın - və kiril əlifbasının əsas hissəsi köməkçi əlifbaya çevriləcək.
İki əlifbaya çıxış sayəsində biz əlifbaların dəyişdirilməsi üçün minimal xərclərlə çoxlu sayda mətni idarə edə bilərik (punktuasiya çox vaxt ASCII-yə qayıtmağa səbəb olacaq, lakin bundan sonra biz əlavə əlifbadan ASCII olmayan bir çox simvol alacağıq. yenidən keçid).
Bonus: alt əlifbanın prefiksi 11xxxxxx və onun ilkin ofsetini seçmək 0xC0, biz CP1252 ilə qismən uyğunluq əldə edirik. Başqa sözlə, CP1252-də kodlanmış Qərbi Avropa mətnlərinin bir çoxu (lakin hamısı deyil) UTF-C-də eyni görünəcək.
Ancaq burada bir çətinlik yaranır: əsas əlifbadan köməkçini necə əldə etmək olar? Eyni ofseti tərk edə bilərsiniz, amma təəssüf ki, burada Unicode quruluşu artıq bizə qarşı oynayır. Çox vaxt əlifbanın əsas hissəsi blokun əvvəlində olmur (məsələn, Rusiyanın paytaxtı “A” kodu var. 0x0410, baxmayaraq ki, kiril bloku ilə başlayır 0x0400). Beləliklə, ilk 64 simvolu zibil qutusuna daxil etdikdən sonra əlifbanın quyruq hissəsinə girişi itirə bilərik.
Bu problemi həll etmək üçün mən əl ilə müxtəlif dillərə uyğun bəzi bloklardan keçdim və onlar üçün əsas əlifba daxilində köməkçi əlifbanın ofsetini təyin etdim. Latın əlifbası, istisna olaraq, ümumiyyətlə, baza64 kimi yenidən sıralanıb.
Son toxunuşlar
Nəhayət, bir şeyi daha harada təkmilləşdirə biləcəyimizi düşünək.
Qeyd edək ki, format 101xxxxx xxxxxxxx xxxxxxxx qədər rəqəmləri kodlamağa imkan verir 0x1FFFFF, və Unicode daha əvvəl bitir 0x10FFFF. Başqa sözlə, son kod nöqtəsi kimi təmsil olunacaq 10110000 11111111 11111111. Ona görə də deyə bilərik ki, əgər birinci bayt formadadırsa 1011xxxx (Harada xxxx 0-dan böyük), onda başqa bir şey deməkdir. Məsələn, bir baytda kodlaşdırma üçün daim mövcud olan daha 15 simvol əlavə edə bilərsiniz, amma mən bunu fərqli etmək qərarına gəldim.
İndi üç bayt tələb edən Unicode bloklarına baxaq. Əsasən, artıq qeyd edildiyi kimi, bunlar Çin simvollarıdır - lakin onlarla bir şey etmək çətindir, onlardan 21 mini var. Ancaq hiragana və katakana da orada uçdu - və artıq onların sayı o qədər də çox deyil, iki yüzdən azdır. Yaponları xatırladığımız üçün emojilər də var (əslində, onlar Unicode-da bir çox yerə səpələnmişdir, lakin əsas bloklar diapazondadır. 0x1F300 - 0x1FBFF). İndi bir anda bir neçə kod nöqtəsindən yığılan emojilərin olduğunu düşünsəniz (məsələn, emoji 7 koddan ibarətdir!), onda hər birinə üç bayt sərf etmək (bir ikona, kabus naminə 7×3 = 21 bayt) tamamilə ayıb olur.
Buna görə də, biz emoji, hiragana və katakanaya uyğun gələn bir neçə seçilmiş diapazon seçirik, onları bir davamlı siyahıya nömrələyirik və üç əvəzinə iki bayt olaraq kodlaşdırırıq:
1011xxxx xxxxxxxx
Əla: yuxarıda qeyd olunan emoji, 7 kod nöqtəsindən ibarət, UTF-8-də 25 bayt tutur və biz onu daxil edirik 14 (hər kod nöqtəsi üçün iki bayt). Yeri gəlmişkən, Habr onu həzm etməkdən imtina etdi (həm köhnə redaktorda, həm də yeni redaktorda), ona görə də onu şəkillə daxil etməli oldum.
Gəlin daha bir problemi həll etməyə çalışaq. Xatırladığımız kimi, əsas əlifba mahiyyətcədir yüksək 6 bit, biz bunu yadda saxlayırıq və hər növbəti deşifrə edilmiş simvolun koduna yapışdırırıq. Blokda olan Çin simvolları vəziyyətində 0x4E00 - 0x9FFF, bu ya bit 0, ya da 1-dir. Bu çox rahat deyil: bu iki dəyər arasında əlifbanı daima dəyişməli olacağıq (yəni üç bayt sərf etməliyik). Ancaq nəzərə alın ki, uzun rejimdə kodun özündən qısa rejimdən istifadə edərək kodlaşdırdığımız simvolların sayını çıxara bilərik (yuxarıda təsvir edilən bütün hiylələrdən sonra bu 10240-dır) - sonra heroqliflərin diapazonu dəyişəcək. 0x2600 - 0x77FF, və bu halda, bütün bu diapazonda ən əhəmiyyətli 6 bit (21 bitdən) 0-a bərabər olacaq. Beləliklə, heroqlif ardıcıllığı hər bir heroqlif üçün iki bayt istifadə edəcək (bu, belə böyük diapazon üçün optimaldır). əlifba keçidlərinə səbəb olur.
Alternativ həllər: SCSU, BOCU-1
Məqalənin başlığını yenicə oxuyan Unicode mütəxəssisləri, çox güman ki, birbaşa Unicode standartları arasında olduğunu xatırlatmağa tələsəcəklər. (SCSU), məqalədə təsvir edilənə çox oxşar bir kodlaşdırma metodunu təsvir edir.
Səmimi etiraf edirəm: onun varlığını yalnız qərarımı yazmağa dərindən batırdıqdan sonra öyrəndim. Bu barədə əvvəldən bilsəydim, yəqin ki, öz yanaşmamla gəlmək əvəzinə bir tətbiq yazmağa çalışardım.
Maraqlısı odur ki, DQİDK mənim təkbaşına ərsəyə gətirdiyim ideyalara çox oxşar ideyalardan istifadə edir (“əlifbalar” anlayışı əvəzinə “pəncərələrdən” istifadə edirlər və məndən daha çoxu var). Eyni zamanda, bu formatın çatışmazlıqları da var: kodlaşdırma alqoritmlərinə nisbətən sıxılma alqoritmlərinə bir az daha yaxındır. Xüsusilə, standart bir çox təmsil üsullarını verir, lakin optimal olanı necə seçmək lazım olduğunu demir - bunun üçün kodlayıcı bir növ evristikadan istifadə etməlidir. Beləliklə, yaxşı qablaşdırma istehsal edən bir SCSU kodlayıcısı mənim alqoritmimdən daha mürəkkəb və daha çətin olacaq.
Müqayisə üçün, mən SCSU-nun nisbətən sadə bir tətbiqini JavaScript-ə köçürdüm - kod həcmi baxımından mənim UTF-C ilə müqayisə oluna bildi, lakin bəzi hallarda nəticə onlarla faiz daha pis oldu (bəzən ondan çox ola bilər, lakin çox deyil). Məsələn, ivrit və yunan dillərindəki mətnlər UTF-C ilə kodlanmışdır SCSU-dan 60% daha yaxşıdır (yəqin ki, onların yığcam əlifbalarına görə).
Ayrı-ayrılıqda əlavə edəcəyəm ki, SCSU-dan başqa Unicode-u kompakt şəkildə təmsil etməyin başqa bir yolu da var - , lakin o, MIME uyğunluğu məqsədi daşıyır (buna ehtiyacım yox idi) və kodlaşdırmaya bir az fərqli yanaşma tətbiq edir. Mən onun effektivliyini qiymətləndirməmişəm, amma mənə elə gəlir ki, onun SCSU-dan yüksək olması ehtimalı azdır.
Mümkün təkmilləşdirmələr
Təqdim etdiyim alqoritm dizayn baxımından universal deyil (yəqin ki, mənim məqsədlərim Unicode Konsorsiumunun məqsədlərindən ən çox ayrılan yer budur). Artıq qeyd etdim ki, o, ilk növbədə bir tapşırıq üçün hazırlanıb (prefiks ağacında çoxdilli lüğətin saxlanması) və onun bəzi xüsusiyyətləri digər tapşırıqlar üçün o qədər də uyğun olmaya bilər. Ancaq bunun standart olmaması bir artı ola bilər - ehtiyaclarınıza uyğun olaraq asanlıqla dəyişdirə bilərsiniz.
Məsələn, açıq şəkildə dövlətin mövcudluğundan qurtula, vətəndaşlığı olmayan kodlaşdırma edə bilərsiniz - sadəcə dəyişənləri yeniləməyin offs, auxOffs и is21Bit kodlayıcıda və dekoderdə. Bu halda, eyni əlifbanın simvol ardıcıllığını effektiv şəkildə yığmaq mümkün olmayacaq, lakin kontekstdən asılı olmayaraq eyni simvolun həmişə eyni baytlarla kodlanmasına zəmanət olacaq.
Bundan əlavə, standart vəziyyəti dəyişdirərək kodlayıcını müəyyən bir dilə uyğunlaşdıra bilərsiniz - məsələn, rus mətnlərinə diqqət yetirin, kodlayıcı və dekoderi başlanğıcda təyin edin offs = 0x0400 и auxOffs = 0. Bu, xüsusən də vətəndaşlığı olmayan rejimdə məna kəsb edir. Ümumiyyətlə, bu, köhnə səkkiz bitlik kodlaşdırmanın istifadəsinə bənzəyəcək, lakin lazım olduqda bütün Unicode-dan simvol daxil etmək qabiliyyətini silmədən.
Daha əvvəl qeyd olunan digər çatışmazlıq, UTF-C ilə kodlanmış böyük mətndə ixtiyari bayta ən yaxın simvol sərhədini tapmaq üçün sürətli bir yol olmamasıdır. Əgər kodlaşdırılmış buferdən sonuncu, məsələn, 100 baytı kəssəniz, heç bir şey edə bilməyəcəyiniz zibil əldə etmək riskiniz var. Kodlaşdırma çox gigabaytlıq qeydləri saxlamaq üçün nəzərdə tutulmayıb, lakin ümumilikdə bu düzəldilə bilər. bayt 0xBF heç vaxt birinci bayt kimi görünməməlidir (lakin ikinci və ya üçüncü ola bilər). Buna görə də, kodlaşdırma zamanı ardıcıllığı daxil edə bilərsiniz 0xBF 0xBF 0xBF hər biri, deyək ki, 10 KB - onda bir sərhəd tapmaq lazımdırsa, oxşar marker tapılana qədər seçilmiş parçanı skan etmək kifayət edəcəkdir. Sonuncunun ardınca 0xBF xarakterin başlanğıcı olacağına zəmanət verilir. (Deşifrə edərkən, bu üç bayt ardıcıllığına, əlbəttə ki, məhəl qoyulmamalıdır.)
Yekunlaşdırma
Bura qədər oxumusunuzsa, təbrik edirik! Ümid edirəm ki, siz də mənim kimi Unicode-un strukturu haqqında yeni bir şey öyrəndiniz (və ya yaddaşınızı təzələdiniz).
Demo səhifəsi. İvrit dili nümunəsi həm UTF-8, həm də SCSU üzərində üstünlükləri göstərir.
Yuxarıda təsvir edilən tədqiqat standartlara təcavüz hesab edilməməlidir. Bununla belə, ümumiyyətlə, işimin nəticələrindən razıyam, ona görə də onlardan razıyam : məsələn, kiçikləşdirilmiş JS kitabxanasının çəkisi cəmi 1710 baytdır (və əlbəttə ki, heç bir asılılığı yoxdur). Yuxarıda qeyd etdiyim kimi, onun işini burada tapa bilərsiniz (UTF-8 və SCSU ilə müqayisə edilə bilən bir sıra mətnlər də var).
Nəhayət, UTF-C-nin istifadə edildiyi hallara bir daha diqqət çəkəcəyəm buna dəyər deyil:
- Sətirləriniz kifayət qədər uzundursa (100-200 simvoldan). Bu vəziyyətdə, deflate kimi sıxılma alqoritmlərindən istifadə etmək barədə düşünməlisiniz.
- Əgər ehtiyacın varsa ASCII şəffaflığı, yəni kodlanmış ardıcıllıqların orijinal sətirdə olmayan ASCII kodlarının olmaması sizin üçün vacibdir. Üçüncü tərəf API-ləri ilə qarşılıqlı əlaqə qurarkən (məsələn, verilənlər bazası ilə işləyərkən) kodlaşdırma nəticəsini sətir kimi deyil, mücərrəd bayt dəsti kimi keçirsəniz, bunun qarşısını almaq olar. Əks halda, gözlənilməz zəifliklər əldə etmək riskiniz var.
- Əgər ixtiyari ofsetdə (məsələn, xəttin bir hissəsi zədələndikdə) xarakter sərhədlərini tez tapa bilmək istəyirsinizsə. Bu edilə bilər, lakin yalnız əvvəldən xətti skan etməklə (və ya əvvəlki bölmədə təsvir edilən modifikasiyanı tətbiq etməklə).
- Əgər sətirlərin məzmunu üzərində əməliyyatları tez yerinə yetirmək lazımdırsa (onları çeşidləyin, onlarda alt sətirləri axtarın, birləşdirin). Bunun üçün əvvəlcə sətirlərin deşifrə edilməsi tələb olunur, ona görə də UTF-C bu hallarda UTF-8-dən daha yavaş olacaq (lakin sıxılma alqoritmlərindən daha sürətli). Eyni sətir həmişə eyni şəkildə kodlandığından, deşifrənin dəqiq müqayisəsi tələb olunmur və bayt-bayt əsasında həyata keçirilə bilər.
Update: istifadəçi UTF-C-nin tətbiqi məhdudiyyətlərini vurğulayan bir qrafik yerləşdirdi. Bu göstərir ki, paketlənmiş sətir daha qısa olduğu müddətcə UTF-C ümumi təyinatlı sıxılma alqoritmindən (LZW variasiyası) daha səmərəlidir. ~140 simvol (lakin qeyd edim ki, müqayisə bir mətn üzərində aparılıb; digər dillər üçün nəticə fərqli ola bilər).
Mənbə: www.habr.com