Đề tài Kỹ thuật nén số liệu bằng phương pháp Huffman

mã hoá Huffman đạt hiệu suất nén cao nhất khi phân bố tần suất xuất hiện của các ký hiệu cần phát khá rộng và các xâu ký hiệu khá dài. Ngược lại, nó không thích hợp cho việc truyền số liệu nhị phân trong máy tính bởi vì các byte nói chung xuất hiện với tần suất gần như nhau trong các file mã nhị phân. Các từ mã tương ứng mỗi ký hiệu được xác định dựa vào cấu trúc cây mã. Trong phương pháp mã hoá Huffman, ta xây dựng cây nhị phân không cân bằng (gồm một số nhánh không bằng nhau). Mức độ không cân bằng của cây là do tần suất xuất hiện tương đối của các ký hiệu quyết định gọi là cây mã Huffman. Ví dụ 6: Mã hoá cho chuỗi ký hiệu “ABBBAAAACDC”. Đối với mã ASSCII sẽ dùng 8 bit để biểu diễn mỗi ký hiệu. Giả sử, theo phương pháp mã hoá Huffman ta xây dựng được cây mã (phương pháp xây dựng cây mã sẽ xét trong phần sau) như sau: 0 A 0 0 1 1 1 C D B Ta có bảng sau: Ký hiệu Số đếm Mã Huffman A 5 0 B 3 10 C 2 110 D 1 111 Như vậy thay vì phải lưu trữ theo mã ASCII với số bit là: 10x8 = 80 bit, ta chỉ cần lưu trữ với số bit bằng: S (số đếm x số bit) = 5x1+ 3x2+2x3+1x3 = 20 bit Rõ ràng, để có được các từ mã tương ứng với từng ký hiệu ta phải dựa vào cây Huffman. Tuỳ thuộc vào mô hình thống kê tĩnh hay động mà cây mã sẽ được xây dựng một lần hay nhiều lần trong quá trình mã hoá hoặc giải mã. Trong đó, mỗi ký hiệu tương ứng với một nút lá. Điều này cho thấy mã Huffman có tính tiền tố (prefix), tính chất tiền tố đảm bảo nó là mã có tính phân tách duy nhất để giải mã tức thì (immediately decodable). Nghĩa là: không có dãy bit nào trong biểu diễn của một ký hiệu là tiền tố của một dãy bit dài hơn biểu diễn một ký hiệu khác. Do đó, khi nhận một dãy bit là mã số cho một ký hiệu, nó có thể được giải mã ngay lập tức, không cần phải xem dãy này có phải là một dãy con của một dãy khác dài hơn biểu diễn một ký hiệu khác. Bên cạnh đó, theo mục II.7.2 ở chương 2 ta thấy mã Huffman là mã có chiều dài trung bình ngắn hơn mã Fano-Shannon. Phương pháp mã hoá Huffman dựa vào phương pháp mã hoá có độ dài từ mã thay đổi bằng cách dùng các mã ngắn hơn cho những ký hiệu xuất hiện thường xuyên hơn và ngược lại. Ví dụ : trong văn bản thì ký hiệu A xuất hiện thường xuyên hơn ký hiệu B, nên chiều dài của mã dành cho ký hiệu A sẽ ngắn hơn chiều dài mã dành cho ký hiệu B. Mục đích là làm cực tiểu chiều dài chờ đợi ( expected length ) của mã cho một ký hiệu. Chiều dài chờ đợi của mã được xác định bằng: Trong đó: - w1, w2, w3, ..., wn các trọng lượng (weight) cho những ký hiệu ; wi là trọng lượng của ký hiệu Ci và là một độ đo nào đó (chẳng hạn như xác suất hay tần số tương đối) để chỉ ra ký hiệu này xuất hiện thường xuyên như thế nào trong các bảng thông báo cần được mã hoá. - l1, l2, ..., ln là chiều dài của các mã cho các ký hiệu C1 , C2 , ..., Cn theo thứ tự đó Ví dụ 7: Ta xét 5 ký hiệu A, B, C, D và E, và giả sử rằng chúng xuất hiện theo các trọng lượng sau đây ( xác suất ) và giả sử những ký hiệu trên được mã hoá như sau: Ký hiệu Số lần xuất hiện Mã A B C D E 0.2 0.1 0.1 0.15 0.45 10 1111 1110 110 0 Vậy chiều dài chờ đợi của mã cho một trong 5 ký hiệu này là: 0.2 x 2 + 0.1 x 4 + 0.1 x 4 + 80.15 x 3 + 0.45 x 1 = 2.1 Từ đó, ta thấy chiều dài chờ đợi càng nhỏ thì hiệu suất nén càng cao vì với cùng một xác suất xuất hiện là w1...wi của ký hiệu tương ứng C1... Ci nếu chiều dài chờ đợi càng nhỏ chứng tỏ l1..li nhỏ, như vậy độ dài từ mã sẽ ngắn. Phương pháp xây dựng cây mã Huffman tĩnh Thuật toán xây dựng cây mã Huffman tĩnh như sau: Bước 1: Xác định hai nút “ tự do ” có trọng lượng nhỏ nhất. Bước 2: Nút cha của hai nút này được tạo ra với trọng lượng là tổng trọng lượng của hai nút con. Bước 3: Nút cha này được thêm vào danh sách các nút. Đánh dấu nút cha là “ tự do”, hai nút con đánh dấu là “ đã xét “. Bước 4: một trong hai nhánh từ nút cha đến nút con được đánh dấu là “0” và nhánh còn lại được đánh dấu là “1”. Bước 5: lặp lại bước 1 cho đến khi chỉ còn một nút tự do. Nút này chính là nút gốc của cây.) Ví dụ 8: Để minh hoạ thuật toán Huffman, ta hãy xét các ký hiệu A, B, C, D và E và giả sử trọng lượng tính được cuả các ký hiệu đã tính được. Theo cơ sở phương pháp xây dựng cây mã, ta bắt đầu bằng cách lập một danh sách các nút (nút lá) cho mỗi ký hiệu : E C D A B 0.35 0.3 0.2 0.1 0.05 Trường hợp 1: Bước 1: Hai nút đầu tiên được chọn là A và B, vì chúng có trọng lượng nhỏ nhất, và kết hợp tạo ra một nút có trọng lượng 0.1 + 0.05 = 0.15, nút vừa được tạo thành là nút cha của 2 nút A, B: E C D A B 0.15 0.35 0.3 0.2 0.1 0.05 1 0 Nút tự do Nút đã xét Bước 2: Hai A,B đã được đánh dấu và loại ra, trong danh sách 4 nút ta chọn như ở bước 1, nút tiếp theo có trọng lượng 0.2 + 0.15 = 0.35 : E C D A B 0.15 0.35 0.3 0.2 0.1 0.05 0.35 1 1 0 0 Bước 3: Lặp lai như bước 1, nút tiếp theo được tạo ra có trọng lượng: 0.35 + 0.3 = 0.65: E C D A B 0.15 0.35 0.3 0.2 0.1 0.05 0.35 1 1 0 0 0.65 1 0 E C D A B 0.15 0.35 0.3 0.2 0.1 0.05 0.35 1 1 0 0 0.65 1 0 1.0 1 0 Bước 4: Cây nhận được cuối cùng : Từ đây ta nhận được các mã Huffman như sau : Ký hiệu Mã Huffman E C D A B 0 10 110 1110 1111 Trường hợp 2: E C D A B 0.15 0 1 0.35 0.3 0.2 0.1 0.05 Trong quá trình tìm kiếm, sự lựa chọn nút có trọng lượng cực tiểu là ngẫu nhiên nên ta có thể chọn cách khác cho những ký hiệu trên: Bước tiếp theo là: E C D A B 0.35 0 1 0.15 0 1 0.35 0.3 0.2 0.1 0.05 Ở cách chọn trước, ta đã chọn nút vừa được tạo ra có trọng lượng 0.35, và nút C từ danh sách, nhưng cũng có thể chọn 2 nút E,C vì nút E cũng có trọng lượng là 0,35 : E C D A B 0.35 0 1 0.15 0 1 0.35 0.3 0.2 0.1 0.05 0.65 0 1 E C D A B 0.35 0 1 0.15 0 1 0.35 0.3 0.2 0.1 0.05 0.65 0 1 1.0 0 1 Và cây Huffman cuối cùng là : Các mã tương ứng với cây này là : Ký hiệu Mã Huffman E C D A B 00 01 10 110 111 Phương pháp giải mã Huffman theo mô hình thống kê tĩnh Nhờ tính chất tiền tố của mã Huffman, các ký hiệu được giải mã bằng cách xuất phát từ nút gốc và lần lượt đi theo các nhánh tương ứng với bit nhận được cho đến khi đến được một nút lá. Lúc đó mã ASCII của ký hiệu tương ứng của nút lá sẽ được ghi vào bộ đệm của bên thu. Ví dụ 9 : Giải mã theo phương pháp mã hóa trên: để minh họa giả sử rằng ta nhận được luồng bit : 0 1 00 1 0 1 0 1 1 1 Từ cây mã Huffman đã được xây dựng ở trường hợp 1, bắt đầu từ gốc của cây này ta đi theo mũi tên được đánh dấu 0 đến ký hiệu E và ta trở lại gốc : 0 1 0 0 1 0 1 0 1 1 1 E 3 bit tiếp theo, 100 dẫn ta đến ngay ký hiệu C : 0 1 0 0 1 0 1 0 1 1 1 E C Sau đó ta nhận được ký hiệu D : 0 1 0 0 1 0 1 0 E C D Và cuối cùng đọc 0 ta có ký hiệu E một lần nữa : 0 1 0 0 1 0 1 0 E C D E Phương pháp mã hoá Huffman theo Mô hình thống kê động Nguyên tắc làm việc của mã Huffman thích ứng là cả bộ mã hoá và giải mã đều phải tự xây dựng và cập nhật cây mã trong suốt quá trình phát và nhận luồng dữ liệu. Việc tính xác suất không phải thực hiện một lần đối với toàn bộ nguồn số liệu mà được tích luỹ trong quá trình mã hoá hoặc giải mã. Với mô hình thống kê động, ta không thể biết trước được xác suất xuất hiện của mỗi ký hiệu trong toàn bộ nguồn tin là bao nhiêu. Phương pháp mã hoá và giải mã vẫn dựa vào cây mã nhưng không phải là cây mã được xây dựng trên xác suất của các ký hiệu trong toàn bộ nguồn số liệu mà dựa vào cây mã xây dựng được tại thời điểm đang xét. Quá trình mã hoá hoặc giải mã được tiến hành như sau: Khởi động cây mã rỗng đầu tiên. Mã hoá hoặc giải mã ký hiệu hiện thời Cập nhật cây mã và quay lại bước 2 Như vậy, việc mã hoá và giải mã chỉ khác nhau ở thủ tục mã hoá và thủ tục giải mã còn thủ tục khởi tạo cây mã rỗng đầu tiên và thủ tục cập nhật cây mã đều được tiến hành theo phương pháp giống nhau. Việc cập nhật cây mã hoàn toàn dựa vào tính chất Sibling của cây mã. Tính chất này được định nghĩa: Trong một cây nhị phân, mọi nút (trừ nút gốc) đều có nút anh em của nó (là một nút khác cùng chung nút cha). Một cây nhị phân được gọi là có tính chất sibling nếu liệt kê tất cả các nút theo trật tự tăng dần của trọng lượng thì trong danh sách đó mọi nút đều đứng bên cạnh nút anh em của nó. Như vậy, một cây mã Huffman có tính chất sibling nếu liệt kê tất cả các nút lá và nút nhánh bắt đầu từ trái qua phải và từ dưới lên trên thì các nút sẽ tuân theo trật tự tăng dần của trọng lượng. Vì vậy, cây mã Huffman chỉ đơn giản là cây nhị phân mà tất cả các nút của nó đều được gán cho một trọng lượng. Khởi động cây mã đầu tiên Các phương pháp mã hoá và giải mã đều khởi động một cây mã Huffman rỗng đầu tiên chỉ gồm một nút gốc và một nút lá rỗng (nút lá rỗng là một nút lá có tần số xuất hiện bằng 0 và được gắn vào nhánh 0 của nút cha). Trong cây luôn tồn tại một nút lá rỗng trong cây nhưng vị trí của nó sẽ thay đổi khi cây mã được cập nhật. Ta sẽ biểu diễn nút lá rỗng này là e0 (espace với số lần hiện là 0).  Thủ tục mã hoá Đối với ký hiệu xuất hiện đầu tiên của ký hiệu này (ta ký hiệu là D1) nên nó sẽ được phát đi ở dạng không mã hoá (nghĩa là ở dạng mã mã ASCII 8-bit : 01000100 (68 )). Bên phát sẽ cập nhật cây mã bằng cách gắn nút lá D1 với nút gốc nhánh 1. Mã hoá đối với các ký hiệu tiếp theo. Trước khi thủ tục mã hoá sẽ kiểm tra xem ký hiệu đó đã có trong cây Huffman hiện thời hay chưa. Nếu đã có rồi thì nó sẽ phát đi từ mã tương ứng với vị trí hiện thời của ký hiệu đó trong cây mã. Nếu chưa có thì bên phát sẽ phát đi từ mã tương ứng với nút lá rỗng hiện thời trong cây và theo sau đó là mã ASCII của ký hiệu đó và thêm ký hiệu này vào cây mã. Sau đó, cập nhật lại cây mã. Thủ tục cập nhật Được thực hiện như sau: nếu ký hiệu mới xuất hiện lần đầu thì việc cập nhật cây mã diễn ra như sau, vị trí của nút lá rỗng được thay bằng một nút nhánh mới, nút nhánh mới này có nút lá rỗng ở nhánh 0 và một nút lá tương ứng với ký hiệu mới ở nhánh 1. Còn nếu đó là một ký hiệu đã có trong cây mã thì việc cập nhật diễn ra như sau: Tăng tần số xuất hiện của nút lá tương ứng với ký hiệu đó thêm 1. Trong cả hai trường hợp đều dẫn đến việc phải tăng trọng lượng của các nút trên đường đi ngược về phía nút gốc. Tiếp theo kiểm tra tính chất Sibling của cây mã, nếu bị vi phạm ta phải tráo đổi các nút với nhau trong cây mã. Thủ tục giải mã Sau khi khởi động cây mã rỗng đầu tiên, thủ tục giải mã hoạt động như sau: đứng từ gốc cây mã, tuỳ theo bit vào là 0 hay 1 mà rẽ theo nhánh 0 hay nhánh 1 cho đến khi đến được nút lá. Nếu nút lá là ký hiệu khác e0 thì xuất ký hiệu đó ra file giải nén. Nếu là e0 nghĩa là ký hiệu đó chưa có mặt trong cây mã hiện thời thì đọc tiếp 8 bit mã từ luồng vào và xuất ra ký hiệu tương ứng với giá trị 8 bit đó ra file giải nén, tiếp đó thêm ký hiệu này vào cây mã. Sau đó, trong cả hai trường hợp ta đều cập nhật cây mã. Quá trình cập nhật cây mã cũng tương tự như ở thủ tục mã hoá. Ví dụ 10: Xét ví dụ cần mã hoá cho luồng bit: DATABOOK T1 A1 e0 D1 *1 *2 1 1 1 0 0 0 0 1 e0 D1 0 e0 1 D1 *1 A1 0 Nguồn tin Từ mã Cập nhật cây mã Danh sách nút kiễm tra sibling D 01000100 e0 D1 Ö A ‘0’01000001 e0 A1 *1 D1 Ö T ‘00’01010100 e0 T1 *1 A1 *2 D1Ö Đổi chỗ 2 nút *2 và D1 e0 T1 *1 A1 D1 *2 Ö A 11 e0 T1 *1 A2 D1 *3 Ö Đổi chỗ cho A2 và D1 e0 T1 *1 D1 A2 *2 Ö 0 1 0 *1 1 D1 *2 A1 0 1 0 e0 T1 1 T1 A2 e0 D1 *1 *3 1 1 1 0 0 0 T1 D1 e0 A2 *1 *2 1 1 1 0 0 0 e0 K1 *1 D1 T1 B1 *2 O2 *2 A2 *4 *4Ö 1 0 T1 A2 *2 *4 2 0 B1 1 0 D1 1 0 K1 e0 1 O2 0 0 2 *2 *4 *1 Tiếp tục quá trình trên, cuối cùng ta có cây mã : N1 Y1 A1 e0 D1 *1 *2 *3 CHƯƠNG 4 CẤU TRÚC DỮ LIỆU + GIẢI THUẬT của PHƯƠNG PHÁP NÉN HUFFMAN THEO MÔ HÌNH THỐNG KÊ Phương pháp mã hoá Huffman theo mô hình thống kê tĩnh Phương pháp mã hoá Huffman theo mô hình thống kê tĩnh Theo cấu trúc cây mã Huffman, ta có mỗi nút lá tương ứng với một ký hiệu. Xét trong bảng mã 1 byte gồm có 256 ký hiệu như vậy cây mã sẽ được xây dựng là một mảng gồm 514 nút (257 nút lá, 255 nút nhánh, 1 nút gốc, 1 nút giả dùng để xây dựng cây mã). Việc phải có 257 nút lá là do các file số liệu trên đĩa ngoài 256 ký hiệu ASCII thông thường có giá trị từ 0 đến 255 còn có thêm một dấu hiệu kết thúc file (EOF - End of File) và ta sẽ gọi đây là ký hiệu END_OF_STREAM (kết thúc luồng)đồng thời gán cho nó giá trị 256. Ta có cấu trúc dữ liệu mô tả cây như sau: typedef struct tree_node { unsigned int count; unsigned int saved_count; int child_0; int child_1; } NODE; Theo cấu trúc của cây ở trên, mỗi nút trong mảng có 4 thành phần: unsigned int count: một biến đếm dùng để giữ trọng lượng của nút int child_0;int child_1: hai thành phần khác là các biến dùng để xác định hai nút con của nút đó unsigned int saved_count: thành phần thứ tư chỉ là một biến tạm sử dụng cho việc xây dựng cây mã. Với cấu trúc dữ liệu như vậy vấn đề đặt ra là làm sao ta có thể nhận biết được ký hiệu đó là ký hiệu gì (mã ASCII) trong cây mã? Có cần thiết phải sử dụng thêm một biến để lưu trữ giá trị ký hiệu hay không? Để giải quyết được vấn đề đó chúng ta sẽ sắp xếp các nút thành một mảng trong đó 257 nút lá sẽ được xếp ở đầu mảng tiếp theo đó là các nút nhánh và cuối cùng là nút giả. Như vậy, việc nhận dạng một nút lá và giá trị của ký hiệu tương ứng có thể dựa vào vị trí của nó trong mảng.Trật tự sắp xếp của mảng 514 nút như sau: Trọng lượng của nút Biến tạm Giá trị của nút con thứ nhất Giá trị của nút con thứ hai 257 nút lá 255 nút nhánh nút gốc nút giả Trật tự sắp xếp trong một nút Hình 4-1 Mảng sắp xếp các nút trong cây mã Huffman tĩnh Chương trình mã hoá làm việc theo trình tự: Đầu tiên là đếm các ký hiệu có mặt trong file và số lượng của chúng. Kết quả đếm được ghi vào một mảng gồm 256 biến đếm. Mỗi biến đếm có kích thước là 2 byte (giá trị đếm được tối đa là 65.535). Sau khi đếm xong, tất cả các kết quả đều được quy giảm xuống theo một hệ số tỷ lệ xác định đủ để chứa trong một byte rồi được sao chép vào các biến đếm tương ứng của 256 nút đầu tiên trong mảng các nút đã nói trước đây. Tiếp theo, ta xây dựng cây mã Huffman theo phương pháp đã đề cập ở chương 3/mục I.2 Sau khi xây dựng xong cây mã, làm thế nào để có được các từ mã của từng ký hiệu?. Ta có quá trình lấy được từ mã: do mỗi ký hiệu tương ứng với mỗi nút nên điểm xuất phát là ở một nút lá. Từ đó, ta đi ngược lên phía nút gốc và tích lũy lại giá trị của các nhánh trên đường đi đến gốc, sau đó đảo ngược trật tự các bit đã tích lũy mới có được từ mã đối với ký hiệu cần phải mã hoá. Nhưng từ cấu trúc cây mã trên ta không thực hiện được điều này vì khi đứng ở một nút, ta không thể xác định được nút cha của nó. Như vậy, đến lúc này ta vẫn chưa mã hoá được ký hiệu. Có 2 giải pháp được đề cập đến: Giải pháp 1: Khi gặp một ký hiệu, ta xuất phát từ nút gốc (cũng như từ một nút nhánh) và bắt đầu duyệt qua toàn bộ cây. Nghĩa là ta lần lượt rẽ theo các nhánh , cho đến khi nào được nút lá là ký hiệu cần mã hoá và xuất từ mã của ký hiệu cần mã hoá. Như vậy, ta không cần đảo ngược các bit do nó được tích luỹ từ gốc đến nút lá trong quá trình tìm kiếm ký hiệu. Giải pháp 2: Ta xây dựng bảng mã từ cây mã. Cấu trúc dữ liệu cho bảng mã là: typedef struct { unsigned int code; int code_bit; } CODE; Ta bắt đầu duyệt toàn bộ cây một lần từ gốc đến tất cả các nút lá và xây dựng một bảng các từ mã cho tất cả các ký hiệu có trong cây. Như vậy, tuy cả hai cùng dùng thủ tục đệ qui để duyệt cây mã nhưng ta chọn giải pháp 2 vì rõ ràng nó mã hoá nhanh hơn do chỉ duyệt cây một lần và sau đó việc mã hoá từng ký hiệu của một file số liệu sẽ được thực hiện rất đơn giản dựa vào bảng các từ mã này. Khi gặp một ký hiệu, dựa vào bảng mã ta có được từ mã tương ứng. Ta có toàn bộ quá trình mã hoá như sau: Đếm tần suất xuất hiện (xác suất) của các ký hiệu trong cần nén Qui giảm xác suất của các ký hiệu đó Xuất số liệu thống kê ra file nén Xây dựng cây mã Huffman tĩnh Xây dựng bảng mã Mã hoá: while (chưa kết thúc file) { Đọc một ký hiệu; Xuất từ mã tương ứng dựa vào bảng mã; } Phương pháp giải mã Huffman theo mô hình thống kê tĩnh Chương trình giải mã muốn làm việc đúng phải có được bản sao của cây mã Huffman đã được chương trinh mã hoá đã sử dụng. Ở đây, ta cũng có 2 giải pháp được đưa ra: Giải pháp 1: Gửi cấu trúc của cây mã nghĩa là gửi toàn bộ số liệu của mảng gồm 514 phần tử nói trên (cỡ 4Kbyte) ra đầu file nén sau đó mới đến các từ mã. Chương trình giải mã sẽ dựa vào cây mã này để mã hoá các ký hiệu bằng cách đọc từ bit một và rẽ theo nhánh 0 hoặc 1 để đến được nút lá, sau đó xuất ký hiệu tương ứng với nút lá vừa tìm được ra file giải nén. Như đã xét trong các chương trước, do mã Huffman là mã có tính chất tiền tố nên ta luôn luôn giải mã được các ký hiệu tương ứng từ luồng bit nhận được dựa vào cây mã. Giải pháp 2: Gửi 256 biến đếm (256 byte) chứa xác suất tương ứng với 256 ký hiệu ra đầu file nén. Tuy nhiên, có những trường hợp không phải tất cả 256 ký hiệu đều có mặt trong một file số liệu (nhất là các file văn bản ASCII), do đó có rất nhiều biến đếm có giá trị bằng 0 do đó ta sẽ không gửi đi các biến đếm đó. Bên cạnh đó với các biến đếm có giá trị khác 0 ta gửi đi theo khuôn dạng tiết kiệm hơn bằng cách phân chia thành từng loạt. Khoảng cách giữa hai loạt biến đếm phải ít nhất là 3 biến đếm có giá trị bằng 0. Trong mỗi loạt biến đếm đó, ta chỉ gửi đi giá trị của ký hiệu đầu và ký hiệu cuối cùng với tất cả các giá trị của các biến đếm trong loạt đó. Dấu hiệu kết thúc loại số liệu thống kê này là một byte có giá trị bằng 0. Dựa vào số liệu này, chương trình giải mã sẽ xây dựng cây mã và quá trình giải mã sẽ tương tự như giải pháp 1. Như vậy với giải pháp 2, có thể ta chỉ tốn một khoảng £ 256 byte (bậc 0). Từ 2 giải pháp trên, ta chọn giải pháp 2 vì ta sẽ tiết kiệm được rất nhiều phần không gian dành cho số liệu thống kê cần phải cung cấp cho chương trình giải mã. Nhờ vậy, hiệu suất nén sẽ được nâng cao. Ở đây, với mô hình bậc 0 thì hiệu suất nén của giải thuật 2 trên chênh lệch không đáng kể nhưng với mô hình bậc cao số liệu thống kê lớn thì hiệu suất nén sẽ chênh lệch đáng kể giữa giải pháp 2 so với giải pháp 1. Ta có quá trình giải mã như sau: Nhập số liệu thống kê: Đầu tiên, ta tạo ra trong bộ nhớ một cấu trúc dữ liệu là một mảng gồm 514 nút như chương trình mã hoá đã làm để chuẩn bị cho việc xây dựng cây mã. Sau đó, mở và đọc toàn bộ các byte số liệu thống kê được chứa ở phần đầu của một file số liệu đã được chương trình mã hoá gởi đầu file để xử lý (dựa trên khuôn dạng đặc biệt đã biết) và chuyển kết quả (giá trị các biến đếm của tất cả các ký hiệu) vào các vị trí thích hợp trong mảng các nút đã khởi tạo. Xây dựng cây mã: Tương tự như chương trình mã hoá Giải mã dựa vào cây mã vừa được xây dựng: Khởi động con trỏ p chỉ đến gốc. while (chưa đạt đến kết thúc thông báo) { Đặt x là bit tiếp theo trong xâu ký hiệu. if (x = 0) Đặt p bằng con trỏ chỉ đến con trỏ bên trái của nó. else Đặt p bằng con trỏ chỉ đến con bên phải của nó. if (p chỉ đến một nút lá) { Xuất ký hiệu tương ứng với nút lá ra file giải nén. Đặt lại p để nó chỉ đến gốc của cây Huffman } } Phương pháp mã hoá Huffman theo mô hình thống kê động (thích ứng) Phương pháp mã hoá Huffman theo mô hình thống kê động Khác với mô hình thống kê tĩnh là cây mã chỉ được xây dựng một lần dựa trên xác suất thống kê trên toàn nguồn số liệu. Với mô hình thống kê động, cây mã luôn luôn được cập nhật sau khi mã hoá được một ký hiệu (cập nhật mô hình) và xác suất của các ký hiệu không được thống kê một lần mã được tích luỹ trong suốt quá trình mã hoá. Như vậy, ở mô hình thống kê động ta không thể biết trước được xác suất xuất hiện của các ký hiệu trong toàn bộ nguồn số liệu là bao nhiêu. Việc cập nhật hoặc xây dựng lại cây mã dựa vào tính chất sibling của cây. Ta xây dựng cấu trúc dữ liệu cho cây mã Huffman động như sau: struct tree { int leaf [SYMBOL_COUNT]; int next_free_node; struct node nodes[NODE_TABLE_COUNT]; }Tree; struct node { unsigned int weight; int parent; int child_is_leaf; int child; }; Với: SYMBOL_COUNT=257, NODE_TABLE_COUNT=515, nghĩa là khác với cây Huffman tĩnh thay vì chỉ có 514 nút thì cây Huffman động có thêm một nút Escape do đó ngoài ký hiệu kết thúc luồng END_OF_STREAM=256 có thêm nút Escape =257 để mã hoá luồng ký hiệu vào. Trong cây mã, mỗi nút gồm có 4 thành phần: unsigned int weight: biến đếm giữ trọng lượng của nút này. int parent: biến dùng để xác định nút cha của nút này. int child_is_leaf: biến logic dùng để phân biệt giữa nút lá và nút nhánh. Nếu biến này có giá trị TRUE là nút lá, nếu biến này có giá trị FALSE là nút nhánh. Int child: biến dùng để xác định nút con thứ nhất của nút ( nút con thứ hai sẽ được xác định nhờ tính chất Sibling của cây mã Huffman). Nếu biến logic của nút là TRUE thì biến này sẽ giữ giá trị của ký hiệu tương ứng với nút lá này. Trong cây mã, theo tính chất sibling các nút được sắp xếp theo thứ tự tăng dần, nhưng ở đây trọng lượng của các nút được sắp xếp theo thứ tự ngược lại là giảm dần. Nút 0 nút 1 nút 2 ... nút 514 Biến thứ nhất Biến thứ hai dùng để Biến logic Biến dùng để xác giữ trọng lượng xác định nút cha TRUE=đây là nút lá định nút con thứ của nút FALSE=đây là nút nhánh nhất hoặc giá trị của ký hiệu Trật tự sắp xếp trong một nút Hình 4-2 Mảng thứ nhất mô tả cây mã Huffman thích ứng Mảng thứ hai dùng để truy cập cây mã khi mã hoá và giải mã. Mảng này gồm 258 thành phần. Tương ứng cấu trúc dữ liệu mô tả cây ở trên là mảng int leaf[SYMBOL_COUNT], trong đó mỗi phần tử dùng để xác định vị trí của một nút lá tương ứng với một ký hiệu trong số 258 ký hiệu ( 256 ký hiệu ASCII, ký hiệu kết thúc luồng EoS và ký hiệu Escape ). Vị trí của nút lá Vị trí của nút lá Vị trí của nút lá Vị trí của nút lá tương ứng với ký tương ứng với ký tương ứng với ký tương ứng với ký hiệu có giá trị 0 hiệu có giá trị 1 hiệu có giá trị 256 hiệu có giá trị 257 0 1 256 257 Hình 4-3 Mảng thứ hai dùng để xác định vị trí các nút lá Một thành phần khác trong cấu trúc cây mã là int next_free_node là một biến để giữ giá trị vị trí hiện thời của nút tiếp theo sau nút cuối cùng trong danh sách các nút đã có trong cây mã để biết được hiện thời danh sách các nút đã có trong cây mã đã kéo dài đến đâu trong mảng mô tả các nút, thành phần này sẽ dùng khi xây dựng lại cây mã. * Toàn bộ quá trình mã hoá như sau: Khởi động cây mã rỗng đầu tiên; while (đọc vào một ký hiệu END_OF_STREAM) { Mã hoá ký hiệu ; Cập nhật cây mã; } Khởi động cây mã rỗng Nút gốc Escape (1) 1 EoS(1) Hình 44 Cây mã rỗng đầu tiên 0 Như đã xét, với cây mã Huffman động ta có thêm nút Escape, nút này gọi là mã thoát (có giá trị =257). Điều này có cần thiết hay không?. Ta thấy rằng, với mô hình thống kê động, việc mã hoá và giải mã đều dựa vào cây mã hiện thời. Mã thoát được sử dụng trong 2 quá trình này. Khi ký hiệu chưa có mặt trong cây mã, lúc này dựa vào mã thoát đã có trong cây mã ta sẽ gởi đi từ mã của mã thoát và mã ASCII của ký hiệu, dựa vào đó chương trình giải mã mới giải mã được chính xác ký hiệu khi nó xuất hiện lần đầu tiên (chưa cómặt trong cây mã hiện thời) này bằng cách cũng dựa vào mã thoát. Khi đọc đến một nút lá là mã Escape, chương trình sẽ đọc tiếp 8 bit và xuất ra ký hiệu tương ứng với giá trị mã ASCII 8 bit này. Ngoài ra, một khía cạnh cũng cần sử dụng đến mã thoát là quá trình thêm một nút mới vào cây mã. Vậy ta thêm nút mới này vào đâu?, có thể thêm vào một cách ngẫu nhiên ở bất kì nút nào trong cây mã không?. Khi thêm một nút vào cây mã ta cũng tuân theo một nguyên tắc nhất định, và nó được thêm vào nút tương ứng với mã thoát (là nút có trọng lượng bé nhất). Nút escape sẽ được thay thế bằng một nhánh mới gồm 2 nút: nút escape và một nút tương ứng với ký hiệu mới thêm vào. Cây mã được khởi tạo gồm có 3 nút: nút đầu tiên (nút 0) sẽ là nút gốc và là nút có trọng lượng lớn nhất trong cây), các nút tiếp theo từ nút 1 trở đi sẽ dành cho các nút phía trong cây gồm các nút nhánh và các nút lá theo nguyên tắc giảm dần của trọng lượng. Với cây mã trên ta có các nút được gán giá trị như sau: Nút 0 (gốc) có trọng lượng bằng 2 (biến thứ nhất đặt = 2), không có nút cha (biến thứ hai đặt = -1), không phải là nút lá (biến logic đặt = FALSE), nút con thứ nhất (gắn với nhánh 0) là nút EoS (biến cuối cùng đặt = 1). Nút 1 (EoS) có trọng lượng bằng 1 (biến thứ nhất đặt = 1), nút cha của nó là nút gốc (biến thứ hai đặt = 0), đây là một nút lá (biến logic đặt = TRUE), giá trị của ký hiệu tương ứng với nó là 256 (biến cuối cùng đặt = 256). Nút 2 (Escape) có trọng lượng bằng 1 (biến thứ nhất đặt = 1), nút cha của nó là nút gốc (biến thứ hai đặt = 0), đây là một nút lá (biến logic đặt = TRUE), giá trị của ký hiệu tương ứng với nó là 257 (biến cuối cùng đặt = 257). Trật tự các nút sắp xếp trong cây mã hiện thời như sau: 2 -1 F 1 1 0 T 256 1 0 T 257 Nút 0 Nút 1 Nút 2 Hình 45 Khởi động giá trị cho 3 nút đầu tiên của cây mã rỗng -1 -1 -1 -1 2 1 0 1 2 255 256 257 Tương ứng, ta có các thành phần trong mảng thứ hai là: Hình 4-6 Khởi động các giá trị đầu cho mảng