Друг велосипед: съхраняваме Unicode низове с 30-60% по-компактни от UTF-8

Ако сте разработчик и сте изправени пред задачата да изберете кодиране, тогава Unicode почти винаги ще бъде правилното решение. Конкретният метод на представяне зависи от контекста, но най-често и тук има универсален отговор - UTF-8. Хубавото при него е, че ви позволява да използвате всички Unicode знаци, без да харчите твърде много много байтове в повечето случаи. Вярно е, че за езици, които използват повече от латинската азбука, „не твърде много“ е поне два байта на знак. Можем ли да се справим по-добре, без да се връщаме към праисторическите кодировки, които ни ограничават до само 256 налични знака?

По-долу предлагам да се запознаете с моя опит да отговоря на този въпрос и да приложа сравнително прост алгоритъм, който ви позволява да съхранявате линии на повечето езици по света, без да добавяте излишъка, който е в UTF-8.

Опровержение. Веднага ще направя няколко важни уговорки: описаното решение не се предлага като универсален заместител на UTF-8, той е подходящ само в тесен списък от случаи (повече за тях по-долу) и в никакъв случай не трябва да се използва за взаимодействие с API на трети страни (които дори не знаят за него). Най-често алгоритмите за компресиране с общо предназначение (например deflate) са подходящи за компактно съхранение на големи обеми текстови данни. Освен това, още в процеса на създаване на моето решение, намерих съществуващ стандарт в самия Unicode, който решава същия проблем - той е малко по-сложен (и често по-лош), но все пак е приет стандарт, а не просто поставен заедно на коляното. Ще ви разкажа и за него.

Относно Unicode и UTF-8

Като начало, няколко думи за това какво представлява Unicode и UTF-8.

Както знаете, 8-битовите кодировки бяха популярни. При тях всичко беше просто: 256 знака могат да бъдат номерирани с числа от 0 до 255, а числата от 0 до 255 очевидно могат да бъдат представени като един байт. Ако се върнем в самото начало, ASCII кодирането е напълно ограничено до 7 бита, така че най-значимият бит в неговото байтово представяне е нула и повечето 8-битови кодировки са съвместими с него (те се различават само в „горния“ част, където най-значимият бит е единица).

Как Unicode се различава от тези кодировки и защо толкова много специфични представяния са свързани с него - UTF-8, UTF-16 (BE и LE), UTF-32? Нека го подредим по ред.

Основният стандарт Unicode описва само съответствието между знаци (и в някои случаи отделни компоненти на знаци) и техните номера. И има много възможни числа в този стандарт - от 0x00 до 0x10FFFF (1 114 112 броя). Ако искаме да поставим число в такъв диапазон в променлива, нито 1, нито 2 байта няма да са ни достатъчни. И тъй като нашите процесори не са много предназначени за работа с трибайтови числа, ще бъдем принудени да използваме до 4 байта на символ! Това е UTF-32, но точно поради тази "разточителност" този формат не е популярен.

За щастие редът на знаците в Unicode не е случаен. Целият им комплект е разделен на 17 "самолети", всяка от които съдържа 65536 (0x10000) "кодови точки" Концепцията за „кодова точка“ тук е проста номер на символа, присвоени му от Unicode. Но, както бе споменато по-горе, в Unicode не само отделните знаци са номерирани, но и техните компоненти и служебни знаци (а понякога изобщо нищо не съответства на номера - може би за момента, но за нас това не е толкова важно), така че по-правилно е винаги да говорите конкретно за броя на самите числа, а не за символи. Въпреки това, по-нататък, за краткост, често ще използвам думата „символ“, загатвайки термина „кодова точка“.

Unicode самолети. Както можете да видите, по-голямата част (самолети от 4 до 13) все още не е използвана.

