Đề tài Nén số liệu bằng kỹ thuật Mã hóa Huffman với Mô hình thống kê

CHƯƠNG 1 MỞ ĐẦU Giới thiệu về đề tài Trong thời đại ngày nay với sự phát triển mạnh mẽ của khoa học công nghệ thông tin, việc ứng dụng Tin học hầu như đã vào trong tất cả mọi lĩnh vực hoạt động sản xuất của con người ở các nước phát triển trên thế giới. Ở nước ta, nhằm góp phần vào công cuộc Công nghiệp hoá-hiện đại hoá đất nước, vấn đề Tin học hoá đã và đang được triển khai. Việc ứng dụng Tin học vào công tác quản lý và điều hành tại các cơ quan xí nghiệp ngày càng cao và đem lại hiệu quả. Bên cạnh đó, đồng nghĩa với nó là vấn đề lưu trữ và xử lý dữ liệu. Cùng với thời gian, sự cập nhật, lưu trữ dữ liệu ngày càng nhiều, điển hình là một số cơ quan hành chính nhà nước như: chi cục thống kê của các tỉnh, thành phố, trung ương... với một khối lượng lớn dữ liệu cần lưu trữ. Vì vậy, vấn đề được đặt ra là làm sao lưu trữ dữ liệu ít tốn kém nhất mà vẫn đảm bảo tính an toàn và chính xác của nó? Do đó, việc tìm ra phương pháp giảm dung lượng lưu trữ mà vẫn đáp ứng được yêu cầu trên là rất cần thiết. Chúng ta thấy rằng: ngày nay với sự phát triển vượt trội trong công nghệ phần cứng, dung lượng đĩa cứng tăng lên một cách đáng kể và nhanh chóng. Một loạt đĩa cứng không ngừng tăng lên về dung lượng ra đời trong khi giá thành sản phẩm lại hạ. Bên cạnh đó còn có các thiết bị lưu trữ khác như băng từ, đĩa quang...cũng được sử dụng rộng rãi. Tuy nhiên, cũng chính vì lý do này mà các nhà lập trình thường sử dụng bất cứ tài nguyên nào có thể, kết quả là nhiều sản phẩm phần mềm ra đời nhưng có kích thước rất lớn, chiếm hàng trăm Mbyte. Thêm vào đó, nhiều lĩnh vực sản xuất áp dụng những phần mềm khác nhau, để đáp ứng được nhu cầu này đòi hỏi người sử dụng tiếp cận nhiều hơn và tạo thói quen lưu trữ nhiều sản phẩm phần mềm, ngoài ra là việc xử lý nhiều tập tin và nhiều loại dữ liệu khác nhau. Do vậy, nén dữ liệu vẫn là vấn đề cần thiết được thực hiện trước khi lưu trữ. Song song với vấn đề trên, một lĩnh vực không thể không kể đến là mạng máy tính. Ngày nay, mạng máy tính mà mọi người đều nhắc đến là mạng Internet -mạng của các mạng- Có thể nói rằng: Internet là mạng thông tin toàn cầu và số người kết nối vào mạng đã lên đến vài chục triệu người. Vì vậy, nhu cầu truyền thông rất lớn. Tất cả mọi người đều muốn có thể tìm kiếm thông tin bất luận chúng ở đâu, đều muốn chia sẻ thông tin, thiết bị với người khác hoặc quản lý thông tin và thực hiện toàn bộ các tác vụ này một cách nhanh chóng, dễ dàng với độ an toàn chính xác cao. Ngoài ra, hiện nay ở nước ta nhằm đáp ứng nhu cầu trao đổi thông tin giữa các cơ quan nhà nước, việc xây dựng Mạng Hành chính Quốc Gia đã được kết nối thông suốt từ năm 1997, dẫn đến vấn đề truyền thông bằng văn bản Tiếng việt càng tăng. Do đó, bên cạnh việc cải tiến phần cứng như: Modem, đường truyền... ta còn phải tìm cách giảm dung lượng dữ liệu cần thiết trước khi truyền để giảm được thời gian truyền và bộ nhớ. Đối với mạng Internet, thực hiện tốt điều đó cho phép giảm được cước phí truy cập mạng. Vậy nén dữ liệu là gì? Ta có thể khái quát: Nén là quá trình giảm dung lượng nhớ cần thiết mà vẫn biểu diễn cùng một dữ liệu cho trước. Trong truyền thông số liệu, nén là một kỹ thuật được áp dụng một cách linh hoạt cho luồng thông tin đang truyền. Công nghệ bên trong về cơ bản cũng như nhau trong cả hai trường hợp là: loại bỏ thông tin dư thừa hoặc biểu thị thông tin dưới dạng chặt chẽ hơn để giảm tổng số byte phải truyền qua phương tiện truyền thông nhằm giảm đến thấp nhất thời gian chiếm phương tiện của một cuộc truyền đã cho. Đối với nén dữ liệu trên máy PC, có nhiều thuật toán nén khác nhau được thiết kế cho nhiều loại dữ liệu khác nhau như: văn bản, hình ảnh, âm thanh... Trong phạm vi của đồ án, ta chỉ xét đến các phương pháp nén văn bản. Nén văn bản là biểu diễn lại lượng thông tin sao cho có kích thước nhỏ hơn ban đầu và một yêu cầu không thể thiếu là dữ liệu của tập tin gốc phải luôn luôn được khôi phục lại hoàn toàn chính xác vì đối với loại văn bản này, sự mất mát thông tin dù chỉ một bit là điều không thể chấp nhận được. Hiện nay, có nhiều phương pháp nén văn bản khác nhau trong đó ta sẽ xét đến phương pháp nén Huffman. Là một trong những phương pháp nén ra đời sớm nhất và đã thành công trong lưu trữ máy tính và viễn thông, phương pháp này thích hợp với kiểu dữ liệu văn bản. Tư tưởng chính của phương pháp như sau: Thay vì lưu trữ mỗi ký hiệu là 8 bit (mã ASCII), dựa vào xác suất (tần suất xuất hiện) của mỗi ký hiệu mà ta sẽ biểu diễn ít bit đối với ký hiệu có xác suất cao và nhiều bit để biểu diễn ký hiệu có xác suất thấp. Ví dụ ta có luồng dữ liệu là :AABBAADCCC, với mỗi ký hiệu được lưu trữ bình thường là 8 bit thì ta phải mất 8x10=80 bit, trong khi đó với phương pháp mã hoá Huffman dựa vào xác suất xuất hiện: A= 4/10, C=3/10,B=2/10,D=1/10, giả sử ta biểu diễn cho ký hiệu A là 1 bit, C là 2 bit, B là 3 bit, D là 4 bit thì chỉ tốn lượng bit là: 1x4+2x3+3x2+4x1=20 bit. Như vậy, ta đã tiết kiệm được 60 bit lưu trữ. Trong phạm vi đồ án, ta sẽ xét đến các phần sau: Phương pháp mã hoá Huffman với Mô hình thống kê tĩnh bậc 0 Phương pháp mã hoá Huffman với Mô hình thống kê động bậc 0 Phương pháp mã hoá Huffman với Mô hình thống kê động bậc 1 So sánh hiệu suất nén giữa các mô hình với nhau So sánh hiệu suất nén giữa phương pháp mã hoá Hufman với các phương pháp nén khác trên thị trường. Tuy nhiên cần nói thêm rằng, ở đây ta chỉ xét đến mô hình ký tự trong khi các phương pháp nén hiện có ở thị trường được thực hiện trên mô hình từ điển nên hiệu suất nén của phương pháp mã hoá trên mô hình ký hiệu sẽ thấp hơn. Do đó, mục đích của đồ án là tìm hiểu các kỹ thuật nén không tổn hao nói chung và chủ yếu là kỹ thuật nén số liệu theo phương pháp mã hoá Huffman với mô hình ký tự. Từ mô hình thống kê động bậc 0 sẽ nâng cấp lên mô hình thống kê động bậc 1 để từ đó cho thấy được hiệu suất nén của một kỹ thuật nén phụ thuộc như thế nào vào mô hình hoá?, so sánh giữa phương pháp mã hoá Huffman tĩnh và Huffman động. Với các vấn đề trên, ta sẽ trình bày chi tiết trong các chương tiếp theo. Y Cấu trúc đồ án : Gồm có 6 chương Chương 1: - Giới thiệu đề tài - Nêu lên mục đích ý nghĩa của đề tài - Khái quát một số lý thuyết tổng quan về nén số liệu Chương 2: Giới thiệu và nên lên nội dung của một bài toán nén số liệu tổng quát, so sánh một số loại mã thống kê tối ưu. Chương 3: Làm rõ bài toán nén số liệu theo phương pháp nén Huffman với mô hình thống kê tĩnh và động bậc 0 Chương 4: Xây dựng cấu trúc dữ liệu và giải thuật cho chương trình nén theo phương pháp Huffman với mô hình thống kê tĩnh và động bậc 0. Cải tiến nâng cấp lên mô hình thống kê động bậc 1. Chương 5: Trình bày các kết quả thực nghiệm, so sánh tỉ số nén, tốc độ nén, tốc độ giải nén đối với các chương trình nén đã được thương mại hoá. Chương 6: Kết luận, nêu lên ưu nhược điểm của phương pháp nén Huffman. Định hướng phát triển của đồ án. Lý thuyết tổng quan về nén số liệu: Khái niệm về nén số liệu Nén số liệu là quá trình làm giảm số liệu cần thiết để biểu diễn cùng một lượng thông tin cho trước. Các kỹ thuật nén số liệu có thể được thực hiện bằng phân cứng chuyên dụng hoặc phần mềm. Các kỹ thuật nén số liệu bằng phần cứng đòi hỏi phải có các phần cứng đặc biệt được thiết kế thích hợp với băng thông cố định của mạng truyền số liệu. Các kỹ thuật nén số liệu bằng phần mềm được thực hiện trên máy tính cá nhân (PC) có thể dùng nén file văn bản, các file ảnh được nhập vào từ scaner hoặc camera và các file âm thanh. Trong khái niệm về nén, ta cần phân biệt giữa số liệu và thông tin. Số liệu (data) dùng để biểu diễn và truyền tải thông tin (information), cùng một lượng thông tin cho trước ta có thể biểu diễn bằng các lượng số liệu khác nhau. Đơn vị đo số liệu (dung lượng) là bit (binary digit). Một bit số liệu về mặt toán học được biểu diễn bằng một chữ số nhị phân 0 và 1, về mặt điện được biểu diễn bằng 1 trong 2 mức điện áp qui ước... Một bit thông tin được định nghĩa là lượng thông tin. Giả sử P là xác suất của một ký hiệu, thì lượng thông tin chứa trong ký hiệu đó được định nghĩa là -Log2P bít, công thức này chính là entropy của ký hiệu. Vậy Entropy là gì? Trong lĩnh vực lý thuyết thông tin sử dụng thuật ngữ entropy là đơn vị đo thông tin được mã hóa trong một thông điệp. Entropy của một thông điệp càng cao thì thông tin nó chứa đựng càng nhiều. Entropy của toàn bộ thông điệp là tổng entropy của các ký hiệu thành phần. Entropy phụ thuộc vào xác suất xuất hiện của ký hiệu, một ký hiệu có xác suất xuất hiện cao thì thông tin chứa đựng trong nó thấp và sẽ cần ít bít hơn để mã hóa. Các kỹ thuật nén số liệu Nén không tổn hao (Lossless Compression) Nén không tổn hao còn được gọi là nén không nhiễu (Noiseless) hay nén không lỗi (Free Error), đảm bảo không mất mát thông tin sau quá trình mã hoá và giải mã (nó tạo lại một bản sao chính xác của số liệu sau quá trình mã hoá và giải mã). Kỹ thuật này sử dụng trên những nguồn số liệu đảm bảo độ chính xác cao khi lưu trữ hoặc truyền đi như các cơ sở dữ liệu, các bảng tính điện tử, các văn bản ...Vì với các tập tin này, việc mất mát dù chỉ một bit thông tin là điều không thể được. Nén tổn hao có các phương pháp mã hoá như: phương pháp mã hoá Huffman, mã hoá số học, mã hoá LZW... Nén tổn hao (Lossy Compression) Nén tổn hao là kỹ thuật nén chấp nhận mất mát một lượng thông tin nhất định để đạt được hiệu quả nén cao. Có thể nói một cách tương tự: Nén tổn hao= Làm trơn + Nén không tổn hao. Làm trơn là quá trình thực hiện một phép biến đổi nào đó (như: biến đổi số liệu từ miền thời gian sang miền tần số bằng phép biến đổi Furiê rời rạc gọi là FFT ( Fast Fourier Transform), hoặc phép biến đổi Cosin rời rạc gọi là DCT (Discrete Cosine Transform)....), tiếp đó là quá trình lượng tử hoá. Số liệu càng được làm trơn thì mất mát thông tin càng nhiều và tỉ số nén càng cao. Nén tổn hao thích hợp với các file hình ảnh, âm thanh được số hoá. Hầu hết các kỹ thuật nén tổn hao đều có thể được điều chỉnh để cân bằng giữa độ chính xác và hiệu quả nén. Các phương pháp nén tổn hao như: phương pháp JPEG, phương pháp Wavelet, phương pháp MPEG... Một số khái niệm cơ bản Vấn đề đặt ra ở đây là có hay không một phương pháp nén tốt? Tiêu chuẩn nào để xác định điều đó? Kết quả cho thấy: Một phương pháp nén tốt khi nó có một mô hình tốt và giải quyết được độ dư thừa về dữ liệu cao. Tuy nhiên, trong thực tế hầu hết các kỹ thuật nén đều không thể xử lý được mọi độ dư thừa khác nhau. Vậy độ dư thừa dữ liệu là gì? Độ dư thừa dữ liệu ( data redundancy ) Độ dư thừa dữ liệu trong một nguồn tin căn cứ vào các yếu tố sau: Sự phân bố ký hiệu: dựa vào sự xuất hiện của các ký hiệu, trong một nguồn tin bao giờ cũng có trường hợp vài ký hiệu được sử dụng nhiều hơn những ký hiệu khác và những ký hiệu này sẽ được mã hoá ít bit hơn. Sự lặp lại của những ký hiệu: Khi các ký hiệu được lặp đi lặp lại nhiều lần liên tiếp nhau, tập tin được mã hoá một cách cô đọng hơn bằng cách chỉ lưu các thuộc tính: số ký hiệu được lặp lại và mã hoá các ký hiệu đó. N hững mẫu sử dụng mật độ cao: Sự tuần tự của những ký hiệu nào đó sẽ tái xuất hiện với tần suất xuất hiện tương đối cao do vậy nó sẽ được mã hoá ít bít hơn những ký hiệu có tần suất xuất hiện thấp. Độ dư thừa vị trí: Nếu những ký hiệu nào đó xuất hiện ở một vị trí có thể dự đoán trước một cách phù hợp trong mỗi một khối dữ liệu. Chẳng hạn, một ảnh lưới chứa một hàng dọc và hàng dọc đó xuất hiện như một vật trong cùng một vị trí ở dòng khác nhau. Khi đó ta có thể mã hoá một cách cô đọng hơn bằng cách giữ vị trí của hàng và cột đó thay vì giữ từng ký hiệu trong cột. Công thức biểu diễn bằng Toán học về độ dư thừa số liệu: RD = 1 - Trong đó: N1: Kích thước file vào,N2: Kích thước file ra, R D: độ dư số liệu tương đối. Nghĩa là: N1 và N2 là lượng số liệu trong hai tập số liệu cùng được dùng để biểu diễn một lượng thông tin cho trước và CN thường được gọi là tỷ số nén: CN = Ta có các trường hợp sau: N1 = N2 thì CN =1 và RD = 0 có nghĩa là so với tập số liệu thứ hai thì tập số liệu thứ nhất không chứa số liệu thừa. Khi N2 << N1 , CN tiến tới vô cùng và RD tiến tới 1 có nghĩa là độ dư thừa số liệu tương đối của tập số liệu thứ nhất là khá lớn hay tập số liệu thứ hai đã được nén khá nhỏ. Tỷ số nén Tỷ số nén là một đại lượng đặc trưng cho một phương pháp nén. Muốn biết một kỹ thuật nén là cao hay thấp người ta căn cứ vào tỷ số nén mà nó đã đạt được để đánh giá. Tỷ số nén được biểu diễn bằng công thức toán học. Có 2 cách định nghĩa như sau: CN = (1) (trong đó CN, N1, N2: đã được định nghĩa trong mục II.3.1) Theo công thức trên, nếu CN càng thấp thì hiệu suất nén càng cao và ngược lại CN = 1- (2) ; nếu CN càng cao thì tỷ số nén càng cao và ngược lại Trong đồ án, ta sẽ tính tỷ số nén theo (2) Độ dài trung bình của từ mã Độ dài trung bình của một từ mã là giá trị trung bình thống kê của tất cả các từ mã trong một bộ mã. Độ dài trung bình của một từ mã không thể nào nhỏ hơn Entropy của nguồn số liệu được mã hoá. Như vậy, một bộ mã tối ưu (có hiệu suất nén cao) là bộ mã có độ dài trung bình của một từ mã gần với Entropy của nguồn số liệu. Các yếu tố của kỹ thuật nén số liệu Số liệu truyền đi trên một kênh thông tin có thể được xem như là một chuỗi các ký hiệu S1, S2, . . . Sn , các ký hiệu đó thuộc một tập ký hiệu nào đó (có thể là một tập vô hạn) chẳng hạn: Tập hợp các chữ số nhị phân : 0, 1; tập hợp các chữ số thập phân : 1, 2, 3 .. Tập hợp các ký hiệu Alphabet : A, B, C ... X, Y, Z ... Tập hợp các từ của một ngôn ngữ. Do vậy có thể nói các kỹ thuật nén số liệu được sử dụng từ trước cho đến nay đều dựa vào một trong các đặc trưng sau : Tính hữu hạn của tập ký hiệu. Tần số xuất hiện tương đối của các ký hiệu. Ngữ cảnh xuất hiện của các ký hiệu. CHƯƠNG 2 KỸ THUẬT NÉN SỐ LIỆU Nén số liệu bao gồm hai quá trình: Nén số liệu = Mô hình hoá + Mã hoá [2] Trong đó: Mô hình xác định chính xác xác suất xuất hiện của từng ký hiệu (nghĩa là nó lựa chọn để đưa ra một từ mã nhất định đối với một ký hiệu hoặc một tập ký hiệu). Bộ mã hoá sẽ tạo ra các từ mã dựa trên các xác suất đó. Như vậy, mô hình hoá và mã hoá là hai vấn đề hoàn toàn khác nhau, và ta có thể phân biệt như sau: Một mô hình hoá nguồn số liệu có thể cùng sử dụng một hoặc nhiều phương pháp mã hoá để cho ra các từ mã. Một phương pháp mã hoá có thể được sử dụng trên một hoặc nhiều mô hình hoá Thế nhưng chúng ta vẫn thường dùng từ mã hóa để chỉ cho toàn bộ quá trình nén số liệu mặc dù đây mới chỉ là một giai đoạn của quá trình nén. Ví dụ chúng ta thường dùng mã hóa Huffman, mã hóa số học...để nói về các kỹ thuật nén này. Có rất nhiều cách để xây dựng mô hình và các mô hình này có thể sử dụng cùng một phương pháp mã hóa. Hình vẽ 2.1 mô tả đầy đủ cấu trúc của bộ nén không tổn hao. Mô hình Mô hình Mã hóa Mã hóa Sự ước lượng Xác suất 10011010001.... Luồng bít đã mã hóa Sự phân bố Xác suất Nguồn ký hiệu Sự phân bố Xác suất Sự ước lượng Xác suất Nguồn ký hiệu MÃ HÓA GIẢI MÃ Hình 21 Cấu trúc của bộ nén không tổn hao [8] Mô hình Mô hình là một tập hợp số liệu cùng các quy tắc được sử dụng để xử lý các ký hiệu vào và đưa ra các từ mã tương ứng. Chúng ta biết rằng quá trình nén số liệu bao gồm hai giai đoạn: mô hình hoá và mã hoá. Tuy nhiên, hiệu quả của nén số liệu phụ thuộc rất nhiều vào mô hình bất chấp hiệu quả của bộ mã hoá. Vì sao như vậy? Chức năng của mô hình là tiên đoán các ký hiệu để cung cấp một sự phân phối xác suất cho ký hiệu tiếp theo. Xét cùng một nguồn tin cần được mã hoá, trong đó xét ký hiệu “u” chẳng hạn, nó sẽ có xác suất thấp hoặc cao tùy thuộc vào bậc của mô hình ta chọn. Như vậy, nếu ta thay đổi bậc mô hình thì xác suất xuất hiện sẽ thay đổi theo và để nén số liệu có hiệu quả cao thì ta phải chọn được một mô hình có thể tiên đoán được sự xuất hiện của các ký hiệu với xác suất cao. Rõ ràng xác suất thay đổi thì Entropy của ký hiệu cũng thay đổi và xác suất càng cao thì cần ít bit hơn để mã hoá tạo ra các từ mã tương ứng sẽ càng ngắn. Vậy bậc của mô hình là gì? Trong một luồng dữ liệu, sự xuất hiện của các ký hiệu là cố định, nhưng việc tính xác suất cho mỗi ký hiệu thì không cố định. Xác suất của ký hiệu có thể thay đổi phụ thuộc vào cách xây dựng mô hình. Việc tính toán xác suất của ký hiệu được dựa vào các ký hiệu đứng trước, các ký hiệu đứng trước gọi là ngữ cảnh (context). Từ đó dẫn đến khái niệm bậc của mô hình, mô hình chỉ tính xác suất của ký hiệu dựa vào số ký hiệu đứng trước mà các ký hiệu này tạo thành ngữ cảnh. Nếu ta tính xác suất của ký hiệu mà không dựa vào ngữ cảnh thì ta có mô hình bậc 0, nếu số ký hiệu trong ngữ cảnh bằng 1 thì mô hình có bậc một, nếu số ký hiệu bằng 2 thì mô hình có bậc 2 .v.v.. Kỹ thuật nén không tổn hao sử dụng hai kiểu mô hình: Mô hình thống kê (Statistical): Mô hình thống kê tĩnh và Mô hình thống kê động Mô hình từ điển (Dictionary): Mô hình từ điển tĩnh và Mô hình từ điển động Mô hình thống kê Mô hình thống kê tĩnh là xây dựng một bảng liệt kê tất cả các giá trị xác suất của một luồng ký hiệu. Điều này đòi hỏi phải gửi đi thêm một lượng số liệu nhất định cho bộ giải mã để giải mã thông điệp. Trước đây, người ta thường xây dựng mô hình tĩnh vạn năng tức là người ta chỉ phân tích một lần đối với các khối số liệu điển hình để có được một bảng đếm số lần xuất hiện của từng ký hiệu. Dựa vào kết quả đó, một cây mã Huffman tĩnh được xây dựng và lưu giữ để sử dụng cho nhiều kiểu số liệu khác nhau. Tuy nhiên, nếu luồng dữ liệu vào không tương hợp thì sẽ dẫn đến hiện tượng “nở số liệu” (luồng dữ liệu ra sẽ có kích thước lớn hơn luồng dữ liệu vào). Để khắc phục hạn chế đó người ta xây dựng một mô hình tĩnh riêng cho từng kiểu số liệu và khi giải mã thì ta phải gửi đi trước một lượng số liệu thống kê nhất định (cấu trúc cây mã) sau đó mới gửi luồng mã đi. Với mô hình bậc 0 lượng số liệu không đáng kể (khoảng 256 byte), tuy nhiên để đạt hiệu quả nén tốt hơn thì phải sử dụng mô hình bật cao hơn, với mô hình bậc 1 thì lượng số liệu thống kê có thể lên đến 64KB. Do vậy, người ta xây dựng mô hình khác gọi là mô hình thống kê động. Trong mô hình này, số liệu thống kê của nguồn số liệu sẽ được tích luỹ và liên tục sửa đổi trong suốt quá trình mã hoá. Ta có sơ đồ mã hoá và giải mã như sau: Xuất mã Cập nhập mô hình Mô hình Đọc ký hiệu vào Mã hóa ký hiệu Luồng vào (các ký hiệu) Luồng ra (các mã) Hình 2- 2 Mã hoá theo mô hình thống kê thích ứng [2] Hình 2-3 Giải mã theo mô hình thống kê thích ứng [2] Luồng ra (các ký hiệu) Đọc mã vào (read input code) Xuất ký hiệu Cập nhập mô hình Mô hình Giải mã ký hiệu Luồng vào (các mã) Với hai sơ đồ trên, chúng ta thấy rằng khi một kí hiệu hoặc một nhóm kí hiệu được đọc vào, nó sẽ mã hoá hoặc giải mã dựa trên mô hình hiện thời rồi sau đó mô hình mới được cập nhật dựa trên kí hiệu hoặc nhóm kí hiệu đó. Trong mô hình thống kê động số liệu thống kê của nguồn số liệu không cần phải gửi đi trước nhưng yêu cầu khối “cập nhập mô hình“ phải hoạt động chính xác như nhau khi mã hoá và giải mã. Với mô hình này, hiệu ứng nén chỉ xuất hiện rõ rệt khi đã làm việc với vài ngàn kí tự, và do không phải gửi đi trước một nguồn số liệu khi giải mã nên hiệu quả nén cao hơn so với mô hình tĩnh, thêm vào đó là khả năng thích ứng cao với mọi kiểu số liệu. Mô hình từ điển Mô hình từ điển tĩnh tương tự như một danh sách tài liệu tham khảo dùng trong sách báo khoa học, trong đó các sách tham khảo được thay thế bằng một con số nằm trong ngoặc vuông và con số này lại trỏ đến một tài liệu xác định nào đó trong danh sách tài liệu tham khảo. Khi đọc vào một từ, nó sẽ tìm một nhóm số liệu tương hợp trên từ điển. Nếu tìm thấy thì xuất ra một con trỏ đến nhóm kí hiệu đó chứ không phải một từ mã trong mô hình thống kê. Số liệu đọc vào càng tương hợp với nhóm kí hiệu tìm thấy trong từ điển thì hiệu quả nén càng cao. Tuy nhiên giống như mô hình thống kê tĩnh, mô hình này có nhược điểm là phải phát từ điển đi trước số liệu đã được mã hoá, như vậy sẽ làm giảm hiệu quả nén. Để khắc phục, ta dùng mô hình từ điển động. Mô hình này giống như cách viết tắt mà ta vẫn thường làm, muốn viết tắt một cụm từ nào đó thì ngay