خوارزمية LZW لضغط البيانات: كيف تعمل ولماذا لا تزال مهمة

LZW اختصار لـ Lempel-Ziv-Welch، وهي خوارزمية لضغط البيانات بلا فقدان (Lossless) — أي أنها تصغّر حجم الملف دون أن تفقد أي بايت من محتواه الأصلي. فكرتها الأساسية بسيطة وأنيقة: بدلاً من تخزين الأنماط المتكررة في البيانات مراراً، تبني الخوارزمية "قاموساً" ديناميكياً يعطي كل نمط متكرر رمزاً رقمياً قصيراً، فتستبدل النص الطويل بأرقام. وأهم ما يميزها أنها لا تحتاج إلى إرسال هذا القاموس مع الملف المضغوط، لأن برنامج فك الضغط يعيد بناءه بنفسه — وهذه هي نقطة عبقريتها التي سنشرحها بعد قليل.

من أين جاء الاسم؟

الخوارزمية ثمرة تطوّر على مرحلتين. أولاً نشر الباحثان الإسرائيليان يعقوب زيف وأبراهام ليمبل خوارزميتَي LZ77 (عام 1977) وLZ78 (عام 1978)، وهما أساس معظم أدوات الضغط الحديثة. ثم جاء تيري ويلش عام 1984 وقدّم نسخة عملية محسّنة من LZ78، فأُضيف اسمه لتصبح LZW. الفكرة كانت جعل الخوارزمية سريعة وسهلة التنفيذ في العتاد والبرمجيات معاً، وهو ما جعلها تنتشر بسرعة كبيرة في الثمانينيات والتسعينيات.

كيف تعمل الخوارزمية فعلياً؟

تمرّ عملية الضغط بثلاث خطوات متكررة:

1. تهيئة القاموس: يبدأ القاموس محمّلاً مسبقاً بكل الرموز المفردة الممكنة — عادةً 256 قيمة تمثّل كل البايتات من 0 إلى 255. لا نبدأ من فراغ.
2. قراءة البيانات تدريجياً: تُقرأ البيانات حرفاً حرفاً مع تجميع "سلسلة حالية". طالما أن السلسلة الحالية موجودة في القاموس، تستمر الخوارزمية في ضمّ الحرف التالي إليها.
3. الإخراج والتعلّم: عند أول سلسلة غير موجودة في القاموس، تُخرج الخوارزمية رمز السلسلة الأقصر (التي كانت موجودة)، ثم تضيف السلسلة الجديدة الأطول إلى القاموس برمز جديد، وتبدأ من جديد. هكذا "يتعلّم" القاموس أنماطاً أطول كلما تقدّمنا في الملف.

مثال عملي مبسّط

لنضغط النص ABABABA (سبعة أحرف). القاموس يبدأ بـ A وB فقط:

• نقرأ A → موجودة، السلسلة الحالية = A.
• نقرأ B → AB غير موجودة: نُخرج رمز A، ونضيف AB للقاموس، نبدأ بـ B.
• نقرأ A → BA غير موجودة: نُخرج رمز B، ونضيف BA، نبدأ بـ A.
• نقرأ B → AB موجودة الآن: السلسلة الحالية = AB.
• نقرأ A → ABA غير موجودة: نُخرج رمز AB، ونضيف ABA، نبدأ بـ A.
• نقرأ B ثم A → ABA موجودة: السلسلة الحالية = ABA.
• انتهى النص: نُخرج رمز ABA.

النتيجة: سبعة أحرف تحوّلت إلى أربعة رموز فقط (A, B, AB, ABA). ولاحظ كيف أن الرموز الأخيرة صارت تمثّل مقاطع أطول — وكلما زاد التكرار في الملف، ازدادت نسبة الضغط.

لماذا لا نحتاج إلى إرسال القاموس؟

