tính tối ưu của độ dài mã

Mục tiêu

Sau khi hoàn tất bài học này bạn có thể:

Hiểu định lý Shannon (1948),

Biết được các tiêu chuẩn đánh giá bảng mã tối ưu tuyệt đối và bảng mã tối ưu tương đối,

Điều kiện nhận biết một bảng mã tối ưu,

Hiểu Định lý Huffman,

Biết Phương pháp sinh mã Huffman,

Vận dụng phương pháp sinh mã Huffman để sinh mã Huffman cho một thông báo,

Vận dụng phương pháp sinh mã Huffman để viết chương trình nén.

Định lý Shannon (1948)

Phát biểu định lý:

Đặt là độ dài trung bình của bảng mã.

Khi đó

Dấu đẳng thức xảy ra khi và chỉ khi

Diễn giải: Đối với mã tách được độ dài trung bình của mã sẽ có cận dưới làH(x)/Log2(d). Nếu mã không tách được độ dài trung bình của nó có thể nhỏ hơn cận dưới. Nếu mã tách được không tối ưu thì độ dài của nó sẽ lớn hơn nhiều so với cận dưới, còn nếu mã tách được tối ưu thì độ dài trung bình của nó gần với cận dưới.

Bài toán đặt ra sẽ là tìm phương pháp xây dựng bảng mã tách được tối ưu.

Chú ý:

là entropy của X với cơ số D.

Bảng mã tối ưu tuyệt đối

Định lý: Bảng mã được gọi là tối ưu tuyệt đối khi

Ví dụ: xét biến ngẫu nhiên X={x₁, x₂, x₃, x₄}

Có phân phối: P={1/2, 1/4, 1/8, 1/8}

Có bảng mã W={w₁= 0, w₂=10, w₃=110, w₄=111}

Ta tính được độ dài trung bình từ mã:

Tính Entropy của X: H(X)= H(0.5, 0.25, 0.125, 0.125) = 0.5 +0.5 + 0.375 + 0.375 =1.75

Log₂D=1.

Bảng mã tối ưu tương đối

Định lý: Bảng mã được gọi là tối ưu tương đối khi:

Điều kiện nhận biết một bảng mã tối ưu

Định lý (với D=2):

• Xác suất p_i càng lớn thì độ dài n_i của từ mã w_i càng nhỏ.
• Giả sử p₁_> p₂ _> …₁_> p_M. Nếu p_i_> p_i+1 _> p_i+r thì n_i <_n_i+1 <_n_i+r thì 2 từ mã tương ứng với 2 giá trị có xác suất nhỏ nhất có độ dài mã bằng nhau n_M-1 =n_M.
• Trong các từ mã có độ dài bằng nhau và cùng bằng n_M (dài nhất) thì tồn tại ít nhất 2 từ mã w_M-1 và w_M có M-1 ký tự đầu giống nhau và ký tự thứ M khác nhau.

Ví dụ: xét bảng mã W={w₁=0, w₂=100, w₃=101, w₄=1101, w₅=1110}

Bảng mã trên không phải là bảng mã tối ưu vì 2 từ mã w₄, w₅ có độ dài lớn nhất =4 ký tự nhưng 3 ký tự đầu khác nhau.

Ghi chú: D > 2 được xét tương tự.

Định lý Huffman

Định lý: Giả sử X có phân phối xác suất với thứ tự giảm dần sau:

Giả sử bảng mã của X là W={w₁, w₂, …, w_M-1, w_M}.

Đặt x_M-1,M={x_M-1, x_M} có xác suất là p_M-1,M=p_M-1+p_M.

và X^* = { x_1, x₂,…, x_M-1,M} có phân phối sau:

Giả sử W* ={w₁, w₂, …, w_M-2, x*_M-1,M} là bảng mã tối ưu của X*. Khi đó:

- w_M-1=w*_M-1,M + “0”.

- w_M =w*_M-1,M + “1”.

Phương pháp sinh mã Huffman

Giả sử X có phân phối xác suất với thứ tự giảm dần sau:

Thủ tục lùi (D=2):

Khởi tạo: Đặt M₀=M

Bước 1:

- Đặt có xác suất

- Sắp xếp lại theo tứ tự giảm dần của xác suất ta nhận được dãy phân phối mới có M₀-1 phần tử như sau:

Bước 2: Lặp lại bước 1 với sự lưu vết

Giảm M₀: M₀=M₀-1, vòng lặp kết thúc khi M₀=2

(Chú ý: trong trường hợp tổng quát, vong lặp kết thúc khi M₀ <_ D.)

Thủ tục tiến:

Đi ngược lại so với thủ tục lùi đồng thời xác định từ mã ở mỗi bước từ sự lưu vết ở thủ tục lùi.

Minh họa phương pháp sinh mã Huffman

Ví dụ 1: sinh bảng mã nhị phân Huffman cho X có phân phối sau:

Thủ tục lùi: Độ dài trung bình của từ mã:

Vecto n=(0.3 x 2)+ (0.25 x 2)+ (0.2 x 2) + (0.1 x 3) +(0.1 x 4) + (0.05 x 4) = 2.4

Entropy của X: H(X) = H(0.3, 0.25; 0.2, 0.1,0.1, 0.05)

= 2.4

Nhận xét: Do D = 2 và log₂D=1, Ta có vecto n = H(X) nên bảng mã trên tối ưu tuyệt đối.

Bài tập

Cho biến ngẫu nhiên X có phân phối sau:

Cho biến ngẫu nhiên Y có phân phối sau:

Cho đoạn văn bản “thoi the thi thoi thi the thoi thi the”. Tìm bảng mã nhị phân Huffman dùng để mã hóa đoạn văn bản trên.

Thay từng ký tự trong đoạn văn bản trên thành một từ mã, cắt từng đoạn 8 bits đổi thành số thập phân. Cho biết dãy số thập phân kết quả.