Đề tài Lempel - Ziv Encoding

TRƯỜNG ĐẠI HỌC ĐIỆN LỰC Khoa Điện Tử Viễn Thông -----š›&š›----- BÀI TẬP NHÓM MÔN LÝ THUYẾT THÔNG TIN ĐỀ TÀI : “Lempel-ziv Encoding” Giảng viên bộ môn: Vũ Ngọc Châm Nhóm Sinh Viên Thực Hiên: Nhóm 10 Sinh viên lớp: Đ5.ĐTVT1 TRƯỜNG ĐAI HỌC ĐIỆN LỰC Khoa Điện Tử Viễn Thông Môn Lý THUYÊT thông tin LEMPEL-ZIV ENCODING Danh Sách Các Thành Viên Nhóm Số 10 1 : NGUYỄN QUỐC QUÂN 2: NGUYỄN VĂN HÙNG 3: NGUYỄN VĂN KHOÁI 4: HOÀNG VĂN LÂM 5: NGUYỄN VĂN TIẾN LÂM Hà nội ngày 11 tháng 9 năm 2012 Mục Lục 1.Danh sách thành viên trong nhóm 10……………………….. 1 2.Lời giới thiệu………………………………………………....2 3.Tổng quan về nén giữ liệu …………………………………...4 4. Cơ sở một số phương pháp nén………..…………………….5 5. Tổng quan về Lempel-ziv coding …………………………...6 6.Từ điển mã hóa……………………………………………….7 7. Họ thuật toán Lempel-Ziv…………………………………..8 +Thuật toán LZ78……………………………………………...8 +Thuật toán LZW ……………………………………………..11 8.Kết Luận……………………………………………………..19 9.Tài liệu tham khảo……………………………………………21 2.Mục lục……………………………………………………….22 Lời giới thiệu. Ngày nay thông tin là một phần gắn kết không thể thiếu của con người trong cuộc sống hiện đại. việc trao đổi thông tin là công việc thường xuyên và được coi như là bình thường của mỗi chúng ta.Có rất nhiều hình thức thể hiện khác nhau của thông tin như âm thanh, hình ảnh,tiếng nói,chữ viết và các loại ký tự……. Chính vì vậy mà cũng nảy sinh ra rất nhiều vấn đề bức thiết xung quanh việc chuyền tải thông tin từ người này tới người khác cũng như đến vấn đề lưu trữ bạn không thể bỏ 250 Gigabyte dung lượng ổ nhớ máy vi tính của bạn ra chỉ để lưu trữ và ghi nhớ một thông tin không quan trọng lắm, hoặc trong việc lưu trữ nó. Ví dụ như dung lượng tập tin mà quá lớn nó sẽ ảnh hưởng vân đề trao đổi thông tin bạn không thể chờ cả ngày để cập nhập một lượng tin quá lớn mà không cần thiết lắm cho cuộc sống của bạn.Chính vì vậy mà người ta mới nghĩ ra một thuật toán mà làm thế nào đó để có thể giảm dung lượng thông tin cần trao đổi đó xuống nhằm mục đích đơn giản và thuận tiện hơn trong việc trao đổi và lưu trữ thông tin. Để giải quyết vấn đề đó, các thuật toán nén đã được ra đời. Ban đầu với phương pháp mã hóa loạt dài RLC (Run Length Coding), phát hiện một loạt các bít lặp lại. Đây là phương pháp đơn giản nhất. Nguyên tắc cơ bản của phương pháp này là phát hiện một ký tự có số lần xuất hiện liên tiếp vượt qua một ngưỡng cố định nào đó. Trong trường hợp này dãy sẽ được thay thế bằng 3 ký tự: Ký tự thứ nhất là ký tự đặc biệt,thông báo dãy tiếp là dãy đặc biệt. Ký tự thứ hai chỉ số lần lặp. Ký tự thứ ba chỉ ký tự lặp.Như vậy tư tưởng của phương pháp này là thay thế một dãy bằng một dãy khác ngắn hơn tuân theo một ngưỡng nào đó, và thông thường ngưỡng có giá trị là 4.Kế đến là phương pháp Huffman, dựa vào mô hình thống kê, tính tần suất xuất hiện của các ký tự, rồi gán cho các ký tự có tần suất cao một từ mã ngắn, các ký tự tần suất thấp từ mã dài. Phương pháp này phải lưu giữ lại bảng mã gắn kèm cùng với dữ liệu nén. Một phương pháp nén hoàn toàn khác là thuật toán nén dữ liệu theo từ điển cơ sở: (Dictionary-based compression) Có 2 loại: Mã hóa từ điển tĩnh (static dictionary coding) Mã hóa từ điển động (dynamic dictionary coding) Có rất nhiều thuật toán áp dụng kỹ thuật này như LZ77, LZR, LZSS, LZH…nhưng trong nội dung bài báo cáo này, chúng ta chỉ đề cập đến hai thuật toán chình là: +Thuât Toán LZ78 + Thuât toán LZW. Nhìn chung không có phương pháp nén tổng quát nào cho kết quả là tốt đối với tất cả các loại tập tin mà ta cần mã hóa cả.Năm 1983 Sperry nộp một bằng sáng chế cho một thuật toán phát triển bởi Terry Welch, một nhân viên tại Trung tâm nghiên cứu Sperry. Thuật toán này là biến thể trên một kỹ thuật nén dữ liệu lần đầu tiên được đề xuất bởi Jakob Ziv và Abraham Lempel năm 1978 của Welch. Kỹ thuật của Welch là cả hai đơn giản hơn và nhanh hơn. Ông đã xuất bản một bài báo trong vấn đề 1984 của Tạp chí máy tính IEEE mô tả kỹ thuật. Kỹ thuật này của Terry Welch trở nên rất phổ biến và được chấp nhận rộng rãi. Đó chính là thuật toán mã hóa mà ngày nay người ta gọi nó với cái tên là Lempel-Ziv-Welch. Hà nội ngày 11 tháng 9 năm 2012 Các thành viên nhóm 10 I: TỔNG QUAN VỀ NÉN GIỮ LIỆU I.1:Nén giữ liệu là gì?. Nén giữ liệu được định nghĩa đơn giản như sau: 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 và do vậy, thông tin thu được sau nén thường nhỏ hơn dữ liệu gốc rất nhiều. Ngoài thuật ngữ “nén dữ liệu”, do bản chất của kỹ thuật này nó còn có một số tên gọi khác như: giảm độ dư thừa, mã hóa ảnh gốc… I.2:Tỷ Số Nén ( Compression rate ) Compression rate được định nghĩa như sau: Tỷ số nén là tỷ lệ giữa kích thướcfile đã nén và kích thước file khi mà chưa nén. + Công thức tỷ số nén như sau:  Chú thích: + Compression rate: Tỷ số nén +Compressed Size: Kích cỡ file sau nén +Uncompressed Size :Kích cỡ file trước nén +Đơn vị thường ký hiệu là tỳ số ví dụ như 1/5 +Ví dụ ở đây ta có một file gốc kích thước 10M sau khi nén thì dung lượng giảm xuống còn 2M.Vậy rõ ràng Tỷ số nén ở đây là 2/10=1/5.Và thường được ký hiệu là tỷ lệ rõ ràng là 1/5. I.3: Khoảng Tiết Kiệm Không Gian (Space savings) Space savings: được định nghĩa như sau nó là sự giảm kích thước tương đối so với kích thước không nén, đơn vị ở đây được dùng là đơn vị %. +Công thức tính như sau. Chú thích: +Space Savings : Khoảng tiết kiệm không gian +Compressed Size: Kích cỡ file sau nén +Uncompressed Size :Kích cỡ file trước nén +Đơn vị thường ký hiệu +Ví dụ Ta có tỷ lệ nén là 1/5 thì sẽ mang lại một khoảng tiết kiệm không gian là 1 - 1/5 = 0.8, vậy sau khi nén ta tiết kiệm được 80% không gian bộ nhớ so với trước khi nén. Đối với các tín hiệu của kích thước không xác định, chẳng hạn như tuyến âm thanh và video, tỉ lệ nén được định nghĩa về tốc độ dữ liệu khi  không nén và khi đã nén thay vì kích thước dữ liệu như tài liệu đã nêu ở trên. Và thay vì tiết kiệm không gian, người ta nói về tốc độ dữ liệu tiết kiệm, được định nghĩa là giảm tốc độ dữ liệu liên quan đến tốc độ dữ liệu không nén. + Công thức tính trong trường hợp này sẽ là: Và Tỷ lệ tiết kiệm giữ liệu Data rate saving sẽ là: Chú thích: + Compression ratio : Tỷ số nén +Compressed Data Rate : Tốc độ nén giữ liệu +Uncompressed Size :Tốc độ khi chưa nén giữ liệu + Ví dụ, bài hát không nén ở định dạng CD có tốc độ dữ liệu 16 bit / kênh x 2 kênh x 44,1 kHz ≅ 1,4 Mbit / s, trong khi AAC các tập tin trên iPod thường được nén đến 128 kbit / s, tỷ lệ năng suất nén của 0,09 , một khoản tiết kiệm dữ liệu tốc độ 0,91, hoặc 91%. + Khi tỷ lệ dữ liệu không nén được biết, tỷ lệ nén có thể được suy ra từ tốc độ dữ liệu nén. II: CƠ SỞ CỦA MỘT SỐ PHƯƠNG PHÁP NÉN Nguyên tắc của các chương trình nén nói chung giống nhau: Tận dụng sự lặp lại của dữ liệu, các chuỗi dữ liệu lặp lại được thay thế bởi con trỏ chung có độ dài bé hơn. Nén nhằm mục đích giảm kích thước dữ liệu bằng cách loại bỏ dư thừa dữ liệu.Việc xác định bản chất các kiểu dư thừa dữ liệu rất có ích cho việc xây dựng các phương pháp nén dữ liệu khác nhau. Nói một cách khác, các phương pháp nén dữ liệu khác nhau là do sử dụng các kiểu dư thừa dữ liệu khác nhau.Người ta coi có 4 kiểu dư thừa giữ liệu và chính vì thế cũng có bốn phương pháp mã hóa cơ bản hiện nay đó là: II.1:Phương pháp mã hoá Huffman. Trong một dãy ký tự, có một số ký tự có tần suất xuất hiện nhiều hơn một số dãy khác. Do vậy, ta có thể mã hoá dữ liệu một cách cô đọng hơn. Các dãy ký tự có tần xuất cao được thay bởi một từ mã nhị phân với số bít nhỏ; ngược lại các dãy có tần xuất thấp sẽ được mã hoá bởi từ mã có nhiều bít hơn. Đây chính là bản chất của phương pháp mã hoá Huffman. II.2: Phương pháp mã hoá Run Length Coding. Trong một số tình huống như trong ảnh, 1 ký hiệu (bít "0" hay bít "1") được lặp đi lặp lại một số lần. Kỹ thuật nén dùng trong trường hợp này là thay dãy lặp đó bởi dãy mới gồm 2 thành phần: số lần lặp và kí hiệu dùng để mã. Phương pháp mã hoá kiểu này có tên là mã hoá loạt dài RLC (Run Length Coding). II.3:Phương pháp mã hóa Lempel-Ziv Welch. Có thể có dãy ký hiệu nào đó xuất hiện với tần suất tương đối cao. Do vậy, có thể mã hoá bởi ít bít hơn. Đây là cơ sở của phương pháp mã hoá kiểu từ điển do Jacob Ziv và Abraham Lempel đề ra vào năm 1977-1978 và do đó có tên gọi là phương pháp nén LZ77, LZ78. Năm 1984, Terry Welch đã cải tiến hiệu quả hơn và đặt tên là LZW (Lempel-Ziv- Welch).Do đó kỹ thuật được cải thiện hơn và nhanh hơn. II.4: Phương pháp mã hoá dự đoán Do sự phụ thuộc lẫn nhau của dữ liệu, đôi khi biết được ký hiệu (giá trị) xuất hiện tại một vị trí, đồng thời có thể đoán trước sự xuất hiện của các giá trị ở các vị trí khác nhau một cách phù hợp.Chẳng hạn, ảnh biểu diễn trong một lưới hai chiều, một số điểm ở hàng dọc trong một khối dữ lệu lại xuất hiện trong cùng vị trí ở các hàng khác nhau.Do vậy, thay vì lưu trữ dữ liệu, ta chỉ cần lưu trữ vị trí hàng và cột.Phương pháp nén dựa trên sự dư thừa này gọi là phương pháp mã hoá dự đoán III: TỔNG QUAN VỀ LEMPEL-ZIV CODING Jacob Ziv và Abraham Lempel đã mô tả kỹ thuật dựa trên từ điển bằng mã hóa LZ77 và LZ78. Ý tưởng dựa trên việc thay thế 1 cụm kí tự bằng một con trỏ, trỏ đến vị trí xuất hiện trước đó của cụm kí tự.LZW là mã hóa trong họ LZ, hoàn thiện hơn LZ77-LZ78 và đang được sử dụng phổ biến hiện nay. III.1: Lempel-Ziv (LZ). Thuật toán LZ (Lempel-Ziv): là thuật toán nén dữ liệu theo từ điển cơ sở (Dictionary-based compression). Được tính bằng tỷ số giữa tổng số bit cần nén 1 từ hay 1 văn bản (vd:mã ascci-7bit) và số bít sử dụng để nén trong bộ từ điển đó. Sử dụng một bảng chứa tất cả các chuỗi ký tự có thể xuất hiện trong văn bản và được chứa trên cả bộ mã hóa và giải mã. Bộ mã hóa thay vì gửi các từ riêng lẻ, nó chỉ gửi chỉ số của từ được lưu trong bảng. Bộ giải mã sẽ truy cập vào bảng xử lý để tái tạo lại văn bản đó. Như các thuật toán tĩnh khác, thuật toán LZ sử dụng 1 từ điển chung cho cả mã hóa và giải mã. Một số gói xử lý từ có liên quan tới từ điển được sử dụng cho việc kiểm tra chính tả và nén văn bản. Thông thường trong khu vực gồm khoảng 25000 từ, do đó cần dùng15 bit để mã hóa. Vì vậy nếu dùng thuật toán LZ để nén từ “multimedia” ta sử dụng 15 bit . Thay vì khi sử dụng mã ASCII (mỗi từ mã dùng 7 bit) ta sẽ phải sử dụng 70 bit. → Compression ratio = 70/15 = 4.7:1 Những từ ngắn hơn sẽ có tỉ lệ nén nhỏ hơn so và những từ dài hơn sẽ có tỉ lệ nén lớn hơn. Thuật toán LZ được phát triển, là sử dụng một bộ từ điển động được xây dựng trên cả bộ mã hóa và giải mã. Do đó kích thước của từ điển sẽ được tối ưu hơn so với từ điển tĩnh thông thường. III.2: Lempel-Ziv-Welch( LZW). Phương pháp nén LZW được phát minh bởi Lempel - Zip và Welch. Nó hoạt động đựa trên một ý tưởng rất đơn giản là người mã hoá và người giải mã cùng xây dựng bản mã. Đầu tiên, từ điển của cả bộ mã hóa và giải mã là tập hợp các từ ví dụ như bảng mã ASCII. Sau đó từ điển động được xây dựng ở cả bộ mã hóa và giải mã từ các từ trong văn bản. Chúng ta có thể thấy, các từ lưu trữ trong từ điển xuất hiện thường xuyên trong văn bản thì mức độ nén cao hơn. IV: TỪ ĐIỂN Mà HÓA (DICTIONNARY CODING) Từ điển mã hóa( Dictionnary coding) gồm có hai loại là từ điển tĩnh (static dictionary coding) và từ điển động (dynamic dictionary coding) hai loại từ điển này gộp chung lại và người ta gọi nó là từ điển cơ sở (Dictionary-based compression), hay hiểu một cách đơn giản từ điển cơ sở là loại từ điển mà bao gồm có hai phần kết hợp tạo thành là từ điển tĩnh và từ điển động. IV.1: Static coding : Dành cho các ứng dụng trong các văn bản biết được các đặc điểm của kí tự và tần suất xuất hiện của chúng. Thay vì sử dụng các từ mã có chiều dài cố định, ta sử dụng bộ từ mã tối ưu có chiều dài thay đổi. Từ mã ngắn nhất sử dụng để biểu diễn cho văn bản. IV.2: Dynamic hoặc adaptive coding : Dành cho các ứng dụng tổng quát hơn trong các văn bản có thể bị chuyển từ dạng này sang dạng khác và bộ từ mã tối ưu cũng thay đổi từ dạng này sang dạng khác. V:HỌ THUẬT TOÁN LEMPEL-ZIV. Có rất nhiều thuật toán áp dụng kỹ thuật này như LZ77, LZR, LZSS, LZH… được mô tả trong hình 1. Hình 1:Họ thuật toán Lempel-Ziv Trong bài báo cáo này chúng ta chỉ đề cập đến hai thuật toán chính và được ứng dụng nhiều trong thực tế hiện nay là: +Thuật Toán LZ78 + Thuật toán LZW V.1: Thuật Toán LZ78. Nói chung thuật toán LZ78 là một thuật toán nén văn bản khá tốt, có thời gian chạy chương trình tương đối nhanh tuy nhiên khả năng tiết kiệm chưa được khai thác Phương Pháp Nén: Thay vì thông báo vị trí đoạn văn lặp lại trong quá khứ, mã LZ78 đánh số tất cả các đoạn văn sao cho mỗi đoạn ghi nhận số hiệu đoạn văn lặp lại trong quá khứ cộng với một ký tự mà nó làm cho đoạn đó khác với đoạn trong quá khứ. Như vậy mỗi đoạn mới là một đoạn ký tự trong quá khứ cộng với một ký tự trong quá khứ. Chính vì thế đoạn mới khác với đoạn cũ trong quá khứ. + Ví dụ: Giả sứ ta có đoạn văn bản :” aaabbabaabaaabab”. Theo thuật toán LZ78 thì chúng được phân đoạn như sau: Input A Aa b Ba baa baaa bab Đoạn 1 2 3 4 5 6 7 output 0+a 1+a 0+b 3+a 4+a 5+a 4+b Bảng b1. Mô phỏng thuật toán LZ78 Bảng b1: Mô tả thuật toán LZ78 Như vậy bản nén của chúng ta là: (0,a); (1,a); (0,b); (3,a); (4,a); (5,a); (4,b) ►Thuật toán nén: Thuật toán nén bao bồm 3 bước Bước 1: Đọc một ký tự -> ch, đoạn được gán bằng 1, kết nạp ký tự đó vào từ điển, w=ch; Bước 2: While not eof(f) do Begin Đọc tiếp ký tự tiếp theo w:= ww+ch; If w thuộc từ điển then ww:=w; Else begin Code(w,j); Ghi j và ch vào tệp nén. Thêm w vào từ điển. End; End; Bước 3: Dừng chương trình. ►Thuật toán giải nén: Thuật toán giải nén cũng bao gồm 3 bước. Bước 1: Đọc thông tin về từ điển đã được lưu trong tệp nén, tl:=false; Bước 2: while not (f) do Begin Đọc byte tiếp theo -> b Decode(b,s,t); If tl=false then w:=w+s Else w:=ww+s; TIMCHU(w,t); If t=false then Begin Ghi s ra tệp giải nén Thêm s vào từ điển End Else Begin ww:=s; End; End; Bước 3: Dừng chương trình. V.2: Thuật Toán LZW. Thuật toán nén LZW có các ưu điểm là hệ số nén tương đối cao, trong tập tin nén không cần phải chứa bảng mã. Nhược điểm của thuật toán này là tốn nhiều bộ nhớ, khó thực hiện dựa trên các mảng đơn giản (bé hơn 64KB) Giải thuật nén LZW xây dựng một từ điển lưu các mẫu có tần suất xuất hiện cao trong dữ liệu. Từ điển là tập hợp những cặp từ vựng và nghĩa của nó. Trong đó, từ vựng sẽ là các từ mã được sắp xếp theo thứ tự nhất định. Nghĩa là một chuỗi con trong dữ liệu , từ điển được xây dựng đồng thời với quá trình đọc dữ liệu. sự có mặt của một chuỗi con trong từ điển khẳng định rằng chuỗi đó đã từng xuất hiện trong phần dữ liệu đã đọc. Thuật toán liên tục “tra cứu” và cập nhật từ điển sau mỗi lần đọc một ký tự dữ liệu đầu vào. Do kích thước bộ nhớ không phải vô hạn và để đảm bảo tốc độ tìm kiếm, từ điển chỉ giới hạn 4096 ở phần tử dùng để lưu lớn nhất là 4096 giá trị của các từ mã. Như vậy độ dài lớn nhất của từ mã là 12 bits (4096 = 212 ). Cấu trúc từ điển như sau. 256 từ mã đầu tiên theo thứ tự từ 0…255 chứa các số nguyên từ 0…255. Đây là mã của 256 ký tự cơ bản trong bảng mã ASCII.Từ mã thứ 256 chứa một mã đặc biệt là “mã xoá” (CC- Clear Code). Mục đích việc dùng mã xoá nhằm khắc phục tình trạng số mẫu lặp trong ảnh lớn hơn 4096. Khi đó một ảnh được quan niệm là nhiều mảnh ảnh, và từ điển là một bộ từ điển gồm nhiều từ điển con. Cứ hết một mảnh ảnh người ta lại gửi một mã xoá để báo hiệu kết thúc mảnh ảnh cũ, bắt đầu mảnh ảnh mới đồng thời khởi tạo lại từ điển cho mảnh ảnh mới. Mã xoá có giá trị là 256.Từ mã thứ 257 chứa mã kết thúc thông tin (EOI – End of information). Mã này có giá trị là 257. Như chúng ta đã biết, một file ảnh GIF có thể có chứa nhiều ảnh.Mỗi một ảnh sẽ được mã hoá riêng.Chương trình giải mã sẽ lặp lại thao tác giải mã từng ảnh cho đến khi gặp mã kết thúc thông tin thì dừng lại. Các từ mã còn lại (từ 258 đến 4095) chứa các mẫu thường lặp lại trong ảnh. 512 phần tử đầu tiên của từ điển biểu diễn bằng 9 bit. Các từ mã từ 512 đến 1023 biểu diễn bởi 10 bit, từ 1024 đến 2047 biểu diễn bởi 11 bit và từ 2048 đến 4095 biểu diễn bởi 12 bit. 0 0 … … 255 255 256 256| Clear Code 257 257| End of Information 258 Chuỗi mới … … 4095 Chuỗi mới 256:Mã xoá CC để khắc phục tình trạng mẫu lặp lớn hơn 4096, nếu mẫu lặp lớn hơn 4096 thì gởi CC để xây dựng từ điển cho phần tiếp theo. Eoi: Báo hiệu hết một phần nén. ► Nguyên Tắc Hoạt Động LZW. Nguyên tắc hoạt động của nó như sau: Một xâu kí tự là một tập hợp từ hai kí tự trở lên. Nhớ tất cả các xâu kí tự đã gặp và gán cho nó một dấu hiệu (token) riêng. Nếu lần sau gặp lại xâu kí tự đó, xâu kí tự sẽ được thay thế bằng dấu hiệu của nó. Phần quan trọng nhất của phương pháp nén này là phải tạo một mảng rất lớn dùng để lưu giữ các xâu kí tự đã gặp (Mảng này được gọi là "Từ điển"). Khi các byte dữ liệu cần nén được đem đến, chúng liền được giữ lại trong một bộ đệm chứa (Accumulator) và đem so sánh với các chuỗi đã có trong "từ điển". Nếu chuỗi dữ liệu trong bộ đệm chứa không có trong "từ điển" thì nó được bổ sung thêm vào "từ điển" và chỉ số của chuỗi ở trong "từ điển" chính là dấu hiệu của chuỗi. Nếu chuỗi trong bộ đệm chứa đã có trong "từ điển" thì dấu hiệu của chuỗi được đem ra thay cho chuỗi ở dòng dữ liệu ra. Có bốn qui tắc để thực hiên việc nén dữ liệu theo thuật toán LZW là: Qui tắc 1: 256 dấu hiệu đầu tiên được dành cho các kí tự đơn (0 - 0ffh). Qui tắc 2: Cố gắng so sánh với "từ điển" khi trong bộ đệm chứa đã có nhiều hơn hai kí tự. Qui tắc 3: Các kí tự ở đầu vào (Nhận từ tập tin sẽ được nén) được bổ sung vào bộ đệm chứa đến khi chuỗi kí tự trong bộ đệm chứa không có trong "từ điển". Qui tắc 4: Khi bộ đệm chứa có một chuỗi mà trong "từ điển" không có thì chuỗi trong bộ đệm chứa được đem vào "từ điển". Kí tự cuối cùng của chuỗi kí tự trong bộ đệm chứa phải ở lại trong bộ đệm chứa để tiếp tục tạo thành chuỗi mới. ► Các bước thực hiện thuật toán. Quá trình nén: LZW bắt đầu bởi 1 từ điển 256 kí tự (trong trường hợp sử dụng bảng mã 8 bits) và sử dụng chúng như tập kí tự chuẩn. Sau đó mỗi lần đọc nó đọc 8 bits (ví dụ 't', 'r', ...) và mã hóa thành con số tương ứng với chỉ mục của kí tự đó trong từ điển. Mỗi khi LZW đi qua 1 chuỗi con mới (giả sử "tr") thì nó thêm chuỗi con đó vào từ điển. Mỗi khi nó đi qua 1 chuỗi con mà nó đã thấy trước đó, nó chỉ đọc thêm 1 kí tự mới nữa và cộng với chuỗi con đã biết để tạo ra 1 chuỗi con mới. Lần tiếp theo LZW bắt gặp một chuỗi con đã có, nó chỉ có việc sử dụng số chỉ mục tương ứng trong từ điển. Thường thì người ta sẽ định sẵn số lượng lớn nhất các từ trong từ điển (giả sử 4096), vì thế việc nén LZW không làm tiêu tốn hết toàn bộ bộ nhớ. Vì vậy mã của các chuỗi con trong ví dụ này là 12 bits (2 ^ 12 = 4096). Cần thiết phải lập mã dài hơn số bits của một kí tự (12 vs 8 bits), do đo khi rất nhiều chuỗi con lặp lại sẽ được thay thế bởi một mã duy nhất thì việc nén được thực hiện. Ví dụ 1: Các bước để mã hoá chuỗi "!BAN!BA!BAA!BAR!" như sau : - Bước 1: Kí tự thứ nhất ‘!’ được cất vào bộ đệm chứa để chuẩn bị tạo nên một chuỗi. - Bước 2: Kí tự thứ hai ‘B’ nối thêm vào sau kí tự !. Vì trong "từ điển" chưa có chuỗi "!B" nên chuỗi này được thêm vào "từ điển" và được gán dấu hiệu là 100h (Vì từ 000h đến 0ffh được dành riêng cho các kí tự đơn: Qui tắc 1). ‘!’ được gửi ra còn ‘B’ phải ở lại trong bộ đệm chứa. - Bước 3: Kí tự thứ ba ‘A’ thêm vào sau ‘B’. Chuỗi "BA" cũng chưa có trong "từ điển" nên nó được thêm vào "từ điển" và gán dấu hiệu là 101h. ‘A’ ở lại trong bộ đệm chứa còn ‘B’ được gửi ra. - Bước 4: Kí tự thứ tư ‘N’ thêm vào sau ‘A’ tạo thành chuỗi "AN" cũng chưa có trong "từ điển" nên được thêm vào "từ điển" và có dâu hiệu là 102h. ‘N’ ở lại trong bộ đệm chứa còn ‘A’ được g