Mã Hóa Huffman

Kỹ thuật nén dữ liệu

Trong khoa học máy tính và lý thuyết thông tin , mã Huffman là một loại mã tiền tố tối ưu cụ thể thường được sử dụng để nén dữ liệu không mất dữ liệu . Quá trình tìm hoặc sử dụng mã như vậy là mã hóa Huffman , một thuật toán do David A. Huffman phát triển khi ông còn là sinh viên khoa học tại MIT và được công bố trong bài báo năm 1952 "Một phương pháp xây dựng mã dự phòng tối thiểu". [1]

Đầu ra từ thuật toán Huffman có thể được xem như một bảng mã có độ dài thay đổi để mã hóa một ký hiệu nguồn (chẳng hạn như một ký tự trong tệp). Thuật toán lấy bảng này từ xác suất hoặc tần suất xuất hiện ước tính ( trọng số ) cho mỗi giá trị có thể có của ký hiệu nguồn. Giống như trong các phương pháp mã hóa entropy khác , các ký hiệu phổ biến hơn thường được biểu diễn bằng ít bit hơn các ký hiệu ít phổ biến hơn. Phương pháp Huffman có thể được triển khai hiệu quả, tìm một mã theo thời gian tuyến tính với số trọng số đầu vào nếu các trọng số này được sắp xếp. [2] Tuy nhiên, mặc dù tối ưu trong số các phương pháp mã hóa ký hiệu riêng biệt, mã hóa Huffman không phải lúc nào cũng tối ưu trong số tất cả các phương pháp nén - nó được thay thế bằng mã hóa số học [3] hoặc hệ thống số bất đối xứng [4] nếu cần tỷ lệ nén tốt hơn.

Lịch sử

Năm 1951, David A. Huffman và các bạn cùng lớp lý thuyết thông tin tại MIT được lựa chọn giữa bài tiểu luận hoặc bài kiểm tra cuối kỳ . Giáo sư Robert M. Fano đã giao bài tiểu luận về vấn đề tìm mã nhị phân hiệu quả nhất. Huffman, không thể chứng minh bất kỳ mã nào là hiệu quả nhất, đã định bỏ cuộc và bắt đầu học cho bài kiểm tra cuối kỳ khi anh nảy ra ý tưởng sử dụng cây nhị phân được sắp xếp theo tần suất và nhanh chóng chứng minh phương pháp này là hiệu quả nhất. [5]

Khi làm như vậy, Huffman đã vượt qua Fano, người đã làm việc với Claude Shannon để phát triển một mã tương tự. Việc xây dựng cây từ dưới lên đảm bảo tính tối ưu, không giống như cách tiếp cận từ trên xuống của mã hóa Shannon–Fano .

Thuật ngữ

Mã hóa Huffman sử dụng một phương pháp cụ thể để chọn biểu diễn cho mỗi ký hiệu, tạo ra một mã tiền tố (đôi khi được gọi là "mã không tiền tố", nghĩa là chuỗi bit biểu diễn một ký hiệu cụ thể không bao giờ là tiền tố của chuỗi bit biểu diễn bất kỳ ký hiệu nào khác). Mã hóa Huffman là một phương pháp phổ biến để tạo mã tiền tố đến mức thuật ngữ "mã Huffman" được sử dụng rộng rãi như một từ đồng nghĩa với "mã tiền tố" ngay cả khi mã như vậy không được tạo ra bởi thuật toán Huffman.

Định nghĩa vấn đề

Mô tả không chính thức

Được cho Một tập hợp các ký hiệu và trọng số của chúng (thường tỷ lệ thuận với xác suất). Tìm thấy Mã nhị phân không có tiền tố (một tập hợp các từ mã) với độ dài từ mã dự kiến ​​tối thiểu (tương đương với một cây có độ dài đường dẫn có trọng số tối thiểu từ gốc).

Mô tả chính thức

Đầu vào . Alphabet , là bảng chữ cái ký hiệu có kích thước . Tuple , là bộ các trọng số ký hiệu (dương) (thường tỷ lệ thuận với xác suất), tức là . Đầu ra . Code , là bộ các từ mã (nhị phân), trong đó là từ mã cho . Mục tiêu . Cho là độ dài đường dẫn có trọng số của code . Điều kiện: đối với bất kỳ code nào . MỘT = ( Một 1 , Một 2 , … , Một N ) {\displaystyle A=(a_{1},a_{2},\dots ,a_{n})} N {\displaystyle n} T = ( chúng tôi 1 , chúng tôi 2 , … , chúng tôi N ) {\displaystyle W=(w_{1},w_{2},\dots ,w_{n})} chúng tôi Tôi = cân nặng ⁡ ( Một Tôi ) , Tôi ∈ { 1 , 2 , … , N } {\displaystyle w_{i}=\operatorname {trọng số} \left(a_{i}\right),\,i\in \{1,2,\dots ,n\}} C ( T ) = ( c 1 , c 2 , … , c N ) {\displaystyle C\left(W\right)=(c_{1},c_{2},\dots ,c_{n})} c Tôi {\displaystyle c_{i}} Một Tôi , Tôi ∈ { 1 , 2 , … , N } {\displaystyle a_{i},\,i\trong \{1,2,\dots ,n\}} L ( C ( T ) ) = ∑ Tôi = 1 N chúng tôi Tôi chiều dài ⁡ ( c Tôi ) {\textstyle L(C(W))=\sum _{i=1}^{n}w_{i}\operatorname {length} (c_{i})} C {\displaystyle C} L ( C ( W ) ) ≤ L ( T ( W ) ) {\displaystyle L(C(W))\leq L(T(W))} T ( W ) {\displaystyle T(W)}

