Lempel–Ziv–Welch ( LZW ) เป็นอัลกอริธึมการบีบอัดแบบไม่สูญเสียข้อมูล สากล ที่สร้างขึ้นโดยAbraham Lempel , Jacob ZivและTerry Welchโดย Welch ได้เผยแพร่ในปี 1984 เพื่อเป็นการปรับปรุง อัลก อริธึม LZ78ที่ Lempel และ Ziv เผยแพร่ในปี 1978 ข้อดีที่กล่าวอ้าง ได้แก่ ง่ายต่อการใช้งานและศักยภาพในการประมวลผลข้อมูลจำนวนมากในการใช้งานฮาร์ดแวร์^{[ 1 ]}

โดยทั่วไป ไฟล์ข้อความภาษาอังกฤษ ขนาดใหญ่สามารถบีบอัดด้วย LZW ให้เหลือขนาดประมาณครึ่งหนึ่งของขนาดเดิมได้

อัลกอริทึมนี้กลายเป็นวิธีการบีบอัดข้อมูลแบบสากลที่ใช้กันอย่างแพร่หลายเป็นครั้งแรกในคอมพิวเตอร์ อัลกอริทึมนี้ถูกนำไปใช้ใน โปรแกรม compressที่มักรวมอยู่ใน ระบบ Unixตั้งแต่ประมาณปี 1986 แต่หลังจากนั้นก็หายไปจากระบบปฏิบัติการหลายๆ ระบบ เนื่องจากทั้งละเมิดสิทธิบัตร LZW และเพราะgzip ให้ผลลัพธ์การบีบอัดที่ดีกว่าโดยใช้อัลกอริทึม DEFLATEที่ใช้ LZ77 เป็นพื้นฐานอัลกอริทึมนี้ได้รับความนิยมอย่างมากเมื่อกลายเป็นส่วนหนึ่งของ รูปแบบภาพ GIFในปี 1987 และอาจใช้ใน ไฟล์ TIFFและPDF ได้ด้วย แม้ว่า LZW จะมีอยู่ในซอฟต์แวร์Adobe Acrobat แต่โดยค่าเริ่มต้น Acrobat จะใช้ DEFLATEสำหรับข้อมูลข้อความและข้อมูลภาพที่ใช้ตารางสีส่วนใหญ่ในไฟล์ PDF

สถานการณ์ที่อธิบายไว้ในเอกสารของ Welch ปี 1984 ^{[ 1 ]}เข้ารหัสลำดับข้อมูล 8 บิตเป็นรหัส 12 บิตความยาวคงที่ รหัสตั้งแต่ 0 ถึง 255 แทนลำดับอักขระ 1 ตัวที่ประกอบด้วยอักขระ 8 บิตที่สอดคล้องกัน และรหัส 256 ถึง 4095 ถูกสร้างขึ้นในพจนานุกรมสำหรับลำดับที่พบในข้อมูลขณะที่ถูกเข้ารหัส ในแต่ละขั้นตอนของการบีบอัด ไบต์อินพุตจะถูกรวบรวมเป็นลำดับจนกว่าอักขระตัวถัดไปจะสร้างลำดับที่ยังไม่มีรหัสในพจนานุกรม รหัสสำหรับลำดับ (ที่ไม่มีอักขระนั้น) จะถูกเพิ่มลงในเอาต์พุต และรหัสใหม่ (สำหรับลำดับที่มีอักขระนั้น) จะถูกเพิ่มลงในพจนานุกรม

ในการประยุกต์ใช้การบีบอัดภาพในทางปฏิบัติ และสำหรับภาพที่อิงตามตารางสี ตัวอักษรธรรมชาติคือชุดดัชนีของตารางสี ในช่วงทศวรรษ 1980 ภาพจำนวนมากมีตารางสีขนาดเล็ก (ประมาณ 16 สี) สำหรับตัวอักษรที่ลดลงเช่นนี้ รหัส 12 บิตแบบเต็มให้การบีบอัดที่ไม่ดี เว้นแต่ภาพจะมีขนาดใหญ่ ดังนั้นจึงมีการนำแนวคิดของ รหัส ความกว้างแปรผันมาใช้ โดยทั่วไปรหัสจะเริ่มต้นด้วยความกว้างที่มากกว่าสัญลักษณ์ที่กำลังเข้ารหัสหนึ่งบิต และเมื่อใช้ขนาดรหัสแต่ละขนาดแล้ว ความกว้างของรหัสจะเพิ่มขึ้น 1 บิต จนถึงค่าสูงสุดที่กำหนดไว้ (โดยทั่วไปคือ 12 บิต) เมื่อถึงค่ารหัสสูงสุดแล้ว การเข้ารหัสจะดำเนินต่อไปโดยใช้ตารางที่มีอยู่ แต่จะไม่สร้างรหัสใหม่เพื่อเพิ่มลงในตาราง

