Chương 3 : Nén văn bản và hình ảnh
1.Các nguyên tắc nén.
Các nguyên tắc nén :
- Source encoder and destination decoders.
- Nén mất mát thông tin và không mất mát thông tin.
- Mã hóa entropy
- Mã hóa dữ liệu nguồn.
1. Source encoder và destination decoders.
- Source endcoder : là nơi thông tin đầu vào được nén.
- Destination decoders : là nơi thông tin sau khi nén được giải nén
2. Nén mất mát thông tin và nén không mất mát thông tin.
Thuật toán nén có thể được chia thành 2 loại :
- Nén mất mát thông tin :dữ liệu trước khi nén và sau khi giải nén không giống nhau
hoàn toàn nhưng vẫn đảm bảo thông tin không bị ảnh hưởng đến chất lượng thông
tin . Ứng dụng trong nén âm thanh , hình ảnh.
- Nén không mất mát thông tin : dữ liệu trước khi nén và sau khi giải nén giống nhau
hoàn toàn.Ứng dụng trong nén văn bản.
3. Mã hóa entropy.
- Là loại nén không mất mát thông tin.
- Nguyên tắc nén : Trong văn bản gốc, tìm những đoạn kí tự giống nhau và thay thế
chúng bằng các codeword mới có độ dài ngắn hơn.
- 2 thuật toán điển hình là : Run-length-encoding(RLE) và statistical encoding.
a. Run-length-encoding.
- Nguyên tắc nén : Đầu tiên tìm trong thông tin nguồn một loạt các kí tự/bit nhị phân
giống nhau. Sau đó thay thế chuỗi các kí tự/bít đó bởi 1 codeword mới bao gồm 2
thông tin :chiều dài của chuỗi con và kí tự/bít lặp.
- Đặc điểm : độ dài của codeword cố định.
- Một ứng dụng điển hình sử dụng kĩ thuật này là việc truyền các chuỗi nhị phân sinh
ra từ bộ quyét của máy fax.
b. Statistical encoding.
- Statiscal encoding sử dụng 1 tập từ mã có độ dài thay đổi với từ mã ngắn được sử

a. Mã hóa vi sai.
- Mã hóa vi sai được sử dụng rộng rãi trong các ứng dụng khi biên độ của 1 giá trị/tín
hiệu nằm trong một phạm vi rộng nhưng sự sai khác trong biên độ giữa các giá
trị/tín hiệu kế tiếp là tương đối nhỏ.Vì vậy lượng thông tin để mã hóa tương đối đơn
giản.
- Trong thực tế mã hóa vi sai có thể là không mất mát thông tinh hoặc mất mát thông
tin và phụ thuộc vào số bit được sử dụng để mã hóa giá trị sai khác . Nếu số bit đã
sử dụng đủ để phục vụ cho giá trị sai khác lớn nhất thì đó là không mất dữ liệu.
Ngược lại, nếu giá trị khác biệt vượt quá số bit tối đa được sử dụng thì kết quả là
mất mát thông tin.
b. Mã hóa biến đổi.
- Nguyên tắc : biến đổi dữ liệu trước khi nén sang 1 dạng khác dễ nén hơn. Nó sử
dụng một phép biến đổi để chuyển từ miền không gian sang miền tần số. Nhìn
chung , là loại nén mất mát thông tin và được sử dụng trong một số ứng dụng liên
quan đến cả ảnh và video.
- Tần số không gian (spatial frequency) :
- DTC (discrete cosine transform) : là kĩ thuật dùng để chuyển đổi một ma trận 2
chiều của các giá trị điểm ảnh thành một ma trận tương đương của các thành phần
tần số không gian. Hành động chuyển đổi này là không mất dữ liệu.
2. Nén văn bản.
- Các thuật toán nén liên quan tới văn bản đề là nén không mất mát thông tin.
- Về cơ bản, có 2 phương pháp mã hoá thống kê được sử dụng với dạng văn bản :
 Nén từng kí tự trong văn bản. Ví dụ : 2 thuật toán là nén huffman và nén số
học(arithmetic coding).
 Nén từng từ trong văn bản. Ví dụ : thuật toán nén LZ và LZW.
- Có 2 loại mã hóa được sử dụng cho văn bản :
 Static coding : Dành cho các ứng dụng trong các văn bản biết được các đặc
điểm của kí tự và tần suất xuất hiện của chúng. Thay vì sử dụng các từ mã có
chiều dài cố định, ta sử dụng bộ từ mã tối ưu có chiều dài thay đổi. Từ mã
ngắn nhất sử dụng để biểu diễn cho các kí tự xuất hiện thường xuyên nhất.

liệu được truyền.Nhược điểm của phương pháp này là chi phí phải gửi các tập từ
mã mới (và kí tự tương ứng) bất cứ khi nào 1 loại dữ liệu mới được gửi và tốn băng
thông để truyền.
b. Dynamic Huffman coding(mã hóa huffman động)
- Với phương pháp này thì cả người gửi(nén) và người nhận(giải nén) cùng xây dựng
cây Huffman động cho các kí tự được truyền.
- Các bước thực hiện hành động nén :
 Bước 1 : Cả người gửi và người nhận bắt đầu xây dựng một cây bao gồm 1
nút và 1 nút lá rỗng(empty leaf node-e0-tần suất xuất hiện là 0 và nhánh
được chỉ định là 0).
 Bước 2 : Cập nhật từng kí tự vào trong cây theo quy tắc :
o Nếu kí tự đang xét chưa xuất hiện trong cây thì thêm mới một nút lávà
nút lá e0 ở trên cây bị chuyển xuống một nhánh mới, nút lá rỗng được chỉ
định là nhánh 0 và và kí tự là nhánh 1.