Ví dụ

Chúng tôi đưa ra một ví dụ về kết quả của mã hóa Huffman cho một mã có năm ký tự và trọng số đã cho. Chúng tôi sẽ không xác minh rằng nó giảm thiểu L trên tất cả các mã, nhưng chúng tôi sẽ tính toán L và so sánh nó với entropy Shannon H của tập trọng số đã cho; kết quả gần như là tối ưu.

Đầu vào ( A , W )	Biểu tượng ( a i )	Một	b	c	ngày	và	Tổng
	Trọng lượng ( w i )	0,10	0,15	0,30	0,16	0,29	= 1
Đầu ra C	Từ mã ( c i )	010	011	11	00	10
	Độ dài từ mã (tính bằng bit) ( ℓ i )	3	3	2	2	2
	Đóng góp vào chiều dài đường dẫn có trọng số ( ℓ i w i )	0,30	0,45	0,60	0,32	0,58	L ( C ) = 2,25
Tối ưu	Ngân sách xác suất ( 2 − ℓ i )	1/8	1/8	1/4	1/4	1/4	= 1,00
	Nội dung thông tin (tính bằng bit) ( −log 2 w i ) ≈	3.32	2,74	1,74	2,64	1,79
	Đóng góp vào entropy ( − w i log 2 w i )	0,332	0,411	0,521	0,423	0,518	H ( A ) = 2,205

Đối với bất kỳ mã nào là biunique , nghĩa là mã có thể giải mã duy nhất , tổng các ngân sách xác suất trên tất cả các ký hiệu luôn nhỏ hơn hoặc bằng một. Trong ví dụ này, tổng này hoàn toàn bằng một; do đó, mã được gọi là mã hoàn chỉnh . Nếu không phải như vậy, người ta luôn có thể suy ra một mã tương đương bằng cách thêm các ký hiệu bổ sung (có liên quan đến xác suất null), để làm cho mã hoàn chỉnh trong khi vẫn giữ được tính biunique .

Theo định nghĩa của Shannon (1948) , nội dung thông tin h (tính bằng bit) của mỗi ký hiệu a i với xác suất không null là

h ( a i ) = log 2 ⁡ 1 w i . {\displaystyle h(a_{i})=\log _{2}{1 \over w_{i}}.}

Entropy H (tính bằng bit) là tổng có trọng số, trên tất cả các ký hiệu a i với xác suất khác không w i , của nội dung thông tin của mỗi ký hiệu:

H ( A ) = ∑ w i > 0 w i h ( a i ) = ∑ w i > 0 w i log 2 ⁡ 1 w i = − ∑ w i > 0 w i log 2 ⁡ w i . {\displaystyle H(A)=\sum _{w_{i}>0}w_{i}h(a_{i})=\sum _{w_{i}>0}w_{i}\log _{2}{1 \over w_{i}}=-\sum _{w_{i}>0}w_{i}\log _{2}w_{i}.}

(Lưu ý: Một ký hiệu có xác suất bằng 0 thì không đóng góp gì vào entropy, vì . Vì vậy, để đơn giản, các ký hiệu có xác suất bằng 0 có thể bị loại khỏi công thức trên.) lim w → 0 + w log 2 ⁡ w = 0 {\displaystyle \lim _{w\to 0^{+}}w\log _{2}w=0}

Theo định lý mã hóa nguồn của Shannon , entropy là thước đo độ dài từ mã nhỏ nhất về mặt lý thuyết có thể có đối với bảng chữ cái đã cho với các trọng số liên quan. Trong ví dụ này, độ dài từ mã trung bình có trọng số là 2,25 bit cho mỗi ký hiệu, chỉ lớn hơn một chút so với entropy được tính toán là 2,205 bit cho mỗi ký hiệu. Vì vậy, mã này không chỉ tối ưu theo nghĩa là không có mã khả thi nào khác hoạt động tốt hơn mà còn rất gần với giới hạn lý thuyết do Shannon thiết lập.

