Đồ án Kỹ thuật mã hóa Huffman với mô hình từ điển

của một từ mã khác dài hơn không. Từ mã của một kí tự được xác định như sau: Xuất phát từ nút lá tương ứng với kí tự đó, đi ngược lên theo các nhánh để đến nút gốc của cây. Trên đường đi, qua nhánh nào ta tích lũy lại giá trị của nhánh đó (0 hoặc 1). Cuối cùng, đảo ngược chuỗi bít tích lũy được ta có từ mã cần tìm. Một số tính chất của cây mã Huffman Tính chất 1. Chỉ có một con đường duy nhất đi từ nút gốc đến một nút lá của cây mã Huffman. Tính chất 2. Độ dài của thông điệp được mã hóa bằng với độ dài đường dẫn ngoại được lấy trọng (weighted external path) của cây mã Huffman. “Độ dài đường dẫn ngoại được lấy trọng” của một cây là tổng của tích tất cả các trọng lượng của các nút lá với khoảng cách tới nút gốc. Đây là một cách để xác định độ dài của thông điệp: Nó tương đương với tổng số lần xuất hiện trên tất cả các kí tự nhân với số bít của sự xuất hiện đó. Tính chất 3. Trong mọi cây có trọng lượng tương ứng giống nhau ở các nút lá thì cây Huffman có độ dài đường dẫn ngoại được lấy trọng ngắn nhất. Bất cứ một cây nào cũng có thể được cấu trúc lại bởi cùng một tiến trình mà ta đã dùng để xây dựng cây Huffman, nhưng không nhất thiết phải chọn ra hai nút có trọng lượng nhỏ nhất ở mỗi bước. Người ta có thể chứng minh được bằng qui nạp là không có chiến lược nào tối ưu hơn chiến lược nhặt ra hai nút có trọng lượng nhỏ nhất đầu tiên. Tính chất 4. Cây mã Huffman có tính chất Sibling. Một cây nhị phân mà mỗi nút được gán cho một trọng lượng được gọi là có tính chất Sibling nếu khi chúng ta liệt kê tất cả các nút trong cây theo thứ tự tăng dần (hoặc giảm 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ó. Trong cây nhị phân, trừ nút gốc ra, mọi nút còn lại đều có một nút anh em của nó (là một nút khác có cùng nút cha). Theo thuật toán xây dựng cây mã Huffman, ta thấy cây Huffman chính là một cây nhị phân có tính chất sau: nếu liệt kê tất cả các nút lá và nút nhánh theo thứ tự từ trái qua phải (hoặc từ phải qua trái) và từ dưới lên trên thì các nút sẽ tuân theo thứ tự giảm dần (hoặc tăng dần) của trọng lượng. Ví dụ, với cây mã trên ta có: I(1) D(1) R(1) ©(2) B(2) ©(3) A(3) ©(5) (Dấu © kí hiệu cho một nút nhánh). Như vậy, cây mã Huffman có tính chất Sibling. Tính chất này sẽ giúp ta cập nhật và xây dựng lại cây mã Huffman động sau này. Ví dụ minh họa : Giả sử cần mã hóa chuỗi “SEAMSTRESS”. Ta có bảng tần suất như sau: Kí tự Số lần xuất hiện Tần suất S 4 0.4 E 2 0.2 A 1 0.1 M 1 0.1 T 1 0.1 R 1 0.1 Trước hết, ta sắp xếp danh sách các nút theo trật tự tăng dần của trọng lượng: 0.1 A 0.1 M 0.1 T 0.1 R 0.2 E 0.4 S Tiếp theo, chọn ra hai nút “tự do” có trọng lượng nhỏ nhất, đó là A và M. Nút cha của hai nút này được tạo ra, có trọng lượng bằng tổng trọng lượng hai nút con, tức là bằng 0.1 + 0.1 = 0.2 và được thêm vào danh sách các nút. Hai nút con A và M được đánh dấu là “đã xét”: S 0.2 0 1 0.1 A 0.1 M 0.1 T 0.1 R 0.2 E 0.4 S Danh sách các nút “tự do” bây giờ là: T, R, E, S và nút có trọng lượng 0.2 vừa được tạo ra. Hai nút tiếp theo được chọn trong số các nút “tự do” là T và R (vì chúng có trọng lượng nhỏ nhất). Nút cha của hai nút này được tạo ra, có trọng lượng bằng 0.1 + 0.1 = 0.2. Đánh dấu “đã xét” cho hai nút T và R: 0.1 A 0.1 M 0.1 T 0.1 R 0.2 E 0.2 0 1 0.2 0 1 0.4 S Quá trình tiếp tục như trên với hai nút “tự do” có trọng lượng nhỏ nhất 0.2: 0.4 0 1 0.1 A 0.1 M 0.1 T 0.1 R 0.2 E 0.2 0 1 0.2 0 1 0.4 S Lúc này còn lại 3 nút “tự do”, trọng lượng của chúng là 0.4, 0.2 và 0.4. Tiếp tục chọn ra hai nút có trọng lượng nhỏ nhất trong số chúng (nút cha tạo ra sẽ có trọng lượng 0.6): 0.6 0 1 0.4 0 1 0.1 A 0.1 M 0.1 T 0.1 R 0.2 E 0.2 0 1 0.2 0 1 0.4 S Xử lý tương tự cho hai nút “tự do” cuối cùng”, và ta sẽ có cây mã Huffman mã hóa cho chuỗi trên là: 1.0 0 1 0.6 0 1 0.4 0 1 0.1 A 0.1 M 0.1 T 0.1 R 0.2 E 0.2 0 1 0.2 0 1 0.4 S Từ cây mã, ta nhận được từ mã cho mỗi kí tự trong chuỗi: Kí tự Mã Huffman S 11 E 10 A 000 M 001 T 010 R 011 Và chuỗi bit mã mã hóa cho chuỗi trên là: 111000000111010011101111 Lưu ý rằng, hình dáng cây mã có thể khác đi (và do vậy, từ mã của mỗi kí tự sẽ khác đi) nếu như trong quá trình xây dựng cây mã, ở một bước nào đó ta có nhiều khả năng lựa chọn hai nút “tự do” có trọng lượng nhỏ nhất. Chẳng hạn, xét tiến trình trên tại thời điểm như sau: 0.4 0 1 0.1 A 0.1 M 0.1 T 0.1 R 0.2 E 0.2 0 1 0.2 0 1 0.4 S Đến đây, ta có hai khả năng chọn hai nút tự do có trọng lượng nhỏ nhất. Giả sử ta chọn khả năng khác với khả năng ở trường hợp cây mã trên: 0.6 0 1 0.4 0 1 0.1 A 0.1 M 0.1 T 0.1 R 0.2 E 0.2 0 1 0.2 0 1 0.4 S Như vậy, ta có một hình dáng khác của cây mã Huffman mã hóa chuỗi trên: 1.0 0 1 0.6 0 1 0.4 0 1 0.1 A 0.1 M 0.1 T 0.1 R 0.2 E 0.2 0 1 0.2 0 1 0.4 S Và các từ mã ứng với cây trên là: Kí tự Mã Huffman S 1 E 01 A 0000 M 0001 T 0010 R 0011 Chuỗi bit mã trong trường hợp này là: 10100000001100100111 Độ dài chuỗi bit mã mã hóa cho chuỗi “SEAMSTRESS” trong hai trường hợp đều bằng 24 (bits). Phương pháp giải mã Huffman tĩnh Do mã Huffman có tính tiền tố (prefix) nên quá trình giải mã tương đối đơn giản: Xuất phát từ gốc của cây và tuần tự đi theo các nhánh tương ứng với bit mã nhận được (0/1) cho đến khi gặp được một nút lá. Khi đó, kí tự ứng với nút lá sẽ được đưa vào bộ đệm. Lưu ý rằng, quá trình giải mã xử lý tuần tự từng bit một của luồng từ mã. Thuật toán giải mã nguồn tin đã được mã hóa bằng cây Huffman : Vào : i. Cây mã Huffman. ii. Luồng từ mã. Ra : Nguồn tin trước khi được mã hóa. Bước 1. Khởi tạo con trỏ p trỏ đến gốc của cây Huffman. Bước 2. Trong khi chưa kết thúc luồng từ mã, lặp lại các bước sau: Đặt b là bit tiếp theo trong luồng từ mã. If b=1 then Đặt p trỏ đến nút con phải của nó. Else Đặt p trỏ đến nút con trái của nó. If (p trỏ đến một nút lá) then i. Đưa kí tự tương ứng với nút lá vào vùng đệm. ii.Cho p trỏ đến nút gốc của cây. Ví dụ: Với luồng từ mã 111000000111010011101111 mã hóa cho chuỗi “SEAMSTRESS” trên, dựa vào cây mã tương ứng, quá trình giải mã sẽ như sau: 111000000111010011101111 S E A M S T R E S S thời gian Xuất phát tại nút gốc, bit đầu tiên của luồng từ mã được xử lý là bit 1, do đó ta rẽ sang nhánh phải (nếu bít là 0, rẽ sang nhánh trái), bắt gặp một nút nhánh nên ta đọc một bit mã tiếp theo, bit này là 1, ta tiếp tục rẽ sang nhánh phải. Đến đây, ta bắt gặp một nút lá, nó chứa kí tự S. Đưa kí tự này vào vùng đệm. Như vậy, từ mã của kí tự S đã được xử lý. Quay về lại nút gốc, ta tiếp tục xử lý các bít mã kế tiếp một cách tương tự cho đến khi kết thúc luồng từ mã. Cần nhớ là sau khi bắt gặp một nút lá thì ta lại quay về gốc. Rõ ràng, để khôi phục chính xác nguồn số liệu gốc, bộ phận giải mã phải biết trước bộ từ mã đã được sử dụng hoặc là cấu trúc của cây mã. Như vậy, cấu trúc của cây mã hoặc bộ từ mã phải được gởi đi cùng với số liệu đã được mã hóa. Ưu và nhược điểm của phương pháp mã hóa Huffman tĩnh với mô hình thống kê Ưu điểm Xử lý khá tốt độ dư thừa phân bố kí tự. Quá trình mã hóa và giải mã tương đối đơn giản. Cho mã có độ dài tối ưu. Hạn chế Giải quyết kém hiệu quả đối với các loại độ dư thừa khác (chẳng hạn như độ dư thừa vị trí). Tốn nhiều thời gian xây dựng cây mã. Cấu trúc của cây mã hoặc bộ từ mã đã dùng để mã hóa phải được gởi đi cùng với số liệu đã được mã hóa. Điều này làm giảm hiệu suất nén. CHƯƠNG III CÁC PHƯƠNG PHÁP NÉN THEO MÔ HÌNH TỪ ĐIỂN Các phương pháp nén sử dụng mô hình thống kê mà chúng ta đã biết thực hiện việc nén bằng cách mã hóa mỗi lúc một kí hiệu đơn thành từ mã có độ dài ngắn hơn so với kí hiệu ban đầu. Hiệu quả nén tăng hay giảm phụ thuộc vào việc phát triển mô hình. Mô hình không những phải dự đoán chính xác xác suất xuất hiện của các kí hiệu mà còn phải dự đoán được các xác suất lệch khỏi giá trị trung bình. Tuy nhiên, các thuật toán nén chính thống dựa trên mô hình từ điển lại sử dụng một kỹ thuật hoàn toàn khác để nén số liệu. Các kỹ thuật nén kiểu này không mã hóa các kí hiệu đơn bằng các từ mã có độ dài thay đổi mà mã hóa các chuỗi kí hiệu có độ dài thay đổi bằng các thẻ bài (token). Các thẻ bài này dùng để ánh xạ vào một từ điển. Nếu mã của các thẻ bài này ngắn hơn chuỗi kí hiệu mà chúng thay thế thì hiệu ứng nén xảy ra. Ở nhiều khía cạnh, phương pháp nén dựa trên mô hình từ điển là dễ hiểu đối với mọi người. Nó khá giống với cách mà những người lập trình hay áp dụng: lập chỉ mục cho cơ sở dữ liệu để dễ dàng truy xuất những lượng dữ liệu lớn. Trong cuộc sống thường nhật, chúng ta vẫn thường bắt gặp các số điện thoại, mã bưu cục mã hóa cho những chuỗi văn bản lớn hơn. Đó chính là nguyên tắc mã hóa dựa trên mô hình từ điển. Để hình dung rõ hơn về phương pháp nén này, ta hãy xét một ví dụ điển hình sau: Giả sử, chúng ta muốn nén chuỗi “The token form an index to a phrase dictionary”. Chúng ta sẽ sử dụng cuốn từ điển “The English Vietnamese Dictionary” (dày 1680 trang, 165.000 mục từ ) của nhà xuất bản Văn hóa thông tin (1999) như một khóa để mã hóa thông tin. Sơ đồ mã hóa mà ta áp dụng dưới đây gồm một bảng tra cứu đơn giản theo dạng: Như vậy, chuỗi trên sẽ được mã hóa thành: 1462/5 1489/20 528/12 37/11 691/10 1487/9 1/1 1029/1 361/17 Chẳng hạn, thẻ bài 1462 / 5 sẽ mã hóa cho từ thứ 5 của trang 1462, tức là chữ “The”. Bây giờ, chúng ta đi tính số bít cần thiết để mã hóa một từ. Mỗi từ có thể ở trong một trang bất kỳ trong số 1680 trang, vậy cần tối đa 11 bits để mã hóa (bởi vì 210 < 1680 < 211) ; mỗi trang có nhiều nhất là 60 mục từ, vậy cần tối đa 6 bits để mã hóa (bởi vì 25< 60 < 26 ). Như vậy, chúng ta cần nhiều nhất 17 bits để mã hóa một từ bất kỳ có trong từ điển. Với ví dụ trên, ta cần tất cả 9x17=153 bits » 19 bytes để mã hóa cho 9 từ. Trong khi đó, nếu dùng mã ASCII thì ta cần đến 46x8 = 368 bits = 46 bytes để biểu diễn. Như vậy, khi mã hóa theo mô hình từ điển, ta đã giảm kích thước của chuỗi đi gần 60%, một con số đáng kể. Trong ví dụ trên, chúng ta đã sử dụng sơ đồ để làm cho việc mã hóa các cụm từ trở nên đơn giản và hiệu quả hơn. Sơ đồ đó chính là một nền tảng quan trọng trong phương pháp nén dựa trên mô hình từ điển. i. Mô hình từ điển tĩnh và mô hình từ điển động Một cách tổng quát, kỹ thuật nén dựa vào mô hình từ điển thay thế các chuỗi kí tự trong nguồn số liệu bằng các thẻ bài (token). Nếu số bit để mã hóa thẻ bài nhỏ hơn số bít của chuỗi thì hiệu ứng nén xảy ra. Tuy vậy, định nghĩa này vẫn còn để ngỏ nhiều vấn đề, chẳng hạn như, chúng ta sẽ xây dựng và duy trì từ điển như thế nào trong quá trình nén hoặc giải nén. Trong vài trường hợp, nếu ta dùng một từ điển đã được xây dựng sẵn để mã hóa nguồn tin thì sẽ rất thuận lợi. Nếu nguồn tin cần được mã hóa là một cơ sở dữ liệu chứa các đăng kí mua phần mềm, chúng ta có thể xây dựng từ điển chỉ chứa vài trăm hạng mục tập trung vào các cụm từ như “Microsoft”, “Windows”, “Office”, “Server”,...Và một khi từ điển đã được biên dịch, nó có thể được lưu giữ một cách trực tiếp và được sử dụng cho cả hai quá trình mã hóa và giải mã khi cần thiết. Một từ điển kiểu như thế gọi là từ điển tĩnh. Nó được xây dựng trước khi quá trình nén xảy ra, và bất biến trong khi dữ liệu đang được nén. Từ điển kiểu tĩnh có nhiều ưu điểm và tất nhiên cũng có những hạn chế. Ưu điểm lớn nhất của nó là có thể làm cho từ điển “thích ứng” với kiểu dữ liệu đem nén. Chẳng hạn, với cơ sở dữ liệu vừa nêu trên, ta có thể mã hóa chuỗi “Windows” bằng ít bit và cấp nhiều bit hơn cho chuỗi “Unix”. Đối với mô hình nén thích ứng, từ điển không thể điều chỉnh trước, bởi vì nó chỉ được phát sinh (và liên tục biến đổi) trong quá trình mã hóa. Điều này có vẻ như là một nhược điểm lớn, nhưng nén theo mô hình từ điển tĩnh cũng gặp phải một vấn đề là làm thế nào để chuyển từ điển từ bộ mã hóa đến bộ giải mã. Tuy nhiên, ở một số trường hợp, từ điển tĩnh có thể không cần chuyển đi cùng với dữ liệu nén nếu như nó đã được duy trì sẵn trong bộ giải mã. Hoặc trong trường hợp luồng dữ liệu vào có kích thước lớn, từ điển có thể được chuyển đi kèm mà không làm tỉ số nén giảm đi nhiều. Mô hình thích ứng (còn gọi là mô hình động) Nhìn chung, hiệu quả của sơ đồ nén theo mô hình từ điển tĩnh phụ thuộc vào từng ứng dụng cụ thể. Do vậy, mô hình từ điển thích ứng được ứng dụng nhiều hơn trong thực tế. Thay vì dùng một từ điển đã định nghĩa trước, ở đây, mô hình thích ứng lại làm việc theo một cơ chế khác, đó là: lúc bắt đầu nén, mô hình thích ứng xuất ra một từ điển tham chiếu ngầm định hay một từ điển rỗng. Khi quá trình nén phát sinh, mô hình thích ứng sẽ thêm một chuỗi mới vào từ điển để sử dụng lại sau này như một thẻ bài đã được mã hóa. Nguyên tắc làm việc của mô hình động có thể minh họa bằng đoạn chương trình giả lập dưới đây : for ( ; ; ) { word = get_word( input_file ); /* lấy một chuỗi từ luồng nhập */ dictionary_index = look_up ( word, dictionary ); /* tìm chuỗi ở từ điển theo chỉ mục*/ if (dictionary_index < 0 ) { /* không tìm thấy chuỗi */ output( word, output_file ); /* xuất chuỗi ra file đích*/ add_to_dictionary( word, dictionary ); /* thêm chuỗi vào từ điển */ }else /* tìm thấy chuỗi*/ output( dictionary_index, output_file ); /*xuất chỉ mục của chuỗi ra file đích*/ } Nếu đề mục của từ điển được dùng ở đây được mã hóa như một chỉ số nguyên trong một bảng thì quá trình nén có thể thực hiện với một thuật toán đơn giản qua các bước sau: Phân tích luồng dữ liệu vào thành các đoạn để tra từ điển. Tra từ điển đối với các đoạn đã được phân tích. Thêm các chuỗi mới vào trong từ điển. Mã hóa văn bản gốc và các chỉ mục của từ điển sao cho có thể phân biệt chúng với nhau. Quá trình giải mã có một vài điểm khác biệt so với các bước trên, nó không cần phân tích cú pháp luồng vào thành các đoạn và cũng không kiểm tra các phân đoạn ngõ vào gắn với từ điển. Thay vào đó, nó thực hiện theo các bước sau: Giải mã luồng vào thành chỉ mục từ điển hoặc văn bản gốc. Thêm các chuỗi mới vào từ điển. Biến đổi chỉ mục của từ điển thành cụm từ. Xuất các cụm từ. Thực tế cho thấy, các tác vụ trên được thực hiện với chi phí tương đối thấp về tài nguyên hệ thống. Điều đó làm cho các kĩ thuật nén dựa trên mô hình từ điển ngày càng trở nên phổ biến. Năm 1989, hãng Stac Electronic đã cài đặt thành công thuật toán nén theo mô hình từ điển trên một chip. Thuật toán này sau đó đã nhanh chóng trở thành một chuẩn công nghiệp và được sử dụng rất rộng rãi. Phương pháp nén này thường được gọi là QIC-122. QIC-122 là một ví dụ điển hình về cách thức làm việc của thuật toán nén cửa sổ trượt, là một thuật toán nén dựa trên mô hình từ điển. Nó dựa vào phương pháp nén cửa sổ trượt LZ77. Khi các kí hiệu được bộ mã hóa đọc vào, chúng được bổ sung vào cuối một bộ đệm (gọi là cửa sổ) có kích thước 2KB để tạo thành từ điển. Để mã hóa một kí hiệu hoặc một chuỗi kí hiệu, bộ mã hóa tiến hành kiểm tra xem kí hiệu hoặc chuỗi kí hiệu đó có mặt trong từ điển hay không, nếu có, nó sẽ tạo ra một thẻ bài (token) để xác định vị trí và độ dài của cụm từ theo từ điển, nếu không, kí hiệu sẽ được phát đi ở dạng không mã hóa. Đầu ra của bộ mã hóa QIC-122 là một luồng số liệu, bao gồm các thẻ bài và các kí hiệu không mã hóa xen lẫn nhau. Một bit cờ được gắn vào trước mỗi thẻ bài hay mỗi kí hiệu chỉ báo rằng phần dữ liệu đi sau nó là một tham chiếu đến từ điển hay là một kí hiệu bình thường. Khuôn dạng của hai dãy đó là: Văn bản gốc: Tham chiếu từ điển: Cơ chế làm việc của bộ mã hóa QIC-122 có thể thấy qua đoạn chương trình giả lập dưới đây: while ( ! out_of_symbols ) { length = find_longest_match( &offset ); if ( length > 1 ) { output_bit ( 0 ); length = find_longest_match( &offset ); output_bits( offset ); output_bits( length ); shift_input_buffer( length ); } else { output_bit( 1 ); output_byte( buffer[ 0 ] ); shift_input_buffer( 1 ); } } ii. Các phương pháp nén Lempel và Ziv [2] Tháng 3/1977, Jacob Ziv và Abraham Lempel đã công bố tài liệu “A Universal Algorithm for Sequential Data Compression” trong “IEEE Transactions on Information Theory”. Tiếp đó, vào năm 1978, họ lại công bố “Compression of Individual Sequences via Variable-Rate Coding”. Đó là những nghiên cứu mới nhất về phương pháp nén dựa trên mô hình từ điển động vào lúc ấy. Chúng đã khởi đầu cho một thời kỳ phát triển mạnh mẽ của các kỹ thuật nén theo mô hình từ điển cho hiệu quả nén cao. Hai kỹ thuật nén được giới thiệu trong các tài liệu trên gọi là LZ77 (Lempel-Ziv 1977) và LZ78 (Lempel-Ziv 1978). II.1. Phương pháp nén LZ77 LZ77 là phương pháp nén sử dụng kỹ thuật cửa sổ trượt (sliding window). Từ điển là một tập hợp các cụm từ có chiều dài cố định được tìm thấy trong một cửa sổ khi nhìn vào văn bản đã được xử lý trước đó. Cửa sổ có kích thước từ 2KB đến 16 KB, chứa các cụm từ có độ dài tối đa từ 16 bytes đến 64 bytes. LZ77 sẽ thay thế các chuỗi có độ dài biến động ở luồng số liệu vào bằng các con trỏ có kích thước cố định ánh xạ vào từ điển để tạo nên hiệu ứng nén. Cấu trúc dữ liệu chính của LZ77 là một cửa sổ văn bản. Cửa sổ này được chia làm hai phần: phần đầu tiên chứa một khối lớn văn bản đã được xử lý trước đó; phần thứ hai, thông thường nhỏ hơn rất nhiều, là một bộ đệm “nhìn thấy trước” (look-ahead buffer) chứa các kí tự được đọc vào từ luồng nhập nhưng chưa được mã hóa. Kích cỡ bình thường của cửa sổ là khoảng vài ngàn kí tự. Trong khi đó, bộ đệm được tạo nhỏ hơn nhiều, có thể chứa từ 10 đến 100 kí tự. Thuật toán luôn luôn tiến hành so khớp (match) nội dung của bộ đệm “nhìn thấy trước” với một chuỗi nào đó trong từ điển. Một ví dụ đơn giản thể hiện như hình dưới đây: for ( i=0 ; i<MAX -1 ; i++ )\r for ( j = i+1 ; j<MAX ; j++ )\r Thân của cửa sổ trượt Bộ đệm Một cửa sổ trượt được sử dụng Cửa sổ trượt trong LZ77 Hình 9. Hình vẽ trên là một đoạn mã nguồn C được đem nén. Cửa sổ trượt có độ dài tổng cộng là 64 bytes, với 16 bytes trong đó được sử dụng bởi bộ đệm. Mỗi thẻ bài gồm có ba hạng mục dữ liệu dùng để xác định một cụm từ với độ dài thay đổi chứa trong bộ đệm hiện tại. Đó là: Vị trí của cụm từ trong cửa sổ. Chiều dài cụm từ. Kí tự đầu tiên ở bộ đệm theo sau cụm từ đó. Ở ví dụ trên, bộ đệm bao gồm cụm kí tự “. Chương trình nén thực hiện thuật toán LZ77 phát ra thẻ bài đầu tiên, sau đó dịch chuyển (trượt) cửa sổ sang phải năm kí tự ( là độ dài cụm từ vừa được mã hóa, kể cả kí tự theo sau ). Năm kí tự mới được đọc vào bộ đệm, và quá trình lặp lại như trên. i=0 ; i<MAX -1 ; i++ )\r for ( j = i+1 ; j<MAX ; j++ )\r a[i] Thân của cửa sổ trượt Bộ đệm Cửa sổ sau khi mã hóa Hình 10. Thẻ bài tiếp theo được phát ra bởi thuật toán nén sẽ mã hóa cụm kí tự “;j+” (bao gồm cả kí tự theo sau) thành . Cú pháp của thẻ bài này cho phép mã hóa cả những cụm từ không xuất hiện trong cửa sổ. Nếu bộ đệm chỉ ra sự không so khớp (ví dụ, nó có thể mã hóa một kí tự đơn lẻ không có mặt trong cửa sổ tại một thời điểm như là cụm từ có độ dài zero: ) thì phương pháp này không hiệu quả, bởi vì để mã hóa một kí tự phải cần đến ba loại thông tin. Tuy nhiên, phải thấy rằng, thuật toán có thể mã hóa mọi chuỗi kí tự. Giải thuật mã hóa của LZ77 là tương đối đơn giản. Nó cho phép xem xét xuyên suốt toàn bộ cửa sổ trượt với sự so khớp tối đa, mã hóa và sau đó chuyển đổi. Thuật toán giải nén cũng khá đơn giản, bởi vì nó không thực hiện những việc so sánh. Nó đọc vào một thẻ bài, xuất ra cụm từ xác định, đưa ra kí tự theo sau, dịch chuyển và lặp lại. Nó duy trì cửa sổ, nhưng không làm việc so sánh chuỗi. Một hiệu ứng phụ tích cực của phương pháp giải nén là nó có thể sử dụng cụm từ chưa được mã hóa để mã hóa cụm từ đã có. Trong một nguồn tin có 100 kí tự “A” liên tiếp, ví dụ, chúng ta có thể mã hóa kí tự “A” đầu tiên là . Lúc này, cửa sổ sẽ như hình dưới: ...................................................................AAAAAAAAAAA Mã hóa cho 100 kí tự ‘A’ liên tiếp nhau Hình 11. Chúng ta có thể mã hóa chín kí tự “A” kế tiếp là (giả sử kích thước của cửa sổ trượt là 38). Điều đó có vẻ như là sử dụng một cụm từ có chín kí tự. Mặc dù chúng ta có thể thấy tám kí tự trong cụm từ là có mặt ở bộ đệm. Khi bộ phận giải mã nhận được thẻ bài , bộ đệm sẽ như hình dưới: ...................................................................A Vị trí so khớp bộ đệm Bộ đệm khi bộ phận giải mã nhận được thẻ bài Hình 12. Nhưng nếu xem xét thuật toán giải nén, ta sẽ thấy cách thức nó tiến hành thủ thuật này. Sau khi kí tự đầu tiên được sao chép, bộ đệm sẽ như sau: ...................................................................AA Vị trí so khớp + i bộ đệm + i Bộ đệm sau khi sao chép kí tự đầu tiên Hình 13. Qua vòng lặp kế tiếp, chín kí tự “A” sẽ được sao chép, mặc dù chúng không có mặt trong cửa sổ khi bắt đầu tiến hành giải mã. Sau khi hoàn tất việc sao chép, kí tự đơn tiếp theo sẽ được đọc vào, và bộ đệm sẵn sàng chuyển dịch như hình sau: ...................................................................AAAAAAAAAAA Vị trí so khớp + i bộ đệm + i Bộ đệm khi sẵn sàng chuyển dịch Hình 14. Ví dụ này cho thấy điểm mạnh của phương pháp nén LZ77: thích ứng nhanh chóng với số liệu đầu vào. Ở ví dụ trên, nó mã hóa một loạt mười kí tự khi mà từ điển của nó chỉ chứa một kí tự đơn. Một vấn đề lớn xuất hiện bên trong LZ77. Đó là, khi mã hóa nó phải so sánh chuỗi kí tự trong bộ đệm với tất cả các vị trí của cửa sổ trượt. Nếu sử dụng một cửa sổ nhỏ để lưu trữ các chuỗi đã được xem xét trước đó, thuật toán sẽ liên tục bỏ qua những thay đổi ở ngõ vào của từ điển, bởi vì nó trượt nhanh qua phần từ điển. Như vậy, để tăng tỷ số nén, ta phải tăng kích thước của cửa sổ trượt. Điều này sẽ dẫn đến hai bất lợi chính. Thứ nhất, chúng ta sẽ tốn một số bit nhiều hơn để mã hóa cho một thẻ bài. Chẳng hạn, khi tăng kích cỡ của cửa sổ từ 4KB lên 64KB, chúng ta sẽ cần 16 bits thay vì 12 bits để mã hóa vị trí trong cửa sổ, và cần 10 bits thay vì 4 bits để mã hóa cho độ dài cụm từ trong bộ đệm nếu kích thước bộ đệm tăng từ 16 bytes lên 1KB. Như vậy, ta cần đến 26 bits thay cho 16 bits để mã hóa một cụm từ. Thứ hai, việc tăng thông số trên sẽ làm cho thời gian nén trong CPU tăng lên đáng kể. Với LZ77, nếu tăng kích thước cửa sổ trượt từ 4KB lên 64KB thì thời gian tìm kiếm chuỗi sẽ tăng lên 16 lần, vì mọi chuỗi trong cửa sổ đều được so sánh với bộ đệm. Tình thế bất lợi chỉ thực sự phát sinh khi tăng kích cỡ bộ đệm, bởi vì thời gian chạy sẽ tăng tỉ lệ với chiều dài bộ đệm. Chương trình sẽ chạy chậm đi khoảng 64 lần nếu tăng dung lượng của bộ đệm từ 16 bytes lên 1024 bytes. Tuy nhiên, mặt tích cực là quá trình giải mã sẽ không chịu hậu quả của việc tăng kích thước cửa sổ trượt lẫn bộ đệm. Quá trình giải mã chỉ tiến hành sao chép lại những cụm từ, không thực hiện việc tìm kiếm chuỗi nên tốc độ thực hiện nhanh hơn. Một vấn đề nữa là khi cụm từ / kí tự ở bộ đệm không tìm thấy trong từ điển. Khi đó, chương trình nén vẫn sử dụng đúng ba loại thông tin liên hệ chỉ để mã hóa một kí tự. Để thấy được sự lãng phí này, giả thiết rằng kích thước cửa sổ trượt là 4KB và bộ đệm là 16 bytes, như vậy cần 12 bits để mã hóa vị trí trong cửa sổ, 4 bits để mã hóa cho chiều dài chuỗi. Nghĩa là khi mã hóa thẻ bài dạng phải cần đến 24 bits mà tất cả chỉ để mã hóa cho một kí tự 8 bit. Đó là một cái giá quá lớn phải trả. Vì những hạn chế nói trên, hai tác giả Lempel và Ziv đã cải tiến LZ77 và đưa ra phương pháp nén LZ78. II.2. Phương pháp nén LZ78 LZ78 từ bỏ khái niệm về một cửa sổ trượt. Trong LZ77, từ điển được định nghĩa là một cửa sổ có kích thước cố định của những đoạn văn bản được đọc vào trước đó. Nhưng với LZ78, từ điển là một danh sách không có giới hạn của những cụm từ đã được xem xét trước đó. LZ78 cũng có một vài điểm tương đồng với LZ77. LZ77 xuất ra một loạt các thẻ bài, mỗi thẻ bài gồm có ba thành phần: . LZ78 cũng xuất ra một loạt các thẻ bài với ý nghĩa tương tự. Mỗi thẻ bài của LZ78 bao gồm: . Không giống như LZ77, chiều dài của chuỗi được chọn không được chuyển đi vì bộ giải mã biết được điều đó. Một điểm khác biệt nữa so với LZ77 là LZ78 không có một cửa sổ đầy những chuỗi được đọc sẵn để sử dụng như một từ điển. Thay vào đó, LZ78 tạo ra một cụm từ mới tại mỗi thời điểm một thẻ bài được xuất ra và cập nhật cụm từ đó vào từ điển. Sau khi cụm từ đã được cập nhật, nó có thể sẽ được bộ mã hóa sử dụng tại một thời điểm bất kỳ trong tương lai chứ không chỉ ở vài ngàn kí tự kế tiếp. Khi sử dụng thuật toán LZ78, cả bộ mã hóa và giải mã đều khởi động với một từ điển gần như trống rỗng. Theo định nghĩa, từ điển chỉ có một xâu đã được mã hóa, đó là xâu rỗng. Mỗi khi một kí tự được đọc vào, nó sẽ được thêm vào chuỗi hiện tại. Chừng nào mà chuỗi hiện hành còn so khớp với một cụm từ nào đó trong từ điển, quá trình này vẫn tiếp tục. Nhưng cuối cùng sẽ đến lúc chuỗi hiện hành không khớp với xâu đã có trong từ điển. Đây là lúc LZ78 xuất ra một thẻ bài và một kí tự. Cần nhớ rằng, chuỗi đã có một sự so khớp trong từ điển cho đến khi kí tự cuối cùng được vào. Vì vậy, chuỗi hiện tại được xem như là sự so khớp cuối cùng cho đến khi một kí