การปรับปรุงเพิ่มเติมได้แก่ การสงวนรหัสเพื่อระบุว่าควรล้างตารางรหัสและคืนค่ากลับสู่สถานะเริ่มต้น ("รหัสล้าง" ซึ่งโดยทั่วไปจะเป็นค่าแรกถัดจากค่าของตัวอักษรแต่ละตัว) และรหัสเพื่อระบุจุดสิ้นสุดของข้อมูล ("รหัสหยุด" ซึ่งโดยทั่วไปจะเป็นค่ามากกว่ารหัสล้างหนึ่งค่า) รหัสล้างช่วยให้ตารางสามารถเริ่มต้นใหม่ได้หลังจากที่เต็ม ซึ่งช่วยให้การเข้ารหัสปรับให้เข้ากับรูปแบบที่เปลี่ยนแปลงในข้อมูลอินพุตได้ ตัวเข้ารหัสอัจฉริยะสามารถตรวจสอบประสิทธิภาพการบีบอัดและล้างตารางเมื่อใดก็ตามที่ตารางที่มีอยู่ไม่ตรงกับข้อมูลอินพุตอีกต่อไป

เนื่องจากมีการเพิ่มรหัสในลักษณะที่กำหนดโดยข้อมูล ตัวถอดรหัสจึงจำลองการสร้างตารางตามที่เห็นรหัสที่ได้ จึงเป็นเรื่องสำคัญที่ตัวเข้ารหัสและตัวถอดรหัสต้องเห็นพ้องต้องกันเกี่ยวกับชนิดของ LZW ที่ใช้ ได้แก่ ขนาดของตัวอักษร ขนาดตารางสูงสุด (และความกว้างของรหัส) การใช้การเข้ารหัสแบบความกว้างแปรผัน ขนาดรหัสเริ่มต้น และการใช้รหัสเคลียร์และรหัสหยุด (และค่าของรหัสเหล่านั้น) รูปแบบส่วนใหญ่ที่ใช้ LZW จะรวมข้อมูลนี้ไว้ในข้อกำหนดของรูปแบบ หรือระบุฟิลด์ที่ชัดเจนสำหรับข้อมูลเหล่านี้ในส่วนหัวการบีบอัดสำหรับข้อมูล

กระบวนการเข้ารหัสสามารถอธิบายได้ดังนี้:

1. กำหนดค่าเริ่มต้นให้พจนานุกรมมีสตริงทั้งหมดที่มีความยาวหนึ่ง
2. ค้นหาสตริงW ที่ยาวที่สุด ในพจนานุกรมที่ตรงกับข้อมูลที่ป้อนเข้ามา
3. ส่งค่าดัชนีพจนานุกรมสำหรับWไปยังเอาต์พุต และลบW ออก จากอินพุต
4. เพิ่มตัว อักษร Wตามด้วยสัญลักษณ์ถัดไปในข้อมูลที่ป้อนเข้าไปในพจนานุกรม
5. ไปที่ขั้นตอนที่ 2

พจนานุกรมจะถูกสร้างขึ้นเพื่อเก็บสตริงที่มีอักขระตัวเดียวซึ่งสอดคล้องกับอักขระอินพุตที่เป็นไปได้ทั้งหมด (และไม่มีอย่างอื่นนอกจากรหัสเคลียร์และรหัสหยุดหากมีการใช้งาน) อัลกอริทึมทำงานโดยการสแกนสตริงอินพุตเพื่อหาสตริงย่อยที่ยาวขึ้นเรื่อยๆ จนกว่าจะพบสตริงย่อยที่ไม่อยู่ในพจนานุกรม เมื่อพบสตริงดังกล่าวแล้ว ดัชนีของสตริงที่ไม่มีอักขระตัวสุดท้าย (เช่น สตริงย่อยที่ยาวที่สุดที่อยู่ในพจนานุกรม) จะถูกดึงมาจากพจนานุกรมและส่งไปยังเอาต์พุต และสตริงใหม่ (รวมถึงอักขระตัวสุดท้าย) จะถูกเพิ่มลงในพจนานุกรมด้วยรหัสที่ว่างอยู่ถัดไป จากนั้นอักขระอินพุตตัวสุดท้ายจะถูกใช้เป็นจุดเริ่มต้นถัดไปในการสแกนหาสตริงย่อย

ด้วยวิธีนี้ สตริงที่ยาวขึ้นเรื่อยๆ จะถูกลงทะเบียนในพจนานุกรมและพร้อมสำหรับการเข้ารหัสในภายหลังเป็นค่าเอาต์พุตเดียว อัลกอริทึมทำงานได้ดีที่สุดกับข้อมูลที่มีรูปแบบซ้ำๆ ดังนั้นส่วนเริ่มต้นของข้อความจึงมีการบีบอัดน้อย อย่างไรก็ตาม เมื่อข้อความมีขนาดใหญ่ขึ้นอัตราส่วนการบีบอัดจะเข้าใกล้ค่าสูงสุดแบบไม่จำกัด (กล่าวคือ ปัจจัยหรืออัตราส่วนการบีบอัดจะดีขึ้นตามเส้นโค้งที่เพิ่มขึ้น ไม่ใช่แบบเชิงเส้น โดยเข้าใกล้ค่าสูงสุดทางทฤษฎีภายในช่วงเวลาที่จำกัด แทนที่จะเป็นช่วงเวลาอนันต์) ^{[ 2 ]}