Nhìn chung, mã Huffman không nhất thiết phải là duy nhất. Do đó, tập hợp các mã Huffman cho một phân phối xác suất nhất định là một tập hợp con không rỗng của các mã tối thiểu hóa cho phân phối xác suất đó. (Tuy nhiên, đối với mỗi phép gán độ dài từ mã tối thiểu hóa, tồn tại ít nhất một mã Huffman có các độ dài đó.) L ( C ) {\displaystyle L(C)}

Kỹ thuật cơ bản

Nén

Kỹ thuật này hoạt động bằng cách tạo ra một cây nhị phân của các nút. Chúng có thể được lưu trữ trong một mảng thông thường , kích thước của mảng này phụ thuộc vào số lượng ký hiệu, . Một nút có thể là một nút lá hoặc một nút bên trong . Ban đầu, tất cả các nút đều là các nút lá, chứa chính ký hiệu , trọng số (tần suất xuất hiện) của ký hiệu và tùy chọn, một liên kết đến một nút cha giúp dễ đọc mã (ngược lại) bắt đầu từ một nút lá. Các nút bên trong chứa một trọng số , liên kết đến hai nút con và một liên kết tùy chọn đến một nút cha . Theo quy ước chung, bit '0' biểu thị theo sau nút con bên trái và bit '1' biểu thị theo sau nút con bên phải. Một cây hoàn chỉnh có tối đa các nút lá và các nút bên trong. Một cây Huffman loại bỏ các ký hiệu không sử dụng sẽ tạo ra độ dài mã tối ưu nhất. n {\displaystyle n} n {\displaystyle n} n − 1 {\displaystyle n-1}

Quá trình bắt đầu với các nút lá chứa xác suất của ký hiệu mà chúng biểu diễn. Sau đó, quá trình lấy hai nút có xác suất nhỏ nhất và tạo một nút nội bộ mới có hai nút này làm nút con. Trọng số của nút mới được đặt thành tổng trọng số của các nút con. Sau đó, chúng ta áp dụng lại quá trình này, trên nút nội bộ mới và trên các nút còn lại (tức là chúng ta loại trừ hai nút lá), chúng ta lặp lại quá trình này cho đến khi chỉ còn lại một nút, đó là gốc của cây Huffman.

Thuật toán xây dựng đơn giản nhất sử dụng hàng đợi ưu tiên trong đó nút có xác suất thấp nhất được ưu tiên cao nhất:

1. Tạo một nút lá cho mỗi ký hiệu và thêm nó vào hàng đợi ưu tiên.
2. Trong khi có nhiều hơn một nút trong hàng đợi:
   1. Xóa hai nút có mức độ ưu tiên cao nhất (xác suất thấp nhất) khỏi hàng đợi
   2. Tạo một nút nội bộ mới với hai nút này là nút con và có xác suất bằng tổng xác suất của hai nút đó.
   3. Thêm nút mới vào hàng đợi.
3. Nút còn lại là nút gốc và cây đã hoàn chỉnh.

Vì các cấu trúc dữ liệu hàng đợi ưu tiên hiệu quả yêu cầu thời gian O(log n ) cho mỗi lần chèn và một cây có n lá có 2 n −1 nút, nên thuật toán này hoạt động trong thời gian O( n log n ), trong đó n là số ký hiệu.

Nếu các ký hiệu được sắp xếp theo xác suất, có một phương pháp thời gian tuyến tính (O( n )) để tạo cây Huffman bằng hai hàng đợi , hàng đợi đầu tiên chứa các trọng số ban đầu (cùng với các con trỏ đến các lá liên quan) và các trọng số kết hợp (cùng với các con trỏ đến các cây) được đặt ở phía sau của hàng đợi thứ hai. Điều này đảm bảo rằng trọng số thấp nhất luôn được giữ ở phía trước của một trong hai hàng đợi:

1. Bắt đầu với số lượng lá bằng với số biểu tượng có trong đó.
2. Xếp hàng tất cả các nút lá vào hàng đợi đầu tiên (theo xác suất tăng dần sao cho phần tử ít có khả năng xuất hiện nhất sẽ ở đầu hàng đợi).
3. Trong khi có nhiều hơn một nút trong hàng đợi:
   1. Xóa hai nút có trọng số thấp nhất khỏi hàng đợi bằng cách kiểm tra mặt trước của cả hai hàng đợi.
   2. Tạo một nút nội bộ mới, trong đó hai nút vừa bị xóa là nút con (mỗi nút có thể là nút con) và tổng trọng số của chúng là trọng số mới.
   3. Đưa nút mới vào cuối hàng đợi thứ hai.
4. Nút còn lại là nút gốc; cây hiện đã được tạo.

Sau khi cây Huffman được tạo ra, nó sẽ được duyệt để tạo ra một từ điển ánh xạ các ký hiệu thành mã nhị phân như sau:

