Jeśli jesteś programistą i stoisz przed zadaniem wyboru kodowania, zazwyczaj odpowiednim rozwiązaniem będzie Unicode. Konkretna metoda reprezentacji zależy od kontekstu, ale najczęściej jest tu również uniwersalna odpowiedź — UTF-8. Jest ono dobre, ponieważ pozwala na użycie wszystkich symboli Unicode, nie marnując zbyt wielu bajtów w większości przypadków. Prawda jest taka, że dla języków, które nie używają tylko alfabetu łacińskiego, „niezbyt wiele” — to co najmniej dwa bajty na znak. Czy można lepiej, nie wracając do prehistorycznych kodowań, które ograniczają nas do zaledwie 256 dostępnych symboli?
Poniżej przedstawiam swoją próbę odpowiedzi na to pytanie oraz implementację stosunkowo prostego algorytmu, który pozwala na przechowywanie ciągów w większości języków świata, nie dodając tej nadmiarowości, która występuje w UTF-8.
Zastrzeżenie. Od razu dokonam kilku ważnych zastrzeżeń: opisana tu metoda nie jest proponowana jako uniwersalne zastępstwo dla UTF-8, nadaje się tylko w wąskim zakresie przypadków (o których poniżej), i w żadnym wypadku nie należy jej stosować do interakcji z zewnętrznymi API (które o tym nie mają pojęcia). Najczęściej do kompaktowego przechowywania dużych ilości danych tekstowych lepiej nadają się algorytmy kompresji ogólnego przeznaczenia (na przykład deflate). Ponadto, już podczas tworzenia mojego rozwiązania odkryłem istniejący standard w samym Unicode, który rozwiązuje tę samą kwestię — jest on nieco bardziej skomplikowany (i często gorszy), ale wciąż jest to uznawany standard, a nie coś stworzonego na kolanie. O tym również opowiem.
O Unicode i UTF-8
Na początek — kilka słów o tym, czym w ogóle jest Unicode i UTF-8.
Jak wiadomo, wcześniej popularne były 8-bitowe kodowania. Z nimi wszystko było proste: 256 znaków można było ponumerować liczbami od 0 do 255, a liczby od 0 do 255 w oczywisty sposób przedstawia się w postaci jednego bajta. Jeśli wrócić do samych źródeł, to kodowanie ASCII ogranicza się w ogóle do 7 bitów, dlatego najwyższy bit w jego przedstawieniu bajtowym wynosi zero, a większość 8-bitowych kodowań jest z nim zgodna (różnią się tylko w „górnej” części, gdzie najwyższy bit wynosi jeden).
Czym więc różni się Unicode od tych kodowań i dlaczego związanych z nim jest wiele konkretnych reprezentacji — UTF-8, UTF-16 (BE i LE), UTF-32? Rozważmy to po kolei.
Główny standard Unicode opisuje jedynie zgodność między symbolami (a w niektórych przypadkach — pojedynczymi komponentami symboli) a ich numerami. A możliwych numerów w tym standardzie jest bardzo wiele — od 0x00 do 0x10FFFF (1 114 112 sztuk). Gdybyśmy chcieli umieścić liczbę w takim zakresie w zmiennej, ani 1, ani 2 bajty by nam nie wystarczyły. A ponieważ nasze procesory nie są dostosowane do pracy z liczbami trzybajtowymi, musielibyśmy używać całych 4 bajtów na jeden symbol! To właśnie jest UTF-32, ale ze względu na tę "marnotrawność" ten format nie cieszy się popularnością.
Na szczęście symbole w Unicode'ie nie są uporządkowane przypadkowo. Cała ich masa podzielona jest na 17 „poziomów», z których każdy zawiera 65536 (0x10000) «punktów kodowych». Pojęcie „punktu kodowego” tutaj — to po prostu numer symbolu, nadany mu przez Unicode. Ale, jak wspomniano wcześniej, w Unicode'ie są numerowane nie tylko pojedyncze symbole, ale także ich komponenty i znaczniki kontrolne (a czasami w ogóle nic nie odpowiada numerowi — być może do czasu, ale dla nas to nie ma znaczenia), dlatego poprawniej jest zawsze mówić o liczbie samych numerów, a nie symboli. Jednak dalej dla skrótu często będę używał słowa „symbol”, mając na myśli termin „punkt kodowy”.
Poziomy Unicode'a. Jak widać, większość (poziomy od 4 do 13) wciąż nie jest wykorzystywana.
Co najciekawsze — cała główna „miękka” leży w zerowym poziomie, nazywa się "Basic Multilingual Plane". Jeśli ciąg zawiera tekst w jednym z nowoczesnych języków (w tym chińskim), nie opuścisz tego poziomu. Ale nie można też odcinać pozostałej części Unicode'a — na przykład emotikony głównie znajdują się na końcu następnego poziomu, "Supplementary Multilingual Plane" (rozciąga się od 0x10000 do 0x1FFFF). Dlatego UTF-16 postępuje w ten sposób: wszystkie symbole, które znajdują się w Basic Multilingual Plane, są kodowane „tak jak są”, odpowiadając im dwu-bajtowym numerem. Jednak część liczb w tym zakresie w ogóle nie oznacza konkretnych symboli, a wskazuje, że po tej parze bajtów należy rozważyć jeszcze jedną — łącząc wartości tych czterech bajtów razem, uzyskamy liczbę obejmującą cały dozwolony zakres Unicode'a. To przedstawienie nazywa się „parami zastępczymi” — być może słyszeliście o nich.
W ten sposób UTF-16 wymaga dwóch lub (w bardzo rzadkich przypadkach) czterech bajtów na jeden „punkt kodowy”. To lepiej niż ciągłe korzystanie z czterech bajtów, ale łacina (i inne znaki ASCII) w takim kodowaniu zajmują połowę miejsca wypełnionego zerami. UTF-8 ma to naprawić: w nim ASCII zajmuje, jak dawniej, tylko jeden bajt; kody od 0x80 do 0x7FF — dwóch bajtów; od 0x800 do 0xFFFF — trzech, a od 0x10000 do 0x10FFFF — czterech. Z jednej strony łacina zyskała: przywrócono zgodność z ASCII, a także rozkład jest bardziej równomiernie „rozmazany” od 1 do 4 bajtów. Jednak alfabety inne niż łaciński niestety nie zyskują na tym w porównaniu do UTF-16, a wiele z nich teraz wymaga trzech bajtów zamiast dwóch — zakres pokrywany dwubajtowym zapisem skurczył się 32 razy, z 0xFFFF do 0x7FF, i nie obejmuje już ani chińskiego, ani, na przykład, gruzińskiego. Cyrylica i jeszcze pięć alfabetów — hurra — miały farta, 2 bajty na symbol.
Dlaczego tak się dzieje? Przyjrzyjmy się, jak UTF-8 reprezentuje kody symboli:
Bezpośrednio do reprezentacji liczb użyto bitów oznaczonych symbolem x. Widać, że w dwubajtowym zapisie takich bitów jest tylko 11 (z 16). Wiodące bity pełnią tutaj tylko funkcję pomocniczą. W przypadku czterobajtowego zapisu na numer kodu punktowego przewidziano 21 bitów z 32 — wydawałoby się, że wystarczyłoby i trzy bajty (które dają łącznie 24 bity), ale znaki pomocnicze zajmują zbyt wiele miejsca.
Czy to jest źle? W rzeczywistości nie bardzo. Z jednej strony — jeśli bardzo dbamy o zajmowaną przestrzeń, mamy algorytmy kompresji, które łatwo eliminują wszelką nadmierną entropię i nadmiarowość. Z drugiej strony — celem Unicode'a było zapewnienie maksymalnie uniwersalnego kodowania. Na przykład, napisana w UTF-8 linia może być zaufać kodowi, który wcześniej działał tylko z ASCII, i nie obawiać się, że zobaczy tam symbol z zakresu ASCII, którego tam w rzeczywistości nie ma (bo w UTF-8 wszystkie bajty, które zaczynają się od zera, to właśnie ASCII). A jeśli nagle chcemy odciąć mały ogon od dużej linii, nie dekodując jej od samego początku (lub przywracając część informacji po uszkodzonym fragmencie) — nie jest trudno znaleźć przesunięcie, w którym zaczyna się jakiś symbol (wystarczy pominąć bajty, które mają prefiks bitowy 10).
Dlaczego zatem wymyślać coś nowego?
Jednocześnie zdarzają się sytuacje, w których algorytmy kompresji, takie jak deflate, są słabo zastosowane, a chęć uzyskania kompaktowego przechowywania ciągów jest duża. Osobiście spotkałem się z takim zadaniem, myśląc o budowie dla dużego słownika, który obejmuje słowa w dowolnych językach. Z jednej strony każde słowo jest bardzo krótkie, więc kompresja byłaby nieefektywna. Z drugiej - implementacja drzewa, którą rozważałem, była zaprojektowana tak, aby każdy bajt przechowywanego ciągu generował oddzielny wierzchołek drzewa, co sprawiało, że minimalizowanie ich liczby było bardzo korzystne. W mojej bibliotece (podobnie jak w , na której się opiera) podobny problem rozwiązuje się prosto — ciągi, spakowane w , są tam przechowywane w . Ale, jak łatwo zrozumieć, działa to dobrze tylko dla ograniczonego alfabetu — ciąg w języku chińskim nie zmieściłby się już w takim słowniku.
Osobno zauważę jeszcze jeden nieprzyjemny niuans, który pojawia się podczas używania UTF-8 w takiej strukturze danych. Na powyższym obrazku widać, że podczas zapisu znaku w postaci dwóch bajtów bity odnoszące się do jego numeru nie są sąsiadujące, a są rozdzielone parą bitów 10 pośrodku: 110xxxxx 10xxxxxx. Z tego powodu, gdy w kodzie znaku przepełniają się najmniejsze 6 bitów drugiego bajtu (tzn. następuje przejście 10111111 → 10000000), to zmienia się również pierwszy bajt. Okazuje się, że litera „п” jest oznaczana przez bajty 0xD0 0xBF, a następna po niej „р” — już przez 0xD1 0x80. W drzewie prefiksowym prowadzi to do podziału wierzchołka rodzica na dwa — jeden dla prefiksu 0xD0, a drugi dla 0xD1 (chociaż cała cyrylica mogłaby być kodowana tylko drugim bajtem).
Co mi wyszło
Stykając się z tym zadaniem postanowiłem poćwiczyć zabawy z bitami, a przy okazji nieco lepiej poznać strukturę Unicode w ogóle. Efektem był format kodowania UTF-C („C” od compact), który nie zużywa więcej niż 3 bajtów na jeden punkt kodowy, a bardzo często pozwala na zużycie tylko jednego zbędnego bajta na cały kodowany ciąg. Prowadzi to do tego, że w wielu nie-ASCII alfabetach takie kodowanie okazuje się o 30-60% bardziej kompaktowe niż UTF-8.
Zrealizowałem przykłady implementacji algorytmów kodowania i dekodowania w formie , możesz swobodnie używać ich w swoim kodzie. Niemniej jednak podkreślam, że w pewnym sensie ten format pozostaje „rowerem” i nie rekomenduję jego użycia bez świadomości, po co ci on jest potrzebny. To wciąż bardziej eksperyment niż poważne „ulepszenie UTF-8”. Mimo to, kod jest napisany starannie, zwięźle, z dużą liczbą komentarzy i pokryciem testami.
Wynik działania testów i porównanie z UTF-8
Dodatkowo stworzyłem , gdzie można ocenić działanie algorytmu, a dalej opowiem szczegółowo o jego zasadach i procesie rozwoju.
Eliminujemy zbędne bity
Za podstawę wziąłem oczywiście UTF-8. Pierwsze i najbardziej oczywiste, co można zmienić — to zmniejszyć liczbę bitów sterujących w każdym bajcie. Na przykład, pierwszy bajt w UTF-8 zawsze zaczyna się albo od 0, albo od 11 — a prefix 10 ma tylko następne bajty. Zastąpimy prefix 11 na 1, a w kolejnych bajtach całkowicie usuniemy prefiksy. Co z tego wyjdzie?
0xxxxxxx — 1 bajt
10xxxxxx xxxxxxxx — 2 bajty
110xxxxx xxxxxxxx xxxxxxxx — 3 bajty
Stop, a gdzie zapis czterobajtowy? A stał się niepotrzebny — przy zapisie trzema bajtami mamy teraz dostępny 21 bit i wystarcza to z zapasem na wszystkie liczby do 0x10FFFF.
Czegoś się tu zrzekliśmy? Najważniejsze — wykrywanie granic symboli z dowolnego miejsca w buforze. Nie możemy wskazać na dowolny bajt i od niego znaleźć początek następnego symbolu. To ograniczenie naszego formatu, ale w praktyce potrzeba takiej funkcjonalności rzadko się pojawia. Zazwyczaj potrafimy przebiec bufor od samego początku (zwłaszcza gdy mowa o krótkich ciągach).
Sytuacja z pokryciem języków 2 bajtami również poprawiła się: teraz dwubajtowy format daje zakres 14 bitów, co oznacza kody do 0x3FFF. Chińczykom się nie wiedzie (ich znaki głównie mieszczą się w zakresie od 0x4E00 do 0x9FFF), ale Gruzinom i wielu innym narodowościom jest teraz weselej — ich języki również mieszczą się w 2 bajtach na symbol.
Wprowadzamy stan enkodera
Zastanówmy się teraz nad właściwościami samych ciągów. W słowniku najczęściej znajdują się słowa napisane znakami jednego alfabetu, a dla wielu innych tekstów również jest to prawda. Dobrze by było raz wskazać ten alfabet, a dalej podawać tylko numer litery w nim. Zobaczmy, czy pomoże nam rozmieszczenie znaków w tabeli Unicode.
Jak wspomniano wcześniej, Unicode jest podzielony na płaszczyzny po 65536 kodów każdy. Ale to nie jest zbyt przydatny podział (jak już wspomniano, najczęściej jesteśmy w zero-osi). Bardziej interesującym podziałem jest bloki. Te zakresy już nie mają stałej długości i mają więcej sensu - zazwyczaj każdy łączy znaki jednego alfabetu.
Blok, zawierający znaki alfabetu bengalskiego. Niestety, z powodów historycznych, jest to przykład niezbyt gęstego pakowania - 96 znaków jest chaotycznie rozrzuconych po 128 punktach kodowych bloku.
Początki bloków i ich rozmiary są zawsze wielokrotnością 16 - zrobiono to po prostu dla wygody. Ponadto wiele bloków zaczyna się i kończy na wartościach wielokrotnych 128 lub nawet 256 - na przykład, podstawowa cyrylica zajmuje 256 bajtów od 0x0400 do 0x04FF. To dość wygodne: jeśli raz zapiszemy prefiks 0x04, to każdy znak cyrylicy można zapisać jednym bajtem. Niestety, tracimy jednak możliwość powrotu do ASCII (i do jakichkolwiek innych znaków w ogóle). Dlatego robimy tak:
- Dwa bajty
10yyyyyy yxxxxxxxnie tylko oznaczają znak o numerzeyyyyyy yxxxxxxx, ale także zmieniają aktualny alfabet nayyyyyy y0000000(tzn. zapamiętujemy wszystkie bity, z wyjątkiem najniższych 7 bitów); - Jeden bajt
0xxxxxxxto znak aktualnego alfabetu. Należy go po prostu dodać do przesunięcia, które zapamiętaliśmy w kroku 1. Dopóki nie zmieniamy alfabetu, przesunięcie wynosi zero, więc zachowaliśmy zgodność z ASCII.
Podobnie dla kodów, które wymagają 3 bajtów:
- Trzy bajty
110yyyyy yxxxxxxx xxxxxxxxoznaczają znak o numerzeyyyyyy yxxxxxxx xxxxxxxx, zmieniają aktualny alfabet nayyyyyy y0000000 00000000(zapamiętaliśmy wszystko, z wyjątkiem najniższych 15 bitów), i ustawiają znacznik, że teraz jesteśmy w długim trybie (przy zmianie alfabetu z powrotem na dwubajtowy, ten znacznik zostanie zresetowany); - Dwa bajty
0xxxxxxx xxxxxxxxw długim trybie to znak aktualnego alfabetu. Podobnie, dodajemy go do przesunięcia z kroku 1. Cała różnica polega na tym, że teraz czytamy dwa bajty (ponieważ przeszliśmy do takiego trybu).
Brzmi nieźle: teraz, dopóki musimy kodować znaki z tego samego 7-bitowego zakresu Unicode, wydajemy 1 dodatkowy bajt na początku i po jednym bajcie na każdy znak.
Działa jedna z wczesnych wersji. Już często omija UTF-8, ale wciąż jest co poprawiać.
Co stało się gorsze? Po pierwsze, mamy stan, a mianowicie przesunięcie aktualnego alfabetu i znacznik długiego trybuDodatkowo ogranicza nas to: teraz te same znaki mogą być kodowane w różny sposób w różnych kontekstach. Szukanie podciągów, na przykład, będzie musiało być już uwzględnione w tym kontekście, a nie tylko porównując bajty. Po drugie, zaraz po zmianie alfabetu, kodowanie znaków ASCII zaczęło sprawiać problemy (a to nie tylko łacińska, ale i podstawowa interpunkcja, w tym spacje) — wymagają one ponownej zmiany alfabetu na 0, co oznacza znowu dodatkowy bajt (a następnie jeszcze jeden, by wrócić do naszego głównego).
Jeden alfabet jest dobry, dwa — lepsze
Spróbujmy nieco zmienić nasze prefiksy bitowe, dodając do tych trzech opisanych jeszcze jeden:
0xxxxxxx — 1 bajt w normalnym trybie, 2 w długim
11xxxxxx — 1 bajt
100xxxxx xxxxxxxx — 2 bajty
101xxxxx xxxxxxxx xxxxxxxx — 3 bajty
Teraz w zapisie dwubajtowym jeden dostępny bit stał się mniej — mogą się zmieścić punkty kodowe aż do 0x1FFF, a nie 0x3FFF. Tyle że wciąż jest to wyraźnie więcej niż w dwubajtowych kodach UTF-8, większość powszechnie używanych języków nadal się mieści, największą stratą jest i , Japończycy są smutni.
Cóż to za nowy kod 11xxxxxx? Это небольшой «загашник» размером в 64 символа, он дополняет наш основной алфавит, поэтому я назвал его вспомогательным (auxiliary) alfabetem. Kiedy przełączamy aktualny alfabet, kawałek starego alfabetu staje się pomocniczy. Na przykład, przełączając się z ASCII na cyrylicę — w „zapleczu” jest teraz 64 znaki, zawierające łacinę, cyfry, spację i przecinek (najczęstsze wstawki w tekstach non-ASCII). Powracając z powrotem do ASCII — pomocniczym alfabetem stanie się główna część cyrylicy.
Dzięki dostępowi do dwóch alfabetów możemy poradzić sobie z dużą ilością tekstów, mając minimalne koszty na przełączanie alfabetów (interpunkcja najczęściej będzie prowadzić do powrotu do ASCII, ale potem wiele znaków non-ASCII będziemy pobierać już z dodatkowego alfabetu, bez ponownego przełączania).
Bonus: oznaczając dodatkowy alfabet prefiksem 11xxxxxx i wybierając jego wstępne przesunięcie równe 0xC0, uzyskujemy częściową zgodność z CP1252. Innymi słowy, wiele (ale nie wszystkie) tekstów zachodnioeuropejskich zakodowanych w CP1252 będzie wyglądać tak samo w UTF-C.
Tutaj jednak pojawia się trudność: jak przełączyć się z głównego alfabetu na pomocniczy? Można zachować to samo przesunięcie, ale — niestety — tutaj struktura Unicode gra przeciwko nam. Bardzo często główna część alfabetu nie znajduje się na początku bloku (na przykład rosyjska wielka litera „A” ma kod 0x0410, chociaż blok cyryliczny zaczyna się od 0x0400). W ten sposób, biorąc w „zaplecze” pierwsze 64 znaki, możliwe, że utracimy dostęp do końcowej części alfabetu.
Aby rozwiązać ten problem, ręcznie przeszedłem przez niektóre bloki odpowiadające różnym językom i wskazałem dla nich przesunięcie pomocniczego alfabetu w obrębie głównego. Łacińskie litery w zasadzie przemieściłem przynajmniej tak jak base64.
Ostatnie szlify
Na koniec pomyślmy, gdzie jeszcze możemy coś dopracować.
Zauważmy, że format 101xxxxx xxxxxxxx xxxxxxxx pozwala zakodować liczby aż do 0x1FFFFF, a Unicode kończy się wcześniej, na 0x10FFFF. Innymi słowy, ostatni punkt kodowy będzie reprezentowany jako 10110000 11111111 11111111. Możemy zatem powiedzieć, że jeśli pierwszy bajt ma postać 1011xxxx (gdzie xxxx więcej niż 0), oznacza to coś innego. Na przykład, można dodać tam jeszcze 15 znaków, które są stale dostępne do kodowania jednym bajtem, ale zdecydowałem się postąpić inaczej.
Przyjrzyjmy się blokom Unicode, które obecnie wymagają trzech bajtów. Głównie, jak już wspomniano, są to chińskie znaki — ale trudno coś z nimi zrobić, jest ich 21 tysięcy. Ale też tam wpadły hiragana i katakana — a tych już nie ma tak dużo, mniej niż dwieście. A skoro wspomnieliśmy o Japończykach — tam też są emotikony (naprawdę są rozsiane w Unicode, ale podstawowe bloki w zakresie 0x1F300 – 0x1FBFF). Jeśli pomyślimy o tym, że obecnie istnieją emotikony, które składają się z kilku punktów kodowych (na przykład emotikona składa się z aż 7 kodów!), to naprawdę szkoda wydawać na każdą po trzy bajty (7×3 = 21 bajtów za jeden znak, to koszmar).
Dlatego wybieramy kilka wybranych zakresów odpowiadających emotikonom, hiraganie i katakanie, numerujemy je ponownie w jedną ciągłą listę i kodujemy w postaci dwóch bajtów zamiast trzech:
1011xxxx xxxxxxxx
Świetnie: wcześniej wspomniana emotikona , składająca się z 7 punktów kodowych, w UTF-8 zajmuje 25 bajtów, a my zmieściliśmy ją w 14 dokładnie po dwa bajty na każdy punkt kodowy). Nawiasem mówiąc, Habr odmówił jej przetworzenia (zarówno w starym, jak i nowym edytorze), więc musiałem wstawić ją jako obrazek.
Spróbujmy naprawić jeszcze jeden problem. Jak pamiętamy, główny alfabet to w rzeczywistości najstarsze 6 bitów, które trzymamy w pamięci i przyklejamy do kodu każdego kolejnego dekodowanego znaku. W przypadku chińskich znaków, które znajdują się w bloku 0x4E00 – 0x9FFF, to jest to albo bit 0, albo 1. To nie jest zbyt wygodne: będziemy musieli cały czas przełączać alfabet między tymi dwoma wartościami (tzn. wydawać po trzy bajty). Ale zauważmy, że w trybie długim z samego kodu możemy odjąć liczbę znaków, które kodujemy przy użyciu trybu krótkiego (po wszystkich wcześniej opisanych sztuczkach to 10240) — wtedy zakres znaków przesunie się do 0x2600 – 0x77FF, a w tym przypadku w całym tym zakresie najwyższe 6 bitów (z 21) będzie równe 0. Tak więc, ciągi znaków będą używać po dwa bajty na znak (co jest optymalne dla tak dużego zakresu), nie powodując przełączeń alfabetu.
Alternatywne rozwiązania: SCSU, BOCU-1
Znawcy Unicode, jeszcze tylko przeczytawszy tytuł artykułu, prawdopodobnie pospieszą się, aby przypomnieć, że bezpośrednio w standardach Unicode istnieje (SCSU), który opisuje sposób kodowania, bardzo podobny do tego opisanego w artykule.
Przyznaję się szczerze: o jego istnieniu dowiedziałem się dopiero głęboko zanurzywszy się w pisanie mojego rozwiązania. Gdybym wiedział o nim od samego początku, prawdopodobnie spróbowałbym napisać jego implementację zamiast wymyślania własnego podejścia.
Co ciekawe, SCSU wykorzystuje pomysły bardzo podobne do tych, do których doszedłem samodzielnie (zamiast pojęcia 'alfabetów' używane są 'okna', a ich dostępnych jest więcej niż u mnie). Jednocześnie ten format ma też minusy: jest nieco bliżej algorytmów kompresji niż kodowania. W szczególności standard oferuje wiele sposobów reprezentacji, ale nie mówi, jak wybrać z nich optymalny — w tym celu enkoder musi stosować jakieś heurystyki. Tak więc, enkoder SCSU, oferujący dobrą kompresję, będzie trudniejszy i bardziej nieporęczny niż mój algorytm.
Dla porównania, przeniosłem stosunkowo prostą implementację SCSU na JavaScript — pod względem objętości kodu okazała się porównywalna z moim UTF-C, ale w niektórych przypadkach uzyskała wyniki o dziesiątki procent gorsze (czasami może ją przewyższać, ale nieznacznie). Na przykład teksty w języku hebrajskim i greckim UTF-C skompresowałem aż o 60% lepiej niż SCSU (najprawdopodobniej z powodu ich kompaktowych alfabetów).
Osobno dodam da, osim SCSU, postoji i drugi način kompakt predstaviti Unicode — , ale ma na celu zgodność z MIME (co nie było mi potrzebne), i używa nieco innego podejścia do kodowania. Nie oceniałem jego efektywności, ale wydaje mi się, że nie będzie ona wyższa niż SCSU.
Możliwe udoskonalenia
Zaproponowany przeze mnie algorytm nie jest uniwersalny z założenia (w tym, chyba, moje cele w największym stopniu rozchodzą się z celami konsorcjum Unicode). Już wspomniałem, że był on projektowany głównie do jednej zadania (przechowywania wielojęzycznego słownika w drzewie prefiksowym), a niektóre z jego cech mogą się słabo sprawdzać w innych zadaniach. Ale fakt, że nie jest standardem, może być również plusem — możesz łatwo dostosować go do swoich potrzeb.
Na przykład, oczywiście, można pozbyć się stanu, przeprowadzając kodowanie bezstanowe — po prostu nie aktualizując zmiennych zwolnienia, auxOffs i is21Bit w enkoderze i dekoderze. W takim przypadku nie będzie można efektywnie pakować sekwencji znaków z jednego alfabetu, ale będzie gwarancja, że ten sam znak zawsze koduje się tymi samymi bajtami, niezależnie od kontekstu.
Ponadto można dostosować enkoder do konkretnego języka, zmieniając stan domyślny — na przykład, orientując się na tekstach rosyjskich, ustawić na początku enkodera i dekodera offs = 0x0400 i auxOffs = 0. W szczególności ma to sens w przypadku trybu bezstanowego. Ogólnie rzecz biorąc, będzie to przypominało użycie starego osiembitowego kodowania, tylko nie pozbawia możliwości wstawiania znaków z całego Unicode w razie potrzeby.
Kolejna wada, wspomniana wcześniej — w obszernej tekście zakodowanym w UTF-C nie ma szybkiego sposobu na znalezienie granicy znaku najbliższego do dowolnego bajtu. Odcinając od zakodowanego bufora ostatnie, powiedzmy, 100 bajtów, ryzykujesz uzyskanie śmieci, z którymi nie można nic zrobić. Kodowanie nie jest zaprojektowane do przechowywania kilku gigabajtowych logów, ale w ogólnym zarysie można to poprawić. Bajt 0xBF nigdy nie powinien występować jako pierwszy bajt (ale może być drugim lub trzecim). Dlatego podczas kodowania można wstawić sekwencję 0xBF 0xBF 0xBF na przykład co 10 KB — wtedy, w razie potrzeby, wystarczy zeskanować wybrany fragment, aż znajdzie się odpowiedni znacznik. Po tym ostatnim 0xBF z pewnością będzie początek znaku. (Podczas dekodowania, tę sekwencję trzech bajtów należy oczywiście zignorować.)
Podsumowując
Jeśli dotarłeś tutaj — gratulacje! Mam nadzieję, że, tak jak ja, nauczyłeś się czegoś nowego (lub odświeżyłeś starą wiedzę) na temat działania Unicode.
Strona demonstracyjna. Na przykładzie hebrajskiego widać zalety zarówno w porównaniu z UTF-8, jak i SCSU.
Nie należy traktować powyższych rozważań jako naruszenie standardów. Jednak ogólnie jestem zadowolony z wyników mojej pracy, więc cieszę się, że podzielić: na przykład, biblioteka JS w zminimalizowanej wersji waży zaledwie 1710 bajtów (i nie ma oczywiście żadnych zależności). Jak wspomniałem wcześniej, można zapoznać się z jej działaniem na (tam znajduje się również zestaw tekstów, na których można porównać ją z UTF-8 i SCSU).
Na koniec jeszcze raz zwrócę uwagę na przypadki, w których używanie UTF-C jest niezalecane:
- Jeśli twoje ciągi są wystarczająco długie (od 100 do 200 znaków). W takim przypadku warto rozważyć zastosowanie algorytmów kompresji, takich jak deflate.
- Jeśli potrzebujesz przezroczystości ASCII, to znaczy ważne jest dla ciebie, aby w zakodowanych sekwencjach nie występowały kody ASCII, które nie były obecne w oryginalnym ciągu. Można uniknąć tych potrzeb, jeśli podczas współpracy z zewnętrznymi API (np. pracując z bazą danych) będziesz przekazywać wyniki kodowania jako abstrakcyjny zbiór bajtów, a nie jako ciągi. W przeciwnym razie ryzykujesz wystąpieniem nieprzewidzianych luk.
- Jeśli chcesz mieć możliwość szybkiego znajdowania granic znaków w dowolnym przesunięciu (na przykład w przypadku uszkodzenia części ciągu). Można to zrobić, ale tylko poprzez zeskanowanie ciągu od początku (lub zastosowanie modyfikacji opisanej w poprzedniej sekcji).
- Jeśli potrzebujesz szybko wykonywać operacje na zawartości ciągów (sortować je, wyszukiwać podciągi, konkatenować). W tym celu ciągi należy najpierw dekodować, dlatego UTF-C będzie wolniejszy niż UTF-8 w tych przypadkach (ale szybszy niż algorytmy kompresji). Ponieważ ten sam ciąg zawsze jest kodowany w ten sam sposób, dokładne porównanie dekodowania nie jest wymagane, można je wykonać bajt po bajcie.
Aktualizacja: użytkownik opublikował wykres pokazujący granice zastosowania UTF-C. Widać na nim, że UTF-C jest bardziej efektywny niż algorytmy kompresji ogólnego przeznaczenia (warianty LZW), dopóki kompresowany ciąg jest krótszy ~140 znaków (choć zauważam, że porównanie było przeprowadzone na jednym tekście; dla innych języków wyniki mogą się różnić).
Źródło: habr.com
