Slide bài giảng môn Lý thuyết thông tin nội dung chương 3: Mã hóa nguồn - nén dữ liệu

lOMoARcPSD| 36067889 Notes Notes lOMoARcPSD| 36067889 M C ục ác tiêu c câu h ủ ỏ a bà i cần i h tr ọ ả c l ời Notes
Mã hóa là gì? Bộ mã là gì? Các thông số cơ bản của một bộ mã? 2/37
Thế nào là mã không suy biến? mã có khả năng giải mã duy nhất? mã có tính
Biên soạn: Phạm Văn Sự (PTIT) prefix?
C3: Mã hóa nguồn - Nén dữ liệu
Trang bị một số khái niệm cơ bản về mã hóa, mã hóa nguồn
Bài toán mã hóa tối ưu? Cách để xây dựng được bộ mã tối ưu? ver. 22a 3/37
Mã hóa tối ưu cho nguồn
Định lý mã hóa thứ nhất của Shannon?
Một số thuật toán mã hóa nguồn phổ biến
Mã hóa khối tin có ưu điểm gì so với mã hóa đơn lẻ từng tin?
Những điểm cơ bản nhất về các thuật toán mã hóa: Shannon, Shannon- Notes
Fano, Shannon-Fano-Elias, mã hóa số học, LZW?
Cách thức thực hiện mã hóa và giải mã cho các phương thức mã hóa :
Shannon, Shannon-Fano, Shannon-Fano-Elias, mã hóa số học, LZW? lOMoARcPSD| 36067889
C3: Mã hóa nguồn - Nén dữ liệu Nội dung chính Notes
Tổng quan về mã hóa nguồn - Nén dữ liệu ver. 22a 4/37
Các định nghĩa và khái niệm cơ bản mã hóa Tổng quan
Nguyên tắc mã hóa tối ưu về mã hóa
Một số phương pháp mã hóa nguồn phổ biến nguồn Mã Shannon Mục tiêu và phân loại Mã Shannon-Fano Mục tiêu của Mã Huffman mã hóa nguồn
Thuật toán mã hóa Shannon-Fano-Elias
Thuật toán mã hóa số học - Arithmetic Coding Thuật toán mã hóa Lempel-Ziv Kết thúc
Thực hiện tìm kiếm các phương thức biểu diễn dữ liệu nhỏ gọn nhất có thể
Nguyên lý của mã hóa nguồn
Loại bỏ các thông tin dư thừa hoặc các thông tin dư thừa và các thông tin không cần thiết.
Theo quan điểm bảo toàn thông tin: Theo phương pháp:
▶ Nén không tổn hao (lossless data
▶ RLE (run length encoding) compression) ▶ Mã hóa thống kê
▶ Nén có tổn hao (lossy data ▶ Mã hóa từ điển compression) ▶ Mã hóa chuyển đổi
Theo đặc tính thay đổi: Theo mô hình n-user:
▶ Mã thích nghi (adaptive) ▶ Tập trung ▶ Mã không thích nghi ▶ Phân tán (nonadaptive)
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a 5/37 lOMoARcPSD| 36067889 Notes Notes lOMoARcPSD| 36067889
C3: Mã hóa nguồn - Nén dữ liệu Nội dung chính Notes
Tổng quan về mã hóa nguồn - Nén dữ liệu 6/37
Các định nghĩa và khái niệm cơ bản mã hóa
Nguyên tắc mã hóa tối ưu
Một số phương pháp mã hóa nguồn phổ biến Mã Shannon Mã Shannon-Fano Mã Huffman
Thuật toán mã hóa Shannon-Fano-Elias
Thuật toán mã hóa số học - Arithmetic Coding Thuật toán mã hóa Lempel-Ziv Kết thúc lOMoARcPSD| 36067889 Notes
{ m , m ,. ., m }
Mã hóa là một phép ánh xạ −
lên tập các từ mã là tổ m 7→ m −
là độ dài từ mã thứ số dấu mã tạo thành từ mã m m nào đó Notes lOMoARcPSD| 36067889
Các định nghĩa và khái niệm cơ bản mã hóa
Các thông số cơ bản của bộ mã Notes
Độ dài từ mã: lk là độ dài từ mã thứ k; lk = const ∀k gọi là mã đều, ngược lại gọi là mã không đều. 8/37
Độ dài trung bình: là trung bình thống kê của độ dài các từ mã: Các định lk nghĩa và
Cơ số mã: số các dấu (chữ mã) khác nhau được sử dụng trong bộ mã. khái niệm
Bộ mã mà tất cả các tổ hợp dấu mã là từ mã của tập tin tương ứng gọi là bộ cơ bản mã
mã đầy, ngược lại gọi là mã không đầy (mã vơi). hóa
Tính hiệu quả của phép mã hóa:
1. Bộ mã hiệu quả khi η → Khái niệm các bộ mã 1. (1)
Độ chậm giải mã: là số dấu (chữ mã) nhận được cần thiết trước khi có Định nghĩa
thể thực hiện được việc giải mã. (Mã không suy
Phương sai độ dài trung bình của bộ mã biến (không dị thường))
Một bộ mã được gọi là không suy biến (non-singular) nếu mọi tin xk của nguồn X ánh
xạ thành các từ mã khác nhau của bộ mã. xk ̸= xl ⇒ mklk ̸= mlll
Đảm bảo cho việc mô tả không bị nhập nhằng giữa các tin sau khi mã hóa
Định nghĩa (Từ mã mở rộng)
Một từ mã mở rộng là việc ánh xạ một chuỗi hữu hạn các tin thành các từ mã liên tiếp nhau. x1x2 ··· 7−→ m l l 1 1 m2 2 ...
Định nghĩa (Bộ mã có khả năng giải mã một cách duy nhất)
Một bộ mã được gọi là bộ mã có khả năng giải mã được một cách duy nhất nếu từ
mã mở rộng của nó là một từ mã không suy biến.
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a 9/37
Các định nghĩa và khái niệm cơ bản mã hóa Notes lOMoARcPSD| 36067889 Notes
Khái niệm các bộ mã (2)
Định nghĩa (Bộ mã có tính prefix)
Một bộ mã được gọi là bộ mã có tính prefix hay còn gọi mã có khả năng giải mã tức
thời nếu không có bất cứ từ mã nào là phần tiền tố (prefix) của một từ mã khác trong bộ mã.
Một bộ mã prefix là bộ mã có khả năng tự phân tách được.
Định lý (Bất đẳng thức Kraft)
Với bất cứ bộ mã prefix nào trên tập dấu (chữ mã) M có kích thước (cơ số) q thì tập
độ dài các từ mã có thể l1, l2,. ., lN phải thỏa mãn bất đẳng thức: N X q−lk ≤ 1 k=1
Ngược lại, với một tập các độ dài từ mã cho trước thỏa mãn bất đẳng thức này thì
tồn tại một bộ mã prefix nhận tập độ dài này làm độ dài các từ mã. 10/37 lOMoARcPSD| 36067889 Notes Notes lOMoARcPSD| 36067889
C3: Mã hóa nguồn - Nén dữ liệu Nội dung chính Notes
Tổng quan về mã hóa nguồn - Nén dữ liệu 12/37
Các định nghĩa và khái niệm cơ bản mã hóa
Nguyên tắc mã hóa tối ưu
Một số phương pháp mã hóa nguồn phổ biến Mã Shannon Mã Shannon-Fano Mã Huffman
Thuật toán mã hóa Shannon-Fano-Elias
Thuật toán mã hóa số học - Arithmetic Coding Thuật toán mã hóa Lempel-Ziv Kết thúc lOMoARcPSD| 36067889 Notes lOMoARcPSD| 36067889 Notes
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a lOMoARcPSD| 36067889 Notes
Độ dài trung bình bộ mã biểu diễn một nguồn có hàm mật độ phân bố với ⌈ ⌉ thỏa mãn || ≤ < || →
|| trong độ dài từ mã trung bình mô tả nguồn. Notes
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a lOMoARcPSD| 36067889 C3: M 3: ã hó M a nguồn ồ - n - Né n Né dữ li ệu ệ u Nộ N i ộ d i un d g un chí c nh hí Notes Tổ T ng quan về ề mã m hóa nguồn - - Nén é dữ liệ li u ệ 18/37 Các địn ị h nghĩa và v khái niệm ệ c m ơ bản mã hóa a
Biên soạn: Phạm Văn Sự (PTIT) Nguyên ê tắc mã hóa tối ưu i ưu
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a 19/37 Một số t s phương pháp mã hóa n a guồn phổ biế bi n ế n Mã Shannon n Mã Shannon-Fan - o Mã Huff f m f an m Th T uật toán mã hóa Shannon o -Fan - o-E - lias Th
T uật toán mã hóa số học - - Arithme m tic Co e ding Th T uật toán mã hóa Lemp Lem el e -Zi - v Kế K t ế thúc
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a lOMoARcPSD| 36067889 Notes
cho trước, mã Shannon có độ dài từ mã xác định bởi ⌈ ⌉ ∀ ∈
Chọn các từ mã có độ dài thích hợp theo thứ tự và tránh việc chọn các từ Notes
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a lOMoARcPSD| 36067889 Notes
C3: Mã hóa nguồn - Nén dữ liệu Nội dung chính
Tổng quan về mã hóa nguồn - Nén dữ liệu
Các định nghĩa và khái niệm cơ bản mã hóa
Nguyên tắc mã hóa tối ưu
Một số phương pháp mã hóa nguồn phổ biến Mã Shannon Mã Shannon-Fano Mã Huffman
Thuật toán mã hóa Shannon-Fano-Elias
Thuật toán mã hóa số học - Arithmetic Coding Thuật toán mã hóa Lempel-Ziv Kết thúc
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a 21/37
Một số phương pháp mã hóa nguồn phổ biến Notes Mã Shannon-Fano
Thuật toán đơn giản xây dựng bộ mã có tính prefix.
Thuật toán tạo bộ mã không đều khá hiệu quả (tính toán đơn giản).
Thuộc lớp thuật toán cận tối ưu (suboptimal).
▶ Không luôn luôn tạo ra bộ mã tối ưu. Ít phổ biến.
Biên soạn: Phạm Văn Sự (PTIT) C3: Mã hóa nguồn - Nén dữ liệu ver. 22a Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 Notes Thuật toán Shannon-Fano 1
Sắp xếp các tin theo thứ tự xác suất (tần suất) từ cao đến thấp từ phía trái sang phía phải. 2
Chia dãy đó thành hai phần sao cho các phần có tổng xác suất xấp xỉ bằng nhau. 3
Gán nhãn cho phần nửa trái một bít 0, và nhóm bên phải bít 1. 4
Lặp lại các bước 3 và 4 cho mỗi nửa bằng cách chia nhóm nhỏ và gán nhãn bít cho
đến tận khi các nhóm chỉ còn một nút tương ứng với lá của cây mã. 5 Từ mã
thu được bằng cách duyệt từ gốc đến các nút lá tương ứng. 22/37
C3: Mã hóa nguồn - Nén dữ liệu Nội dung chính
Tổng quan về mã hóa nguồn - Nén dữ liệu
Các định nghĩa và khái niệm cơ bản mã hóa
Nguyên tắc mã hóa tối ưu
Một số phương pháp mã hóa nguồn phổ biến Mã Shannon Mã Shannon-Fano Mã Huffman
Thuật toán mã hóa Shannon-Fano-Elias
Thuật toán mã hóa số học - Arithmetic Coding Thuật toán mã hóa Lempel-Ziv Kết thúc
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a 23/37
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a lOMoARcPSD| 36067889 Notes
Một số phương pháp mã hóa nguồn phổ biến
Notes Mã Huffman: Tổng quan
Thuộc lớp mã hóa Entropy, mã hóa nén dữ liệu không tổn hao (lossless data compression)
Là lớp mã với độ dài từ mã thay đổi (variable-length code) Bộ
mã thu được là bộ mã có tính prefix.
Yêu cầu phân bố của nguồn phải biết trước.
Thuộc dạng thuật toán "Greedy".
Là thuật toán mã hóa tối ưu. Định lý
Mã hóa Huffman là mã hóa tối ưu. Nói cách khác, gọi l¯H là độ dài trung bình từ mã
của bộ mã Huffman cho nguồn rời rạc X, l¯là độ dài trung bình từ mã của bộ mã tạo
được bởi một phương pháp nào đó, khi đó chúng ta có: l¯H ≤ l¯ 24/37
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a lOMoARcPSD| 36067889 Mộ M t số s p hươn ươ g ph g p áp á mã hóa n a guồn ồ ph p ổ ổ bi ến ế n
C3: Mã hóa nguồn - Nén dữ liệu Mã M H ã uff uf m f an: B an ài : Nh t ậ oán n m xét ã hóa Nội dung chính Notes
Phép mã hóa tối ưu Huffman: tập các từ mã cho bộ mã tối ưu là không duy nhất. Nói cá Tổn ch k g qu hác, an v có ề t m h ã ể h có óa n n hi guề ồu h n - ơn N m én ộ d t t ữ ậ li p ệ cá
u c độ dài cho cùng độ dài trung bình:
Biên soạn: Phạm Văn Sự (PTIT) ▶ Việc g Các đị án nh n n hãn gh "0" và "1" l ĩa và khái n à t iệ ù my ý. c ơ bản mã hóa
C3: Mã hóa nguồn - Nén dữ liệu
▶ Việc sắp xếp các phân bố xác suất hợp (cây thay thế) có thể thực hiện: xếp "trội" nhất, ver. 22a 25/37
Nguyên tắc mã hóa tối ưu Nhập vào: X = hoặc{x x k ế } p vớ "c i cá hì c xá m" nh c
ất suất phân bố p(xk) tương ứng. Việc x M ế ộ p t s x ố ác phsuất ươn ph g p ân h b áp ố "tr mã ộ h i" ó n a nhấ gut s ồ ẽ n ch ph o ổ b bi ộ ế m
n ã có phương sai độ dài từ mã nhỏ nhất (g Mã ần Sh b an ộ n m on X
ã đều nhất) Mã Huffman thỏa mãn mã tố i ưu: In r M a: Các ột s t ố Mã ừ Shannon-Fano N pm ếu hã nh p ươ ị p (x n hân g p m lk há tươn p g ứng v mã hó ớ a i t n in x Notes k gu k ồn phổ biến
k) > p(xl) thì lk < ll.
Biên soạn: Phạm Văn Sự (PTIT) Mã Huffman: T Mã hu Hu ậftf to m án an m ã hóa
C3: Mã hóa nguồn - Nén dữ liệu
Hai từ mã có độ dài nhất có cùng độ dài.
Thuật toán mã hóa Shannon-Fano-Elias ver. 22a 27/37 TH h ai uậtừ t m to ã án có đ mã ộ h d ó ài a s n ố hấ ọt ch c - ỉ khác Arithm n e hau m tic Co ộ d t in b g ít T ở h u v ậ ị
t trí cuối cùng, và hai từ mã n Kh ày tởi đ to ộ ươn án n g g d ứn mã an g v hó h ớ a sách i hai Lem câ tin pel y - n (ký Zi h v ị h ip ệ h u ân có ) có m xá ộ c s t u n ấ ú t t ch xuấ ứ t a hi các ện t tr hấọpng s nh ố ấ t.là xác suất phân Mã b H ố uf tươn fman g ứ cũ n n g c g t ủ h a ỏ các a m tin ãn x gi k ớ , s i hắ ạp n xế l¯ p k t ≤ h H eo (X) thứ
+ 1 tự tăng dần từ trái sang phải. Kết thúc M Th ột ự sc h ố iệ pn l h ặp cá ươ c b n ướ g p c s háau p đến khi t mã hó hu a đ n ược m guồ ộ n t n p ú h t d ổ uy bi nếhấ n t. Notes
Mã Huffman: Bài toán giải mã, Thuật toán giải mã
Biên soạn: Phạm Văn Sự (PTIT) 1
Tìm hai cây T′ và T′′ trong danh sách các nút gốc có trọng lượng tối thiểu p′ và p′′.
Thay thế chúng bằng một cây có nút gốc có trọng bằng p′ + p′′ và các cây con là T′ và
C3: Mã hóa nguồn - Nén dữ liệu T′′. ver. 22a 29/37 2
Đánh nhãn 0 và 1 trên các nhánh từ gốc mới đến các cây T′ và T′′. 3
Sắp xếp các nút theo thứ tự tăng dần của trọng xác suất.
Nhập vào: Chuỗi bít thông tin In r Du a yệt t : Dãy t ừ in g t ốc cu ươn ố g i cù
ứng ng đến nút lá với các bít là các nhãn ta được từ mã tương ứ ng v Khớ ởi cá i đ c t ộn in g, .
đặt con trỏ P chỉ đến gốc (root) của cây mã hóa Huffman. Gán con trỏ bít b rỗng.
Lặp các bước sau đến khi kết thúc chuỗi bít thông tin 1
Gán b bằng bít tiếp theo của chuỗi. Nếu b = 0 dịch con trỏ P theo nhánh có nhãn 0, 26/37
nếu ngược lại, dịch con trỏ P theo nhánh có nhãn 1. 2
Nếu P đã chỉ đến nút lá thì ghi ra tin tương ứng với từ mã. Khởi động lại con trỏ chỉ đến gốc 28/37
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a lOMoARcPSD| 36067889
C3: Mã hóa nguồn - Nén dữ liệu Nội dung chính Notes
Tổng quan về mã hóa nguồn - Nén dữ liệu
Một số phương pháp mã hóa nguồn phổ biến Notes
Các định nghĩa và khái niệm cơ bản mã hóa Mã hóa Shannon-Fano-Elias Biên soạn: Phạm Văn Sự (PTIT) C3: Mã hóa Nguy S ê ử n tdắụng h c mã àm m hóa t ậ ố t độ
i ưu phân bố tích lũy để thực hiện mã nguồn - Nén dữ liệu hóa.
Một số phương pháp mã hóa nguồn phổ biến ver. 22a 31/37
Định nghĩa hàm mật độ phân bố tích lũy cải tiến: Mã Shannon Mã Shannon-Fano F¯(x) = X< p Mã Huffman Một số phương pháp a mã hó x a nguồn phổ biến k
Thuật toán mã hóa Shannon-Fano-Elias Notes Mã hóa T s h ố u h ậ
ọc t toán mã hóa số học - Arithmetic Coding Thuật
▶ F¯(a) ≠ F¯(b) nếu a ≠ b. toán mã hóa Lempel-Ziv
▶ → có thể sử dụng F¯(x) như là một mã cho xk. Kết thúc CTắt huF¯(x) cò ộc lớp n l mã hóa không đều.
k bít, ký hiệu là ⌊F¯⌋lk .
Thuộc lớp mã hóa Entropy. Nếu l k 1 thì:
Thuộc lớp mã hóa không tổn hao. 1
Được sử dụng rộng rãi trong thực tế và trong các trình tiện ích nén dữ liệu 2l k thương mại. ▶ → Thlk ựbít l c hià đ ện ủ v đ i ể ệ c c ó th mã ể h mô óa t mả ộ xk t nhóm dữ liệu. 30/37
Là một mở rộng trực tiếp của phương pháp mã hóa Shannon-Fano-Elias.
Ý tưởng quan trọng là tính toán và sử dụng hàm phân bố xác suất của X n 32/37
Biên soạn: Phạm Văn Sự (PTIT)
C3: Mã hóa nguồn - Nén dữ liệu ver. 22a lOMoARcPSD| 36067889
C3: Mã hóa nguồn - Nén dữ liệu Nội dung chính Notes
Tổng quan về mã hóa nguồn - Nén dữ liệu
Biên soạn: Phạm Văn Sự (PTIT)
Các định nghĩa và khái niệm cơ bản mã hóa
C3: Mã hóa nguồn - Nén dữ
Nguyên tắc mã hóa tối ưu liệu ver. 22a 33/37
Một số phương pháp mã hóa nguồn phổ biến Mã Shannon Mã Shannon-Fano Notes Mã Huffman
Thuật toán mã hóa Shannon-Fano-Elias
Thuật toán mã hóa số học - Arithmetic Coding Thuật toán mã hóa Lempel-Ziv Kết thúc lOMoARcPSD| 36067889
Một số phương pháp mã hóa nguồn phổ biến
Thuật toán mã Lempel-Ziv-Welch: Tổng quan Notes
Thuộc lớp mã hóa không tổn hao.
Thuộc lớp mã hóa thuật toán từ điển. ver. 22a 34/37
Không yêu cầu phải biết trước phân bố của nguồn, thuật toán thích nghi.
Ứng dụng rộng rãi trong thực tế, là cơ sở của nhiều trình tiện ích nén dữ liệu thương mại. Mã hóa Huffman Mã hóa LZ
Yêu cầu biết phân bố của nguồn
Không cần biết phân bố của nguồn
Bảng mã được chọn trước
Bảng mã được tạo trong quá trình
Phương thức mã độ dài cố định-thay đổi
Phương thức độ dài thay đổi-cố định
Bảng: So sánh giữa mã hóa Huffman và mã hóa LZ. © GIT lOMoARcPSD| 36067889 Notes X ... n rất lớn X , X ′
Cập nhật bảng mã với từ mã mới được tạo thành từ ,
Tổng quan về mã hóa nguồn - Nén dữ liệu
Nguyên tắc mã hóa tối ưu lOMoARcPSD| 36067889 Notes