Калі вы распрацоўшчык і перад вамі стаіць задача выбару кадоўкі, то амаль заўсёды правільным рашэннем будзе Юнікод. Канкрэтны спосаб уяўлення залежыць ад кантэксту, але часцей за ўсё тут таксама ёсць універсальны адказ – UTF-8. Ён добры тым, што дазваляе выкарыстоўваць усе знакі Юнікод, не марнуючы занадта шмат байт у большасці выпадкаў. Праўда, для моў, якія выкарыстоўваюць не толькі лацінку, "не занадта шмат" - гэта як мінімум два байта на сімвал. Ці можна лепш, не вяртаючыся да дагістарычных кадовак, якія абмяжоўваюць нас усяго 256 даступнымі знакамі?
Ніжэй прапаную азнаёміцца з маёй спробай даць адказ на гэтае пытанне і рэалізацыю адносна простага алгарытму, які дазваляе захоўваць радкі на большасці моў свету, не дадаючы той надмернасці, якая ёсць у UTF-8.
Дысклеймер. Адразу зраблю некалькі важных агаворак: апісанае рашэнне не прапануецца як універсальная замена UTF-8, яно падыходзіць толькі ў вузкім спісе выпадкаў (пра іх ніжэй), і яго ні ў якім разе нельга выкарыстоўваць для ўзаемадзеяння са іншымі API (якія пра яго і ведаць не ведаюць). Часцей за ўсё для кампактнага захоўвання вялікіх аб'ёмаў тэкставых дадзеных падыдуць алгарытмы сціску агульнага прызначэння (напрыклад, deflate). Акрамя таго, ужо падчас стварэнняў свайго рашэння я знайшоў існуючы стандарт у самім Юнікод, які вырашае тую ж задачу - ён некалькі складаней (і нярэдка горш), але ўсё-такі з'яўляецца прынятым стандартам, а не сабраным на каленцы. Пра яго я таксама раскажу.
Аб Unicode і UTF-8
Для пачатку - некалькі слоў аб тым, што наогул такое Unicode и UTF-8.
Як вядома, раней мелі папулярнасць 8-бітныя кадоўкі. З імі ўсё было проста: 256 сімвалаў можна занумараваць лікамі ад 0 да 255, а лікі ад 0 да 255 відавочна прадстаўляюцца ў выглядзе аднаго байта. Калі вяртацца да самых вытокаў, то кадоўка ASCII і зусім абмяжоўваецца 7 бітамі, таму самы старэйшы біт у яе байтавым уяўленні роўны нулю, і большасць 8-бітных кадовак з ёй сумяшчальныя (яны адрозніваюцца толькі ў "верхняй" частцы, дзе старэйшы біт - адзінка ).
Чым жа ад тых кадовак адрозніваецца Юнікод і чаму з ім звязана адразу мноства канкрэтных уяўленняў - UTF-8, UTF-16 (BE і LE), UTF-32? Разбярэмся па парадку.
Асноўны стандарт Юнікод апісвае толькі адпаведнасць паміж сімваламі (а ў некаторых выпадках - асобнымі кампанентамі сімвалаў) і іх нумарамі. І магчымых нумароў у гэтым стандарце вельмі шмат - ад 0x00 да 0x10FFFF (1 штук). Калі б мы хацелі пакласці лік у такім дыяпазоне ў зменную, ні 114, ні 112 байт нам бы не хапіла. А бо пад працу з трохбайтавымі лікамі нашы працэсары не вельмі заменчаныя, мы былі бы змушаныя выкарыстоўваць цэлых 1 байта на адзін знак! Гэта і ёсць UTF-2, але менавіта з-за гэтай «марнатраўнасці» гэты фармат не карыстаецца папулярнасцю.
На шчасце, сімвалы ўнутры Юнікод упарадкаваны не выпадкова. Усе іх мноства падзелена на 17плоскасцей», кожная з якіх змяшчае 65536 (0x10000) «кодавых кропак». Паняцце «кодавай кропкі» тут - гэта проста нумар сімвала, прысвоены яму Юнікод. Але, як было сказана вышэй, у Юнікодзе занумараваны не толькі асобныя знакі, але таксама іх кампаненты і службовыя пазнакі (а часам і зусім нумару нічога не адпавядае - магчыма, да пары да часу, але для нас гэта не так важна), таму карэктней заўсёды казаць менавіта пра колькасць саміх нумароў, а не сімвалаў. Аднак далей для сцісласці я часта буду ўжываць слова "знак", маючы на ўвазе тэрмін "кодавая кропка".
Плоскасці Юнікод. Як відаць, большая частка (плоскасці з 4 па 13) усё яшчэ не выкарыстана.
Што самае выдатнае - уся асноўная "мякотка" ляжыць у нулявой плоскасці, яна называецца "Basic Multilingual PlaneКалі радок утрымлівае тэкст на адной з сучасных моў (уключаючы кітайскую), за межы гэтай плоскасці вы не выйдзеце.Supplementary Multilingual Plane" (яна распасціраецца ад 0x10000 да 0x1FFFF). Таму UTF-16 паступае так: усе знакі, якія трапляюць у Basic Multilingual Plane, кадуюцца «як ёсць», які адпавядае ім двухбайтавым лікам. Аднак частка лікаў у гэтым дыяпазоне наогул не пазначаюць пэўныя знакі, а паказваюць на тое, што следам за гэтай парай байт трэба разгледзець яшчэ адну - скамбінаваўшы значэння гэтых чатырох байт разам, у нас атрымаецца лік, якое ахоплівае ўвесь дапушчальны дыяпазон Юнікод. Такое ўяўленне называецца «сурагатнымі парамі» - магчыма, вы пра іх чулі.
Такім чынам, UTF-16 патрабуе два ці (у вельмі рэдкіх выпадках) чатыры байта на адну "кодавую кропку". Гэта лепш, чым увесь час выкарыстоўваць чатыры байта, але лацінка (і іншыя ASCII-знакі) пры такім кадаванні расходуе палову займанага месца на нулі. UTF-8 закліканы гэта паправіць: ASCII у ім займае, як раней, усяго адзін байт; коды ад 0x80 да 0x7FF - два байта; ад 0x800 да 0xFFFF - тры, а ад 0x10000 да 0x10FFFF - чатыры. З аднаго боку, лацінцы стала добра: вярнулася сумяшчальнасць з ASCII, ды і размеркаванне больш раўнамерна размазана ад 1 да 4 байт. Але алфавіты, выдатныя ад лацінскага, нажаль, ніяк не выйграваюць у параўнанні з UTF-16, а шматлікія і зусім зараз патрабуюць трох байт замест двух - дыяпазон, які пакрываецца двухбайтавым запісам, звузіўся ў 32 разу, з 0xFFFF да 0x7FF, і ў яго не трапляе ўжо ні кітайская, ні, да прыкладу, грузінская. Кірыліцы і яшчэ пяці алфавітам - ура - пашанцавала, 2 байта на сімвал.
Чаму так выходзіць? Давайце паглядзім, як UTF-8 уяўляе коды знакаў:
Непасрэдна для прадстаўлення лікаў тут выкарыстаны біты, пазначаныя сімвалам x. Відаць, што ў двухбайтавым запісе такіх біт толькі 11 (з 16). Вядучыя біты тут нясуць толькі службовую функцыю. У выпадку з чатырохбайтавым запісам і зусім пад нумар кодавай кропкі адведзены 21 біт з 32 – здавалася б, тут хапіла б і трох байт (якія даюць сумарна 24 біта), але службовыя маркеры з'ядаюць занадта шмат.
Ці дрэнна гэта? Насамрэч, не вельмі. З аднаго боку - калі мы моцна клапоцімся аб займаемай прасторы, у нас ёсць алгарытмы сціску, якія лёгка ўхіляць усю лішнюю энтрапію і надмернасць. З іншага - мэтай Юнікод было даць максімальна універсальнае кадаваньне. Напрыклад, закадаваную ў UTF-8 радок мы можам даверыць коду, які раней працаваў толькі з ASCII, і не баяцца, што ён там убачыць сімвал з ASCII-дыяпазону, якога там насамрэч няма (бо ў UTF-8 усе байты, якія пачынаюцца з нулявога біта - гэта менавіта ASCII і ёсць). А калі мы захочам раптам адрэзаць маленькі хвост ад вялікага радка, не дэкадуючы яе з самага пачатку (ці аднавіць частку інфармацыі пасля пашкоджанага ўчастку) - нам нескладана знайсці тое зрушэнне, дзе пачынаецца нейкі знак (досыць прапусціць байты, мелыя бітавы прэфікс 10).
Навошта тады выдумляць нешта новае?
У той жа час, зрэдку бываюць сітуацыі, калі алгарытмы сціску накшталт deflate дрэннапрымяняльныя, а дамагчыся кампактнага захоўвання радкоў жадаецца. Асабіста я сутыкнуўся з такой задачай, разважаючы аб пабудове для вялікага слоўніка, які ўключае словы на адвольных мовах. З аднаго боку - кожнае слова вельмі кароткае, таму сціскаць яго будзе неэфектыўна. З іншага - рэалізацыя дрэва, якую я разглядаў, была разлічана на тое, што кожны байт захоўваемага радка спараджаў асобную вяршыню дрэва, так што мінімізаваць іх колькасць было вельмі карысна. У маёй бібліятэцы (як і ў , На якім яна заснавана) падобная праблема вырашаецца проста - радкі, спакаваныя ў -слоўнік, захоўваюцца там у . Але, як няцяжка зразумець, гэта добра працуе толькі для абмежаванага алфавіту - радок на кітайскай мове ў такі слоўнік ужо не скласці.
Асобна адзначу яшчэ адзін непрыемны нюанс, які ўзнікае пры выкарыстанні UTF-8 у такой структуры дадзеных. На малюнку вышэй відаць, што пры запісе знака ў выглядзе двух байт, біты, якія адносяцца да яго нумара, не ідуць запар, а разарваныя парай біт 10 пасярэдзіне: 110xxxxx 10xxxxxx. З-за гэтага, калі ў кодзе знака перапаўняюцца малодшыя 6 біт другога байта (г.зн. адбываецца пераход 10111111 → 10000000), то мяняецца і першы байт таксама. Атрымліваецца, што літара "п" абазначаецца байтамі. 0xD0 0xBF, а наступная за ёй "р" - ужо 0xD1 0x80. У прэфіксным дрэве гэта прыводзіць да расшчаплення бацькоўскай вяршыні на дзве - адной для прэфікса. 0xD0, і іншы для 0xD1 (хоць уся кірыліца магла б кадзіравацца толькі другім байтам).
Што ў мяне атрымалася
Сутыкнуўшыся з гэтай задачай я вырашыў папрактыкавацца ў гульнях з бітамі, а заадно крыху лепш пазнаёміцца са структурай Юнікод ў цэлым. Вынікам стаў фармат кадавання UTF-C («C» ад кампактны), які марнуе не больш за 3 байт на адну кодавую кропку, а вельмі часта дазваляе марнаваць толькі адзін лішні байт на ўвесь кадаваны радок. Гэта прыводзіць да таго, што на шматлікіх не-ASCII алфавітах такое кадаваньне аказваецца на 30-60% кампактней UTF-8.
Я аформіў прыклады рэалізацыі алгарытмаў кадавання і дэкадавання ў выглядзе , вы можаце свабодна выкарыстоўваць іх у сваім кодзе. Але я ўсё ж падкрэслю, што ў некаторым сэнсе гэты фармат застаецца "роварам", і я не рэкамендую яго выкарыстоўваць без усведамлення таго, навошта ён вам патрэбен. Гэта ўсёткі больш эксперымент, чым сур'ёзнае "паляпшэнне UTF-8". Тым не менш, код там напісаны акуратна, лаканічна, з вялікай колькасцю каментароў і пакрыццём тэстамі.
Вынік выканання тэстаў і параўнанне з UTF-8
Яшчэ я зрабіў , дзе можна ацаніць працу алгарытму, а далей я распавяду падрабязней пра яго прынцыпы і працэс распрацоўкі.
Ухіляем залішнія біты
За аснову я ўзяў, вядома, UTF-8. Першае і самае відавочнае, што ў ім можна памяняць - паменшыць колькасць службовых біт у кожным байце. Напрыклад, першы байт у UTF-8 заўсёды пачынаецца альбо з 0, альбо з 11 - а прэфікс 10 ёсць толькі ў наступных байт. Заменім прэфікс 11 на 1, А ў наступных байт прыбярэм прэфіксы зусім. Што атрымаецца?
0xxxxxxx - 1 байт
10xxxxxx xxxxxxxx - 2 байта
110xxxxx xxxxxxxx xxxxxxxx - 3 байта
Стоп, а дзе ж чатырохбайтавы запіс? А яна стала не патрэбна - пры запісе трыма байтамі ў нас зараз даступны 21 біт і гэтага з запасам хапае на ўсе лікі да 0x10FFFF.
Чым мы ахвяравалі тут? Самае галоўнае - выяўленнем меж сімвалаў з адвольнага месца буфера. Мы не можам ткнуць у адвольны байт і ад яго знайсці пачатак наступнага знака. Гэта - абмежаванне нашага фармату, але на практыцы неабходнасць у такім устае нячаста. Звычайна мы здольныя прабегчы буфер з самага пачатку (асабліва калі гаворка ідзе аб кароткіх радках).
Сітуацыя з пакрыццём моў 2 байтамі таксама стала лепшай: цяпер двухбайтавы фармат дае дыяпазон у 14 біт, а гэта коды да 0x3FFF. Кітайцам не вязе (іх іерогліфы ў асноўным ляжаць у дыяпазоне ад 0x4E00 да 0x9FFF), але вось грузінам і шматлікім іншым народам стала весялей - іх мовы таксама ўкладваюцца ў 2 байта на знак.
Уводны стан энкодэра
Давайце зараз падумаем пра ўласцівасці саміх радкоў. У слоўніку часцей за ўсё ляжаць словы, напісаныя сімваламі аднаго алфавіту, ды і для многіх іншых тэкстаў гэта таксама дакладна. Было б добра адзін раз пазначыць гэты алфавіт, а далей указваць толькі нумар літары ўнутры яго. Паглядзім, ці дапаможа нам размяшчэнне сімвалаў у табліцы Юнікод.
Як было сказана вышэй, Юнікод падзелены на плоскасці па 65536 кодаў кожная. Але гэта не вельмі карыснае дзяленне (як ужо сказанае, часцей за ўсё мы знаходзімся ў нулявой плоскасці). Цікавейшым з'яўляецца дзяленне на блокі. Гэтыя дыяпазоны ўжо не маюць фіксаванай даўжыні, і нясуць больш сэнсу - як правіла, кожны аб'ядноўвае сімвалы аднаго алфавіту.
Блок, які змяшчае сімвалы бенгальскага алфавіту. Нажаль, па гістарычных чынніках, гэта прыклад не вельмі шчыльнага пакавання — 96 знакаў хаатычна раскіданыя па 128 кодавых кропках блока.
Пачаткі блокаў і іх памеры заўсёды кратныя 16 зроблена гэта проста для выгоды. Акрамя таго, шматлікія блокі пачынаюцца і сканчаюцца на значэннях, кратных 128 ці нават 256 - напрыклад, асноўная кірыліца займае 256 байт ад 0x0400 да 0x04FF. Гэта даволі зручна: калі мы адзін раз захаваем прэфікс 0x04, то далей любы кірылічны сімвал можна запісваць адным байтам. Праўда, так мы страцім магчымасць вярнуцца да ASCII (і да любых іншых сімвалаў наогул). Таму робім так:
- Два байта
10yyyyyy yxxxxxxxне толькі абазначаюць сімвал з нумарамyyyyyy yxxxxxxx, але і мяняюць бягучы алфавіт наyyyyyy y0000000(г.зн. запамінаем усе біты, акрамя малодшых 7 біт); - Адзін байт
0xxxxxxxгэта сімвал бягучага алфавіту. Яго трэба проста скласці з тым зрушэннем, якое мы запомнілі на кроку 1. Пакуль алфавіт мы не мянялі, зрушэнне роўна нулю, так што сумяшчальнасць з ASCII мы захавалі.
Аналагічна для кодаў, якія патрабуюць 3 байт:
- Тры байта
110yyyyy yxxxxxxx xxxxxxxxабазначаюць сімвал з нумарамyyyyyy yxxxxxxx xxxxxxxx, мяняюць бягучы алфавіт наyyyyyy y0000000 00000000(запомнілі ўсё, акрамя малодшых 15 біт), і ставяць сцяжок, што мы зараз у доўгім рэжыме (пры змене алфавіту зваротна на двухбайтавы гэты сцяжок мы скінем); - Два байта
0xxxxxxx xxxxxxxxу доўгім рэжыме гэта сімвал бягучага алфавіту. Аналагічна, мы складаем яго са зрушэннем з кроку 1. Уся розніца толькі ў тым, што зараз мы чытаем па два байта (таму што мы пераключыліся ў такі рэжым).
Гучыць нядрэнна: зараз пакуль нам трэба кадзіраваць сімвалы з аднаго і таго ж 7-бітнага дыяпазону Юнікод, мы трацім 1 лішні байт у пачатку і ўсяго па байце на кожны сімвал.
Праца адной з ранніх версій. Ужо часта абыходзіць UTF-8, але яшчэ ёсць што паляпшаць.
Што стала горш? Па-першае, у нас з'явіўся стан, а менавіта зрушэнне бягучага алфавіту і сцяжок доўгага рэжыму. Гэта нас дадаткова абмяжоўвае: зараз адны і тыя ж сімвалы могуць быць закадзіраваны па-рознаму ў розных кантэкстах. Пошук падрадкоў, напрыклад, давядзецца рабіць ужо з улікам гэтага, а не проста параўноўваючы байты. Па-другое, як толькі мы змянілі алфавіт, стала дрэнна з кадаваннем ASCII-знакаў (а гэта не толькі лацінка, але і базавая пунктуацыя, уключаючы прабелы) - яны патрабуюць паўторнай змены алфавіту ў 0, гэта значыць зноў лішняга байта (а потым яшчэ аднаго, каб вярнуцца да нашага асноўнага).
Адзін алфавіт добра, два - лепш
Паспрабуем крыху змяніць нашы бітавыя прэфіксы, уціснуўшы да трох вышэйапісаным яшчэ адзін:
0xxxxxxx - 1 байт у звычайным рэжыме, 2 у доўгім
11xxxxxx - 1 байт
100xxxxx xxxxxxxx - 2 байта
101xxxxx xxxxxxxx xxxxxxxx - 3 байта
Цяпер у двухбайтавым запісе на адзін даступны біт стала менш - змяшчаюцца кодавыя кропкі аж да 0x1FFF, А не 0x3FFF. Зрэшты, усё яшчэ адчувальна больш, чым у двухбайтавых кодах UTF-8, большая частка распаўсюджаных моў усё яшчэ залазіць, самая прыкметная страта – выпала и , японцы ў смутку.
Што ж за новы код 11xxxxxx? Гэта невялікі «загашнік» памерам у 64 знакі, ён дапаўняе наш асноўны алфавіт, таму я назваў яго дапаможным (дапаможны) алфавітам. Калі мы перамыкаем бягучы алфавіт, то кавалак старога алфавіту становіцца дапаможным. Напрыклад, пераключыліся з ASCII на кірыліцу - у «загашніку» зараз 64 знака, якія змяшчаюць лацінку, лічбы, прабел і коску (самыя частыя ўстаўкі ў не-ASCII тэкстах). Пераключыліся назад на ASCII – і дапаможным алфавітам стане асноўная частка кірыліцы.
Дзякуючы доступу да двух алфавітаў, мы можам справіцца з вялікай колькасцю тэкстаў, маючы мінімальныя выдаткі на пераключэнне алфавітаў (пунктуацыя часцей за ўсё будзе прыводзіць да вяртання ў ASCII, але пасля гэтага многія не-ASCII сімвалы мы будзем даставаць ужо з дадатковага алфавіту, без паўторнага пераключэння ).
Бонус: пазначыўшы дапалфавіт прэфіксам 11xxxxxx і выбраўшы яго пачатковае зрушэнне роўным 0xC0, у нас атрымліваецца частковая сумяшчальнасць з CP1252. Іншымі словамі, шматлікія (але не ўсе) заходнееўрапейскія тэксты, закадаваныя ў CP1252, будуць выглядаць гэтак жа і ў UTF-C.
Тут, праўда, узнікае цяжкасць: як з асноўнага алфавіту атрымаць дапаможны? Можна пакінуць тое ж самае зрушэнне, але - нажаль - тут структура Юнікод ўжо гуляе супраць нас. Вельмі часта асноўная частка алфавіту знаходзіцца не ў пачатку блока (напрыклад, руская загалоўная "А" мае код 0x0410, хоць кірылічны блок пачынаецца з 0x0400). Такім чынам, узяўшы ў «загашнік» першыя 64 знакі, мы, магчыма, страцім доступ да хваставой часткі алфавіту.
Для ўхілення гэтай праблемы я ўручную прайшоўся па некаторых блоках, якія адпавядаюць розным мовам, і паказаў для іх зрушэнне дапаможнага алфавіту ўсярэдзіне асноўнага. Лацінку, у парадку выключэння, наогул пераўпарадкаваў накшталт base64.
Фінальныя рыскі
Давайце напрыканцы падумаем, дзе мы яшчэ можам нешта дапрацаваць.
Заўважым, што фармат 101xxxxx xxxxxxxx xxxxxxxx дазваляе закадаваць лічбы аж да 0x1FFFFF, а Юнікод сканчаецца раней, на 0x10FFFF. Іншымі словамі, апошняя кодавая кропка будзе прадстаўлена як 10110000 11111111 11111111. Такім чынам, мы можам сказаць, што калі першы байт мае выгляд 1011xxxx (дзе xxxx больш за 0), то ён пазначае нешта яшчэ. Напрыклад, можна дадаць туды яшчэ 15 сімвалаў, якія пастаянна даступныя для кадавання адным байтам, але я вырашыў паступіць па-іншаму.
Паглядзім на тыя блокі Юнікод, якія патрабуюць трох байт зараз. У асноўным, як ужо было сказана, гэта кітайскія іерогліфы - але з імі цяжка нешта зрабіць, іх 21 тысяча. Але яшчэ туды паляцела хірагана з катаканай - а іх ужо не так шмат, менш за дзвесце. І, раз ужо мы ўспомнілі пра японцаў - тамака жа ляжаць эмоджы (насамрэч яны шмат дзе раскіданыя ў Юнікодзе, але асноўныя блокі ў дыяпазоне 0x1F300 - 0x1FBFF). Калі падумаць аб тым, што зараз існуюць эмоджы, якія збіраюцца з адразу некалькіх кодавых кропак (напрыклад, эмоджы складаецца ажно з 7 кодаў!), то становіцца зусім шкада марнаваць на кожную па тры байта (7×3 = 21 байт дзеля аднаго значка, кашмар жа).
Таму выбіраемы некалькі абраных дыяпазонаў, якія адпавядаюць эмодзі, хірагане і катакане, перанумароўваем іх у адзін бесперапынны спіс і кадуем у выглядзе двух байт замест трох:
1011xxxx xxxxxxxx
Выдатна: вышэйзгаданы эмоджы , Які складаецца з 7 кодавых кропак, у UTF-8 займае 25 байт, а мы змясцілі яго ў 14 (роўна па двух байта на кожны кодавы пункт). Дарэчы, Хабр адмовіўся яго пераварваць (як у старым, так і ў новым рэдактары), так што прыйшлося ўставіць яго карцінкай.
Паспрабуем выправіць яшчэ адну праблему. Як мы памятаем, асноўны алфавіт гэта па сутнасці старэйшыя 6 біт, якія мы трымаем у розуме, і прыляпляем да кода кожнага чарговага дэкадуемага сімвала. У выпадку з кітайскімі іерогліфамі, якія знаходзяцца ў блоку 0x4E00 - 0x9FFF, гэта альбо біт 0, альбо 1. Гэта не вельмі зручна: нам трэба будзе ўвесь час перамыкаць алфавіт паміж гэтымі двума значэннямі (г.зн. марнаваць па тры байта). Але заўважым, што ў доўгім рэжыме з самога кода мы можам адняць лік знакаў, якое мы кадуем з дапамогай кароткага рэжыму (пасля ўсіх вышэйапісаных хітрасцяў гэта 10240) - тады дыяпазон іерогліфаў зрушыцца да 0x2600 - 0x77FF, і ў гэтым выпадку на ўсім гэтым дыяпазоне старэйшыя 6 біт (з 21) будуць роўныя 0. Такім чынам, паслядоўнасці іерогліфаў будуць выкарыстоўваць па два байта на іерогліф (што аптымальна для такога вялікага дыяпазону), не выклікаючы пераключэнняў алфавіту.
Альтэрнатыўныя рашэнні: SCSU, BOCU-1
Знаўцы Unicode, яшчэ толькі прачытаўшы назву артыкула, хутчэй за ўсё, паспяшаюцца нагадаць, што непасрэдна сярод стандартаў Юнікод ёсць (SCSU), які апісвае спосаб кадавання, вельмі падобны з апісаным у артыкуле.
Прызнаюся сапраўды: аб яго існаванні я пазнаў толькі ўжо глыбока пагрузіўшыся ў напісанне свайго рашэння. Ведай аб ім з самага пачатку, я, верагодна, паспрабаваў бы напісаць яго рэалізацыю замест прыдумляння ўласнага падыходу.
Што цікава, SCSU выкарыстоўвае ідэі, вельмі падобныя на тыя, да якіх я прыйшоў самастойна (замест паняцця "алфавітаў" там выкарыстоўваюцца "вокны", і іх даступна больш, чым у мяне). У той жа час, у гэтага фармату таксама ёсць мінусы: ён крыху бліжэй да алгарытмаў сціску, чым кадавання. У прыватнасці, стандарт дае мноства спосабаў прадстаўлення, але не кажа, як выбраць з іх аптымальны - для гэтага энкодэр павінен прымяняць нейкія эўрыстыкі. Такім чынам, SCSU-энкодэр, які дае добрае пакаванне, будзе складаней і больш грувасткі, чым мой алгарытм.
Для параўнання я перанёс адносна простую рэалізацыю SCSU на JavaScript – па аб'ёме кода яна апынулася параўнальная з маім UTF-C, але ў шэрагу выпадкаў паказала вынік на дзясяткі адсоткаў горш (часам яна можа і пераўзыходзіць яго, але ненашмат). Напрыклад, тэксты на іўрыце і грэцкай UTF-C закадаваў аж на 60% лепш, чым SCSU (верагодна, з-за іх кампактных алфавітаў).
Асобна дадам, што акрамя SCSU існуе таксама іншы спосаб кампактнага падання Юнікод — , але ён ставіць за мэту сумяшчальнасць з MIME (што мне не патрабавалася), і выкарыстоўвае некалькі іншы падыход да кадавання. Яго эфектыўнасць я не ацэньваў, але мне здаецца, што яна наўрад ці будзе вышэйшай за SCSU.
Магчымыя дапрацоўкі
Прыведзены мной алгарытм не ўніверсальны by design (у гэтым, мусіць, мае мэты мацней за ўсё разыходзяцца з мэтамі кансорцыўма Unicode). Я ўжо згадаў, што ён распрацоўваўся пераважна пад адну задачу (захоўванне мультымоўнага слоўніка ў прэфіксным дрэве), і некаторыя яго асаблівасці могуць дрэнна падыходзіць для іншых задач. Але той факт, што ён не з'яўляецца стандартам, можа быць і плюсам. вы можаце лёгка дапрацаваць яго пад свае патрэбы.
Напрыклад, відавочнай выявай можна пазбавіцца ад наяўнасці стану, зрабіць кадаванне stateless - проста не абнаўляць зменныя offs, auxOffs и is21Bit у энкодэры і дэкодэры. У такім разе не атрымаецца эфектыўна пакаваць паслядоўнасці знакаў аднаго алфавіту, затое будзе гарантыя, што адзін і той жа знак заўсёды кадуецца аднымі і тымі ж байтамі, незалежна ад кантэксту.
Акрамя таго, можна завастрыць кадавальнік пад пэўную мову, памяняўшы стан па змаўчанні — напрыклад, арыентуючыся на рускія тэксты, выставіць у пачатку энкодэра і дэкодэра. offs = 0x0400 и auxOffs = 0. У асаблівасці гэта мае сэнс менавіта ў выпадку stateless рэжыму. У цэлым гэта будзе падобна на выкарыстанне старой васьмібітнай кадоўкі, толькі не пазбаўляе магчымасці ўстаўляць сімвалы з усяго Юнікод па неабходнасці.
Яшчэ адзін недахоп, згаданы раней – у аб'ёмным тэксце, закадаваным у UTF-C, няма хуткага спосабу знайсці мяжу знака, найблізкага да адвольнага байта. Адрэзаўшы ад закадаванага буфера апошнія, скажам, 100 байт, вы рызыкуеце атрымаць смецце, з якім нічога не зрабіць. На захоўванне шматгігабайтных логаў кадзіроўка і не разлічана, але ў цэлым гэта можна паправіць. Байт 0xBF ніколі не павінен сустракацца ў якасці першага байта (але можа быць другім ці трэцім). Таму пры кадаванні можна ўстаўляць паслядоўнасць 0xBF 0xBF 0xBF кожныя, скажам, 10 Кб - тады пры неабходнасці знайсці мяжу будзе дастаткова прасканаваць абраны кавалак да таго часу, пакуль не знойдзецца падобны маркер. Услед за апошнім 0xBF гарантавана будзе пачатак знака. (Пры дэкадаванні гэтую паслядоўнасць з трох байт, вядома, трэба будзе ігнараваць.)
Падводзячы вынік
Калі вы дачыталі дасюль – віншую! Спадзяюся, вы, як і я, даведаліся нешта новае (ці асвяжылі ў памяці старое) аб прыладзе Юнікод.
Дэмантрацыйная старонка. На прыкладзе іўрыта бачныя перавагі як перад UTF-8, так і перад SCSU.
Не варта разглядаць вышэйапісаныя пошукі як замах на стандарты. Аднак я ў цэлым задаволены вынікамі сваіх напрацовак, таму рады імі : напрыклад, JS-бібліятэка ў мініфікаваным выглядзе важыць усяго 1710 байт (і не мае залежнасцяў, вядома). Як я згадваў вышэй, з яе працай можна азнаёміцца на (Там жа ёсць набор тэкстаў, на якіх яе можна параўноўваць з UTF-8 і SCSU).
Напрыканцы яшчэ раз звярну ўвагу на кейсы, у якіх выкарыстоўваць UTF-C не варта:
- Калі вашыя радкі дастаткова доўгія (ад 100-200 сімвалаў). У такім разе варта задумацца аб ужыванні алгарытмаў сціску накшталт deflate.
- Калі вам неабходна ASCII transparency, гэта значыць вам важна, каб у закадаваных паслядоўнасцях не ўзнікалі ASCII-коды, якіх не было ў зыходным радку. Патрэбнасці ў гэтым можна пазбегнуць, калі пры ўзаемадзеянні са іншымі API (напрыклад, працуючы з БД) вы будзеце перадаваць вынік кадавання як абстрактны набор байт, а не як радкі. У адваротным выпадку вы рызыкуеце атрымаць непрадбачаныя ўразлівасці.
- Калі вы жадаеце мець магчымасць хутка знаходзіць межы знакаў па адвольным зрушэнні (напрыклад, пры пашкоджанні часткі радка). Гэта можна рабіць, але толькі прасканаваўшы радок ад пачатку (ці ўжыўшы дапрацоўку, апісаную ў папярэдняй частцы).
- Калі вам трэба хутка рабіць аперацыі над зместам радкоў (сартаваць іх, шукаць у іх падрадкі, канкатэнаваць). Для гэтага радкі патрабуецца спачатку дэкадаваць, таму UTF-C будзе павольней UTF-8 у гэтых выпадках (але хутчэй алгарытмаў сціску). Паколькі адзін і той жа радок заўсёды кадуецца аднолькава, дакладнае параўнанне дэкадавання не патрабуе, яго можна вырабляць пабайтава.
абнаўленне: карыстальнік выклаў графік, які падкрэслівае мяжу дастасавальнасці UTF-C. На ім відаць, што UTF-C эфектыўней алгарытму сціску агульнага прызначэння (варыяцыі LZW) датуль, пакуль пакаваны радок карацей. ~140 сімвалаў (праўда, адзначу, што параўнанне праводзілася на адным тэксце; для іншых моў вынік можа адрознівацца).
Крыніца: habr.com