Dlaczego UTF-8 marnuje kilka bitów na kodowanie?

17

Zgodnie z artykułem Wikipedii UTF-8 ma ten format:

Pierwszy kod Ostatni kod Bajty Bajt 1 Bajt 2 Bajt 3 Bajt 4
punkt punkt Używany
U + 0000 U + 007F 1 0xxxxxxx
U + 0080 U + 07FF 2 110xxxxx 10xxxxxx
U + 0800 U + FFFF 3 1110xxxx 10xxxxxx 10xxxxxx
U + 10000 U + 1FFFFF 4 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
x oznacza, że ​​ten bit służy do wyboru punktu kodowego.

Marnuje to dwa bity na każdym bajcie kontynuacji i jeden bit w pierwszym bajcie. Dlaczego kod UTF-8 nie jest kodowany w następujący sposób?

Pierwszy kod Ostatni kod Bajty Bajt 1 Bajt 2 Bajt 3
punkt punkt Używany
U + 0000 U + 007F 1 0xxxxxxx
U + 0080 U + 3FFF 2 10xxxxxx xxxxxxxx
U + 0800 U + 1FFFFF 3 110xxxxx xxxxxxxx xxxxxxxx

Zapisałby jeden bajt, gdy punkt kodowy jest poza podstawową płaszczyzną wielojęzyczną lub jeśli punkt kodowy znajduje się w zakresie [U + 800, U + 3FFF].

Dlaczego UTF-8 nie jest kodowany w bardziej wydajny sposób?

qbt937
źródło
3
cl.cam.ac.uk/~mgk25/ucs/utf-8-history.txt Proponowane kodowanie jest podobne do oryginalnej propozycji FSS / UTF. Ken Thompson i Rob Pike chcieli własności samosynchronizującej.
ninjalj
4
Ponadto kodowanie nie gwarantuje, że wartości kodu ASCII nie pojawią się w żadnej części reprezentacji znaków spoza ASCII. FSS / UTF i UTF-8 są przeznaczone do pracy ze starszymi programami (np. Tymi, które używają ASCII NUL i slash (separator ścieżek) jako separatorów).
ninjalj

Odpowiedzi:

26

Odbywa się to, aby można było wykryć, że znajdujesz się w środku sekwencji wielobajtowej. Patrząc na UTF-8 danych, wiesz, że jeśli widzisz 10xxxxxx, że jesteś w środku wielobajtowego znaku i powinien wykonać kopię zapasową w strumieniu aż zobaczysz albo 0xxxxxxalbo 11xxxxxx. Korzystanie z systemu, bajty 2 lub 3 może łatwo skończyć z wzorach, jak też 0xxxxxxxczy11xxxxxx

Należy również pamiętać, że ile zaoszczędzono, zależy całkowicie od rodzaju kodowanych danych łańcuchowych. W przypadku większości tekstów, nawet tekstów azjatyckich, rzadko można zobaczyć czterobajtowe znaki z normalnym tekstem. Ponadto naiwne oceny ludzi dotyczące wyglądu tekstu są często błędne. Mam zlokalizowany tekst dla UTF-8, który zawiera ciągi japońskie, chińskie i koreańskie, ale tak naprawdę rosyjski zajmuje najwięcej miejsca. (Ponieważ nasze azjatyckie ciągi znaków często zawierają rzymskie znaki przeplatane nazwami własnymi, interpunkcją itp. Oraz ponieważ średnie chińskie słowo ma 1-3 znaków, podczas gdy średnie rosyjskie słowo ma wiele, wiele innych.)