هذه النقطة تربك كثيرين. برنامج فك الضغط يبدأ بنفس القاموس الأولي (البايتات 0–255)، ثم يقرأ الرموز الواردة ويعيد بناء نفس السلاسل بنفس الترتيب الذي بناها به الضاغط. أي أن الطرفين يتّبعان القاعدة ذاتها، فيتولّد القاموس نفسه تلقائياً عند الطرفين. لهذا لا نضيّع أي مساحة على إرسال جدول القاموس — وهو ما يجعل LZW سريعة وموفّرة في آنٍ واحد.

أين تُستخدم LZW اليوم؟

رغم قِدمها، لا تزال حاضرة في أماكن قد تستعملها يومياً:

• صيغة الصور GIF: تعتمد على LZW كلياً، وكذلك تدعمها صيغة TIFF.
• ملفات PDF: أحد مرشّحات الضغط المتاحة داخلها.
• أداة compress في أنظمة يونكس القديمة (ملفات .Z).

نقطة مهمة للسياق التاريخي: كانت شركة Unisys تملك براءة اختراع على LZW، ما أثار جدلاً حول استخدام GIF في التسعينيات ودفع المجتمع إلى ابتكار صيغة PNG الحرّة (التي تستخدم خوارزمية DEFLATE بدل LZW). انتهت صلاحية تلك البراءة منذ سنوات، وصارت LZW اليوم متاحة للجميع دون قيود.

LZW أم Huffman؟ مقارنة سريعة

كثيراً ما تُقارن LZW بترميز هوفمان، وهما يعملان بمنطقين مختلفين تماماً وغالباً ما يُدمجان معاً:

الجانب	LZW	ترميز هوفمان (Huffman)
الفكرة	استبدال السلاسل المتكررة برموز	إعطاء الرموز الأكثر شيوعاً أكواداً أقصر
القاموس	يُبنى ديناميكياً أثناء العمل	يعتمد على تكرار كل رمز
الحاجة لتمرير جدول	لا (يُعاد بناؤه)	نعم عادةً (شجرة الترميز)
الأفضل مع	البيانات ذات الأنماط المتكررة	البيانات ذات توزيع تكراري غير متساوٍ

في الممارسة الحديثة، خوارزمية DEFLATE (المستخدمة في ZIP وPNG وGZIP) تجمع بين منطق LZ ومنطق هوفمان معاً لتحصل على أفضل ما في العالمين.

نصيحة عملية وخطأ شائع

الخطأ الأكثر شيوعاً هو الظن بأن LZW تضغط أي ملف. الحقيقة أن كفاءتها تعتمد على وجود تكرار. إذا مررت عليها بيانات عشوائية تماماً أو ملفاً مضغوطاً مسبقاً (مثل JPEG أو ZIP)، فقد يكبر الحجم قليلاً بدل أن يصغر، لأنك تضيف رموزاً لقاموس لا يجد ما يعيد استخدامه. القاعدة العملية: الضغط بلا فقدان يفيد النصوص والصور البسيطة ذات المساحات المتكررة، وليس البيانات المشفّرة أو المضغوطة أصلاً.

الأسئلة الشائعة

هل LZW ضغط بفقدان أم بلا فقدان؟ بلا فقدان تماماً؛ تستعيد البيانات الأصلية بايتاً ببايت دون أي تغيير.

ما الفرق بين LZ77 وLZ78 وLZW؟ LZ77 وLZ78 هما الأساسان الأصليان من زيف وليمبل، أما LZW فهي تحسين عملي لـ LZ78 قدّمه ويلش ليكون أسهل تنفيذاً وأسرع.

هل ما زالت LZW مستخدمة أم صارت قديمة؟ ما زالت مستخدمة في GIF وTIFF وPDF، لكن للأغراض العامة حلّت محلها خوارزميات أحدث مثل DEFLATE وZstandard لأنها تعطي نسب ضغط أعلى.

لماذا لا تضغط بعض الملفات جيداً بـ LZW؟ لأنها تفتقر إلى الأنماط المتكررة، أو لأنها مضغوطة سلفاً، فلا يجد القاموس سلاسل يعيد استخدامها.