กระบวนการถอดรหัสสามารถอธิบายได้ดังนี้:

1. กำหนดค่าเริ่มต้นให้พจนานุกรมมีสตริงทั้งหมดที่มีความยาวหนึ่ง
2. อ่านสัญลักษณ์ที่เข้ารหัสถัดไป
3. หากสัญลักษณ์นั้นไม่ได้ถูกเข้ารหัสไว้ในพจนานุกรม ให้ไปที่ขั้นตอนที่ 7
4. ส่งออกสตริงW ที่เกี่ยวข้อง ไปยังเอาต์พุต
5. นำสตริงที่ส่งออกก่อนหน้านี้มาต่อกับสัญลักษณ์แรกของWแล้วเพิ่มลงในพจนานุกรม
6. ไปที่ขั้นตอนที่ 9
7. นำสตริงที่ส่งออกก่อนหน้านี้มาต่อกับสัญลักษณ์ตัวแรก แล้วตั้งชื่อสตริงนี้ว่าV
8. เพิ่มค่าVลงในพจนานุกรมและส่งค่าVออกทางเอาต์พุต
9. ทำซ้ำขั้นตอนที่ 2 จนกว่าจะป้อนข้อมูลเสร็จสิ้น

อัลกอริทึมการถอดรหัสทำงานโดยการอ่านค่าจากข้อมูลที่เข้ารหัสและส่งออกสตริงที่สอดคล้องกันจากพจนานุกรม อย่างไรก็ตาม ไม่จำเป็นต้องใช้พจนานุกรมทั้งหมด เพียงแค่พจนานุกรมเริ่มต้นที่มีสตริงตัวอักษรเดี่ยว (ซึ่งโดยปกติจะถูกเขียนไว้ในโปรแกรมแทนที่จะส่งมาพร้อมกับข้อมูลที่เข้ารหัส) แต่พจนานุกรมทั้งหมดจะถูกสร้างขึ้นใหม่ในระหว่างกระบวนการถอดรหัสด้วยวิธีดังต่อไปนี้: หลังจากถอดรหัสค่าและส่งออกสตริงแล้ว ตัวถอดรหัสจะนำค่าที่ได้ไปต่อกับอักขระตัวแรกของ สตริงที่ถอดรหัสได้ ถัดไป (หรืออักขระตัวแรกของสตริงปัจจุบัน หากไม่สามารถถอดรหัสสตริงถัดไปได้ เนื่องจากหากไม่ทราบค่าถัดไป ค่าดังกล่าวจะต้องเป็นค่าที่เพิ่มเข้าไปในพจนานุกรมใน รอบ นี้ดังนั้นอักขระตัวแรกจึงเหมือนกับอักขระตัวแรกของสตริงปัจจุบัน) และอัปเดตพจนานุกรมด้วยสตริงใหม่ จากนั้นตัวถอดรหัสจะดำเนินการกับข้อมูลป้อนเข้าถัดไป (ซึ่งอ่านไปแล้วในรอบก่อนหน้า) และประมวลผลเช่นเดิม และทำเช่นนี้ไปเรื่อยๆ จนกว่าจะประมวลผลข้อมูลป้อนเข้าทั้งหมดเสร็จสิ้น

หากมีการใช้รหัสที่มีความกว้างแปรผันได้ ตัวเข้ารหัสและตัวถอดรหัสต้องระมัดระวังในการเปลี่ยนความกว้าง ณ จุดเดียวกันในข้อมูลที่เข้ารหัส เพื่อไม่ให้เกิดความขัดแย้งเกี่ยวกับขอบเขตระหว่างรหัสแต่ละตัวในสตรีม ในเวอร์ชันมาตรฐาน ตัวเข้ารหัสจะเพิ่มความกว้างจากpเป็นp + 1 เมื่อ พบ ลำดับ ω +  s ที่ไม่อยู่ในตาราง (ดังนั้นจึงต้องเพิ่มรหัสสำหรับลำดับนี้) แต่รหัสถัดไปที่มีอยู่ในตารางคือ ^2p (รหัสแรกที่ต้องการp  + 1 บิต) ตัวเข้ารหัสจะส่งรหัสสำหรับ ω ที่ความกว้างp (เนื่องจากรหัสนั้นไม่ต้องการp  + 1 บิต) จากนั้นจะเพิ่มความกว้างของรหัสเพื่อให้รหัสถัดไปที่ส่งออกมามี ความกว้าง p + 1 บิต