Най-забележителното е, че цялата основна „пулпа“ лежи в нулевата равнина, тя се нарича "Основен многоезичен план". Ако редът съдържа текст на един от съвременните езици (включително китайски), няма да излезете отвъд тази равнина. Но не можете да отрежете и останалата част от Unicode - например емотикони се намират главно в края на следващият самолет,"Допълнителен многоезичен самолет"(простира се от 0x10000 до 0x1FFFF). Така че UTF-16 прави това: всички символи, попадащи в рамките Основен многоезичен план, са кодирани „както е“ със съответния двубайтов номер. Въпреки това, някои от числата в този диапазон изобщо не показват конкретни знаци, а показват, че след тази двойка байтове трябва да разгледаме още една - чрез комбиниране на стойностите на тези четири байта заедно, получаваме число, което покрива целия валиден Unicode диапазон. Тази идея се нарича „сурогатни двойки“ – може би сте чували за тях.

Така че 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 бита) биха били достатъчни, но сервизните маркери изяждат твърде много.

това лошо ли е Не точно. От една страна, ако държим много на пространството, имаме алгоритми за компресиране, които могат лесно да премахнат цялата допълнителна ентропия и излишък. От друга страна, целта на Unicode беше да осигури възможно най-универсалното кодиране. Например, можем да поверим ред, кодиран в UTF-8, на код, който преди това е работил само с ASCII, и да не се страхуваме, че ще види символ от диапазона ASCII, който всъщност не е там (в крайна сметка в UTF-8 всички байтове, започващи от нулевия бит - точно това е ASCII). И ако внезапно искаме да отрежем малка опашка от голям низ, без да го декодираме от самото начало (или да възстановим част от информацията след повредена секция), за нас е лесно да намерим отместването, където започва знак (достатъчно е за да пропуснете байтове, които имат битов префикс 10).

Защо тогава да измислят нещо ново?

В същото време понякога има ситуации, когато алгоритми за компресиране като deflate са слабо приложими, но искате да постигнете компактно съхранение на низове. Лично аз се сблъсках с този проблем, когато мислех за изграждане компресирано префиксно дърво за голям речник, включващ думи на произволни езици. От една страна, всяка дума е много кратка, така че компресирането й ще бъде неефективно. От друга страна, реализацията на дървото, която разгледах, беше проектирана така, че всеки байт от съхранения низ генерира отделен връх на дърво, така че минимизирането на техния брой беше много полезно. В моята библиотека Az.js (Както в пиморфия2, на който се основава) подобен проблем може да бъде решен просто - низове, пакетирани в Dawg-речник, съхраняван там в добрият стар CP1251. Но, както е лесно да се разбере, това работи добре само за ограничена азбука - ред на китайски не може да бъде добавен към такъв речник.

Отделно бих искал да отбележа още един неприятен нюанс, който възниква при използването на UTF-8 в такава структура на данните. Картината по-горе показва, че когато знакът е записан като два байта, битовете, свързани с неговия номер, не идват в ред, а са разделени от двойка битове 10 по средата: 110xxxxx 10xxxxxx. Поради това, когато долните 6 бита на втория байт препълват в кода на символа (т.е. възниква преход 10111111 → 10000000), тогава първият байт също се променя. Оказва се, че буквата "p" се обозначава с байтове 0xD0 0xBF, а следващото „r“ е вече 0xD1 0x80. В префиксно дърво това води до разделянето на родителския възел на два - един за префикса 0xD0, и друг за 0xD1 (въпреки че цялата кирилица може да бъде кодирана само от втория байт).

Какво получих

Изправен пред този проблем, реших да се упражнявам да играя игри с битове и в същото време да се запозная малко по-добре със структурата на Unicode като цяло. Резултатът беше форматът за кодиране UTF-C ("C" за компактен), който изразходва не повече от 3 байта на кодова точка и много често ви позволява да харчите само един допълнителен байт за целия кодиран ред. Това води до факта, че на много не-ASCII азбуки такова кодиране се оказва 30-60% по-компактен от UTF-8.

Представих примери за внедряване на алгоритми за кодиране и декодиране във формата JavaScript и Go библиотеки, можете свободно да ги използвате във вашия код. Но все пак ще подчертая, че в известен смисъл този формат си остава „велосипед“ и не препоръчвам да го използвате без да осъзнавате защо ви трябва. Това все още е повече експеримент, отколкото сериозно „подобрение на 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 байта на знак.

Въведете състоянието на енкодера

