Mengapa UTF-8 membuang beberapa bit dalam pengkodeannya

17

Menurut artikel Wikipedia , UTF-8 memiliki format ini:

Kode pertama Kode terakhir Bytes Byte 1 Byte 2 Byte 3 Byte 4
point point Digunakan
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 berarti bit ini digunakan untuk memilih titik kode.

Ini membuang dua bit pada setiap byte lanjutan dan satu bit pada byte pertama. Mengapa UTF-8 tidak dikodekan seperti berikut ini?

Kode pertama Kode terakhir Bytes Byte 1 Byte 2 Byte 3
point point Digunakan
U + 0000 U + 007F 1 0xxxxxxx
U + 0080 U + 3FFF 2 10xxxxxx xxxxxxxx
U + 0800 U + 1FFFFF 3 110xxxxx xxxxxxxx xxxxxxxx

Ini akan menghemat satu byte ketika titik kode di luar Basic Multilingual Plane atau jika titik kode berada dalam kisaran [U + 800, U + 3FFF].

Mengapa UTF-8 tidak dikodekan dengan cara yang lebih efisien?

character-encoding utf-8 text-encoding qbt937
sumber
3
cl.cam.ac.uk/~mgk25/ucs/utf-8-history.txt Pengkodean yang Anda ajukan mirip dengan proposal FSS / UTF yang asli. Ken Thompson dan Rob Pike menginginkan properti sinkronisasi itu sendiri.
ninjalj
4
Selain itu, penyandian Anda tampaknya tidak menjamin bahwa nilai-nilai kode ASCII tidak muncul di bagian mana pun dari representasi untuk karakter non-ASCII. FSS / UTF dan UTF-8 dirancang untuk bekerja dengan program lawas, (misalnya: mereka yang menggunakan ASCII NUL dan slash (pemisah jalur) sebagai pemisah).
ninjalj

Jawaban:

26

Hal ini dilakukan agar Anda dapat mendeteksi ketika Anda berada di tengah urutan multi-byte. Saat melihat data UTF-8, Anda tahu bahwa jika Anda melihat 10xxxxxx, bahwa Anda berada di tengah-tengah karakter multibyte, dan harus kembali dalam aliran sampai Anda melihat salah satu 0xxxxxxatau 11xxxxxx. Menggunakan skema Anda, byte 2 atau 3 dapat dengan mudah berakhir dengan pola seperti salah satu 0xxxxxxxatau11xxxxxx

Juga perlu diingat bahwa berapa banyak yang disimpan sepenuhnya bervariasi pada jenis data string apa yang Anda encoding. Untuk sebagian besar teks, bahkan teks Asia, Anda jarang akan melihat empat byte karakter dengan teks normal. Juga, perkiraan naif orang tentang bagaimana teks akan terlihat sering salah. Saya memiliki teks yang dilokalkan untuk UTF-8 yang mencakup string Jepang, Cina, dan Korea, namun sebenarnya bahasa Rusia yang mengambil sebagian besar ruang. (Karena string Asia kita sering memiliki karakter Romawi diselingi untuk nama yang tepat, tanda baca dan semacamnya dan karena kata Cina rata-rata adalah 1-3 karakter sedangkan rata-rata kata Rusia banyak, banyak lagi.)

Gort the Robot
sumber
Tetapi dengan skema saya jika Anda mulai dari lokasi yang dikenal sebagai pengemis dari sebuah karakter, maka Anda dapat mengetahui berapa banyak byte yang ada dalam karakter tersebut dan mendapatkan pengemis dari karakter berikutnya.
qbt937
11
Tentu. Skema Anda lebih padat informasi tetapi tidak memiliki fitur penting yang disediakan UTF-8. Secara umum, orang lebih menyukai keselamatan, itulah sebabnya UTF-8 dimungkinkan. Selain itu, untuk benar-benar membuktikan skema Anda sebenarnya lebih efisien, Anda ingin memberikan statistik menggunakan teks nyata. Anda mungkin menemukan bahwa dalam kebanyakan teks nyata, skema Anda menyimpan jumlah yang sangat sepele dan karenanya penghematan tidak sepadan.
Gort the Robot
3
Satu karakteristik penting lainnya: Jika tidak ada titik nol nol tertanam, tidak ada nol yang tertanam di dalam string.
Deduplicator
Untuk skrip Thailand, Anda harus mengizinkan 4 byte per karakter yang dicetak. Mereka tidak hanya datang terlambat ke pesta dan mendapat kelompok kode bernomor tinggi. Banyak hal yang terlihat seperti satu karakter ketika dicetak sebenarnya terdiri dari tiga karakter unicode yang berbeda.
James Anderson
@ qbt937: Menggunakan skema Anda, bagaimana cara cepat memindai untuk mengetahui apakah satu string berisi lainnya?
supercat
6

Cara resmi memungkinkan decoder tahu ketika itu di tengah-tengah tupel dan ia tahu untuk melewati byte (atau pergi ke belakang) sampai byte dimulai dengan 0atau 11; ini mencegah nilai-nilai sampah ketika satu byte rusak.

ratchet freak
sumber
3

Jawaban singkatnya, proposal Anda tidak membedakan antara byte pertama dan byte lanjutan.

Pola bit di ujung atas byte pertama memberi tahu Anda berapa banyak byte karakter sebenarnya dibangun. Pola-pola ini juga menyediakan beberapa pengenalan kesalahan saat mengurai string. Jika Anda membaca byte pertama dari sebuah karakter dan Anda mendapatkan 10xxxxxx maka Anda tahu bahwa Anda tidak selaras.

Kitana
sumber
2

Apa yang belum disebutkan adalah bahwa jika Anda memiliki urutan poin kode yang benar, dan pointer yang dijamin untuk menunjuk ke byte pertama dari titik kode, dengan UTF-8 Anda dapat dengan mudah menemukan pointer ke byte pertama. dari titik kode sebelumnya (lewati semua byte yang dimulai dengan 01xx xxxx). Dengan penyandian Anda, tidak mungkin tanpa berpotensi memeriksa semua byte hingga awal string.

Pertimbangkan urutan (2n + 2) byte

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

dan 

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

Jika Anda memiliki pointer ke byte pertama dari titik kode pertama setelah urutan ini, Anda harus memeriksa semua byte untuk mengetahui apakah titik kode terakhir adalah 0xxxxxxx atau (10xxxxxx, 0xxxxxxx).

Sebenarnya ada skema pengkodean yang lebih efisien, di mana pergi ke titik kode sebelumnya dapat dilakukan dalam waktu yang konstan, dan pointer ke tengah titik kode dapat diperbaiki. Izinkan kode berikut:

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

Jika salah satu dari tiga byte sebelumnya adalah ≥ 236 maka itu adalah awal dari urutan 3 byte, karena tidak mungkin ada dua byte seperti itu dalam setiap urutan 3 byte yang valid. Jika tidak, jika salah satu dari dua byte sebelumnya adalah ≥ 128 maka itu adalah awal dari urutan dua byte. Jika tidak, byte sebelumnya adalah byte tunggal <128.

Mencari substring menjadi sedikit lebih sulit. Anda mungkin ingin mengecualikan nol byte sehingga string hanya berisi byte nol jika mengandung titik kode nol.

gnasher729
sumber
Apa yang belum disebutkan ... - tidak benar-benar mengikuti langsung dari pengamatan yang dibuat dalam jawaban @ scratchet freak ini.
Piotr Dobrogost