ตัวถอดรหัสจะสร้างตารางโดยมีรหัสตามหลังตัวเข้ารหัสอยู่หนึ่งรหัสเสมอ ดังนั้นเมื่อมันเห็นรหัสสำหรับ ω มันจะสร้างรายการสำหรับรหัส 2p ⁻  1 เนื่องจากนี่คือจุดที่ตัวเข้ารหัสเพิ่มความกว้างของรหัส ตัวถอดรหัสจึงต้องเพิ่มความกว้าง ณ จุดนี้ด้วยเช่นกัน— ณ จุดที่มันสร้างรหัสที่ใหญ่ที่สุดที่พอดีกับpบิต

น่าเสียดายที่การใช้งานอัลกอริทึมการเข้ารหัสในยุคแรกๆ บางแบบจะเพิ่มความกว้างของรหัสแล้วส่งค่า ω ที่ความกว้างใหม่แทนที่จะเป็นความกว้างเดิม ทำให้ตัวถอดรหัสเข้าใจผิดว่าความกว้างเปลี่ยนไปหนึ่งรหัสเร็วเกินไป ปรากฏการณ์นี้เรียกว่า "การเปลี่ยนแปลงก่อนกำหนด" (early change) ซึ่งก่อให้เกิดความสับสนอย่างมาก จนปัจจุบัน Adobe อนุญาตให้ใช้ทั้งสองเวอร์ชันในไฟล์ PDF แต่ได้เพิ่มแฟล็กที่ชัดเจนในส่วนหัวของแต่ละสตรีมที่บีบอัดด้วย LZW เพื่อระบุว่ามีการใช้การเปลี่ยนแปลงก่อนกำหนดหรือไม่ สำหรับรูปแบบไฟล์กราฟิกที่รองรับการบีบอัด LZW นั้นTIFFใช้การเปลี่ยนแปลงก่อนกำหนด ในขณะที่GIFและรูปแบบอื่นๆ ส่วนใหญ่ไม่ได้ใช้

เมื่อตารางถูกล้างเพื่อตอบสนองต่อรหัสล้าง ทั้งตัวเข้ารหัสและตัวถอดรหัสจะเปลี่ยนความกว้างของรหัสหลังจากรหัสล้างกลับไปเป็นความกว้างของรหัสเริ่มต้น โดยเริ่มจากรหัสถัดจากรหัสล้างทันที

เนื่องจากรหัสที่ส่งออกมามักไม่ตรงกับขอบเขตของไบต์ ตัวเข้ารหัสและตัวถอดรหัสจึงต้องตกลงกันว่าจะบรรจุรหัสลงในไบต์อย่างไร วิธีการที่ใช้กันทั่วไปสองวิธีคือLSB-first (“ บิตที่มีค่าน้อยที่สุดก่อน”) และMSB-first (“ บิตที่มีค่ามากที่สุดก่อน”) ในการบรรจุแบบ LSB-first รหัสแรกจะถูกจัดเรียงเพื่อให้บิตที่มีค่าน้อยที่สุดของรหัสตกอยู่ในบิตที่มีค่าน้อยที่สุดของไบต์สตรีมแรก และหากรหัสมีมากกว่า 8 บิต บิตที่มีค่าสูงกว่าที่เหลืออยู่จะถูกจัดเรียงให้ตรงกับบิตที่มีค่าน้อยที่สุดของไบต์ถัดไป รหัสเพิ่มเติมจะถูกบรรจุโดยให้ LSB เข้าไปในบิตที่มีค่าน้อยที่สุดที่ยังไม่ได้ใช้ในไบต์สตรีมปัจจุบัน และดำเนินการไปยังไบต์ถัดไปตามความจำเป็น การบรรจุแบบ MSB-first จะจัดเรียงรหัสแรกเพื่อให้ บิตที่มีค่า มากที่สุดตกอยู่ใน MSB ของไบต์สตรีมแรก โดยบิตที่เกินจะถูกจัดเรียงให้ตรงกับ MSB ของไบต์ถัดไป รหัสเพิ่มเติมจะถูกเขียนโดยให้ MSB เข้าไปในบิตที่มีค่ามากที่สุดที่ยังไม่ได้ใช้ในไบต์สตรีมปัจจุบัน

ไฟล์ GIF ใช้ลำดับการจัดเรียงข้อมูลแบบ LSB-first ส่วนไฟล์ TIFF และ PDF ใช้ลำดับการจัดเรียงข้อมูลแบบ MSB-first

