Đồ án Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov

hiện văn bản z, và là độ dài bản mã của nó. (định lý đã được chứng minh trong tài liệu lý thuyết mã nén của nhóm tác giả: Nguyễn Lê Anh, Trần Duy Lai, Phạm Thế Long, Nguyễn Văn Xuất). Từ đây, ta chỉ đề cập đến các mã tổng nhị phân. Nếu các từ mã có độ dài cố định thì ta luôn giải mã được. Nhưng nếu độ dài của từ mã thay đổi thì không phải với ánh xạ mã nào cũng có thể giải mã được. Ví dụ 2.1. Xét ánh xạ mã a -> 100 b -> 1000 c -> 0 Mã của "ac" và "b" đều là dãy bit "1000". Như vậy khi nhận được chuỗi bit 1000 ta không thể biết được rằng văn bản ban đầu là "b" hay là "ac". Cho nên ánh xạ tạo thành bảng mã cho các chữ cái cần phải có tính chất là giải mã được. Tính phân tách được đưa ra dưới đây sẽ đảm bảo cho tính giải được của mã. Định nghĩa 2.3: Cho A và B là hai đoạn tạo ra từ các bit 0/1. Ta nói A là đầu của B nếu như có một đoạn C sao cho B = A + C. Định nghĩa 2.4: Một tập hợp M tạo ra từ các đoạn bit 0/1 được gọi là phân tách nếu không có đoạn nào là đầu của đoạn kia. Như vậy, mã có độ dài từ mã cố định là mã phân tách. Định lý 2.2. Điều kiện đủ để giải mã được một dãy bit được tạo bởi một mã tổng từ một bảng mã bit "0/1" có độ dài thay đổi là mỗi chữ cái ứng với một xâu bit không có xâu nào là bắt đầu của xâu khác. Định lý 2.3. (Kraft-McMilan) Điều kiện cần và đủ để có mã tổng mã các chữ cái W={a1, a2, ..,am} bằng xâu bit 0/1 với độ dài tương ứng Ji=J(ai) là . - Điều kiện cần (Định lý McMillan) - Điều kiện đủ (Định lý Kraft) (định lý đã được chứng minh trong tài liệu lý thuyết mã nén của nhóm tác giả: Nguyễn Lê Anh, Trần Duy Lai, Phạm Thế Long, Nguyễn Văn Xuất). Hệ quả Mọi mã tổng đều có thể thay thế bằng mã phân tách có cùng độ dài các từ mã. 2.2. Mã Shannon Xét bảng các chữ cái W={a1,a2,......am} với xác suất tương ứng p1³ p2 ³ ... ³ pm>0. Ta xây dựng một mã phân tách cho bảng chữ cái W như sau. Với mỗi pi có thể chỉ ra số nguyên ri sao cho . Rõ ràng, nếu i<j thì do nên ri £ rj . Sử dụng kí hiệu Q1 = 0 Q2 = p1 Q3 = p1+ p2 Q4 = p1+ p2+ p3 ..... Qm = p1+ p2+.......+ pm-1 Khi đó do p1, p2 ,..., pm>0 nên Q1< Q2<......<Qm<1 Một số x<1 bất kỳ có thể biểu diễn duy nhất ở dạng x= Trong đó ai là các số hoặc bằng 0 hoặc bằng 1. Ta sử dụng ký hiệu 0,aia2a3...ak... để ghi lại tổng trên và gọi nó là biểu diễn theo cơ số 2 của số x. Như vậy, số có dạng 0,11 có nghĩa là . Trong phần chứng minh sau vì không có khả năng gây ra nhầm lẫn nên để cho đơn giản ta bỏ “0,” ra khỏi biểu diễn trên, và vẫn gọi aia2a3....ak... là biểu diễn cơ số 2 của x. Xét biểu diễn các số Q1< Q2<......<Qm dưới dạng cơ số 2 như trên. Cứ với mỗi một trong m dãy cơ số 2 nói trên ta giữ lại, tương ứng với từng Qi dãy Ãi tạo ra từ r i số đầu tiên. Như vậy, ta có m dãy Ãi với i=1..m là các dãy tạo ra từ các bit “0,1”. Với mỗi i=1..m ta sử dụng Ãi để mã hoá trạng thái ai thì thu được một phương pháp mã nhị phân trong đó mỗi trạng thái ai được ứng với một dãy có ri bit. Loại mã này gọi là mã Shannon. Thuật toán tìm mã Shannon. Input. nhập n và các giá trị xác suất P1³ P2³..... Pn Out put. tính code[i] Q:=0; for i:=1 to n do begin r:=1;w:=1/2; while not (w<= Pi) do begin w:=w/2;r:=r+1; end; code[i]:=’’; S:=Q;Q:=Q+ Pi; for j:=1 to r do begin S:=S*2; if S>1 then begin S:=S-1; code[i]:=code[i]+'1' end else code[i]:=code[i]+'0' end; end; Chương trình minh hoạ tạo mã Shannon. const n=20; {Số ký tự của bảng chữ cái} var P:array[1..n] of real; {Xác suất từng ký tự} code:array[1..n] of string; {Mã Shannon cho từng ký tự} Procedure coding; Var S,Q,w: real; i,j,r:integer; Begin Q:=0; for i: =1 to n do begin r:=1;w:=1/2; while not (w<= P[i]) do begin w:=w/2;r:=r+1;end; code[i]:=''; S:= Q;Q:=Q+ P[i]; for j:=1 to r do begin S:=S*2; if S>1 then begin S:=S-1;code[i]:=code[i]+'1';end else code[i]:=code[i]+'0' end; end; End; {Phần chính của trình.} const U:array[1..n] of integer= (371,332,313,257,252,249,205,202,178,173,151,132,123,107,73,59,48,4,2,1); Var i:integer; s:real; f:text; Begin {Nhập dữ liệu} s:=0;for i:=1 to n do s:=s+U[i]; for i:=1 to n do begin p[i]:=U[i]/s;code[i]:=''; end; {Tạo mã} Codi ng; {Ghi kết quả ra file} assign(f,'c:\kq.txt');rewrite(f); for i:=1 to n do writeln(f,code[i]:15,U[i]:5); close(f); End. Định lý 2.4. Cho bảng chữ cái W={a1,a2,......am} với xác suất tương ứng p1³ p2 ³ ... ³ pm>0. Mã Shannon là mã phân tách. Nó mã mỗi chữ cái ai với xác suất pi bằng một từ mã nhị phân có độ dài ri thoả mãn Bit trung bình của mã Shannon thoả mãn hệ thức . Hay Entropy(W)£ < Entropy(W)+1. (định lý đã được chứng minh trong tài liệu lý thuyết mã nén của nhóm tác giả: Nguyễn Lê Anh, Trần Duy Lai, Phạm Thế Long, Nguyễn Văn Xuất). 2.3. Mã tối ưu và sự tồn tại của mã tối ưu 2.3.1. Định nghĩa mã tối ưu. Cho bảng chữ cái W={a1,a2,.....,am} với xác suất tương ứng p1 ³ p2 ³......³ pm >0. Xét mã tổng x trên W với các từ mã tương ứng là e1=x (a1), e2=x (a2),..., em=x (am). Các từ mã e1, e2,...., em có độ dài tương ứng là J1, J2,...., Jm. Một mã tổng x được gọi là tối ưu nếu bit trung bình của mã là nhỏ nhất có thể. Lưu ý rằng mọi mã tổng có thể thay thế bởi một mã phân tách cho nên mã tối ưu là mã phân tách. Ta đi chứng minh có tồn tại mã tối ưu. 2.3.2. Sự tồn tại của mã tối ưu Khẳng định: Mã tối ưu đã tồn tại Trong số các mã tối ưu thì tìm được một mã tối ưu mà Chữ cái có xác suất lớn hơn sẽ có độ dài từ mã bé hơn. Từ mã của hai chữ cái có xác suất nhỏ nhất có cùng độ dài và chỉ khác nhau bit cuối cùng. (Khẳng định đã được chứng minh trong tài liệu lý thuyết mã nén của nhóm tác giả: Nguyễn Lê Anh, Trần Duy Lai, Phạm Thế Long, Nguyễn Văn Xuất). 2.4. Mã Huffman Định nghĩa 2.5 Nếu bảng chữ cái chỉ có 2 chữ cái thì ta đánh mã chúng là "0" và "1". Ta định nghĩa mã Huffman cho bảng có m chữ cái bằng đệ qui như sau: Xếp bảng chữ cái theo thứ tự xác suất xuất hiện của nó giảm dần ( p1³p2³ ... ³ pm >0). Như vậy chữ cái ở cuối bảng là chữ cái có xác suất xuất hiện nhỏ nhất. Ghép 2 chữ cái với xác suất nhỏ nhất lại thành một chữ cái kép với xác suất xuất hiện là tổng của hai xác suất ấy. Như vậy trong bảng chữ cái mới 2 chữ cái này bị loại nhưng chữ cái kép được thêm vào. Tạo mã Huffman cho bảng chữ cái mới này ( có m - 1 chữ). Tạo 2 từ mã mới bằng cách thêm "0" và thêm "1" vào mã của chữ cái kép. Gán 2 mã này cho 2 chữ cái bị ghép lại. Thuật toán tạo mã Huffman. Bước 1. Liệt kê tất cả chữ cái cùng với xác suất của nó theo thứ tự giảm dần. Bước 2. Ghép 2 chữ cái có xác suất nhỏ nhất ( 2 chữ cuối bảng) thành một chữ cái kép. Giả sử như 2 chữ ấy là "a","b". Ta dùng kí hiệu {a,b} để ký hiệu chữ cái kép ấy. Xác suất của chữ cái kép bằng tổng của 2 xác suất của 2 chữ cái tạo ra chữ kép ấy. Bước 3. Nếu đã tìm được mã cho bảng cái "kép" thì mã của chữ "a" sẽ gồm mã của chữ kép thêm 0, và mã chữ "b" thêm 1. Bước 4. Quay lại bước 1 cho đến khi chỉ còn 1 chữ kép có xác suất bằng 1. Ví dụ 2.2. Với không gian xác suất các sự kiện {e, a, i, o, u, ô} các xác suất tương ứng là (e,0. 3) (a,0.2) (o,0.2) (i,0.1) (u,0.1) (ô,0.1) thì ta cần ghép 5 lần như sau: e ® 0.3 e ®0.3 e ®0.3 {a,o}®0.4 {{{u,«},i},e}®0.6 {{{{u,«},i},e},{a,o}}®1.0 a ® 0.2 a ®0.2 {{u,«},i}®0.3 e ®0.3 {a,o} ®0.4 o ® 0.2 o ®0.2 a ®0.2 {{u,«},i}®0.3 i ® 0.1 {u,«} ®0.2 o ®0.2 u ® 0.1 i ®0.1 « ® 0.1 B¶ng 2.1 {{{{u,«},i},e},{a,o}} {a,o} {{{u,«},i},e} {{u,«},i} {u,«} 1 1 0 0 0 0 1 1 1 0 o a e i « u B¶ng m· cña c¸c ch÷ c¸i. u®0000 «®0001 i®001 e®01 a®10 o®11 ViÖc g¸n m· ®­îc thùc hiÖn nh­ sau: Trình minh hoạ tạo mã Huffman Dưới đây là trình lập mã Huffman bằng Pascal theo thuật toán đã mô tả ở trên. Sử dụng phương pháp đệ qui thì có ưu điểm là dễ hiểu nhưng cũng có nhược điểm là đòi hỏi bộ nhớ lớn. Const n=20; Type nod=record code:string; prob:integer; end; var a:array[1..n] of nod; x:nod; Sx:string; i,k:integer; f:text; Procedure coding(m:integer); var k:integer; y:integer; begin Case m of 1 :exit; 2..n :begin {Điều kiện thoát} if m=2 then begin a[m-1].code:='0';a[m].code:='1';exit; end; {Tạo chữ cái kép} y:=a[m-1].prob;inc(a[m-1].prob,a[m].prob); {Xếp lại} k:=m-1; while (k>1)and (a[k].prob>a[k-1].prob) do begin x:=a[k-1]; a[k-1]:=a[k]; a[k]:=x; k:=k-1; end; {Giả sử đã có mã cho bảng chữ cái "kép"} coding(m-1); {Khi đó mã của các chữ cái là} Sx: =a[k].code; for i:=k to m-2 do a[i]:=a[i+1]; a[m-1].code:=Sx+'0';a[m-1].prob:=y; a[m].code:=Sx+'1'; end; end; end; {Phần chính của trình.} const U:array[1..n] of integer = (371,332,313,257,252,249,205,202,178,173,151,132,123,107,73,59,48,4,2,1); begin {Nhập dữ liệu} for i:=1 to n do begin a[i].prob:=U[i]; a[i].code:=''; end; {Tạo mã} coding(n); {In kết quả} assign(f,'c:\KQ.txt');rewrite(f); for i:=1 to n do writeln(f,a[i].prob:4,' ',a[i].code); close(f); end. Định lý 2.5. Mã Huffman là mã tối ưu. Định lý 2.6. Đối với mã tối ưu thì £ £ 1+. (Các định lý đã được chứng minh trong tài liệu lý thuyết mã nén của nhóm tác giả: Nguyễn Lê Anh, Trần Duy Lai, Phạm Thế Long, Nguyễn Văn Xuất). 2.5. Mã Fano. Thuật toán tạo mã Fano: Giả sử ai với i=1..n là các chữ của một alphabet nào đó và ai xuất hiện với tần suất tương ứng là pi. Lưu ý rằng p1+p2+... + pn=1 Bước 1. Bằng cách xếp và kí hiệu lại ta có thể coi các chữ cái a1, a2, ..., an, có tần suất là p1³ p2³ ... ³ pn (theo thứ tự giảm dần). Bước 2. Chia các chữ cái ra làm 2 nửa, nửa trên và nửa dưới, sao cho chúng có tổng gần bằng nhau nhất. Nửa trên nhận mã là 0, nửa dưới là 1. Bước 3. Lặp lại công việc cho từng nửa và cứ tiếp tục với các nửa mới sinh ra cho tới khi trong mỗi nửa mới chỉ có 1 chữ cái. Dãy các số 0,1 được tạo ra là mã của các chữ cái. Ví dụ 2.3. Không gian xác suất các sự kiện {e, a, i, o, u, ô} với các xác suất tương ứng là (e,0.3) (a,0.2) (i,0.2) (o,0.1) (u,0.1) (ô,0.1). Trình minh hoạ tạo mã Fano Const n=20; {số ký tự của bảng mã} Type nod = record code:string; {mã Huffman} prob:real; {tần xuất} end; var a:array[1..n] of nod; f:text; i:integer; Procedure coding(bottom,top:integer); var s, r:real; h:integer; Begin {Điều kiện dừng} if bottom = top then exit; {Chia bảng mã ra làm 2 phần} s:=0; for i:=bottom to top do s:=s+a[i].prob; h:=bottom; r:=a[h].prob; while r<s-r do begin h:=h+1; r:=r+a[h].prob; end; if h=top then h:=h-1; {Nửa dưới nhận mã 1} for i:=bottom to h do a[i].code:=a[i].code+'1'; {Nửa trên nhận mã 0} for i:=h+1 to top do a[i].code:=a[i].code+'0'; {làm tương tự như vậy cho mỗi nửa thu được} coding(bottom,h);coding(h+1,top); end; const U:array[1..n] of integer= (371,332,313,257,252,249,205,202,178,173,151,132,123,107,73,59,48,4,2,1); Begin {Nhập dữ liệu} for i:=1 to n do begin a[i].prob:=U[n-i];a[i].code:= ''; end; {Tìm mã} coding(1,n); {Ghi kết quả} assign(f, 'c:\KQ.txt ');rewrite(f); for i:=n downto 1 do writeln(f,a[i].prob:4:0, ' ',a[i].code); close(f); End. Kết quả chạy các chương trình trên được trình bày trong bảng tổng hợp ở phía sau. Kết quả tính. Bảng tổng hợp. Mã Shannon Mã Fano Mã Huffman Tần xuất 0000 000 100 371 0001 001 110 332 0011 010 111 313 0101 0110 0001 257 0110 0111 0010 252 0111 100 0011 249 1000 1010 0101 205 1001 10110 0110 202 10101 10111 1010 178 10111 1100 1011 173 11001 1101 00000 151 11010 11100 00001 132 11011 11101 01000 123 11101 11110 01110 107 111100 111110 01111 73 111101 1111110 010010 59 1111101 11111110 0100110 48 1111111101 111111110 01001110 4 11111111110 1111111110 010011110 2 111111111110 1111111111 010011111 1 Bảng 2.2 Bít trung bình cho từng loại: Shannon Fano Huffman xác suất Mã độ dài xs* độ dài Mã độ dài xs* độ dài Mã độ dài xs* độ dài 0000 4 0.459 000 3 0.344 100 3 0.344 0.115 0001 4 0.411 001 3 0.308 110 3 0.308 0.103 0011 4 0.387 010 3 0.291 111 3 0.291 0.097 0101 4 0.318 0110 4 0.318 0001 4 0.318 0.080 0110 4 0.312 0111 4 0.312 0010 4 0.312 0.078 0111 4 0.308 100 3 0.231 0011 4 0.308 0.077 1000 4 0.254 1010 4 0.254 0101 4 0.254 0.063 1001 4 0.250 10110 5 0.313 0110 4 0.250 0.063 10101 5 0.275 10111 5 0.275 1010 4 0.220 0.055 10111 5 0.268 1100 4 0.214 1011 4 0.214 0.054 11001 5 0.234 1101 4 0.187 00000 5 0.234 0.047 11010 5 0.204 11100 5 0.204 00001 5 0.204 0.041 11011 5 0.190 11101 5 0.190 01000 5 0.190 0.038 11101 5 0.166 11110 5 0.166 01110 5 0.166 0.033 111100 6 0.136 111110 6 0.136 01111 5 0.113 0.023 111101 6 0.110 1111110 7 0.128 010010 6 0.110 0.018 1111101 7 0.104 11111110 8 0.119 0100110 7 0.104 0.015 1111111101 10 0.012 111111110 9 0.011 01001110 8 0.010 0.001 11111111110 11 0.007 1111111110 10 0.006 010011110 9 0.006 0.001 111111111110 12 0.004 1111111111 10 0.003 010011111 9 0.003 0.000 bit trung bình 4.408 4.009 3.958 Bảng 2.3 Theo như kết quả trên thì mã Huffman có bít trung bình nhỏ nhất, vì thế hệ số nén cao nhất. Khẳng định. Với nguồn có n sự kiện thì qui trình mã/giải nén mã Huffman và Shannon được thực hiện với 0(log2n) phép toán. Chứng minh. Quá trình mã là việc tra từ điển tìm mã 0/1 của nó. Quá trình này được thực hiện nhờ thuật toán tìm kiếm nhanh hết 0(log2(n)) phép toán. Quá trình giải nén thực hiện tìm kiếm nhanh nhờ cây nhị phân hết 0(log2(n)) phép toán. Như vậy tổng số thời gian cần để mã và giải nén hết 0(log2(n)) phép toán. 2.6. Mã Huffman động. Cây nhị phân cho mã Huffman động. Nguyên lý tạo mã động là dựa vào việc tạo lại mã với bảng tần xuất mới. Tuy nhiên việc tạo lại bảng mã mất thời gian tính, làm giảm hiệu quả mã và giải mã. Phần này ta làm quen với thuật toán tạo nhanh bảng mã Huffman song song với quá trình mã và giải mã. Nguyên tắc tạo mã Huffman là dựa vào việc thay hai chữ cái có tần xuất thấp nhất thành một chữ cái kép có tần xuất bằng tổng của chúng. Thực hiện quá trình nhóm cho tới khi ta chỉ có hai chữ cái. Quá trình sinh mã Huffman ngược với quá trình nhóm. Kết quả là ta thu được một cây nhị phân, mà lá của nó là các chữ cái. Tại mỗi lá có ghi tần xuất xuất hiện của chữ cái ấy và tại mỗi nhánh ghi tổng các tần xuất có ở các lá của nhánh. Các chỉ số này được gọi là "trọng số nhánh". Trọng số của nhánh bên trái luôn không nhỏ hơn trọng số của nhánh bên phải. Quá trình giải mã. Ta bắt đầu đi từ đỉnh cây và nếu gặp bit '1' thì rẽ sang nhánh bên phải, gặp bit '0' thì rẽ sang nhánh trái. Khi nào tới lá thì dừng lại và in chữ cái đó ra. Quá trình mã. Nhập chữ cái vào và kiểm tra xem có lá nào chứa chữ cái này không. Nếu có thì in ra con đường đi từ lá ấy tới gốc của cây, sao cho nếu rẽ sang trái thì in ra bit ‘1’ rẽ sang phải thì in ra bit ‘0’. 540 501 1041 824 442 382 1865 3169 722 647 371 351 332 313 283 257 202 180 178 173 107 73 237 205 123 114 59 55 48 7 4 3 151 132 252 249 2 1 5034 a u o n h H×nh 2.1 Cứ mỗi khi mã, hay giải mã được 1 chữ thì số lượng chữ cái mỗi loại thay đổi theo, vì thế cây nhị phân Huffman cần phải được sửa lại cho hợp với các số liệu thống kê mới. Giả sử tại một thời điểm nào đó có cây nhị phân mã Huffman sau: 540 501 1041 825 443 382 1866 3169 722 647 371 351 332 313 283 257 202 180 178 173 107 73 238 205 123 115 59 56 48 8 4 4 151 132 252 249 2 2 5035 a u o n h H×nh 2.2 Nếu chữ cái tiếp theo là "a" thì các trọng số sẽ thay đổi nhưng việc sửa chữa cây không xảy ra. Nếu chữ tiếp theo là "a" nữa thì cây nhị phân sẽ đổi như sau: 540 501 1041 826 444 382 1867 3169 722 647 371 351 332 313 283 257 202 180 178 173 107 73 239 205 123 116 59 57 48 9 5 4 151 132 252 249 3 2 5036 u a o n h H×nh 2.3 Trình tạo mã Huffman động Thủ tục coding() được gọi đệ qui. Sau khi tìm được vị trí đúng cho đỉnh ghép thì 2 đỉnh cuối được tạo ra bằng các lệnh: Sx:=a[k]; a[m-1]:=y; a[m-1].code:=Sx.code+'0'; a[m].code:=Sx.code+'1'; trong đó y là đỉnh m-1 được lưu lại từ trước. Do đỉnh ghép chèn vào giữa, nên các đỉnh phía sau phải dịch xuống: for i:=k to m-2 do a[i]:=a[i+1]; Trình chính gọi lại coding(n) mỗi khi đọc thêm 1 chữ của văn bản và tính lại tần số. Const n=8; Type nod=record w:byte; c ode:string; prob:integer; end; var a : array[1..n] of nod; Sx, x : nod; k,i : integer; f : text; Procedure coding(m:integer); var k:integer; y:nod; begin Case m of 1: exit; 2..n: begin if m=2 then begin a[m-1].code:='0';a[m].code:='1';exit;end; y:=a[m-1];inc(a[m-1].prob,a[m].prob); k:=m-1; while (k>1) and (a[k].prob>a[k-1].prob) do begin x:=a[k-1];a[k-1]:=a[k];a[k]:=x;k:=k-1; end; coding(m-1); Sx:=a[k];for i:=k to m-2 do a[i]:=a[i+1]; a[m-1]:=y;a[m-1].code:=Sx.code+'0'; a[m].code:=Sx.code+'1'; end; end; end; {Phần chính của trình.} const U:array[1..n] of integer=(1,1,1,1,1,1,1,1); S:string='aaaaaabcdefghaahhaaaaagabghabaecdcaaadaecccccccccghaacbgbchaecbdhabdehahcghghaebcd'; Var h:word; begin for i:=1 to n do begin a[i].prob:=U[i];a[i].code:='';end; a[1].w:=ord('a');a[2].w:=ord('b');a[3].w:=ord('c');a[4].w:=ord('d'); a[5].w:=ord('e');a[6].w:=ord('f');a[7].w:=ord('g');a[8].w:=ord('h'); assign(f,'c:\KQ.txt');rewrite(f); h:=0; while true do begin coding(n); {tạo mã} for i:=1 to n do writeln(f,char(a[i].w),' ',a[i].prob:4,' ',a[i].code);writeln(f); h:=h+1;if h>length(s) then begin close(f);exit;end; for i:=1 to n do if a[i].w=ord(s[h]) then inc(a[i].prob); {thống kê lại tần số} for i:=1 to n do a[i].code:=''; for i:=n downto 2 do {xếp lại} if a[i].prob>a[i-1].prob then begin x:=a[i];a[i]:=a[i-1];a[i-1]:=x;end; end; end. Đưa văn bản aaaaaabcdefghaahhaaaaagabghabaecdcaaadaecccccccccghaacbgbchaecbdhabdehahcghghaebcd Vào cho trình chương trình trên chạy, ta sẽ thu được bảng mã Huffman động. Để hình dung được sự thay đổi từ mã, ta in kết quả của 8 bước chạy trình, mỗi lần chạy đọc 1 chữ cái của văn bản. a 010 b 011 c 000 d 001 e 110 f 111 g 100 h 101 a 01 b 001 c 0000 d 0001 e 110 f 111 g 100 h 101 a 00 b 011 c 0100 d 0101 e 110 f 111 g 100 h 101 a 1 b 011 c 0100 d 0101 e 0010 f 0011 g 0000 h 0001 a 1 b 011 c 0100 d 0101 e 0010 f 0011 g 0000 h 0001 a 1 b 011 c 0100 d 0101 e 0010 f 0011 g 0000 h 0001 a 0 b 111 c 1100 d 1101 e 1010 f 1011 g 1000 h 1001 a 1 b 010 c 0010 d 0011 e 0000 f 0001 g 0110 h 0111 Bảng 2.4 Theo dõi kết quả in ra ta nhận thấy có sự thay đổi liên tục của bảng mã, và cũng có lúc bảng mã không thay đổi. Sử dụng các mã do trình trên tạo ra, ta có dược mã của văn bản trên là 235 bit. 0100100111111001000010110001101100101001000101111111011110001000000110001101000101000100011111011010110000000000100100010000000000001111100000101000111010010011000100010111010000110011011101110011000111001000110100011000100011010 Khi thực hiện nén và giải nén bằng mã Huffman động. Thông thường khi nén và giải nén các file, người ta sử dụng bảng chữ cái có 256 byte. Mặc dù điều này là không cần thiết. Mỗi khi gặp chữ cái mới, thì cây sẽ sinh thêm 1 nhánh cho lá ấy. Như vậy khi bắt đầu nén và giải nén cây có thể chỉ gồm 1 gốc và 1 lá. Ngoài ra nội dung của lá mới này được ghi ngay vào bản mã nén, để phục vụ cho việc giải nén. Chương 3. Mã số học 3.1. Biểu diễn nguồn. Mỗi văn bản được ứng duy nhất với một khoảng §Ó cho ®¬n gi¶n ta gäi t¾t nöa ®o¹n d¹ng [x,y) lµ kho¶ng. có độ dài bằng xác suất xuất hiện của văn bản. Văn bản dài thêm ra thì ứng với khoảng nhỏ dần. ý tưởng chung Cách biểu diễn nguồn được trình bày ở đây đúng cho mọi mô hình nguồn mà theo đó tại mọi thời điểm ta biết được chữ nào sẽ xuất hiện với xác suất Nh­ vËy ®iÒu quan träng lµ lµm thÕ nµo ®Ó lu«n cã thÓ x¸c ®Þnh ®­îc x¸c suÊt xuÊt hiÖn cña ch÷ tiÕp theo? bao nhiêu và xác suất ấy chỉ phụ thuộc vào các chữ đã xuất hiện trước đó. Chữ tiếp theo là một trong số các chữ cái của bảng chữ cái. Chữ cái đầu tiên của luồng tin S là empty. Biểu diễn empty là khoảng [0,1). Chia khoảng [0,1) ra thành các khoảng theo thứ tự tương ứng với các chữ cái của bảng chữ cái. Độ dài của các khoảng chia tương ứng với xác suất mà chữ cái ấy xuất hiện sau empty. Như vậy chữ xuất hiện tiếp theo empty sẽ là một trong số các khoảng [L(a),H(a)). Ta có thể coi khoảng [L(a),H(a)) như là khoảng [0,1) và xét kí tự xuất hiện tiếp theo. Lặp lại thao tác trên ta thu được một luồng tin S tương ứng duy nhất với khoảng [L(S),H(S)) nằm trong khoảng [0,1). Độ dài của khoảng này H(S)-L(S) bằng xác suất xuất hiện luồng tin S. Biểu diễn văn bản S thông qua khoảng [L(S),H(S)) được gọi là biểu diễn nguồn. Bất kỳ một số thực nào nằm trong khoảng [L(S),H(S)) là đủ để xác định văn bản S. Một số bất kỳ nằm trong khoảng [L(S),H(S)) được gọi là mã số học của S. Người ta thường biểu diễn số ở dạng nhị phân và mã số học của S được chọn ở dạng số nhị phân hữu hạn có độ dài nhỏ nhất có thể. Biểu diễn nguồn cho mô hình Markov. Ta xét mô hình Markov W có m trạng thái {u1, u2, .., um } với xác suất p1, p2, p3, ...., pm tương ứng và sắp xếp thứ tự cho các cạnh đi ra từ từng trạng thái kèm theo xác xuất của nó. Giả sử đi ra từ trạng thái ui là các trọng số wij (j=1,2,.., mi). Xét văn bản S = a1 a2 a3 ...., an ... trong đó a1=, a2=,.... am=, ... Ta có thể biểu diễn hình học dãy S như sau. Chia khoảng [0,1) ra làm m phần theo thứ tự D1, D2,... , Dm không giao nhau có dạng [x,y) có độ dài ứng với xác suất p1, p2, p3, ..., pm của các phần tử W. Như thế để biểu diễn trạng thái thứ nhất của dãy S thì ta chỉ việc chỉ ra đoạn con ứng với trạng thái a1, ký hiệu đó là . Để biểu diễn trạng thái tiếp theo a2, ta coi khoảng như là khoảng [0,1), sau đó tiến hành chia và chọn tương tự như với a1. Cụ thể là ta chia ra làm một số khoảng tỷ lệ với các trọng số có thể chuyển đi từ a1 theo thứ tự của các cạnh đã được định ra trước. Chọn khoảng Ì ứng với a2 trong số các khoảng con vừa chia ra được từ . Như thế khoảng có độ dài là tích của xác suất chọn a1 là và xác suất chọn a2 khi đã chọn a1 là . Tức là độ dài của là xác suất xuất hiện của phép chọn kép a1, a2. Nếu ta cứ tiếp tục kéo dài biểu diễn các phần tử của dãy S thì ta thu được khoảng biểu diễn dãy a1a2a3....an sao cho độ dài của bằng xác suất xuất hiện của văn bản a1 a2 a3... an. Phép tương ứng mỗi dãy các trạng thái ngẫu nhiên liên tiếp của nguồn trạng thái W bằng một khoảng như thế được gọi là biểu diễn số của nguồn. Trong biểu diễn số, entropy của văn bản a1a2a3....an bằng . Nhận xét rằng để xác định một khoảng như trên ta cần ch