Pengodean Huffman: mengapa tidak perlu pemisah?

17 
Char        Code
====        ====
E           0000
i           0001
y           0010
l           0011
k           0100
.           0101
space       011
e           10
r           1100
s           1101
n           1110
a           1111

Teks asli:

Mata menakutkan terlihat di dekat danau


Disandikan : 0000101100000110011100010101101101001111101011111100011001111110100100101

Mengapa tidak perlu pemisah dalam pengkodean Huffman?

coding-theory encoding-scheme huffman-coding BufBills
sumber
1
Karena ketika Anda mendekode nilai biner, Anda mengambil potongan "kiri ke kanan" bit mana yang lebih dulu cocok dengan nilai dari teks asli. Seperti dalam kasus ini, Anda melihat potongan paling kiri (0000) cocok dengan E. Jika ada simbol dengan nilai 000 di kode karakter Anda, Anda akan mengganti 000 dengan simbol itu, dan kemudian mulai mencari lagi dari bit yang tersisa di cara "kiri ke kanan". Itu sebabnya Anda tidak perlu pemisahan.
Syed Ali Hamza
1
Pertanyaannya menyiratkan bahwa pemisah biasanya diperlukan. Anda sudah tahu bahwa Anda tidak memerlukan pemisah di Eerie eyes seen near lake(well, kecuali untuk karakter spasi). Tetapi karakter itu sendiri tidak membutuhkan pemisah. Kenapa tidak?
MSalters
coba untuk memecahkan kode sendiri, tidak pernah ada ambiguitas.
njzk2
@MSalters: Tapi pemisah yang biasanya diperlukan dengan kata-kata variabel-panjang: cat cheat for mice≠ catch eat form ice. Analogi Anda cacat: setiap huruf adalah atom; surat-surat dibedakan secara sepele dan secara intrinsik dapat dipisahkan. Analogi yang lebih baik adalah "Mengapa Anda bisa membaca skrip kursif (tulisan tangan), ketika setiap kata hanya satu baris panjang, coretan, memotong garis sendiri?", Dan bahkan itu adalah analogi yang buruk, karena Anda dapat melihat kata tulisan tangan ( atau bahkan sebagian dari satu) dan membedakan masing-masing huruf - sedangkan string yang dikodekan Huffman adalah omong kosong jika Anda tidak dapat melihat awal.
G-Man Mengatakan 'Reinstate Monica'
@Malter Saya tidak melihat poin Anda. Saya tidak memerlukan pemisah untuk karakter karena kami menggunakan pengodean dengan lebar tetap: setiap blok delapan bit berturut-turut sesuai dengan satu karakter. Tetapi pengkodean Huffman tidak tetap-lebar, karena itu pertanyaannya.
David Richerby

Jawaban:

50

Anda tidak memerlukan pemisah karena kode Huffman adalah kode bebas awalan (juga, tidak membantu, dikenal sebagai "kode awalan"). Ini berarti bahwa tidak ada codeword yang merupakan awalan dari codeword lainnya. Misalnya, kode kata untuk "e" dalam contoh Anda adalah 10, dan Anda dapat melihat bahwa tidak ada kata kode lain dimulai dengan angka 10.

Ini berarti bahwa Anda dapat mendekode dengan rakus dengan membaca string yang disandikan dari kiri ke kanan dan menghasilkan karakter segera setelah Anda melihat kata sandi. Misalnya, 0, 00 dan 000 tidak membuat kode apa pun sehingga Anda terus membaca bit. Ketika Anda membaca 0000, yang mengkodekan "E" dan, karena kode bebas awalan, Anda tahu tidak ada 0000x codeword lain, jadi Anda sekarang dapat menampilkan "E" dan mulai membaca codeword berikutnya. Sekali lagi, 1 tidak mengkodekan apa pun kecuali 10 mengkodekan "e". Tidak ada codeword lain yang dimulai dengan "10", sehingga Anda dapat menampilkan "e". Dan seterusnya.