แอปพลิเคชันจำนวนมากขยายอัลกอริทึมโดยการใช้การเข้ารหัสเพิ่มเติมกับลำดับของสัญลักษณ์เอาต์พุต บางแอปพลิเคชันจะบรรจุสตรีมที่เข้ารหัสแล้วเป็นอักขระที่พิมพ์ได้โดยใช้การเข้ารหัสไบนารีเป็นข้อความในรูป แบบใดรูปแบบหนึ่ง ซึ่งจะเพิ่มความยาวของการเข้ารหัสและลดอัตราการบีบอัด ในทางกลับกัน การบีบอัดที่เพิ่มขึ้นมักทำได้โดยใช้ตัวเข้ารหัสเอนโทรปีแบบปรับได้ตัวเข้ารหัสดังกล่าวจะประมาณการการกระจายความน่าจะเป็นสำหรับค่าของสัญลักษณ์ถัดไป โดยอิงจากความถี่ของค่าที่สังเกตได้จนถึงปัจจุบัน จากนั้นการเข้ารหัสเอนโทรปีมาตรฐาน เช่นการเข้ารหัสฮัฟฟ์แมนหรือการเข้ารหัสเลขคณิตจะใช้รหัสที่สั้นกว่าสำหรับค่าที่มีความน่าจะเป็นสูงกว่า

ตัวอย่างต่อไปนี้แสดงให้เห็นการทำงานของอัลกอริธึม LZW โดยแสดงสถานะของเอาต์พุตและพจนานุกรมในทุกขั้นตอน ทั้งในการเข้ารหัสและถอดรหัสข้อมูล ตัวอย่างนี้สร้างขึ้นเพื่อให้ได้การบีบอัดที่เหมาะสมสำหรับข้อความสั้น ๆ ในข้อมูลข้อความจริง การทำซ้ำมักไม่เด่นชัดนัก ดังนั้นโดยทั่วไปจึงจำเป็นต้องใช้สตรีมอินพุตที่ยาวกว่าก่อนที่การบีบอัดจะให้ประสิทธิภาพที่ดีขึ้น

ข้อความต้นฉบับที่จะเข้ารหัส (จากตัวอักษรที่ใช้เฉพาะตัวพิมพ์ใหญ่) คือ:

TOBEORNOTTOBEORTOBEORNOT# 

ตัวอักษรในข้อความต้นฉบับมี 26 ตัว (ตัวพิมพ์ใหญ่AถึงZ ) #ใช้สำหรับแทนรหัสหยุด: รหัสที่อยู่นอกเหนือตัวอักษรในข้อความต้นฉบับซึ่งจะทำให้เกิดการประมวลผลพิเศษ เรากำหนดค่า 1 ถึง 26 ให้กับตัวอักษร และ 0 สำหรับรหัสหยุด '#' โดยพลการ (โดยทั่วไปแล้ว LZW ส่วนใหญ่จะวางรหัสหยุดไว้หลังตัวอักษรข้อมูล แต่ไม่มีข้อกำหนดใดในอัลกอริธึมพื้นฐานที่บังคับให้เป็นเช่นนั้น ตัวเข้ารหัสและตัวถอดรหัสเพียงแค่ต้องตกลงกันว่ารหัสหยุดมีค่าเท่าใด)

คอมพิวเตอร์จะแปลงค่าเหล่านี้เป็นสตริงของบิตจำเป็นต้องใช้รหัส 5 บิตเพื่อให้ได้ชุดค่าผสมที่เพียงพอสำหรับค่าทั้ง 27 ค่า พจนานุกรมเริ่มต้นด้วยค่าทั้ง 27 ค่านี้ เมื่อพจนานุกรมมีขนาดใหญ่ขึ้น ความกว้างของรหัสจะต้องเพิ่มขึ้นเพื่อรองรับรายการเพิ่มเติม รหัส 5 บิตให้ ชุดค่าผสมของบิตที่เป็นไปได้ ^2⁵ = 32 ชุด ดังนั้นเมื่อสร้างคำในพจนานุกรมคำที่ 33 อัลกอริทึมจะต้องเปลี่ยนจากสตริง 5 บิตเป็นสตริง 6 บิต (สำหรับ ค่ารหัส ทั้งหมดรวมถึงค่าที่เคยแสดงผลด้วย 5 บิต) โปรดทราบว่าเนื่องจากมีการใช้รหัสศูนย์ทั้งหมด 00000 และถูกกำหนดให้เป็น "0" ดังนั้นรายการในพจนานุกรมคำที่ 33 จึงถูกกำหนดให้เป็น32 (ผลลัพธ์ที่สร้างขึ้นก่อนหน้านี้จะไม่ได้รับผลกระทบจากการเปลี่ยนแปลงความกว้างของรหัส แต่เมื่อสร้างค่า 6 บิตในพจนานุกรมแล้ว ค่าดังกล่าวอาจเป็นรหัสถัดไปที่ถูกสร้างขึ้น ดังนั้นความกว้างสำหรับผลลัพธ์ถัดไปจะเปลี่ยนเป็น 6 บิตเพื่อรองรับค่าดังกล่าว)