1. Bắt đầu với nút hiện tại được đặt ở gốc.
2. Nếu nút không phải là nút lá, hãy gắn nhãn cạnh đến nút con bên trái là 0 và cạnh đến nút con bên phải là 1. Lặp lại quy trình ở cả nút con bên trái và nút con bên phải.

Mã hóa cuối cùng của bất kỳ ký hiệu nào sau đó được đọc bằng cách nối các nhãn trên các cạnh dọc theo đường dẫn từ nút gốc đến ký hiệu.

Trong nhiều trường hợp, độ phức tạp về thời gian không quá quan trọng khi lựa chọn thuật toán ở đây, vì n ở đây là số ký hiệu trong bảng chữ cái, thường là một số rất nhỏ (so với độ dài của thông điệp cần mã hóa); trong khi phân tích độ phức tạp liên quan đến hành vi khi n tăng lên rất lớn.

Nhìn chung, việc giảm thiểu phương sai của độ dài từ mã là có lợi. Ví dụ, bộ đệm giao tiếp nhận dữ liệu được mã hóa Huffman có thể cần lớn hơn để xử lý các ký hiệu đặc biệt dài nếu cây đặc biệt không cân bằng. Để giảm thiểu phương sai, chỉ cần phá vỡ mối quan hệ giữa các hàng đợi bằng cách chọn mục trong hàng đợi đầu tiên. Sửa đổi này sẽ giữ nguyên tính tối ưu về mặt toán học của mã hóa Huffman trong khi vừa giảm thiểu phương sai vừa giảm thiểu độ dài của mã ký tự dài nhất.

Giải nén

Nói chung, quá trình giải nén chỉ đơn giản là vấn đề dịch luồng mã tiền tố thành các giá trị byte riêng lẻ, thường là bằng cách duyệt từng nút cây Huffman khi đọc từng bit từ luồng đầu vào (việc đạt đến một nút lá nhất thiết sẽ kết thúc quá trình tìm kiếm giá trị byte cụ thể đó). Tuy nhiên, trước khi điều này có thể diễn ra, cây Huffman phải được tái tạo bằng cách nào đó. Trong trường hợp đơn giản nhất, khi tần suất ký tự khá dễ đoán, cây có thể được xây dựng trước (và thậm chí điều chỉnh thống kê trên mỗi chu kỳ nén) và do đó được sử dụng lại mỗi lần, với cái giá phải trả là ít nhất một số biện pháp hiệu quả nén. Nếu không, thông tin để tái tạo cây phải được gửi trước. Một cách tiếp cận ngây thơ có thể là thêm số lần đếm tần suất của từng ký tự vào luồng nén. Thật không may, chi phí trong trường hợp như vậy có thể lên tới vài kilobyte, do đó phương pháp này ít có ứng dụng thực tế. Nếu dữ liệu được nén bằng mã hóa chuẩn , mô hình nén có thể được tái tạo chính xác chỉ bằng các bit thông tin (trong đó B là số bit trên mỗi ký hiệu). Một phương pháp khác là chỉ cần thêm từng bit một cây Huffman vào luồng đầu ra. Ví dụ, giả sử giá trị 0 biểu thị một nút cha và 1 biểu thị một nút lá, bất cứ khi nào gặp nút lá, quy trình xây dựng cây chỉ cần đọc 8 bit tiếp theo để xác định giá trị ký tự của nút lá cụ thể đó. Quá trình tiếp tục đệ quy cho đến khi đạt đến nút lá cuối cùng; tại thời điểm đó, cây Huffman sẽ được tái tạo một cách trung thực. Chi phí sử dụng phương pháp như vậy dao động từ khoảng 2 đến 320 byte (giả sử bảng chữ cái 8 bit). Nhiều kỹ thuật khác cũng khả thi. Trong mọi trường hợp, vì dữ liệu nén có thể bao gồm "bit theo sau" chưa sử dụng nên trình giải nén phải có khả năng xác định thời điểm dừng tạo đầu ra. Điều này có thể thực hiện được bằng cách truyền độ dài của dữ liệu đã giải nén cùng với mô hình nén hoặc bằng cách xác định ký hiệu mã đặc biệt để biểu thị kết thúc đầu vào (tuy nhiên, phương pháp sau có thể ảnh hưởng xấu đến tính tối ưu của độ dài mã). B ⋅ 2 B {\displaystyle B\cdot 2^{B}}

Tính chất chính

Xác suất được sử dụng có thể là xác suất chung cho miền ứng dụng dựa trên kinh nghiệm trung bình hoặc có thể là tần suất thực tế tìm thấy trong văn bản đang được nén. Điều này yêu cầu phải lưu trữ bảng tần suất cùng với văn bản đã nén. Xem phần Giải nén ở trên để biết thêm thông tin về các kỹ thuật khác nhau được sử dụng cho mục đích này.

Tối ưu