Нека сега да помислим за свойствата на самите линии. Речникът най-често съдържа думи, написани с букви от същата азбука, а това важи и за много други текстове. Би било добре да посочите тази азбука веднъж и след това да посочите само номера на буквата в нея. Да видим дали подредбата на знаците в Unicode таблицата ще ни помогне.

Както бе споменато по-горе, Unicode е разделен на самолет 65536 кода всеки. Но това не е много полезно деление (както вече казахме, най-често сме в нулевата равнина). По-интересно е разделението по блокове. Тези диапазони вече нямат фиксирана дължина и са по-смислени - като правило всеки комбинира знаци от една и съща азбука.

Блок, съдържащ знаци от бенгалската азбука. За съжаление, поради исторически причини, това е пример за не много плътна опаковка - 96 знака са хаотично разпръснати в 128 блокови кодови точки.

Началото на блоковете и техните размери винаги са кратни на 16 - това се прави просто за удобство. В допълнение, много блокове започват и завършват на стойности, които са кратни на 128 или дори 256 - например основната кирилица заема 256 байта от 0x0400 до 0x04FF. Това е доста удобно: ако запазим префикса веднъж 0x04, тогава всеки кирилски знак може да бъде записан в един байт. Вярно е, че по този начин ще загубим възможността да се върнем към ASCII (и към всички други знаци като цяло). Затова правим това:

1. Два байта 10yyyyyy yxxxxxxx не само обозначават символ с число yyyyyy yxxxxxxx, но и промяна текуща азбука на yyyyyy y0000000 (т.е. помним всички битове с изключение на най-маловажните 7 бита);
2. Един байт 0xxxxxxx това е символът на настоящата азбука. Просто трябва да се добави към отместването, което запомнихме в стъпка 1. Въпреки че не променихме азбуката, отместването е нула, така че поддържахме съвместимост с ASCII.

По същия начин за кодове, изискващи 3 байта:

1. Три байта 110yyyyy yxxxxxxx xxxxxxxx обозначете символ с цифра yyyyyy yxxxxxxx xxxxxxxx, промяна текуща азбука на yyyyyy y0000000 00000000 (помни всичко, освен по-младите 15 бита) и поставете отметка в квадратчето, в което се намираме сега дълго режим (когато променим азбуката обратно на двубайтова, ще нулираме този флаг);
2. Два байта 0xxxxxxx xxxxxxxx в дълъг режим това е символът на текущата азбука. По същия начин го добавяме с отместването от стъпка 1. Единствената разлика е, че сега четем два байта (защото превключихме на този режим).

Звучи добре: сега, докато трябва да кодираме знаци от същия 7-битов Unicode диапазон, изразходваме 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.

Тук обаче възниква трудност: как да се получи спомагателна от основната азбука? Можете да оставите същото отместване, но - уви - тук Unicode структурата вече играе срещу нас. Много често основната част от азбуката не е в началото на блока (например руската главна „А“ има кода 0x0410, въпреки че кирилският блок започва с 0x0400). По този начин, след като сме взели първите 64 знака в скривалище, можем да загубим достъп до опашната част на азбуката.

За да коригирам този проблем, ръчно преминах през някои блокове, съответстващи на различни езици, и посочих отместването на спомагателната азбука в рамките на основната за тях. Латинската азбука, като изключение, обикновено беше пренаредена като base64.

Последни щрихи

Нека най-накрая да помислим къде другаде можем да подобрим нещо.

Имайте предвид, че форматът 101xxxxx xxxxxxxx xxxxxxxx ви позволява да кодирате числа до 0x1FFFFF, а Unicode завършва по-рано, на 0x10FFFF. С други думи, последната кодова точка ще бъде представена като 10110000 11111111 11111111. Следователно можем да кажем, че ако първият байт е от формата 1011xxxx (Където xxxx по-голямо от 0), тогава това означава нещо друго. Например, можете да добавите още 15 знака там, които са постоянно достъпни за кодиране в един байт, но реших да го направя по различен начин.