David Richerby
sumber
1
Kode awalan juga umumnya dikenal sebagai Kode Instan (lihat misalnya, Elemen Teori Informasi oleh Cover & Thomas). Saya pikir istilah kode Awalan muncul jauh lebih sering daripada kode awalan-bebas.
Batman
3
Perlu juga disebutkan bahwa untuk dapat memecahkan kode urutan kode Huffman, seseorang harus diberi batas codeword yang benar untuk memulainya. Jika seseorang mencoba men-decode urutan pada batas codeword yang salah, proses decoding akan menghasilkan urutan simbol output yang salah.
rwong
@ rwong: Jika kode Huffman mulai disinkronkan secara tidak benar, kode Huffman dapat terus menghasilkan simbol yang salah tanpa batas waktu, tetapi setiap kali kode tersebut secara salah menentukan panjang simbol, jumlah kemungkinan kondisi yang salah akan dikurangi.
supercat
@supercat Saya kira saya akan mengucapkannya dengan cara yang berbeda: Jika decoder Huffman pada awalnya ditetapkan pada batas codeword yang salah dan mulai diproses, ada kemungkinan (yang mungkin nol atau apa pun, dan mungkin tergantung pada kamus dan bit stream content) bahwa ia dapat mendarat pada batas codeword yang benar secara kebetulan dalam waktu yang terbatas, dan ketika itu terjadi akan menghasilkan hasil decoding yang benar untuk simbol-simbol berikutnya. Telah ada beberapa penelitian ke dalam properti (pada kamus kode kata, dan pada bit stream) yang akan menjamin sinkronisasi ulang ini.
rwong
@ rwong: Jika data asli acak dengan distribusi sedemikian rupa sehingga bit aliran masing-masing akan memiliki probabilitas independen menjadi satu atau nol, probabilitas untuk tetap tidak sinkron untuk lebih dari N simbol akan meluruh secara eksponensial dengan meningkatnya N. Data aktual lebih cenderung mengandung pola yang mungkin mencegah sinkronisasi ulang, tetapi dalam praktiknya tidak mungkin bahwa kesalahan pada awal file teks 100MB akan merusak semua teks 100MB.
supercat
13

Sangat membantu untuk membayangkannya sebagai pohon. Anda cukup melintasi pohon sampai Anda menekan simpul daun, dan kemudian memulai kembali dari root. Dari algoritma yang melakukan huffman coding, Anda dapat melihat bahwa struktur semacam ini dibuat dalam proses.

https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png

quietContest
sumber
6
Aspek penting di sini adalah bahwa semua kata kode yang valid adalah daun. Anda akan membutuhkan pemisah jika Anda memiliki simbol pada node batin juga.
MvG
3

Tidak ada kode selain E dimulai dengan 0000. Tidak ada kode selain saya mulai dengan 0001. Dan seterusnya. Sebagai kasus ekstrem, tidak ada kode selain e dimulai dengan 01. Anda tidak memiliki hal-hal seperti E = 0000, spasi = 000, di mana Anda tidak akan tahu apa yang harus dilakukan jika Anda menemukan tiga nol.

Lihatlah string Anda yang disandikan: 0000101100000 ...

Anda membaca nol pertama. Anda tahu kode itu salah satu dari E, i, y, l, k, koma, atau spasi. Nol berikutnya berarti bukan k, koma, atau spasi, tetapi E, i, y atau l. Nol berikutnya berarti E atau i. Nol berikutnya berarti E. Ketika Anda tahu kode mana, Anda tahu Anda telah menguraikan semua bit untuk kode itu.

Maka Anda memiliki 101100000 ... 1 berarti Anda memiliki e, r, s, n atau a. Bit selanjutnya adalah 0, jadi kodenya adalah e. Sekali lagi, Anda selesai dengan karakter itu.

gnasher729
sumber
-2

Kami tidak dapat menggunakan pemisah dalam pengkodean Huffman karena setiap biner setara huruf tidak cocok dengan kode awalan huruf apa pun, sehingga kami dapat melakukannya tanpa menggunakan pemisah.

Sandeep Das
sumber
3
Bukankah saya sudah mengatakan itu, hanya tanpa tingkat membingungkan banyak negasi bersarang. (Dan, omong-omong, bukan karena kita tidak bisa menggunakan pemisah; Hanya saja kita tidak perlu .)
David Richerby