ดังนั้น พจนานุกรมฉบับเริ่มต้นจึงประกอบด้วยรายการต่อไปนี้:

บัฟเฟอร์อักขระอินพุตในลำดับ ω จนกว่า ω + อักขระถัดไปจะไม่อยู่ในพจนานุกรม ส่งรหัสสำหรับ ω และเพิ่ม ω + อักขระถัดไปลงในพจนานุกรม เริ่มบัฟเฟอร์อีกครั้งด้วยอักขระถัดไป (สตริงที่จะเข้ารหัสคือ "TOBEORNOTTOBEORTOBEORNOT#")

ความยาวก่อนเข้ารหัส = 25 สัญลักษณ์ × 5 บิต/สัญลักษณ์ = 125 บิต

ความยาวของการเข้ารหัส = (6 รหัส × 5 บิต/รหัส) + (11 รหัส × 6 บิต/รหัส) = 96 บิต

การใช้ LZW ช่วยประหยัดบิตได้ 29 บิตจากทั้งหมด 125 บิต ลดขนาดข้อความลงได้มากกว่า 23% หากข้อความยาวกว่านี้ คำศัพท์ในพจนานุกรมก็จะเริ่มแทนส่วนของข้อความที่ยาวขึ้นเรื่อยๆ ทำให้การส่งคำซ้ำๆ เป็นไปอย่างกระชับมาก

ในการถอดรหัสไฟล์เก็บถาวรที่บีบอัดด้วย LZW จำเป็นต้องทราบพจนานุกรมเริ่มต้นที่ใช้ล่วงหน้า แต่สามารถสร้างรายการเพิ่มเติมขึ้นใหม่ได้ เนื่องจากรายการเหล่านั้นมักเป็นการนำรายการก่อนหน้ามา ต่อกัน

ในแต่ละขั้นตอน ตัวถอดรหัสจะได้รับรหัส X; มันจะค้นหา X ในตารางและส่งออกลำดับ χ ที่มันเข้ารหัส และมันจะคาดเดาว่า χ + ? คือรายการที่ตัวเข้ารหัสเพิ่งเพิ่มเข้าไป – เนื่องจากตัวเข้ารหัสส่งค่า X สำหรับ χ ออกมาอย่างแม่นยำเพราะ χ + ? ไม่อยู่ในตาราง และตัวเข้ารหัสจึงดำเนินการเพิ่มเข้าไป แต่ตัวอักษรที่หายไปคืออะไร? มันคือตัวอักษรตัวแรกในลำดับที่เข้ารหัสโดย รหัส Z ถัดไปที่ตัวถอดรหัสได้รับ ดังนั้นตัวถอดรหัสจึงค้นหา Z ถอดรหัสเป็นลำดับ ω และนำตัวอักษรตัวแรก z มาต่อท้าย χ เป็นรายการพจนานุกรมถัดไป

วิธีนี้ใช้ได้ตราบใดที่รหัสที่ได้รับอยู่ในพจนานุกรมของตัวถอดรหัส เพื่อให้สามารถถอดรหัสเป็นลำดับได้ แล้วจะเกิดอะไรขึ้นถ้าตัวถอดรหัสได้รับรหัส Z ที่ยังไม่มีอยู่ในพจนานุกรม? เนื่องจากตัวถอดรหัสจะตามหลังตัวเข้ารหัสอยู่เพียงหนึ่งรหัสเสมอ รหัส Z จะอยู่ในพจนานุกรมของตัวเข้ารหัสได้ก็ต่อเมื่อตัวเข้ารหัสเพิ่งสร้างมันขึ้นมาเมื่อส่งรหัส X ก่อนหน้าสำหรับ χ ดังนั้น Z จึงเข้ารหัส ω บางตัวที่เป็น χ + ? และตัวถอดรหัสสามารถระบุอักขระที่ไม่ทราบค่าได้ดังนี้:

1. ตัวถอดรหัสจะเห็น X ก่อน แล้วจึงเห็น Z โดยที่ X เข้ารหัสลำดับ χ และ Z เข้ารหัสลำดับ ω ที่ไม่ทราบค่า
2. ตัวถอดรหัสรู้ว่าตัวเข้ารหัสได้เพิ่ม Z เป็นรหัสสำหรับ χ + อักขระที่ไม่ทราบค่าc ดังนั้น ω = χ + c
3. เนื่องจากcเป็นอักขระตัวแรกในสตรีมอินพุตหลังจาก χ และเนื่องจาก ω เป็นสตริงที่ปรากฏต่อจาก χ ทันที ดังนั้นcจึงต้องเป็นอักขระตัวแรกของลำดับ ω
4. เนื่องจาก χ เป็นสตริงย่อยเริ่มต้นของ ω ดังนั้นcจึงต้องเป็นอักขระตัวแรกของ χ ด้วยเช่นกัน
5. ดังนั้น แม้ว่ารหัส Z จะไม่อยู่ในตาราง แต่ตัวถอดรหัสก็สามารถอนุมานลำดับที่ไม่ทราบค่าได้ และเพิ่ม χ + (อักขระตัวแรกของ χ) ลงในตารางเป็นค่าของ Z

