Jeśli jesteś programistą i stoisz przed zadaniem wyboru kodowania, Unicode prawie zawsze będzie właściwym rozwiązaniem. Konkretny sposób reprezentacji zależy od kontekstu, ale najczęściej i tutaj istnieje uniwersalna odpowiedź - UTF-8. Dobrą rzeczą jest to, że pozwala używać wszystkich znaków Unicode bez wydawania pieniędzy za dużo w większości przypadków dużo bajtów. To prawda, że w przypadku języków, które używają więcej niż tylko alfabetu łacińskiego, „nie za dużo” to przynajmniej dwa bajty na znak. Czy możemy zrobić lepiej bez powrotu do prehistorycznego kodowania, które ogranicza nas do zaledwie 256 dostępnych znaków?
Poniżej proponuję zapoznać się z moją próbą odpowiedzi na to pytanie i zaimplementować stosunkowo prosty algorytm, który pozwala na przechowywanie linii w większości języków świata bez dodawania redundancji jaka jest w UTF-8.
Zastrzeżenie. Od razu zrobię kilka ważnych zastrzeżeń: opisywane rozwiązanie nie jest oferowane jako uniwersalny zamiennik UTF-8, nadaje się tylko w wąskiej liście przypadków (więcej na ten temat poniżej) i w żadnym wypadku nie powinien być używany do interakcji z interfejsami API stron trzecich (które nawet o tym nie wiedzą). Najczęściej algorytmy kompresji ogólnego przeznaczenia (na przykład deflate) nadają się do kompaktowego przechowywania dużych ilości danych tekstowych. Poza tym już w trakcie tworzenia mojego rozwiązania znalazłem istniejący standard w samym Unicode, który rozwiązuje ten sam problem - jest nieco bardziej skomplikowany (i często gorszy), ale nadal jest to standard przyjęty, a nie tylko stawiany razem na kolanie. O nim też opowiem.
Informacje o Unicode i UTF-8
Na początek kilka słów o tym co to jest Unicode и UTF-8.
Jak wiadomo, popularne było kiedyś kodowanie 8-bitowe. Dzięki nim wszystko było proste: 256 znaków można ponumerować liczbami od 0 do 255, a liczby od 0 do 255 można oczywiście przedstawić jako jeden bajt. Jeśli cofniemy się na sam początek, kodowanie ASCII jest całkowicie ograniczone do 7 bitów, zatem najbardziej znaczącym bitem w jego reprezentacji bajtowej jest zero i większość kodowań 8-bitowych jest z nim kompatybilna (różnią się jedynie „górną” część, gdzie najbardziej znaczący bit to jeden).
Czym Unicode różni się od tych kodowań i dlaczego wiąże się z nim tak wiele specyficznych reprezentacji - UTF-8, UTF-16 (BE i LE), UTF-32? Uporządkujmy to po kolei.
Podstawowy standard Unicode opisuje jedynie zgodność między znakami (a w niektórych przypadkach poszczególnymi składnikami znaków) i ich liczbami. W tym standardzie jest wiele możliwych liczb - od 0x00 do 0x10FFFF (1 114 112 sztuk). Gdybyśmy chcieli umieścić w zmiennej liczbę z takiego zakresu, nie wystarczyłby nam ani 1, ani 2 bajty. A ponieważ nasze procesory nie są zbyt zaprojektowane do pracy z liczbami trzybajtowymi, bylibyśmy zmuszeni użyć aż 4 bajtów na znak! Jest to UTF-32, ale właśnie z powodu tej „marnotrawstwa” ten format nie jest popularny.
Na szczęście kolejność znaków w Unicode nie jest przypadkowa. Cały ich zestaw jest podzielony na 17-calowesamoloty", z których każdy zawiera 65536 (0x10000) «punkty kodowe" Koncepcja „punktu kodowego” jest tutaj prosta numer znaku, przypisany do niego przez Unicode. Ale, jak wspomniano powyżej, w Unikodzie numerowane są nie tylko poszczególne znaki, ale także ich elementy składowe i znaki usługowe (a czasami w ogóle nic nie odpowiada numerowi - może na razie, ale dla nas nie jest to tak ważne), więc bardziej poprawne jest zawsze mów konkretnie o liczbie samych liczb, a nie symboli. Jednak w dalszej części, dla zachowania zwięzłości, często będę używał słowa „symbol”, sugerując termin „punkt kodowy”.
Samoloty Unicode. Jak widać większość z nich (płaszczyzny od 4 do 13) jest nadal niewykorzystana.
Najbardziej niezwykłe jest to, że cała główna „miazga” leży w płaszczyźnie zerowej, nazywa się to „Podstawowa płaszczyzna wielojęzyczna”. Jeśli linia zawiera tekst w jednym ze współczesnych języków (w tym chińskim), nie wyjdziesz poza tę płaszczyznę. Ale nie możesz też odciąć reszty Unicode - na przykład emoji znajdują się głównie na końcu następny samolot”Dodatkowy samolot wielojęzyczny„(rozciąga się od 0x10000 do 0x1FFFF). Więc UTF-16 robi to: wszystkie znaki, które się w nim mieszczą Podstawowa płaszczyzna wielojęzyczna, są kodowane „tak jak jest” z odpowiednią liczbą dwubajtową. Jednak część liczb z tego zakresu w ogóle nie wskazuje konkretnych znaków, a wskazuje, że po tej parze bajtów trzeba rozważyć kolejną - łącząc razem wartości tych czterech bajtów, otrzymamy liczbę obejmującą cały prawidłowy zakres Unicode. Pomysł ten nazywa się „parami zastępczymi” – być może o nich słyszałeś.
Zatem UTF-16 wymaga dwóch lub (w bardzo rzadkich przypadkach) czterech bajtów na „punkt kodowy”. Jest to lepsze niż ciągłe używanie czterech bajtów, ale kodowanie w języku łacińskim (i innych znakach ASCII) powoduje marnowanie połowy miejsca na zera. UTF-8 ma to poprawić: ASCII w nim zajmuje, jak poprzednio, tylko jeden bajt; kody z 0x80 do 0x7FF - dwa bajty; z 0x800 do 0xFFFF - trzy i od 0x10000 do 0x10FFFF - cztery. Z jednej strony alfabet łaciński stał się dobry: powróciła zgodność z ASCII, a dystrybucja jest bardziej równomiernie „rozłożona” od 1 do 4 bajtów. Ale alfabety inne niż łaciński nie przynoszą żadnych korzyści w porównaniu z UTF-16, a wiele z nich wymaga obecnie trzech bajtów zamiast dwóch – zakres objęty dwubajtowym rekordem zawęził się 32 razy, przy czym 0xFFFF do 0x7FFi nie są w nim uwzględnione ani chińskie, ani na przykład gruzińskie. Cyrylica i pięć innych alfabetów - hurra - na szczęście, 2 bajty na znak.
Dlaczego to się dzieje? Zobaczmy, jak UTF-8 reprezentuje kody znaków:
Do bezpośredniego przedstawienia liczb używane są tutaj bity oznaczone symbolem x. Można zauważyć, że w rekordzie dwubajtowym jest tylko 11 takich bitów (z 16). Bity wiodące pełnią tutaj jedynie funkcję pomocniczą. W przypadku rekordu czterobajtowego na numer punktu kodowego przydzielanych jest 21 z 32 bitów - wydawałoby się, że trzy bajty (co daje w sumie 24 bity) wystarczą, ale znaczniki usług pochłaniają zbyt dużo.
Czy to jest złe? Nie bardzo. Z jednej strony, jeśli bardzo zależy nam na przestrzeni, mamy algorytmy kompresji, które z łatwością mogą wyeliminować całą dodatkową entropię i redundancję. Z drugiej strony celem Unicode było zapewnienie możliwie najbardziej uniwersalnego kodowania. Przykładowo możemy powierzyć linię zakodowaną w UTF-8 kodowi, który wcześniej działał tylko w ASCII i nie bać się, że zobaczy znak z zakresu ASCII, którego tak naprawdę nie ma (w końcu w UTF-8 wszystkie bajtów zaczynając od bitu zerowego - to jest dokładnie to, czym jest ASCII). A jeśli nagle zechcemy odciąć mały ogonek od dużego sznurka bez dekodowania go od początku (lub przywrócić część informacji po uszkodzonym fragmencie), łatwo nam znaleźć przesunięcie w miejscu, w którym zaczyna się znak (wystarczy aby pominąć bajty z przedrostkiem bitowym 10).
Po co więc wymyślać coś nowego?
Jednocześnie czasami zdarzają się sytuacje, w których algorytmy kompresji, takie jak deflate, nie nadają się do zastosowania, a chcesz uzyskać kompaktowe przechowywanie ciągów znaków. Osobiście napotkałem ten problem myśląc o budowie dla dużego słownika zawierającego słowa w dowolnych językach. Z jednej strony każde słowo jest bardzo krótkie, więc jego kompresja będzie nieskuteczna. Z drugiej strony, rozważana przeze mnie implementacja drzewa została zaprojektowana w taki sposób, że każdy bajt przechowywanego ciągu generował oddzielny wierzchołek drzewa, więc minimalizacja ich liczby była bardzo użyteczna. W mojej bibliotece (Jak w , na którym się opiera) podobny problem można rozwiązać w prosty sposób - pakując ciągi znaków -słownik, przechowywany tam w . Ale, jak łatwo zrozumieć, działa to dobrze tylko w przypadku ograniczonego alfabetu - do takiego słownika nie można dodać wiersza w języku chińskim.
Osobno chciałbym zwrócić uwagę na jeszcze jeden nieprzyjemny niuans, który pojawia się podczas używania UTF-8 w takiej strukturze danych. Powyższy rysunek pokazuje, że gdy znak jest zapisywany jako dwa bajty, bity związane z jego numerem nie są ułożone w rzędzie, ale są oddzielone parą bitów 10 pośrodku: 110xxxxx 10xxxxxx. Z tego powodu, gdy 6 dolnych bitów drugiego bajtu przepełni się w kodzie znaku (tj. nastąpi przejście 10111111 → 10000000), wówczas zmienia się także pierwszy bajt. Okazuje się, że litera „p” jest oznaczona bajtami 0xD0 0xBF, a następne „r” już jest 0xD1 0x80. W drzewie przedrostków prowadzi to do podziału węzła nadrzędnego na dwa - jeden dla przedrostka 0xD0, i kolejny dla 0xD1 (chociaż całą cyrylicę można było zakodować tylko w drugim bajcie).
Co dostałem
W obliczu tego problemu postanowiłem poćwiczyć grę z bitami, a jednocześnie trochę lepiej zapoznać się ze strukturą Unicode jako całości. W rezultacie powstał format kodowania UTF-C („C” dla kompaktowy), który zużywa nie więcej niż 3 bajty na punkt kodowy i bardzo często pozwala na wydawanie tylko jeden dodatkowy bajt na całą zakodowaną linię. Prowadzi to do tego, że w przypadku wielu alfabetów innych niż ASCII takie kodowanie okazuje się być 30-60% bardziej kompaktowy niż UTF-8.
Przedstawiłem przykłady realizacji algorytmów kodowania i dekodowania w postaci , możesz swobodnie używać ich w swoim kodzie. Ale nadal będę podkreślał, że w pewnym sensie format ten pozostaje „rowerem” i nie polecam go używać nie zdając sobie sprawy, dlaczego tego potrzebujesz. To wciąż bardziej eksperyment niż poważne „ulepszenie UTF-8”. Niemniej jednak kod tam napisany jest zgrabnie, zwięźle, z dużą liczbą komentarzy i pokryciem testów.
Wyniki testu i porównanie z UTF-8
Ja też to zrobiłem , gdzie możesz ocenić wydajność algorytmu, a następnie opowiem Ci więcej o jego zasadach i procesie rozwoju.
Eliminacja zbędnych bitów
Jako podstawę wziąłem oczywiście UTF-8. Pierwszą i najbardziej oczywistą rzeczą, którą można w nim zmienić, jest zmniejszenie liczby bitów usług w każdym bajcie. Na przykład pierwszy bajt w UTF-8 zawsze zaczyna się od jednego z nich 0, lub z 11 - przedrostek 10 Mają go tylko następujące bajty. Zamieńmy przedrostek 11 na 1, a dla kolejnych bajtów całkowicie usuniemy prefiksy. Co się stanie?
0xxxxxxx — 1 bajt
10xxxxxx xxxxxxxx - 2 bajty
110xxxxx xxxxxxxx xxxxxxxx - 3 bajty
Czekaj, gdzie jest czterobajtowy rekord? Ale nie jest to już potrzebne - pisząc w trzech bajtach, mamy teraz do dyspozycji 21 bitów i to wystarczy dla wszystkich liczb do 0x10FFFF.
Co tutaj poświęciliśmy? Najważniejsze jest wykrycie granic znaków z dowolnego miejsca w buforze. Nie możemy wskazać dowolnego bajtu i znaleźć z niego początku kolejnego znaku. Jest to ograniczenie naszego formatu, ale w praktyce rzadko jest to konieczne. Bufor zazwyczaj udaje nam się przebiec od samego początku (zwłaszcza jeśli chodzi o krótkie linie).
Poprawiła się także sytuacja z pokryciem języków 2 bajtami: teraz format dwubajtowy daje zakres 14 bitów, a są to kody do 0x3FFF. Chińczycy mają pecha (ich charaktery przeważnie wahają się od 0x4E00 do 0x9FFF), ale Gruzini i wiele innych narodów mają więcej zabawy - ich języki również mieszczą się w 2 bajtach na znak.
Wprowadź stan kodera
Zastanówmy się teraz nad właściwościami samych linii. Słownik zawiera najczęściej wyrazy zapisane znakami tego samego alfabetu i dotyczy to także wielu innych tekstów. Dobrze byłoby wskazać ten alfabet raz, a potem podać tylko numer litery w nim zawartej. Zobaczmy, czy układ znaków w tabeli Unicode nam pomoże.
Jak wspomniano powyżej, Unicode jest podzielony na samolot 65536 kodów każdy. Ale nie jest to zbyt przydatny podział (jak już powiedziano, najczęściej jesteśmy w płaszczyźnie zerowej). Bardziej interesujący jest podział przez Bloki. Zakresy te nie mają już stałej długości i są bardziej znaczące - z reguły każdy łączy w sobie znaki z tego samego alfabetu.
Blok zawierający znaki alfabetu bengalskiego. Niestety, ze względów historycznych, jest to przykład niezbyt gęstego opakowania – 96 znaków jest chaotycznie rozrzuconych po 128 blokowych punktach kodowych.
Początki bloków i ich rozmiary są zawsze wielokrotnościami 16 - robi się to po prostu dla wygody. Ponadto wiele bloków zaczyna się i kończy na wartościach będących wielokrotnościami 128, a nawet 256 - na przykład podstawowa cyrylica zajmuje 256 bajtów z 0x0400 do 0x04FF. Jest to całkiem wygodne: jeśli zapiszemy prefiks raz 0x04, wówczas dowolny znak cyrylicy można zapisać w jednym bajcie. To prawda, że w ten sposób stracimy możliwość powrotu do ASCII (i ogólnie do innych znaków). Dlatego robimy to:
- Dwa bajty
10yyyyyy yxxxxxxxnie tylko oznaczają symbol z liczbąyyyyyy yxxxxxxx, ale także zmienić aktualny alfabet nayyyyyy y0000000(tj. pamiętamy wszystkie bity z wyjątkiem tych najmniej znaczących Bit 7); - Jeden bajt
0xxxxxxxtaki jest charakter obecnego alfabetu. Należy go tylko dodać do przesunięcia, które zapamiętaliśmy w kroku 1. Chociaż nie zmieniliśmy alfabetu, przesunięcie wynosi zero, więc zachowaliśmy zgodność z ASCII.
Podobnie dla kodów wymagających 3 bajtów:
- Trzy bajty
110yyyyy yxxxxxxx xxxxxxxxwskazać symbol liczbąyyyyyy yxxxxxxx xxxxxxxx, zmiana aktualny alfabet nayyyyyy y0000000 00000000(pamiętałem wszystko oprócz młodszych Bit 15) i zaznacz pole, w którym się teraz znajdujemy długi tryb (przy zmianie alfabetu z powrotem na dwubajtowy zresetujemy tę flagę); - Dwa bajty
0xxxxxxx xxxxxxxxw trybie długim jest to znak bieżącego alfabetu. Podobnie dodajemy go z przesunięciem z kroku 1. Jedyną różnicą jest to, że teraz czytamy dwa bajty (bo przeszliśmy na ten tryb).
Brzmi nieźle: teraz, gdy musimy zakodować znaki z tego samego 7-bitowego zakresu Unicode, wydajemy 1 dodatkowy bajt na początku i łącznie jeden bajt na znak.
Praca z jedną z wcześniejszych wersji. Już często bije UTF-8, ale wciąż jest nad czym pracować.
Co jest gorsze? Po pierwsze mamy warunek, a mianowicie aktualne przesunięcie alfabetu i pole wyboru tryb długi. To nas jeszcze bardziej ogranicza: teraz te same znaki mogą być kodowane inaczej w różnych kontekstach. Na przykład wyszukiwanie podciągów będzie musiało zostać przeprowadzone z uwzględnieniem tego, a nie tylko poprzez porównanie bajtów. Po drugie, jak tylko zmieniliśmy alfabet, zrobiło się źle z kodowaniem znaków ASCII (i to nie tylko alfabet łaciński, ale także podstawowe znaki interpunkcyjne, łącznie ze spacjami) - wymagają ponownej zmiany alfabetu na 0, czyli znowu dodatkowy bajt (a potem kolejny, aby wrócić do naszego głównego punktu).
Jeden alfabet jest dobry, dwa są lepsze
Spróbujmy zmienić trochę nasze przedrostki bitowe, wciskając jeszcze jeden z trzech opisanych powyżej:
0xxxxxxx — 1 bajt w trybie normalnym, 2 w trybie długim
11xxxxxx — 1 bajt
100xxxxx xxxxxxxx - 2 bajty
101xxxxx xxxxxxxx xxxxxxxx - 3 bajty
Teraz w dwubajtowym rekordzie jest o jeden bit mniej - punkty kodowe do 0x1FFFI nie 0x3FFF. Jednak nadal jest zauważalnie większy niż w dwubajtowych kodach UTF-8, większość popularnych języków nadal się mieści, najbardziej zauważalna strata wypadła и , Japończycy są smutni.
Co to za nowy kod? 11xxxxxx? To mała „skrytka” o wielkości 64 znaków, która uzupełnia nasz główny alfabet, więc nazwałem ją pomocniczą (pomocniczy) alfabet. Gdy zmienimy obecny alfabet, fragment starego alfabetu stanie się pomocniczy. Na przykład przeszliśmy z ASCII na cyrylicę - skrytka zawiera teraz 64 znaki zawierające Alfabet łaciński, cyfry, spacja i przecinek (najczęstsze wstawki w tekstach innych niż ASCII). Wróciliśmy do ASCII - a główna część alfabetu cyrylicy stanie się alfabetem pomocniczym.
Dzięki dostępowi do dwóch alfabetów jesteśmy w stanie obsłużyć dużą liczbę tekstów przy minimalnych kosztach zmiany alfabetów (interpunkcja najczęściej będzie prowadziła do powrotu do ASCII, ale potem otrzymamy wiele znaków spoza ASCII z dodatkowego alfabetu, bez ponowne przełączanie).
Bonus: przedrostek podalfabetu 11xxxxxx i wybranie jego początkowego przesunięcia 0xC0, uzyskujemy częściową kompatybilność 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 uzyskać pomocniczy z alfabetu głównego? Możesz zostawić to samo przesunięcie, ale - niestety - tutaj struktura Unicode już 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 cyrylicy zaczyna się od 0x0400). Zatem po wniesieniu do skrytki pierwszych 64 znaków możemy utracić dostęp do końcowej części alfabetu.
Aby rozwiązać ten problem, ręcznie przejrzałem kilka bloków odpowiadających różnym językom i określiłem dla nich przesunięcie alfabetu pomocniczego w obrębie alfabetu głównego. Alfabet łaciński, jako wyjątek, został ogólnie zmieniony, podobnie jak base64.
Ostatnie poprawki
Zastanówmy się wreszcie, gdzie jeszcze możemy coś ulepszyć.
Należy pamiętać, że format 101xxxxx xxxxxxxx xxxxxxxx umożliwia kodowanie numerów do 0x1FFFFF, a Unicode kończy się wcześniej, o godz 0x10FFFF. Innymi słowy, ostatni punkt kodowy będzie reprezentowany jako 10110000 11111111 11111111. Dlatego możemy powiedzieć, że jeśli pierwszy bajt ma postać 1011xxxx (Gdzie xxxx większa niż 0), to oznacza to coś innego. Można na przykład dodać tam kolejnych 15 znaków, które są stale dostępne do zakodowania w jednym bajcie, ale zdecydowałem się zrobić to inaczej.
Przyjrzyjmy się teraz blokom Unicode, które wymagają trzech bajtów. Zasadniczo, jak już wspomniano, są to znaki chińskie - ale trudno z nimi cokolwiek zrobić, jest ich 21 tysięcy. Ale latały tam też hiragana i katakana - a nie ma ich już tak wiele, mniej niż dwieście. A ponieważ pamiętaliśmy Japończyków, są też emoji (w rzeczywistości są one rozproszone w wielu miejscach w Unicode, ale główne bloki znajdują się w zakresie 0x1F300 - 0x1FBFF). Jeśli pomyślisz o tym, że obecnie istnieją emoji złożone z kilku punktów kodowych jednocześnie (na przykład emoji składa się z aż 7 kodów!), to szkoda wydawać po trzy bajty na każdy (7×3 = 21 bajtów dla jednej ikony, koszmar).
Dlatego wybieramy kilka wybranych zakresów odpowiadających emoji, hiraganie i katakanie, przenumerowujemy je w jedną ciągłą listę i kodujemy jako dwa bajty zamiast trzech:
1011xxxx xxxxxxxx
Świetnie: wspomniany emoji, składający się z 7 punktów kodowych, zajmuje 8 bajtów w UTF-25 i dopasowujemy go 14 (dokładnie dwa bajty na każdy punkt kodowy). Swoją drogą Habr nie chciał go przetrawić (zarówno w starym, jak i nowym edytorze), więc musiałem go wstawić ze zdjęciem.
Spróbujmy rozwiązać jeszcze jeden problem. Jak pamiętamy, podstawowy alfabet to w zasadzie wysokie 6 bitów, o którym pamiętamy i przyklejamy do kodu każdego kolejnego zdekodowanego symbolu. W przypadku znaków chińskich znajdujących się w bloku 0x4E00 - 0x9FFF, jest to albo bit 0, albo 1. Nie jest to zbyt wygodne: będziemy musieli stale przełączać alfabet między tymi dwiema wartościami (tj. wydawać trzy bajty). Należy jednak pamiętać, że w trybie długim od samego kodu możemy odjąć liczbę znaków, które kodujemy w trybie krótkim (po wszystkich trikach opisanych powyżej jest to 10240) - wówczas zakres hieroglifów przesunie się do 0x2600 - 0x77FF, i w tym przypadku w całym tym zakresie najbardziej znaczące 6 bitów (spośród 21) będzie równe 0. Zatem sekwencje hieroglifów będą wykorzystywać dwa bajty na hieroglif (co jest optymalne dla tak dużego zakresu), bez powodując przełączenie alfabetu.
Rozwiązania alternatywne: SCSU, BOCU-1
Eksperci Unicode, zaraz po przeczytaniu tytułu artykułu, najprawdopodobniej spieszą z przypomnieniem, że bezpośrednio wśród standardów Unicode znajduje się (SCSU), który opisuje metodę kodowania bardzo podobną do opisanej w artykule.
Przyznam szczerze: o jego istnieniu dowiedziałam się dopiero po tym, jak głęboko pogrążyłam się w pisaniu swojej decyzji. Gdybym wiedział o tym od początku, prawdopodobnie próbowałbym napisać implementację, zamiast wymyślać własne podejście.
Co ciekawe, SCSU wykorzystuje pomysły bardzo podobne do tych, które sam wymyśliłem (zamiast pojęcia „alfabetów” używają „okien”, a jest ich więcej niż ja). Jednocześnie format ten ma również wady: jest nieco bliższy algorytmom kompresji niż algorytmom kodowania. W szczególności standard podaje wiele metod reprezentacji, ale nie mówi, jak wybrać optymalną - w tym celu koder musi zastosować jakąś heurystykę. Zatem koder SCSU, który tworzy dobre opakowanie, będzie bardziej złożony i bardziej uciążliwy niż mój algorytm.
Dla porównania przeniosłem stosunkowo prostą implementację SCSU na JavaScript - pod względem objętości kodu okazał się porównywalny z moim UTF-C, jednak w niektórych przypadkach wynik był kilkadziesiąt procent gorszy (czasami może go przekroczyć, ale nie za bardzo). Na przykład teksty w języku hebrajskim i greckim zostały zakodowane w formacie UTF-C 60% lepszy niż SCSU (prawdopodobnie ze względu na ich zwarte alfabety).
Osobno dodam, że oprócz SCSU istnieje jeszcze inny sposób na zwięzłe przedstawienie Unicode - , ale ma na celu zapewnienie zgodności MIME (której nie potrzebowałem) i przyjmuje nieco inne podejście do kodowania. Nie oceniałem jego skuteczności, ale wydaje mi się, że jest mało prawdopodobne, aby była wyższa od SCSU.
Możliwe ulepszenia
Algorytm, który przedstawiłem, nie jest z założenia uniwersalny (prawdopodobnie w tym miejscu moje cele najbardziej odbiegają od celów Konsorcjum Unicode). Wspomniałem już, że został on opracowany przede wszystkim do jednego zadania (przechowywanie słownika wielojęzycznego w drzewie prefiksów) i niektóre jego funkcje mogą nie nadawać się dobrze do innych zadań. Ale fakt, że nie jest to standard, może być plusem - z łatwością możesz go modyfikować, dostosowując go do swoich potrzeb.
Przykładowo w oczywisty sposób możesz pozbyć się stanu, zrobić kodowanie bezstanowe - po prostu nie aktualizuj zmiennych offs, auxOffs и is21Bit w koderze i dekoderze. W takim przypadku nie będzie możliwe efektywne spakowanie sekwencji znaków tego samego alfabetu, ale będzie gwarancja, że ten sam znak będzie zawsze zakodowany tymi samymi bajtami, niezależnie od kontekstu.
Dodatkowo możesz dostosować koder do konkretnego języka zmieniając stan domyślny - np. skupiając się na tekstach rosyjskich ustaw na początku koder i dekoder offs = 0x0400 и auxOffs = 0. Ma to szczególnie sens w przypadku trybu bezstanowego. Ogólnie rzecz biorąc, będzie to podobne do korzystania ze starego ośmiobitowego kodowania, ale bez usuwania możliwości wstawiania znaków ze wszystkich Unicode, jeśli to konieczne.
Inną wadą wspomnianą wcześniej jest to, że w dużym tekście zakodowanym w UTF-C nie ma szybkiego sposobu na znalezienie granicy znaku najbliższej dowolnemu bajtowi. Jeśli odetniesz ostatnie, powiedzmy, 100 bajtów z zakodowanego bufora, ryzykujesz otrzymaniem śmieci, z którymi nie będziesz mógł nic zrobić. Kodowanie nie jest przeznaczone do przechowywania logów wielogigabajtowych, ale ogólnie można to poprawić. Bajt 0xBF nigdy nie może występować jako pierwszy bajt (ale może być drugim lub trzecim bajtem). Dlatego podczas kodowania można wstawić sekwencję 0xBF 0xBF 0xBF co, powiedzmy, 10 KB - wtedy, jeśli trzeba znaleźć granicę, wystarczy zeskanować wybrany fragment, aż znajdzie się podobny znacznik. Podążając za ostatnim 0xBF z pewnością będzie początkiem znaku. (Podczas dekodowania tę sekwencję trzech bajtów należy oczywiście zignorować.)
Reasumując
Jeśli doczytałeś aż dotąd, gratulacje! Mam nadzieję, że podobnie jak ja dowiedziałeś się czegoś nowego (lub odświeżyłeś pamięć) na temat struktury Unicode.
Strona demonstracyjna. Przykład języka hebrajskiego pokazuje przewagę zarówno nad UTF-8, jak i SCSU.
Wyżej opisanych badań nie należy traktować jako naruszenia standardów. Generalnie jednak jestem zadowolony z efektów swojej pracy, więc jestem z nich zadowolony : na przykład zminimalizowana biblioteka JS waży tylko 1710 bajtów (i oczywiście nie ma żadnych zależności). Jak wspomniałem powyżej, jej prace można znaleźć pod adresem (jest też zestaw tekstów, na których można to porównać z UTF-8 i SCSU).
Na koniec jeszcze raz zwrócę uwagę na przypadki, w których używany jest format UTF-C nie warto:
- Jeśli Twoje linie są wystarczająco długie (od 100-200 znaków). W takim przypadku powinieneś pomyśleć o zastosowaniu algorytmów kompresji, takich jak deflate.
- Jeśli potrzebujesz Przezroczystość ASCII, czyli ważne jest dla Ciebie, aby zakodowane sekwencje nie zawierały kodów ASCII, których nie było w oryginalnym ciągu. Można tego uniknąć, jeśli podczas interakcji z interfejsami API innych firm (na przykład podczas pracy z bazą danych) wynik kodowania zostanie przekazany jako abstrakcyjny zestaw bajtów, a nie jako ciągi znaków. W przeciwnym razie ryzykujesz pojawieniem się nieoczekiwanych luk w zabezpieczeniach.
- Jeśli chcesz móc szybko znaleźć granice znaków przy dowolnym przesunięciu (na przykład, gdy część linii jest uszkodzona). Można to zrobić, ale tylko skanując linię od początku (lub stosując modyfikację opisaną w poprzednim rozdziale).
- Jeśli potrzebujesz szybko wykonać operacje na zawartości ciągów (sortować je, szukać w nich podciągów, łączyć). Wymaga to najpierw zdekodowania ciągów znaków, więc UTF-C będzie w takich przypadkach wolniejszy niż UTF-8 (ale szybszy niż algorytmy kompresji). Ponieważ ten sam ciąg znaków jest zawsze kodowany w ten sam sposób, dokładne porównanie dekodowania nie jest wymagane i można je przeprowadzić bajt po bajcie.
aktualizacja: użytkownik opublikował wykres przedstawiający ograniczenia zastosowania UTF-C. Pokazuje, że UTF-C jest bardziej wydajny niż algorytm kompresji ogólnego przeznaczenia (odmiana LZW), o ile upakowany ciąg jest krótszy ~140 znaków (Zaznaczam jednak, że porównanie przeprowadzono na jednym tekście, w przypadku innych języków wynik może się różnić).
Źródło: www.habr.com