Thuật toán gốc của Huffman là tối ưu cho mã hóa từng ký hiệu với phân phối xác suất đầu vào đã biết, tức là mã hóa riêng các ký hiệu không liên quan trong luồng dữ liệu như vậy. Tuy nhiên, nó không tối ưu khi hạn chế từng ký hiệu bị loại bỏ hoặc khi các hàm khối lượng xác suất không xác định. Ngoài ra, nếu các ký hiệu không độc lập và phân phối giống hệt nhau , thì một mã duy nhất có thể không đủ để đạt được tính tối ưu. Các phương pháp khác như mã hóa số học thường có khả năng nén tốt hơn.

Mặc dù cả hai phương pháp đã đề cập ở trên đều có thể kết hợp một số lượng ký hiệu tùy ý để mã hóa hiệu quả hơn và thường thích ứng với số liệu thống kê đầu vào thực tế, mã hóa số học thực hiện như vậy mà không làm tăng đáng kể độ phức tạp về mặt tính toán hoặc thuật toán (mặc dù phiên bản đơn giản nhất chậm hơn và phức tạp hơn mã hóa Huffman). Tính linh hoạt như vậy đặc biệt hữu ích khi xác suất đầu vào không được biết chính xác hoặc thay đổi đáng kể trong luồng. Tuy nhiên, mã hóa Huffman thường nhanh hơn và mã hóa số học trước đây là chủ đề gây lo ngại về các vấn đề bằng sáng chế . Do đó, nhiều công nghệ trước đây đã tránh mã hóa số học để ủng hộ Huffman và các kỹ thuật mã hóa tiền tố khác. Tính đến giữa năm 2010, các kỹ thuật được sử dụng phổ biến nhất cho giải pháp thay thế này cho mã hóa Huffman đã chuyển sang phạm vi công cộng vì các bằng sáng chế ban đầu đã hết hạn.

Đối với một tập hợp các ký hiệu có phân phối xác suất đồng đều và số phần tử là lũy thừa của hai , mã hóa Huffman tương đương với mã hóa khối nhị phân đơn giản , ví dụ, mã hóa ASCII . Điều này phản ánh thực tế là không thể nén với đầu vào như vậy, bất kể phương pháp nén nào, tức là không làm gì với dữ liệu là điều tối ưu cần làm.

Mã hóa Huffman là tối ưu trong số tất cả các phương pháp trong mọi trường hợp mà mỗi ký hiệu đầu vào là một biến ngẫu nhiên độc lập và phân phối giống hệt nhau đã biết có xác suất là dyadic . Mã tiền tố, và do đó là mã hóa Huffman nói riêng, có xu hướng kém hiệu quả trên các chữ cái nhỏ, trong đó xác suất thường nằm giữa các điểm tối ưu (dyadic) này. Trường hợp xấu nhất đối với mã hóa Huffman có thể xảy ra khi xác suất của ký hiệu có khả năng xảy ra nhất vượt xa 2 −1 = 0,5, khiến giới hạn trên của sự kém hiệu quả trở nên vô hạn.

Có hai cách tiếp cận liên quan để giải quyết tình trạng kém hiệu quả này trong khi vẫn sử dụng mã hóa Huffman. Việc kết hợp một số lượng ký hiệu cố định với nhau ("chặn") thường làm tăng (và không bao giờ làm giảm) khả năng nén. Khi kích thước của khối tiến tới vô cực, về mặt lý thuyết, mã hóa Huffman sẽ tiến tới giới hạn entropy, tức là nén tối ưu. [6] Tuy nhiên, việc chặn các nhóm ký hiệu lớn tùy ý là không thực tế, vì độ phức tạp của mã Huffman là tuyến tính theo số khả năng được mã hóa, một con số theo cấp số nhân theo kích thước của một khối. Điều này giới hạn lượng chặn được thực hiện trong thực tế.

Một giải pháp thay thế thực tế, được sử dụng rộng rãi, là mã hóa độ dài chạy . Kỹ thuật này bổ sung một bước trước mã hóa entropy, cụ thể là đếm (chạy) các ký hiệu lặp lại, sau đó được mã hóa. Đối với trường hợp đơn giản của quá trình Bernoulli , mã hóa Golomb là tối ưu trong số các mã tiền tố để mã hóa độ dài chạy, một thực tế được chứng minh thông qua các kỹ thuật mã hóa Huffman. [7] Một cách tiếp cận tương tự được thực hiện bởi máy fax sử dụng mã hóa Huffman đã sửa đổi . Tuy nhiên, mã hóa độ dài chạy không thích ứng với nhiều loại đầu vào như các công nghệ nén khác.

Biến thể

Có nhiều biến thể của mã hóa Huffman, [8] một số trong đó sử dụng thuật toán giống Huffman, và một số khác tìm mã tiền tố tối ưu (trong khi, ví dụ, đặt các hạn chế khác nhau cho đầu ra). Lưu ý rằng, trong trường hợp sau, phương pháp không cần phải giống Huffman, và thực tế, thậm chí không cần phải là thời gian đa thức .

