BK
TP.HCM
2008
dce
Nén và mã hóa dữ liệu
Nén dữ liệu
Mã hóa dữ liệu
2008
dce Nén dữ liệu
Run-length encoding (packed decimal)
Là phương pháp rất đơn giản sử dụng cho dạng
dữ liệu mà trong đó chứa nhiều chuỗi dữ liệu
giống nhau
Sử dụng các chữ số để thể hiện số lần lặp của
chuỗi ký thự đó
Ví dụ:
chuỗi wwwwbbbbcccccdd có thể được biểu diễn như sau:
4w4b6c2d
2008
dce Nén dữ liệu
Differenial encoding (relative encoding)
Chỉ gửi phần thay đổi so với giá trị cũ
Original 1509 1506 1508 1510 1511 1509 1513
Encoded 1509 -3 +2 +2 +1 -2 +4
‘+’
STX ’1’ ’‘‘+’ ‘2’ ‘’‘+’ …‘’ETX BCC
End-of-value delimiters
+3
Flag +4 +5 +5 +4 +3 …Flag
All difference values binary-encoded
in a single (signed) byte
2008
dce Nén dữ liệu
Huffman encoding (Statistical Methods)
Đặc điểm
Đây là mã thống kê (phương pháp nén mã tối ưu)
Mã hóa dựa trên xác suất sử dụng của các ký tự
Những ký tự được dùng nhiều nhất sẽ có từ mã ngắn nhất
Không có tính prefix
Giải thuật
Sắp xếp các nguồn tin có xác suất giảm dần
Một cặp bit 0-1 được gán cho 2 nguồn tin có xác suất nhỏ nhất
2 nguồn tin này được kết hợp, tạo thành nguồn tin mới có xác suất
bằng tổng xác suất của 2 nguồn tin thành phần
Sắp xếp lại các nguồn tin theo thứ tự giảm dần của xác suất
Quá trình trên được lặp lại đến khi 2 nguồn tin cuối cùng được kết hợp
Từ mã cho mỗi nguồn tin được viết theo thứ tự từ gốc đến ngọn
2008
dce Nén dữ liệu
Huffman encoding (Statistical Methods)
Chiều dài từ mã trung bình Lavg = Σlix pi
li: chiều dài nguồn tin Xi
pi: xác suất xuất nguồn tin Xi