Gort the Robot
źródło
Ale ze mną schemat, jeśli zaczniesz w miejscu, o którym wiadomo, że jest na początku postaci, możesz powiedzieć, ile bajtów jest w postaci i przejść do początku następnej postaci.
qbt937
11
Pewnie. Twój schemat jest bardziej gęsty, ale nie ma ważnej funkcji, którą zapewnia UTF-8. Ogólnie ludzie wolą bezpieczeństwo, dlatego UTF-8 jest możliwy. Poza tym, aby naprawdę udowodnić, że twój schemat jest faktycznie bardziej wydajny, chciałbyś podać statystyki przy użyciu prawdziwego tekstu. Może się okazać, że w większości prawdziwych tekstów twój program oszczędza bardzo trywialną kwotę, a zatem oszczędności nie są tego warte.
Gort the Robot
3
Inna ważna cecha: Jeśli nie ma osadzonego punktu zerowego, w ciągu nie ma żadnych zer.
Deduplicator
W przypadku skryptu tajskiego należy zezwolić na 4 bajty na drukowany znak. Nie tylko spóźnili się na przyjęcie i otrzymali grupę kodów o wysokim numerze. Wiele rzeczy, które po wydrukowaniu wyglądają jak pojedynczy znak, w rzeczywistości składają się z trzech różnych znaków Unicode.
James Anderson
@ qbt937: W jaki sposób można szybko skanować, aby sprawdzić, czy jeden ciąg zawiera inny?
supercat
6

Oficjalny sposób informuje dekoder, kiedy znajduje się w środku krotki i wie, że może pomijać bajty (lub cofać się), dopóki bajt nie zaczyna się od 0lub 11; zapobiega to wartościom śmieci, gdy pojedynczy bajt zostanie uszkodzony.

maniak zapadkowy
źródło
3

Krótka odpowiedź, twoja propozycja nie rozróżnia między bajtem pierwszym a bajtem kontynuacji.

Wzór bitowy na górnym końcu pierwszego bajtu informuje o tym, ile bajtów zbudowany jest rzeczywisty znak. Te wzorce zapewniają również pewne rozpoznawanie błędów podczas parsowania łańcucha. Jeśli czytasz (pozornie) pierwszy bajt znaku i dostajesz 10xxxxxx, to wiesz, że nie jesteś zsynchronizowany.

Kitana
źródło
2

Nie wspomniano jednak, że jeśli masz prawidłową sekwencję punktów kodowych i wskaźnik, który gwarantuje, że wskazuje pierwszy bajt punktu kodowego, dzięki UTF-8 możesz bardzo łatwo znaleźć wskaźnik do pierwszego bajtu poprzedniego punktu kodowego (pomiń wszystkie bajty zaczynające się od 01xx xxxx). W przypadku kodowania jest to niemożliwe bez potencjalnego sprawdzenia wszystkich bajtów aż do początku łańcucha.

Rozważ sekwencje (2n + 2) bajtów

0xxxxxxx
n times (10xxxxxx, 10xxxxxx)
0xxxxxxx

i

n times (10xxxxxx, 10xxxxxx)
(10xxxxxx, 0xxxxxxx)

Jeśli masz wskaźnik do pierwszego bajtu pierwszego punktu kodowego po tej sekwencji, musisz sprawdzić wszystkie bajty, aby dowiedzieć się, czy ostatnim punktem kodowym jest 0xxxxxxx lub (10xxxxxx, 0xxxxxxx).

W rzeczywistości istnieją bardziej wydajne schematy kodowania, w których przejście do poprzedniego punktu kodowego można wykonać w stałym czasie, a wskaźniki do środka punktu kodowego można naprawić. Zezwól na następujące kody:

X where X < 128
YX where 128 ≤ Y < 236, X < 128
ZYY where 236 ≤ Z < 256, 0 ≤ Y < 236. 

Jeśli jeden z trzech poprzednich bajtów ma wartość ≥ 236, oznacza to początek 3-bajtowej sekwencji, ponieważ nie może być dwóch takich bajtów w żadnej prawidłowej sekwencji 3-bajtowej. W przeciwnym razie, jeśli jeden z dwóch poprzednich bajtów ma wartość ≥ 128, jest to początek sekwencji dwóch bajtów. W przeciwnym razie poprzedni bajt jest pojedynczym bajtem <128.

Wyszukiwanie podciągów staje się nieco trudniejsze. Możesz wykluczyć zero bajtów, aby ciąg zawierał tylko bajt zerowy, jeśli zawiera zerowy punkt kodowy.

gnasher729
źródło
Co nie zostało wspomniane… - nie tak naprawdę, ponieważ wynika to bezpośrednio z obserwacji dokonanej w odpowiedzi maniaka @ratchet.
Piotr Dobrogost