Нека сега разгледаме онези Unicode блокове, които изискват три байта. По принцип, както вече споменахме, това са китайски йероглифи - но е трудно да се направи нещо с тях, има 21 хиляди от тях. Но хирагана и катакана също летяха там - и вече няма толкова много от тях, по-малко от двеста. И тъй като си спомнихме японците, има и емотикони (всъщност те са разпръснати на много места в Unicode, но основните блокове са в диапазона 0x1F300 - 0x1FBFF). Ако се замислите върху факта, че сега има емотикони, които се сглобяват от няколко кодови точки наведнъж (например емотикони ‍‍‍ се състои от цели 7 кода!), тогава става пълен срам да харчите три байта за всеки (7×3 = 21 байта в името на една икона, кошмар).

Затова избираме няколко избрани диапазона, съответстващи на емоджи, хирагана и катакана, преномерираме ги в един непрекъснат списък и ги кодираме като два байта вместо три:

1011xxxx xxxxxxxx

Страхотно: гореспоменатите емотикони, състоящ се от 7 кодови точки, отнема 8 байта в UTF-25 и ние го поставяме в 14 (точно два байта за всяка кодова точка). Между другото, Habr отказа да го смила (както в стария, така и в новия редактор), така че трябваше да го вмъкна със снимка.

Нека се опитаме да разрешим още един проблем. Както си спомняме, основната азбука е по същество високи 6 бита, които имаме предвид и залепваме към кода на всеки следващ декодиран символ. В случай на китайски йероглифи, които са в блока 0x4E00 - 0x9FFF, това е или бит 0, или 1. Това не е много удобно: ще трябва постоянно да превключваме азбуката между тези две стойности (т.е. да изразходваме три байта). Но имайте предвид, че в дългия режим, от самия код можем да извадим броя знаци, които кодираме с помощта на краткия режим (след всички трикове, описани по-горе, това е 10240) - тогава диапазонът от йероглифи ще се измести към 0x2600 - 0x77FFи в този случай, в целия този диапазон, най-значимите 6 бита (от 21) ще бъдат равни на 0. По този начин последователностите от йероглифи ще използват два байта на йероглиф (което е оптимално за такъв голям диапазон), без причинявайки смяна на азбуката.

Алтернативни решения: SCSU, BOCU-1

Експертите по Unicode, току-що прочели заглавието на статията, най-вероятно ще побързат да ви напомнят, че директно сред стандартите на Unicode има Стандартна схема за компресиране за Unicode (SCSU), който описва метод на кодиране, много подобен на описания в статията.

Признавам честно: научих за съществуването му едва след като бях дълбоко потопен в писането на решението си. Ако знаех за това от самото начало, вероятно щях да се опитам да напиша имплементация, вместо да измисля собствен подход.

Интересното е, че SCSU използва идеи, много подобни на тези, които измислих сам (вместо концепцията за „азбуки“ те използват „прозорци“ и има повече от тях, отколкото имам). В същото време този формат има и недостатъци: той е малко по-близък до алгоритмите за компресиране, отколкото до тези за кодиране. По-специално, стандартът дава много методи за представяне, но не казва как да изберете оптималния - за това енкодерът трябва да използва някакъв вид евристика. По този начин SCSU енкодер, който произвежда добра опаковка, ще бъде по-сложен и по-тромав от моя алгоритъм.

За сравнение прехвърлих сравнително проста реализация на SCSU към JavaScript - по отношение на обема на кода се оказа сравнима с моя UTF-C, но в някои случаи резултатът беше с десетки процента по-лош (понякога може да го надвишава, но не много). Например текстове на иврит и гръцки бяха кодирани с UTF-C 60% по-добре от SCSU (вероятно поради компактните им азбуки).

Отделно ще добавя, че освен SCSU има и друг начин за компактно представяне на Unicode - BOCU-1, но има за цел MIME съвместимост (която не ми трябваше) и използва малко по-различен подход към кодирането. Не съм оценявал ефективността му, но ми се струва, че едва ли ще е по-висока от SCSU.

Възможни подобрения

Алгоритъмът, който представих, не е универсален по дизайн (тук вероятно моите цели се разминават най-много с целите на Unicode Consortium). Вече споменах, че е разработен основно за една задача (съхраняване на многоезичен речник в префиксно дърво) и някои от функциите му може да не са подходящи за други задачи. Но фактът, че не е стандарт, може да е плюс - можете лесно да го промените, за да отговаря на вашите нужди.

