Nén dữ liệu kiểu huffman tĩnh.

Question

Em có 1 câu hỏi như thế này.

Đối với nén dữ liệu theo kiểu huffman tĩnh thì không gian lưu trũ của nó có bị thay đổi không.

VD: 1 chuỗi gồm 2 triệu ký tự A, 1

triệu ký tự B, và 1 triệu ký tự C. Hãy cho biết việc nén chuỗi đã giúp tiết kiệm được không gian
lưu trữ như thế nào trong các trường hợp:

a. Các cụm ký tự AB, AC xen kẽ nhau (ABAC..ABAC…ABAC)

b. Toàn bộ ký tự A xuất hiện liên tục rồi đến toàn bộ ký tự B rồi đến toàn bộ ký tự C.
(AA…A..ABB…B..BBCC..C..C)

Em muốn hỏi ở 2 câu a và b kết quả có giống nhau không. Nếu được xin giải thích giúp em vì sao.

Em xin cảm ơn!

 

Answer 1

2 câu a và b cho ra kết quả không giống nhau, nhưng độ dài đều ngang nhau. Nén Huffman chỉ quan tâm đến tần suất xuất hiện của mỗi kí tự trong chuỗi input, và không bị ảnh hưởng bởi thứ tự các kí tự.

Ví dụ như mã của mỗi kí tự sau khi chạy Huffman với 2 input abcabca và aaabbcc (cả 2 đều có tuần suất kí tự như nhau) đều cho ra như sau:
a: 0
b: 10
c: 11
Output của abcabca sẽ là: 01011010110 (11 bit)
Output của aaabbcc sẽ là: 00010101111 (cũng 11 bit!)