N-ary mã hóa Huffman

Thuật toán Huffman n -ary sử dụng bảng chữ cái {0, 1,..., n − 1} để mã hóa thông điệp và xây dựng một cây n -ary. Cách tiếp cận này đã được Huffman xem xét trong bài báo gốc của ông. Thuật toán tương tự được áp dụng cho mã nhị phân ( ), ngoại trừ việc n ký hiệu có xác suất nhỏ nhất được lấy cùng nhau, thay vì chỉ 2 ký hiệu có xác suất nhỏ nhất. Lưu ý rằng đối với n lớn hơn 2, không phải tất cả các tập hợp từ nguồn đều có thể tạo thành một cây n -ary cho mã hóa Huffman. Trong những trường hợp này, phải thêm các ký tự giữ chỗ có xác suất 0 bổ sung. Điều này là do cây phải tạo thành một nhà thầu n đến 1; [ cần làm rõ ] đối với mã hóa nhị phân, đây là một nhà thầu 2 đến 1 và bất kỳ tập hợp có kích thước nào cũng có thể tạo thành một nhà thầu như vậy. Nếu số lượng từ nguồn đồng dư với 1 modulo n  − 1, thì tập hợp các từ nguồn sẽ tạo thành một cây Huffman thích hợp. n = 2 {\displaystyle n=2}

Mã hóa Huffman thích ứng

Một biến thể gọi là mã hóa Huffman thích ứng liên quan đến việc tính toán xác suất động dựa trên tần suất thực tế gần đây trong chuỗi ký hiệu nguồn và thay đổi cấu trúc cây mã hóa để phù hợp với ước tính xác suất được cập nhật. Nó hiếm khi được sử dụng trong thực tế, vì chi phí cập nhật cây làm cho nó chậm hơn mã hóa số học thích ứng được tối ưu hóa , linh hoạt hơn và có khả năng nén tốt hơn.

Thuật toán mẫu Huffman

Thông thường, các trọng số được sử dụng trong các triển khai mã hóa Huffman biểu diễn các xác suất số, nhưng thuật toán nêu trên không yêu cầu điều này; nó chỉ yêu cầu các trọng số tạo thành một monoid giao hoán được sắp xếp hoàn toàn , nghĩa là một cách để sắp xếp các trọng số và cộng chúng lại. Thuật toán mẫu Huffman cho phép người ta sử dụng bất kỳ loại trọng số nào (chi phí, tần suất, cặp trọng số, trọng số không phải số) và một trong nhiều phương pháp kết hợp (không chỉ là phép cộng). Các thuật toán như vậy có thể giải quyết các vấn đề tối thiểu hóa khác, chẳng hạn như tối thiểu hóa , một vấn đề đầu tiên được áp dụng cho thiết kế mạch. max i [ w i + l e n g t h ( c i ) ] {\displaystyle \max _{i}\left[w_{i}+\mathrm {length} \left(c_{i}\right)\right]}

Mã hóa Huffman giới hạn độ dài/Mã hóa Huffman phương sai tối thiểu

Mã hóa Huffman giới hạn độ dài là một biến thể trong đó mục tiêu vẫn là đạt được độ dài đường dẫn có trọng số tối thiểu, nhưng có một hạn chế bổ sung là độ dài của mỗi từ mã phải nhỏ hơn một hằng số nhất định. Thuật toán hợp nhất gói giải quyết vấn đề này bằng một cách tiếp cận tham lam đơn giản rất giống với cách tiếp cận được sử dụng bởi thuật toán Huffman. Độ phức tạp thời gian của nó là , trong đó là độ dài tối đa của một từ mã. Không có thuật toán nào được biết đến có thể giải quyết vấn đề này trong thời gian hoặc , không giống như các vấn đề Huffman thông thường được sắp xếp trước và không được sắp xếp. O ( n L ) {\displaystyle O(nL)} L {\displaystyle L} O ( n ) {\displaystyle O(n)} O ( n log ⁡ n ) {\displaystyle O(n\log n)}

Mã hóa Huffman với chi phí chữ cái không bằng nhau

Trong bài toán mã hóa Huffman chuẩn, người ta cho rằng mỗi ký hiệu trong tập hợp mà các từ mã được xây dựng có chi phí truyền tải bằng nhau: một từ mã có độ dài là N chữ số sẽ luôn có chi phí là N , bất kể có bao nhiêu chữ số trong số đó là số 0, bao nhiêu chữ số là số 1, v.v. Khi làm việc theo giả định này, việc giảm thiểu tổng chi phí của tin nhắn và giảm thiểu tổng số chữ số là như nhau.