สถานการณ์นี้เกิดขึ้นเมื่อใดก็ตามที่ตัวเข้ารหัสพบข้อมูลป้อนเข้าในรูปแบบcScScโดยที่cเป็นอักขระตัวเดียวSเป็นสตริง และcSมีอยู่ในพจนานุกรมแล้ว แต่cScไม่มี ตัวเข้ารหัสจะส่งรหัสสำหรับcS ออกมา ทำให้รหัสใหม่สำหรับcSc ถูกเพิ่ม เข้าไปในพจนานุกรม จากนั้น เมื่อตัวเข้ารหัสเห็นcScในข้อมูลป้อนเข้า (เริ่มต้นที่c ตัวที่สอง ของcScSc ) มันจะส่งรหัสใหม่ที่เพิ่งเพิ่มเข้าไปออกมา ข้อโต้แย้งข้างต้นแสดงให้เห็นว่าเมื่อใดก็ตามที่ตัวถอดรหัสได้รับรหัสที่ไม่มีอยู่ในพจนานุกรม สถานการณ์จะต้องเป็นเช่นนี้

แม้ว่ารูปแบบการป้อนข้อมูลcScScอาจดูไม่น่าเป็นไปได้ แต่รูปแบบนี้ค่อนข้างพบได้บ่อยเมื่อกระแสข้อมูลขาเข้ามีลักษณะของการทำซ้ำจำนวนมาก โดยเฉพาะอย่างยิ่ง สตริงยาวๆ ของอักขระตัวเดียว (ซึ่งพบได้ทั่วไปในภาพประเภทที่ LZW มักใช้ในการเข้ารหัส) จะสร้างรูปแบบประเภทนี้ซ้ำๆ กัน

มีการออกสิทธิบัตรต่างๆ ใน สหรัฐอเมริกาและประเทศอื่นๆ สำหรับอัลกอริทึม LZW และอัลกอริทึมที่คล้ายคลึงกัน LZ78 ได้รับการคุ้มครองโดยสิทธิบัตรของสหรัฐอเมริกาหมายเลข 4,464,650โดย Lempel, Ziv, Cohn และ Eastman ซึ่งมอบสิทธิ์ให้แก่Sperry Corporationต่อมาคือUnisys Corporation ยื่นขอเมื่อวันที่ 10 สิงหาคม 1981 มีการออกสิทธิบัตรของสหรัฐอเมริกา 2 ฉบับสำหรับอัลกอริทึม LZW ได้แก่สิทธิบัตรของสหรัฐอเมริกาหมายเลข 4,814,746โดยVictor S. MillerและMark N. Wegmanซึ่งมอบสิทธิ์ให้แก่IBMยื่นขอครั้งแรกเมื่อวันที่ 1 มิถุนายน 1983 และสิทธิบัตรของสหรัฐอเมริกาหมายเลข 4,558,302โดย Welch ซึ่งมอบสิทธิ์ให้แก่ Sperry Corporation ต่อมาคือ Unisys Corporation ยื่นขอเมื่อวันที่ 20 มิถุนายน 1983

นอกจากสิทธิบัตรข้างต้นแล้ว สิทธิบัตรของเวลช์ในปี 1983 ยังมีการอ้างอิงถึงสิทธิบัตรอื่นๆ อีกหลายฉบับที่มีอิทธิพลต่อสิทธิบัตรดังกล่าว ได้แก่ สิทธิบัตรของญี่ปุ่น 2 ฉบับในปี 1980 ( JP9343880AและJP17790880A ) จากจุน คานัตสึ แห่งNEC สิทธิบัตรของสหรัฐอเมริกาหมายเลข 4,021,782 (1974) จากจอห์น เอส. โฮร์นิงสิทธิบัตรของสหรัฐอเมริกาหมายเลข 4,366,551 (1977) จากเคลาส์ อี. โฮลทซ์ และสิทธิบัตรของเยอรมนีในปี 1981 ( DE19813118676 ) จากคาร์ล เอ็คฮาร์ท ไฮนซ์^{[ 3 ]}

ในปี 1993–1994 และอีกครั้งในปี 1999 บริษัท Unisys Corporation ได้รับการประณามอย่างกว้างขวางเมื่อพยายามบังคับใช้ค่าลิขสิทธิ์สำหรับไฟล์ LZW ในภาพ GIF ข้อพิพาทระหว่าง Unisys และ CompuServe ในปี 1993–1994 ( CompuServeเป็นผู้สร้างรูปแบบไฟล์ GIF) กระตุ้นให้เกิด การสนทนาใน Usenet comp.graphics ในหัวข้อ "ความคิดเห็นเกี่ยวกับรูปแบบไฟล์ทดแทน GIF" ซึ่งนำไปสู่การแลกเปลี่ยนอีเมลที่ในที่สุดก็ส่งผลให้เกิดการสร้างรูปแบบไฟล์ Portable Network Graphics (PNG) ที่ไม่ติดสิทธิบัตรในปี 1995

