Huffman kodlamasında bu nasıl kullanılır?

Question

frekansları vardır ile sıkıştırma karakter için giriş,

A = 1 
B = 2 
C = 4 
D = 8 
E = 16 
F = 32 
G = 64 
H = 128 
I = 256 
J = 512 
K = 1024 
L = 2048 
M = 4096 
N = 8192 

Huffman kodlama algoritmasıdır,

Önce olanların toplamı olarak ebeveyni ile iki düşük frekansları karakterleri almak ve bir ağaç uygulamak zorunda iki karakter frekansı. 0'dan sol çocuğa ve 1'den sağ çocuğa. Son olarak her karakterin değerini ikili form olarak seçin, bu form kökünü başlatır ve sola veya sağa yerleştirilir, sonra soldaki 0'a yerleştirilirse, sonra doğruysa, 0 ekleyin.

Bir ağaç oluşturur, 8 seviyesinin üzerine çıkar. İkiliden sadece 8 bite bahsetmeliyiz. Fakat bu giriş için, bit 8. 'u kesiyor. Burada ne yapmamız gerekiyor?

Answer 1

Tüm 256 olası değeri kodlarsanız, bazıları 8 bitden fazla tarafından temsil edilir, doğru. Ancak, kodlanmış diziniz bir dizi ob bayt olarak yorumlanmaz, ancak bir bayttan fazla bayt içerebilen bir dizi bit olarak, Huffman ağacınızın dallarının sekizden daha derine inmesi iyi olur.

sen (diğerleri arasında) bu kodlamalar içeren bir Huffman ağacı olduğunu varsayalım: Eğer dize EEXEEEX kodlamak istediğinizde Şimdi

E   000    # 3 bits 
X   0100000001  # 10 bits 
NUL  001    #3 bits 

elde edersiniz:

E E X   E E E X   NUL  # original text 
000 000 0100000001 000 000 000 0100000001 001  # encoded bits 

Artık bu düzenleme

eeeEEExx xxxxxxxx EEEeeeEE Exxxxxxx xxxNNN  # orig 

00000001 00000001 00000000 00100000 00100100 # bits 
enc[0]  enc[1]  enc[2]  enc[3]  enc[4]  # bytes 

(alt blok: 8 bloklar halinde bit dizisi, bu bayt dört sadece kolay okuma içindir. Son iki sıfır biti doldurmadır.) Bayt dizisi enc artık kodlanmış dizenizdir. Sıkıştırma, sık kullanılan karakterlerin bir bayttan daha az meşgul olması gerçeğinden kaynaklanmaktadır. Örneğin, ilk iki Es tek bir bayta sığar. Buradaki X gibi seyrek olan kırılmalar, birkaç bayt bile kapsayabilen daha uzun bir kodlamaya sahiptir.

Huffman ağacınızı hareket ettirmek için geçerli bitin geçerli bitini elbette çıkarmalısınız. Bunun için bitly operatörleri gerekir.