Например, по очевидния начин можете да се отървете от наличието на състояние, да направите кодиране без състояние - просто не актуализирайте променливите offs, auxOffs и is21Bit в енкодера и декодера. В този случай няма да е възможно ефективно да се опаковат поредици от знаци от една и съща азбука, но ще има гаранция, че един и същи знак винаги е кодиран с едни и същи байтове, независимо от контекста.

Освен това можете да приспособите енкодера към конкретен език, като промените състоянието по подразбиране - например, като се фокусирате върху руски текстове, задайте енкодера и декодера в началото offs = 0x0400 и auxOffs = 0. Това има особено смисъл в случай на режим без състояние. Като цяло това ще бъде подобно на използването на старото осембитово кодиране, но без да се премахва възможността за вмъкване на знаци от всички Unicode, ако е необходимо.

Друг недостатък, споменат по-рано, е, че в голям текст, кодиран в UTF-C, няма бърз начин за намиране на границата на знака, която е най-близо до произволен байт. Ако отрежете последните, да речем, 100 байта от кодирания буфер, рискувате да получите боклук, с който не можете да направите нищо. Кодирането не е предназначено за съхраняване на многогигабайтови регистрационни файлове, но като цяло това може да бъде коригирано. Байт 0xBF никога не трябва да се появява като първи байт (но може да бъде втори или трети). Следователно, когато кодирате, можете да вмъкнете последователността 0xBF 0xBF 0xBF всеки, да речем, 10 KB - тогава, ако трябва да намерите граница, ще бъде достатъчно да сканирате избраното парче, докато се намери подобен маркер. След последното 0xBF гарантирано е началото на герой. (Когато се декодира, тази последователност от три байта, разбира се, трябва да се игнорира.)

Резюмиране

Ако сте прочели дотук, поздравления! Надявам се, че и вие като мен сте научили нещо ново (или сте освежили паметта си) за структурата на Unicode.

Демо страница. Примерът на иврит показва предимствата както пред UTF-8, така и пред SCSU.

Гореописаните изследвания не трябва да се считат за посегателство върху стандартите. Като цяло обаче съм доволен от резултатите от моята работа, така че съм доволен от тях дял: например минимизирана JS библиотека тежи само 1710 байта (и няма зависимости, разбира се). Както споменах по-горе, нейната работа може да бъде намерена на демо страница (има и набор от текстове, по които може да се сравни с UTF-8 и SCSU).

И накрая, отново ще обърна внимание на случаите, в които се използва UTF-C не си струва:

• Ако вашите редове са достатъчно дълги (от 100-200 знака). В този случай трябва да помислите за използването на алгоритми за компресиране като deflate.
• Ако се нуждаеш ASCII прозрачност, тоест за вас е важно кодираните последователности да не съдържат ASCII кодове, които не са били в оригиналния низ. Необходимостта от това може да бъде избегната, ако при взаимодействие с API на трети страни (например работа с база данни) предавате резултата от кодирането като абстрактен набор от байтове, а не като низове. В противен случай рискувате да получите неочаквани уязвимости.
• Ако искате да можете бързо да намирате граници на знаци при произволно отместване (например, когато част от ред е повредена). Това може да стане, но само чрез сканиране на реда от началото (или прилагане на модификацията, описана в предишния раздел).
• Ако трябва бързо да извършвате операции върху съдържанието на низове (сортирайте ги, търсете поднизове в тях, конкатенирайте). Това изисква първо да се декодират низове, така че UTF-C ще бъде по-бавен от UTF-8 в тези случаи (но по-бърз от алгоритмите за компресиране). Тъй като един и същи низ винаги е кодиран по един и същи начин, не е необходимо точно сравнение на декодирането и може да се направи на база байт по байт.

Update: потребител Тьомич в коментарите по-долу публикува графика, подчертаваща границите на приложимост на UTF-C. Това показва, че UTF-C е по-ефективен от алгоритъм за компресия с общо предназначение (разновидност на LZW), стига пакетираният низ да е по-къс ~140 знака (отбелязвам обаче, че сравнението е извършено върху един текст; за други езици резултатът може да се различава).


Източник: www.habr.com