สิทธิบัตรของ Unisys ในสหรัฐอเมริกาเกี่ยวกับอัลกอริทึม LZW หมดอายุเมื่อวันที่ 20 มิถุนายน พ.ศ. 2546 ^{[ 4 ]} 20 ปีหลังจากที่ยื่นจดสิทธิบัตร สิทธิบัตรที่ยื่นจดในสหราชอาณาจักร ฝรั่งเศส เยอรมนี อิตาลี ญี่ปุ่น และแคนาดา ต่างก็หมดอายุในปี พ.ศ. 2547 ^{[ 4 ]}เช่นเดียวกัน 20 ปีหลังจากที่ยื่นจดสิทธิบัตร

LZMW (1985) โดยVictor MillerและMark Wegman [ ^{5 ] ค้นหา}อินพุตสำหรับสตริงที่ยาวที่สุดที่มีอยู่แล้วในพจนานุกรม (การจับคู่ "ปัจจุบัน") จากนั้นเพิ่มการต่อกันของการจับคู่ก่อนหน้ากับการจับคู่ปัจจุบันลงในพจนานุกรม รายการในพจนานุกรมจึงเติบโตเร็วขึ้น แต่แผนการนี้ซับซ้อนกว่ามากในการนำไปใช้ Miller และ Wegman แนะนำให้ลบรายการที่มีความถี่ต่ำออกจากพจนานุกรมเมื่อพจนานุกรมเต็ม

LZAP (1988) โดย James Storer ^{[ 6 ]}เป็นการดัดแปลง LZMW แทนที่จะเพิ่มเพียงการต่อกันของการจับคู่ก่อนหน้ากับการจับคู่ปัจจุบันลงในพจนานุกรม ให้เพิ่มการต่อกันของการจับคู่ก่อนหน้ากับสตริงย่อยเริ่มต้นแต่ละสตริงของการจับคู่ปัจจุบัน ("AP" ย่อมาจาก "all prefixes") ตัวอย่างเช่น หากการจับคู่ก่อนหน้าคือ "wiki" และการจับคู่ปัจจุบันคือ "pedia" ตัวเข้ารหัส LZAP จะเพิ่มลำดับใหม่ 5 ลำดับลงในพจนานุกรม ได้แก่ "wikip", "wikipe", "wikiped", "wikipedi" และ "wikipedia" ในขณะที่ตัวเข้ารหัส LZMW จะเพิ่มเพียงลำดับเดียวคือ "wikipedia" วิธีนี้ช่วยลดความซับซ้อนของ LZMW ลงได้ แต่ต้องแลกมาด้วยการเพิ่มรายการในพจนานุกรมมากขึ้น

LZWLเป็นรูปแบบหนึ่งของ LZW ที่แบ่งตามพยางค์

• การถ่วงน้ำหนักต้นไม้บริบท
• การแปลงโคไซน์แบบไม่ต่อเนื่อง  – เทคนิคที่ใช้ในการประมวลผลสัญญาณและการบีบอัดข้อมูล
• LZMA  – อัลกอริทึมการบีบอัดแบบไม่สูญเสียข้อมูลหน้าเว็บที่แสดงคำอธิบายสั้น ๆ ของเป้าหมายการเปลี่ยนเส้นทาง
• Lempel–Ziv–Storer–Szymanski  – อัลกอริธึมการบีบอัดข้อมูลแบบไม่สูญเสียข้อมูล
• LZ77 และ LZ78  – อัลกอริทึมการบีบอัดข้อมูลแบบไม่สูญเสียข้อมูล
• LZJB – อัลกอริทึมการบีบอัดข้อมูลแบบไม่สูญเสียสำหรับ ZFS

• วิกิ Rosettacode: อัลกอริทึมในภาษาต่างๆ
• สิทธิบัตรสหรัฐอเมริกาหมายเลข 4,558,302เทอร์รี เอ. เวลช์อุปกรณ์และวิธีการบีบอัดและคลายข้อมูลความเร็วสูง
• SharpLZW – การใช้งานแบบโอเพนซอร์สด้วยภาษา C#
• MIT OpenCourseWare: การบรรยายเกี่ยวกับอัลกอริธึม LZW
• มาร์ค เนลสัน, การบีบอัดข้อมูล LZWในวารสารของดร. ด็อบส์ (1 ตุลาคม 1989)
• Shrink, Reduce, and Implode: The Legacy Zip Compression Methodsอธิบายถึง LZW และวิธีการใช้งานในPKZIP