Mã hóa Huffman với chi phí chữ cái không bằng nhau là khái quát hóa không có giả định này: các chữ cái của bảng chữ cái mã hóa có thể có độ dài không đồng đều, do đặc điểm của phương tiện truyền dẫn. Một ví dụ là bảng chữ cái mã hóa của mã Morse , trong đó một 'dấu gạch ngang' mất nhiều thời gian hơn để gửi so với một 'dấu chấm' và do đó chi phí của một dấu gạch ngang trong thời gian truyền cao hơn. Mục tiêu vẫn là giảm thiểu độ dài từ mã trung bình có trọng số, nhưng không còn đủ để chỉ giảm thiểu số ký hiệu được sử dụng bởi thông điệp. Không có thuật toán nào được biết đến có thể giải quyết vấn đề này theo cùng một cách hoặc với cùng hiệu quả như mã hóa Huffman thông thường, mặc dù nó đã được Richard M. Karp [9] giải quyết, giải pháp của ông đã được Mordecai J. Golin tinh chỉnh cho trường hợp chi phí số nguyên. [10]

Cây nhị phân chữ cái tối ưu (mã hóa Hu–Tucker)

Trong bài toán mã hóa Huffman chuẩn, người ta cho rằng bất kỳ từ mã nào cũng có thể tương ứng với bất kỳ ký hiệu đầu vào nào. Trong phiên bản chữ cái, thứ tự chữ cái của đầu vào và đầu ra phải giống hệt nhau. Do đó, ví dụ, không thể gán mã , mà thay vào đó phải gán một trong hai hoặc . Điều này cũng được gọi là bài toán Hu–Tucker , theo tên TC Hu và Alan Tucker , tác giả của bài báo trình bày giải pháp lần đầu tiên cho bài toán chữ cái nhị phân tối ưu này, [11] có một số điểm tương đồng với thuật toán Huffman, nhưng không phải là biến thể của thuật toán này. Một phương pháp sau này, thuật toán Garsia–Wachs của Adriano Garsia và Michelle L. Wachs (1977), sử dụng logic đơn giản hơn để thực hiện các phép so sánh giống nhau trong cùng một giới hạn thời gian tổng thể. Các cây nhị phân chữ cái tối ưu này thường được sử dụng làm cây tìm kiếm nhị phân . [12] A = { a , b , c } {\displaystyle A=\left\{a,b,c\right\}} H ( A , C ) = { 00 , 1 , 01 } {\displaystyle H\left(A,C\right)=\left\{00,1,01\right\}} H ( A , C ) = { 00 , 01 , 1 } {\displaystyle H\left(A,C\right)=\left\{00,01,1\right\}} H ( A , C ) = { 0 , 10 , 11 } {\displaystyle H\left(A,C\right)=\left\{0,10,11\right\}} O ( n log ⁡ n ) {\displaystyle O(n\log n)}

Mã Huffman chuẩn mực

Nếu các trọng số tương ứng với các đầu vào được sắp xếp theo thứ tự chữ cái theo thứ tự số, mã Huffman có cùng độ dài với mã chữ cái tối ưu, có thể được tìm thấy bằng cách tính toán các độ dài này, khiến mã hóa Hu–Tucker trở nên không cần thiết. Mã thu được từ đầu vào được sắp xếp (lại) theo thứ tự số đôi khi được gọi là mã Huffman chuẩn và thường là mã được sử dụng trong thực tế, do dễ mã hóa/giải mã. Kỹ thuật tìm mã này đôi khi được gọi là mã hóa Huffman–Shannon–Fano , vì nó tối ưu giống như mã hóa Huffman, nhưng có xác suất trọng số theo chữ cái, giống như mã hóa Shannon–Fano . Mã Huffman–Shannon–Fano tương ứng với ví dụ là , có cùng độ dài từ mã như giải pháp ban đầu, cũng là tối ưu. Nhưng trong mã Huffman chuẩn , kết quả là . { 000 , 001 , 01 , 10 , 11 } {\displaystyle \{000,001,01,10,11\}} { 110 , 111 , 00 , 01 , 10 } {\displaystyle \{110,111,00,01,10\}}

Ứng dụng

Mã hóa số học và mã hóa Huffman tạo ra các kết quả tương đương — đạt được entropy — khi mọi ký hiệu có xác suất ở dạng 1/2 k . Trong những trường hợp khác, mã hóa số học có thể cung cấp khả năng nén tốt hơn mã hóa Huffman vì — theo trực giác — "từ mã" của nó có thể có độ dài bit không phải số nguyên, trong khi các từ mã trong mã tiền tố như mã Huffman chỉ có thể có số bit là số nguyên. Do đó, một từ mã có độ dài k chỉ khớp tối ưu với một ký hiệu có xác suất 1/2 k và các xác suất khác không được biểu diễn một cách tối ưu; trong khi độ dài từ mã trong mã hóa số học có thể được thực hiện để khớp chính xác với xác suất thực của ký hiệu. Sự khác biệt này đặc biệt nổi bật đối với các kích thước chữ cái nhỏ. [ cần trích dẫn ]

