Tài liệu Nén văn bản tiếng việt theo huffman

i ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG PHẠM THU HƯỜNG NÉN VĂN BẢN TIẾNG VIỆT THEO HUFFMAN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2013 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG PHẠM THU HƯỜNG NÉN VĂN BẢN TIẾNG VIỆT THEO HUFFMAN Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: PGS.TS Nguyễn Hữu Điển Thái Nguyên - 2013 ii LỜI CẢM ƠN Để đạt được kết quả ngày hôm nay l à một sự cố gắng, nỗ lực rất lớn của bản thân, cũng như sự giúp đỡ nhiệt tình của quý thầy cô, bạn bè để tôi hoàn thành luận văn này. Tôi xin trân trọng cảm ơn: - PGS.TS Nguyễn Hữu Điển – Giám đốc Trung tâm tính toán hiệu năng cao Trường Đại học khoa học tự nhiên Hà Nội. - Các thầy cô trong hội đồng phản biện. Cuối cùng tôi xin chân thành cảm ơn các thầy, cô, các bạn đã động viên và giúp đỡ tôi trong thời gian làm luận văn. Xin trân trọng cám ơn quý thầy cô, các bạn!. iii DANH MỤC CÁC HÌNH Hình 1. Quy trình nén dữ liệu .............................................................................. 3 Hình 2. Xây dựng cây nhị phân từ bảng mã không ở dạng tiền tố ...................... 8 Hình 3. Sắp xếp danh sách các ký tự ................................................................... 20 Hình 4. Xây dựng cây Huffman ........................................................................... 22 Hình 5. Cây Huffman điền đầy đủ thành phần .................................................... 22 Hình 6. Một trường hợp xây dựng khác ............................................................... 23 Hình 7. Lưu đồ giả i mã ........................................................................................ 24 Hình 8. Ý tưởng xây dựng cây theo phương pháp Shannon – Fano ................... 26 Hình 9. Xây dựng cây theo phương pháo Shannon-Fano .................................... 27 Hinh 10. Mã hóa bằng phương pháp Huffman động .......................................... 31 Hình 11. Giải mã bằng phương pháp Huffman động ......................................... 33 Hình 12. Quá trình thực hiện nén bằng LZ ......................................................... 43 Hình 13. Sơ đồ nén LZ 78 .................................................................................... 47 Hình 14. Sơ đồ giải nén LZ78 ............................................................................. 48 Hình 15. Sơ đồ nén LZW .................................................................................... 51 Hình 16. Sơ đồ giải nén LZW ............................................................................. 54 Hình 17. Phương pháp MTF ( tốt ) ...................................................................... 57 Hình 18. Phương pháp MTF ( xấu) ...................................................................... 57 Hình 19. Phương pháp BW tìm chuỗi sau mã hóa............................................... 59 Hình 20. Hai cách tìm chuỗi gốc.......................................................................... 60 Hình 21. Giao diện chương trình ........................................................................ 62 iv MỤC LỤC LỜI CẢM ƠN .......................................................................................................... iii DANH MỤC CÁC HÌNH ....................................................................................... iv MỞ ĐẦU ....................................................................................................................1 1. Đặt vấn đề ...........................................................................................................1 2. Đối tượng và phạm vi nghiên cứu .....................................................................1 2.1. Đối tượng .....................................................................................................1 2.2. Phạm vi ........................................................................................................2 3. Hướng nghiên cứu của đề tài ............................................................................2 4. Phương pháp nghiên cứu ..................................................................................2 5. Ý nghĩa khoa học của luận văn ........................................................................2 CHƯƠNG 1: TỔNG QUAN VỀ CÔNG NGHỆ NÉN DỮ LIỆU .........................3 1.1. Sơ lược về nén dữ liệu .....................................................................................3 1.1.1. Khái niệm về nén dữ liệu ........................................................................3 1.1.2. Những vấn đề phải giải quyết trong nén dữ liệu ..................................4 1.1.3. Phân loại chương trình nén ....................................................................5 1.1.4. Đánh giá chất lượng của chương trình nén ..........................................6 1.2. Mã nén dữ liệu ................................................................................................7 1.2.1. Định nghĩa mã hoá ..................................................................................7 1.2.2. Các khái niệm về ký tự mã hóa..............................................................8 1.2.3. Mã tổng và mã phân tách .....................................................................13 1.2.4. Định lý mã nén.......................................................................................18 CHƯƠNG 2. MỘT SỐ MÃ NÉN CƠ BẢN ..........................................................21 2.1. Mã hóa Huffman (Huffman coding) ...........................................................21 2.1.1. Phương pháp mã hóa ............................................................................21 2.1.2. Thuật toán tạo mã Huffman ................................................................21 2.1.3. Giải mã thuật toán Huffman : .............................................................25 2.2. Mã hóa Huffman động ( Adaptive Huffman coding ) .................................31 2.2.1. Phương pháp mã hóa: ...........................................................................31 2.2.2. Thuật toán nén .......................................................................................31 2.2.3. Thuật toán giải nén ...............................................................................33 2.3. Thuật toán xử lý sự lặp lại của xâu (RLE) ..................................................36 v 2.3.1. Phương pháp: ........................................................................................36 2.3.2. Thuật toán tạo mã .................................................................................36 2.3.3. Quá trình giải mã ..................................................................................36 2.4. Mã hóa kiểu từ điển (Dictionary -based compression).................................39 2.4.1. Nguyên lý LZ .........................................................................................39 2.4.2.Từ điển ....................................................................................................40 2.4.3. Quá trình thực hiện khi nén bằng mã LZ ...........................................41 2.4.4. Các thuật toán nén LZ ..........................................................................42 2.5. Một số phương pháp biến đổi (transform) ...................................................54 2.5.1. Phương pháp đẩy về phía trước (Move to front): ..............................54 2.5.2. Phương pháp Burrows – Wheeler (BW): ...........................................56 CHƯƠNG 3. XÂY DỰNG CHƯƠNG TRÌNH NÉN TIẾNG VIỆT SỬ DỤNG PHƯƠNG PHÁP MÃ HÓA HUFFMAN ..............................................................59 3.1. Bộ gõ Tiếng việt .............................................................................................59 3.2. Quy ước biểu diễn ký tự tiếng Việt. ..............................................................59 3.3. Chuẩn dấu Tiếng việt....................................................................................60 3.3.1. Unicode...................................................................................................60 3.3.2. TCVN3 ...................................................................................................60 3.3.3. VNI .........................................................................................................60 3.4. Phương pháp mã hóa Huffman ...................................................................60 3.5. Giới thiệu chương trình ................................................................................61 3.5.1. Hướng dẫn sử dụng...............................................................................62 3.5.2. Kết quả kiểm thử chương trình ...........................................................64 KẾT LUẬN ..............................................................................................................65 TÀI LIỆU THAM KHẢO ......................................................................................66 PHỤ LỤC .................................................................................................................67 vi MỞ ĐẦU 1. Đặt vấn đề Một trong những chức năng chính của máy tính là xử lý dữ liệu và lưu trữ. Bên cạnh việc xử lý nhanh, người ta còn quan tâm đến việc lưu trữ được nhiều dữ liệu nhưng lại tiết kiệm được vùng nhớ và giảm chi phí lưu trữ . Về mặt lý thuyết thì các thiết bị lưu trữ là không có giới hạn nhưng ngày nay do nhu cầu xử lý nhiều tập tin, nhiều loại dữ liệu trong cùng một tệp do vậy mà kích thước tệp trở nên khá lớn . Những vấn đề trên nảy sinh ra khái niệm nén dữ liệu, nén dữ liệu là quá trình làm giảm lượng thông tin “dư thừa” trong dữ liệu gốc, do vậy lượng thông tin thu được sau nén thường nhỏ hơn dữ liệu gốc rất nhiều. Nén dữ liệu là giải pháp hợp lý nhất nhằm mục đích giảm chi phí cho người sử dụng. Như chúng ta cũng đã biết tiếng Việt là một ngôn thuộc hệ thống chữ cái Latin sử dụng nhiều dấu đi kèm với nguyên âm. Với bảng m ã ASCII 8 bit sử dụng phổ biến trên máy tính, chúng ta có thể mã hóa 256 ký tự. Để đưa tiếng Việt vào máy tính, các phần mềm tiếng Việt hiện nay sử dụng một trong hai phương pháp mã hóa : mã dựng sẵn hoặc mã tổ hợp để xây dựng trang mã ký tự tiếng Việt . Bảng mã phổ biến nhất chúng ta thường sử dụng là bảng mã Unicode để thể hiện tiếng Việt. Nhưng bảng mã Unicode yêu cầu 16 bit để thể hiện một ký tự điều này sẽ dẫn đến sự lãng phí và dư thừa dữ liệu. Vì vậy, “ Nén văn bản tiếng Việt theo Huffman ” được em chọn làm luận văn tốt nghiệp của mình. 2. Đối tượng và phạm vi nghiên cứu 2.1. Đối tượng − Các phần mềm nén dữ liệu; − Các thuật toán nén dữ liệu; − Các phương pháp mã hóa tiếng Việt; − Hệ thống phần mềm nén dữ liệu từ đó ứng dụng vào để nén dữ liệu cho tiếng Việt. 1 2.2. Phạm vi − Các khái niệm của ký tự mã hóa, các thuật toán của nén văn bản. Kiến trúc, chức n ãng và các thành phần của nén dữ liệu cụ thể cho bài toán nén văn bản Tiếng việt sử dụng phương pháp mã hóa Huffman. − Các chức nãng chính và quy trình thực thi của bài toán nén dữ liệu; − Hệ thống chương trình cho bài toán nén dữ liệu; Vì thời gian có hạn, trong khuôn khổ một luận văn tốt nghiệp cao học, việc giải quyết bài toán nén dữ liệu chỉ giới hạn ở một vài thuật toán nén cổ điển. 3. Hướng nghiên cứu của đề tài − Tìm hiểu tổng quan về nén dữ liệu và nghiên cứu một thu ật toán nén cụ thể − Tìm hiểu bài toán nén dữ liệu, tiến hành phân tích; − Thu thập các số liệu có liên quan; − Phân tích, đánh giá thông qua các số liệu thu thập được; − Cài đặt thực nghiệm. 4. Phương pháp nghiên cứu − Nghiên cứu các tài liệu và viết tổng quan; − Phương pháp khảo sát thực tế; − Phương pháp phân tích và đánh giá các thuật toán; − Nghiên cứu triển khai thu ật toán và thử nghiệm hệ thống. 5. Ý nghĩa khoa học của luận văn − Bản thân hiểu sâu hơn và áp dụng được các thuật toán của nén dữ liệu vào thực tế; − Triển khai một số thuật toán nén dữ liệu qua đó ứng dụng chính là phương pháp mã hóa Huffman vào tiếng Việt; − Xây dựng được chương trình nén dữ liệu dành cho tiếng Việt trên máy tính. 2 CHƯƠNG 1: TỔNG QUAN VỀ CÔNG NGHỆ NÉN DỮ LIỆU 1.1. Sơ lược về nén dữ liệu 1.1.1. Khái niệm về nén dữ liệu Nén là một quá trình giảm lượng không gian cần thiết để biểu diễn cùng một lượng thông tin cho trước. Người ta còn gọi nén là biến đổi một luồng ký hiệu thành một luồng các từ mã. Quá trình nén như sau: Văn bản Mô hình Mã hoá Bản mã Hình 1. Quy trình nén dữ liệu Trong đó: - Văn bản là văn bản ban đầu cần nén. - Mô hình là tập hợp các chữ cái cùng quy tắc được sử dụng để xử lý các chữ cái vào và đưa ra các từ mã. Một mô hình sẽ xác định chính xác xác suất xuất hiện của từng chữ cái và một bộ mã sẽ tạo ra các từ mã dựa trên xác suất đó. - Mã hoá là chỉ quá trình thay thế các chữ cái trong văn bản ban đầu bằng các từ mã tương ứng để đưa ra bản mã chính xác. Như vậy, quá trình nén diễn ra như sau: quá trình mô hình căn cứ vào văn bản cần nén sẽ tạo ra các từ mã. Sau đó, từ bộ từ mã vừa tạo được và văn bản ban đầu quá trình nén sẽ đưa ra bản mã. 3 Mã hoá và mô hình là hai giai đoạn hoàn toàn khác nhau vì trong giai đoạn mô hình có rất nhiều cách để xử lý các chữ cái của văn bản mà cùng sử dụng một phương pháp xây dựng mã để cho ra các từ mã. Nếu bản mã có kích thước nhỏ hơn văn bản thì phương pháp nén đó có hiệu quả. Ví dụ : Chúng ta sử dụng cùng phương pháp mã Huffman cho hai mô hình khác nhau: - Mô hình 1: dựa trên xác suất độc lập của từng chữ cái xuất hiện bất kì trong văn bản. - Mô hình 2: cần tính được xác suất phụ thuộc dựa trên những chữ cái nhận được lúc đó trong văn bản. Do mô hình khác nhau nên cùng sử dụng mã Huffman để đưa ra từ mã nhưng hiệu quả nén của chún g rất khác nhau. Tuy nhiên, chúng ta vẫn quen dùng từ mã hoá để chỉ cho cả quá trình nén văn bản mặc dù đó chỉ là một giai đoạn của một quá trình nén. Người ta thường mã hoá thông qua các từ mã của một bảng chữ cái nào đó. Có thể có nhiều thuật toán nén dữ liệu khác nhau. Mỗi thuật toán có một kiểu dữ liệu nhất định và cùng một số modem có đặc điểm nén thích ứng có nghĩa là chúng có khả năng chọn thuật toán nén thích hợp phụ thuộc vào kiểu dữ liệu cần nén. Trong số các cách mã thì cách nào mã ngắn hơn chúng ta nói là nó nén tốt hơn (so với cách mã khác). 1.1.2. Những vấn đề phải giải quyết trong nén dữ liệu Mục tiêu của nén dữ liệu là đưa ra thuật toán để giảm thiểu sự l ãng phí từ những phần giống nhau khi biểu diễn dữ liệu. Thông th ường một chương trình né n cần quan tâm đến khả n ãng nó có thể cẳt triết được nhiều hay ít dung lư ợng của dữ liệu sau khi nén, điều này còn phụ thuộc vào thuật toán, và điều kiện đầu vào của dữ liệu. Nh ư vậy những dữ liệu đầu vào khác nhau có thể đòi hỏi những thuật toán khác nhau để nhận diện nhậy nhất những chỗ tiêu sài lãng phí bộ nhớ. Cần nhận ra 4 các đặc trư g riêng của từng tập dữ liệu, để từ đó sáng tạo ra thuật toán phù hợp đặc biệt dành riêng cho loại dữ liệu này. Đầu vào của quá trình nén có thể là đoạn văn bản, hình ảnh, â m thanh, hay là những đoạn b ãng dưi dạng số. Kết quả của quá trình nén là đư ra những tệp có kích thưc nhỏ nhất có thể mà khi khôi phục lại dữ liệu, phải được dữ liệu chính xác. Bất kỳ một chương trình nén nào cũng phải đi đôi với chưng trình giải nén, bởi khi dữ liệu ở dạng nén, nó bị áp dụng nhiều quy tắc biểu diễn tiết kiệm mới, không dễ dàng để có thể hiểu đư c ngay khi đọc. Dữ liệu sau quá trình nén có thể đư c coi là ở dạng m ã hóa. Trên thực tế, có rất nhiều tình huống phải sử dụng đến chưng trình giải nén nhiều hơn chương trình nén. Ví dụ như dữ liệu nặng đ ược tải về từ các trang web trên mạng, một ngườ i đưa thông tin lên, và có vô số người nhận thông tin, muốn sử dụng được thì cần phải giải nén. 1.1.3. Phân loại chương trình nén Trên thực tế, những phần mềm nén, hoặc hệ điều hành th ường được hợp thành bởi nhiều kiểu nén. Dựa vào dữ liệu sau khi đ ược giải nén, so sánh với dữ liệu đầu vào của quá trình nén, có thể chia thành nén bảo toàn và nén không bảo toàn. Một chương trình được gọi là nén bảo toàn khi nó có thể dựng lại được dữ liệu nguyên gốc từ dữ liệu đã được nén. Trong thực tế, nén bảo toàn đ ược dùng đối với các loại dữ liệu quan trọng: các bức ảnh thuộc về ngành sinh học, y tế như bức ảnh tế bào bệnh, văn bản chữ viết, những phần mềm,... Một ch ương trình đ ược gọi là nén không bảo toàn khi nó không có khả nãng dựng lại nguyên mẫu dữ liệu ban đầu từ dữ liệu đ ã qua quá trình nén. Nén không bảo toàn thường được áp dụng để nén ảnh, đoạn b ãng. Dựa vào khả nãng cập nhật thông số cho thuật toán trong quá trình mã hóa và giải mã, có thể chia ra 2 loại: nén tĩnh (static compression) và nén động (adaptive compression). Nén tĩnh: các quy luật, dữ liệu vào của thuật toán không bị thay đổi trong suốt quá trình nén và giải nén. Nén động: các quy luật hoặc dữ li ệu vào của thuật toán được cập nhật thường xuyên, có thể lại đ ược cập nhật bằng chính những dữ liệu vừa mới ra. (Một số chương trình nén động đ ược xây dựng từ những dữ liệu khởi đầu là trắng) Nếu như một chương trình nén và giải nén đ ược thực hiện với các thao tác 5 đồng nhất nh ư nhau thì thuật toán mã hóa được gọi là cân đối (symmetric) và ng ược lại thì đ ược gọi là không cân đối (non – symmetric /asymmetric). Cãn cứ độ dài ký tự tr ước và sau nén, cũng có thể chia thuật toán dùng để nén dữ liệu ra các kiểu sa u: Fixed to fixed: độ dài biểu diễn trên máy tính của từng ký tự phải đều bằng nhau, và khi được nén, độ dài biểu diễn m ã của các ký tự cũng phải bằng nhau; Fixed to variable: những ký tự trước khi nén thì đều có độ dài nh ư nhau, nhưng những ký tự đã được nén sẽ có độ dài không cân đối t ương đồng nhau nữa; Variable to fixed: những dãy ký tự có độ dài khác nhau sau khi đ ược nén, trở thành những dãy ký tự có độ dài bằng nhau; Variable to variable: các chuỗi ký tự trước khi nén và sau khi nén có độ dài khác nhau, không nhất thiết phải t ương ứng theo đúng t ỷ lệ. 1.1.4. Đánh giá chất lượng của chương trình nén Hiệu quả của một thuật toán nén đ ược đánh giá thông qua lượng dữ liệu mà nó có thể giúp tiết kiệm đ ược không gian lưu trữ của bộ nhớ. Không nên đánh giá hiệu quả một thuật toán bằng cách công nghiệp dập khuôn, bởi khả nãng của một chương trình nén còn phụ thuộc rất nhiều vào dữ liệu ban đầu, dữ liệu ấy có thể chứa hay không chứa những kiểu dư thừa mà thuật toán đào sâu xử lý. Trong nén bảo toàn, có thể đo hiệu quả của chương trình nén bằng sự hao hụt giữa kích thước dữ liệu đầu vào và kích thước dữ liệu đầu ra. Từ đó, có thể xét tới một vài thông số được định nghĩa sau: - Tỷ lệ nén (compression ratio): Là Tỷ lệ củ a kích thước sau nén và kích thước trước nén. - Thừa số nén (compression factor): Là nghịch đảo của Tỷ lệ nén. - Mức độ hao hụt (saving percentage): Là Tỷ lệ của độ chênh lệch 2 kích thước với kích thước ban đầu. Ngoài ra, còn một số tiêu chí cần đánh giá trên thuật toán: độ phức tạp của thuật toán, thời gian thực hiện nén và giải nén, số lượng bit nhị phân trung bình ít nhất biểu diễn ký tự m ã hóa trung bình (entropy), sự dư thừa của bảng ch ữ sau khi được mã hóa (redundancy), … 6 1.2. Mã nén dữ liệu 1.2.1. Định nghĩa mã hoá Định nghĩ a 1.2.1.1. Mã hoá Mã hoá dữ liệu X theo bộ mã M là phép ánh xạ 1:1 biến đổi một ký hiệu x i  X thành một tổ hợp các ký hiệu của bộ mã M. Dữ liệu X = {x 1, x2, …, xn} Bộ mã M = {m 1, m2, …, mk} Trong đó, k là cơ số của bộ mã. Nếu k = 2 là mã nhị phâ n, k = 10 là mã thập phân, k = 16 là mã thập lục phân. Nếu x i được mã hoá thành: xi ↔ mr1mr2…mrl Khi đó mr1mr2…mrl được gọi là từ mã để mã hoá x i. Ở đây l là số ký hiệu của bộ mã dùng để biểu diễn x i, l được gọi là độ dài từ mã. Ví dụ: Dữ liệu X = {x 1, x2, x3, x4} Bộ mã nhị phân M = {0, 1} Mã hoá x1 = 00, x2 = 01, x3 = 10, x4 = 11. Ta gọi tắt phép ánh xạ 1:1 để mã hoá dữ liệu X ở trên là mã. Định nghĩa 1.2.1.2. Mã văn bản Bảng chữ cái là một tập hợp Σ = {a 1, a2, a3, ..., am}. Mỗi phần tử a i của nó được gọi là chữ cái hay kí tự. Nếu bảng chữ cái chỉ có hai chữ cái thì chúng ta gọi các chữ cái là bít và ký hiệu là 0/1. Văn bản là một dãy gồm các chữ cái của một bảng chữ cái. Số lượng các chữ cái được gọi là độ dài của văn bản. Cho A và B là các tập hợp văn bản . Một song ánh f : f:A→B x  f(x) = y 7 Chúng ta gọi f là ánh xạ mã các văn bản trong tập A thành các văn bản trong tập B. Nếu tập B gồm các văn bản được tạo ra từ các bít 0/1 thì chúng ta gọi loại ánh xạ mã này là mã nhị phân. Các văn bản trong tập B được gọi là bản mã, còn văn bản được ngầm hiểu là các văn bản trong tập A. Trong các phần sau đây chúng ta chỉ sử dụng mã nhị phân. 1.2.2. Các khái niệm về ký tự mã hóa 1.2.2.1. Bít trung bình Chúng ta thường dùng trình nén để nén các file, tức là các văn bản được tạo ra từ 256 byte. Nén một file nhiều lần liên tiếp thì đến một lúc nào đó chúng ta cũng sẽ thu được một file mà trình nén này không thể thu nhỏ lại được nữa. Bởi vì, nếu không chúng ta sẽ nén được file ấy xuống thành một file không có bít nào cả. Từ đó, chúng ta có khẳng định: Với mọi thuật toán mã các file văn bản luôn tồn tại một văn bản mà nó không thể nén được thành file có dung lượng nhỏ hơn. Từ khẳng định trên suy ra không thể vạch định ra được một gianh giới rõ rà ng giữa một bên là mã hoá và một bên là mã nén. Để đánh giá khả năng nén của một thuật toán chúng ta đưa ra khái niệm về số bít trung bình cần thiết để ghi lại một chữ cái của văn bản. Định nghĩa 1.2.2.1. Bít trung bình Tỷ số giữa độ dài của bản mã chia ch o số các chữ cái của văn bản được gọi là bít trung bình cho một chữ cái của văn bản, hay còn gọi tắt là bít trung bình (hay bít trung bình cho từng chữ cái). Ký hiệu An là tập các văn bản có độ dài n tạo ra từ các chữ cái a 1, a2, ..., am. Giả sử chúng ta có một cách mã nào đó mà văn bản  An có bản mã dài L() bit.  P( ) L( ) Khi đó chúng ta định nghĩa bít trung bình của cách mã đó là giá trị trong đó P() là xác suất của văn bản . 8   An n , Trong một ngôn ngữ nhất định, mỗi văn bản  xuất hiện với xác suất P() nào đó. Trong định nghĩa trên chúng ta gặp một khó khăn là làm thế nào để biết được P(). Về nguyên tắc thì xác suất này là phụ thuộc vào người sử dụng văn bản. Văn bản nào hay được dùng hơn thì có xác suất xuất hiện lớn hơn, văn bản nào ít đ ược dùng hơn thì có xác suất xuất hiện nhỏ hơn. Như vậy định nghĩa này bao hàm ý tưởng, để có thể nén được tốt hơn thì một văn bản cần phải được mã nén không phụ thuộc vào văn bản ấy dài hay ngắn mà là phụ thuộc theo xác suất mà người ta sử dụng nó. Tuy nh iên có một thực tế là phần lớn các văn bản lưu trữ trong kho rất ít khi được sử dụng. Như vậy thì rất khó để xác định được xác suất sử dụng các văn bản một khi chúng ta chưa hề hoặc rất ít khi được sử dụng. Nhu cầu nén dữ liệu buộc chúng ta phải suy nghĩ vấn đề này dưới góc độ khác hơn. Việc một văn bản được sử dụng như thế nào, nhiều hay ít là phụ thuộc vào nội dung của văn bản. Như vậy cần tìm cách làm thế nào đánh giá được xác suất xuất hiện văn bản thông qua ngay chính nội dung của nó. Ký hiệu xác suất xuất hiện của các chữ cái tương ứng là p1 = p(a1), p2 = p(a2), ..., pm = p(am). Nếu văn bản = 12...n được sinh ra từ việc chọn ngẫu nhiên các chữ cái thì sẽ có xác suất xuất hiện là p() = p(1) p(2)... p(n). Tuy vậy sự đơn giản này không mang ý nghĩa thực tế lắm. Bởi vì các chữ cái trong một văn bản mà do con người tạo ra đương nhiên là phụ thuộc lẫn nhau tuân thủ theo các qui tắc tạo từ, tạo câu... Nếu sự xuất hiện của các chữ cái là phụ thuộc lẫn nhau thì xác suất p() xuất hiện văn bản = 12...n có thể sẽ không bằng p(1) p(2)... p(n). Như vậy, chúng ta phải đi xây dựng mô hình mô tả sự phụ thuộc của các chữ cái trong một văn bản với nhau như thế nào để có thể đáp ứng được cả 2 yếu tố: - Mô hình phải thể hiện được sự phụ thuộc. - Cho phép ước lượn g gần đúng xác suất xuất hiện của văn bản. 1.2.2.2. Chiều dài trung bình của bảng mã (average length) 9 Cho bảng chữ cái S= (S1, S2,…, Sn) và xác suất xuất hiện của mỗi chữ cái là P = (P1, P2,…,Pn). Các ký tự thuộc bảng chữ cái sau khi được mã hóa là C = ( C1, C2,…, Cn) với độ dài của từng ký tự là L = (l 1, l2,…, ln). Định nghĩa chiều dài trung bình của bảng mã: n l ( P, L )   p i l i i 1 1.2.2.3. Tính xác định duy nhất khi giải mã (Unique decodability) Một bảng mã được xác định duy nhất tức là chỉ có một k hả nãng để giải mã từ một bản mã hóa. Ví dụ: Cho A mã hóa bởi 0, B mã hóa bởi 1 và C mã hóa bởi 10. Như vậy khi nhận được một thông điệp là 10 sẽ có hai khả nãng để giải được mã, hoặc là C hoặc là BA, bảng mã không xác định duy nhất. 1.2.2.4. Phần đầu c ủa một ký tự mã hóa (Prefix codes) Khi hai kí tự được mã hóa có độ dài khác nhau, thì rất có thể từ có độ dài ngắn hơn sẽ là phần đầu của từ có độ dài lớn hơn. Ví dụ: Cho A mã hóa bởi 101 và B mã hóa bởi 10110, như vậy A có mã hóa chính là phần đầu của B. Một bảng mã hóa được gọi là ở dạng tiền tố nếu như không có một ký tự nào là phần đầu của ký tự khác ở trong bảng mã hóa. Ví dụ: Bảng mã sau được gọi là tiền tố ( prefix code ): (1,01,001,000). Để kiểm tra được sự rối ren này, có thể lập một cây nhị phân. Nếu như tồn tại một nút, không phải lá, mà lại có trọng số là một ký tự được mã hóa, thì ắt hẳn, nó phải là phần đầu của một ký tự khác ở tận cùng ngoài lá. Đối với ví dụ A mã 101 là tiền tố của B mã 10110, cây được xác định: 10 Hình 2. Xây dựng cây nhị phân từ bảng mã không ở dạng tiền tố Một bảng mã hóa ở dạng tiền tố thì luôn luôn cho xác định duy nhất khi giải mã. Điều ngược lại không đúng, vì tồn tại một bảng mã cho phép xác định duy nhất khi giải mã, nhưng bảng mã ấy không phải ở dạng tiền tố. Ví dụ: Cho bảng chữ cái ( A,B,C,D ), được mã hóa bởi (0,01,011,0111). Bảng mã này không phải ở dạng tiền tố vì ký tự 0 là phần đầu của các ký tự còn lại. Nhưng khi đưa ra một thông điệp được mã hóa, từ bảng này chỉ cho ra duy nhất một kết quả. Bởi vì mã 0 là mã bắt đầu của mọi chữ cái, mã 0 đánh dấu để biết được khi nào ký tự tiếp theo bắt đầu. Cho thông điệp là 0110111010 thì lúc ấy buộc phải tách được thành các nhóm: 011,0111,01,0 1.2.2.5. Số bit ít nhất biểu diễn ký tự mã hóa (self-information) Cho bảng chữ cái S= ( s1, s2,…, sn) với xác suất hiện là P= ( p 1, p2,…, pn) và i 1 pi  1.I si   log 2 n 1   log 2 pi pi I(si) được gọi là số bít ít nhất để biểu diễn s( i). Trong trường hợp đặc biệt, xác suất xuất hiện một ký tự nào đó là 1, I(si) =0. Tức là bảng chữ cái chỉ có một ký tự có thể xuất hiện, không cần phải tính toán đến số bit biểu diễn này nữa. 1.2.2.6. Số bit ít nhất biểu diễn ký tự mã hóa trung bình (entropy) Định lý: Cho S,P,I(si) như trên, định nghĩa: 11 N n I 1 i 1 H P    p I I si    pi log 2 1 pi H(P): số bit trung bình ít nh ất để biểu diễn được bảng chữ cái mã hóa. Định lý: Với những bảng mã tiền tố có chiều dài các ký tự mã hóa trung bình là l  1 pi li (li xây dựng dựa trên điều kiện số bit ít nhất biểu diễn ký tự mã hóa – n self-information) ta có H P   l  H P   1 . Chứng minh: a. Chứng minh H P   l n   1 n 1  pi li   pi  log 2 l i log 2 2  pi i 1 pi i 1   n H P   l   pi log 2 i 1 n n    1 1   pi  log 2 l i log 2 2 l   pi  log 2 pi pi 2li i 1   i 1  n  1   pi log 2 e log 2 pi 2li i 1     n  1   log 2 e pi ln pi 2li i 1  Vì ln x  x  1 nên n n  1   n 1   n 1  H P   l  log 2 e pi   1  log 2 e  li   pi   log 2 e  li  1 i 1 i 1  i 1 2   i 1 2   pi 2li  Theo bất đẳng thức Kraft-McMillan cho bảng mã ở dạng t iền tố: n n 1 1  1  1  0   li li i 1 2 i 1 2  Vậy, H P   l  log 2 e i 1 n  1   1  0 li 2  b. Chứng minh l  H P   1 Nếu xây dựng bảng mã dựa trên số bit ít nhất biểu diễn ký tự mã hóa ( self  information) li  log 2    1  i  1, n thì: pi  n n n   n 1 1 l   pi li   pi  log 2  1   pi log 2   pi  H P   1 pi pi i 1 i 1 i 1   i 1 1.2.2.7. Bảng mã hóa ở điều kiện tốt nhất Cho S, P, I(si), l , H(P) như trên, định nghĩa: 12 E P, L   H P   100% l E(P,L) là hiệu suất của bảng mã. Hiệu suất đạt 100% thì bảng mã ở điều kiện tốt nhấ t ( Chiều dài trung bình của bảng mã đạt được mứ c bằng số bit ít nhất biểu diễn ký tự mã hóa trung bình ). 1.2.3. Mã tổng và mã phân tách 1.2.3.1. Mã tổng Định nghĩa 1.2.3.1.1. Văn bản tổng Cho A và B là hai văn bản. Tổng của A + B là một văn bản mới thu được từ A viết tiếp B vào bên phải của A. Như vậy độ dài của tổng các văn bản là tổng của các độ dài của chúng.  +  =  Định nghĩa 1.2.3.1.2. Mã tổng Một mã được gọi là mã tổng nếu như bản mã của tổng các văn bản là tổng các bản mã. v¨n b¶n  +  =  b¶n m· 1001010 + = 111000 1001010111000 Trong định nghĩa cho mã tổng ta đã sử dụng khái niệm “tổng của các văn bản”. Nếu bản mã của văn bản “a” là f(a), của văn bản b là f(b) thì bản mã của “ab” là “f(a)f(b)”, bản mã của “ba” là “f(b)f(a)”. Xét mã tổng trên bảng chữ cái Σ = {a 1, a2, ...., am}. Mỗi chữ cái a 1, a2, ..., am có từ mã tương ứng. Từ mã của các chữ cái xác định ánh xạ f : Σ → M, từ tập các chữ cái vào tập các xâu bít “0/1”. Như vậy với mọi a i Σ, xâu bít f(ai) là từ mã của a i, độ dài xâu bít f(ai) được ký hiệu là (ai). Theo định nghĩa mã tổng thì xâu các chữ cái = 12...n tương ứng duy nhất với xâu bít có dạng f() = f(1)f(2)...f(n). Bản mã f() có độ dài n L()=  (i ) bit. i 1 13 Định lý 1.2.3.1.1. Nếu f : Σ → M là mã tổng xác định trên bảng chữ cái Σ = {a 1, a2, ...., am}, mà mỗi chữ cái a1, a2, ..., am có xác suất xuất hiện tương ứng là p1, p2, ..., pm thì: 1. Bít trung bình cho một chữ cái của hầu hết các văn bản có n chữ cái  = n 12...n thoả mãn lim  ( ) i i 1 n  n m   p j (a j ) , ở đây () là độ dài từ mã j 1 của chữ cái   Σ.  P( ) L( ) 2. Bít trung bình của mã   An n m =  p j ( a j ) j 1 Trong đó P() = p(1)p(2)...p(n) là xác suất xuất hiện văn bản  và L( ) là độ dài bản mã của nó. 1.2.3.2. Mã phân tách Từ đây chúng ta chỉ đề cập đến các mã tổng n hị phân. Nếu các từ mã có độ dài định thì ta luôn giải mã được. Nhưng nếu độ dài của từ mã thay đổi thì không cố phải với cách mã nào cũng có thể giải mã được. Xét cách mã sau: a -> 100 b -> 1000 c -> 0 Bản mã của “ac” và b đều là dãy bít “1000”. Như vậy k hi nhận được chuỗi bít 1000 chúng ta không thể biết được rằng văn bản ban đầu là “b” hay là “ac”. Điều kiện quan trọng của việc tạo mã là cho phép khi nhận được bản mã, chúng ta phải tách ra được thành các thành phần cơ bản là các từ mã và cách tách này phải là duy nhất và đúng đắn. Tính phân tách được đưa ra dưới đây sẽ đảm bảo cho điều này. Định nghĩa 1.2.3.2.1. Cho A và B là hai đoạn tạo ra từ các bít 0/1. Chúng 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 1.2.3.2.2. Một tập hợp M tạo ra từ các đoạn bít 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ý 1.2.3.2.1. 14