Tuy nhiên, mã tiền tố vẫn được sử dụng rộng rãi vì tính đơn giản, tốc độ cao và không có phạm vi bảo hộ bằng sáng chế . Chúng thường được sử dụng như một "phần phụ trợ" cho các phương pháp nén khác. Deflate ( thuật toán của PKZIP ) và các codec đa phương tiện như JPEG và MP3 có mô hình phần đầu và lượng tử hóa tiếp theo là sử dụng mã tiền tố; chúng thường được gọi là "mã Huffman" mặc dù hầu hết các ứng dụng sử dụng mã có độ dài thay đổi được xác định trước thay vì mã được thiết kế bằng thuật toán Huffman.

Tài liệu tham khảo

Wikimedia Commons có thêm phương tiện truyền tải về Mã hóa Huffman .

1. ^ Huffman, D. (1952). "Một phương pháp xây dựng mã dự phòng tối thiểu" (PDF) . Biên bản của IRE . 40 (9): 1098–1101. doi :10.1109/JRPROC.1952.273898.
2. ^ Van Leeuwen, Jan (1976). "Về việc xây dựng cây Huffman" (PDF) . ICALP : 382–410 . Truy cập ngày 20 tháng 2 năm 2014 .
3. ^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (2014-04-09). Cơ sở của Đa phương tiện. Springer Science & Business Media. ISBN 978-3-319-05290-8.
4. ^ J. Duda, K. Tahboub, NJ Gadil, EJ Delp, Việc sử dụng hệ thống số bất đối xứng để thay thế chính xác cho mã hóa Huffman, Hội thảo về mã hóa hình ảnh, 2015.
5. ^ Huffman, Ken (1991). "Hồ sơ: David A. Huffman: Mã hóa "Sự gọn gàng" của số 1 và số 0". Scientific American : 54–58.
6. ^ Gribov, Alexander (10-04-2017). "Nén tối ưu một đường đa giác với các đoạn và cung tròn". arXiv : 1604.07476 [cs.CG].
7. ^ Gallager, RG; van Voorhis, DC (1975). "Mã nguồn tối ưu cho bảng chữ cái số nguyên phân bố hình học". IEEE Transactions on Information Theory . 21 (2): 228–230. doi :10.1109/TIT.1975.1055357.
8. ^ Abrahams, J. (1997-06-11). "Mã hóa và phân tích cú pháp cây cho mã hóa nguồn không mất dữ liệu". Được viết tại Arlington, VA, Hoa Kỳ. Biên bản báo cáo. Nén và độ phức tạp của SEQUENCES 1997 (Mã số danh mục 97TB100171) . Phân ban Toán học, Khoa học máy tính và thông tin, Văn phòng nghiên cứu hải quân (ONR). Salerno: IEEE . trang 145–171. CiteSeerX 10.1.1.589.4726 . doi :10.1109/SEQUEN.1997.666911. ISBN  0-8186-8132-2Mã số S2CID  124587565.
9. ^ Karp, Richard M. (31-01-1961). "Mã hóa dự phòng tối thiểu cho kênh không nhiễu rời rạc" . Giao dịch IRE về Lý thuyết thông tin . 7 (1). IEEE: 27–38. doi :10.1109/TIT.1961.1057615 – qua IEEE.
10. ^ Golin, Mordekai J. (tháng 1 năm 1998). "A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes with Unequal Letter Costs" (PDF) . IEEE Transactions on Information Theory . 44 (5) (xuất bản ngày 1998-09-01): 1770–1781. doi :10.1109/18.705558. S2CID  2265146 . Truy cập ngày 10 tháng 9 năm 2024 .
11. ^ Hu, TC ; Tucker, AC (1971). "Cây tìm kiếm máy tính tối ưu và mã chữ cái có độ dài thay đổi". Tạp chí SIAM về Toán ứng dụng . 21 (4): 514. doi :10.1137/0121057. JSTOR  2099603.
12. ^ Knuth, Donald E. (1998), "Thuật toán G (thuật toán Garsia–Wachs cho cây nhị phân tối ưu)", Nghệ thuật lập trình máy tính, Tập 3: Sắp xếp và tìm kiếm (ấn bản lần 2), Addison–Wesley, trang 451–453. Xem thêm Lịch sử và tài liệu tham khảo, trang 453–454.

Tài liệu tham khảo

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , và Clifford Stein . Giới thiệu về thuật toán , Phiên bản thứ hai. MIT Press và McGraw-Hill, 2001. ISBN 0-262-03293-7 . Mục 16.3, trang 385–392. 

Liên kết ngoài

• Mã hóa Huffman bằng nhiều ngôn ngữ khác nhau trên Rosetta Code
• Mã Huffman (triển khai python)
• Mã Huffman chuẩn (triển khai C)
• Hình ảnh trực quan về mã hóa Huffman