شرح تفصيلي لخوارزمية LZ77: كيف يعمل ضغط القاموس؟

الخلاصة أولًا: LZ77 هي خوارزمية ضغط قواميس قائمة على النافذة المنزلقة، والفكرة الجوهرية هي "استخدام البيانات التاريخية كقاموس، وعند مواجهة محتوى مكرر نشير إليه". عند الترميز تُخرَج ثلاثية (distance, length, next_char): ارجع مسافة distance من الأحرف لتجد التطابق، طول التطابق length، متبوعًا بحرف غير متطابق next_char. بأخذ "abracadabra" المؤلفة من 11 حرفًا كمثال، يكفي بعد ترميز LZ77 تمثيلها بـ 5 ثلاثيات فقط، وأثر الضغط واضح. LZ77 هي المكون الأساسي لـ DEFLATE (ZIP/GZIP/PNG)، وهي أيضًا السلف المشترك لخوارزميات الضغط الحديثة مثل LZSS/LZMA/LZ4. سنبدأ أدناه بمبدأ النافذة المنزلقة، ثم نشرح عملية الترميز خطوة بخطوة.

إذا لم تكن ملمًا بمبدأ ترميز Huffman، فننصح بقراءة مبدأ ترميز Huffman: شرح تفصيلي لحجر الأساس لخوارزميات الضغط أولًا.

أولًا: ما هو ضغط القاموس

تنقسم خوارزميات الضغط إلى مدرستين كبيرتين: الترميز الإحصائي (مثل ترميز Huffman) يخصص كلمات كود متغيرة الطول حسب تكرار الأحرف؛ ضغط القاموس يستبدل المحتوى المكرر بـ "مرجع بمؤشر". تنتمي LZ77 إلى مدرسة ضغط القاموس، فهي لا تبني جدول قاموس مسبقًا، بل تستخدم البيانات التاريخية المعالجة كقاموس ضمني — عند مواجهة محتوى مكرر، تستخدم "مؤشر رجوع" يشير إلى الموضع الذي ظهر فيه سابقًا.

مدرسة الضغط	المبدأ الجوهري	الخوارزميات الممثلة	الميزة	العيب
الترميز الإحصائي	تخصيص أكواد متغيرة الطول حسب التردد	Huffman، الترميز الحسابي	يقترب من الحد الأدنى للإنتروبيا	غير ملائم للتكرار بعيد المدى
ضغط القاموس	استبدال المحتوى المكرر بمرجع	LZ77، LZW، LZMA	ممتاز في أنماط التكرار	غير فعّال على البيانات العشوائية
الترميز الهجين	مرحلتان: قاموس + إحصاء	DEFLATE، ZSTD	التوليفة المثلى	التنفيذ أعقد
ترميز التحويل	التحويل إلى مجال التردد ثم التكميم	DCT (JPEG)، DWT	ضغط فاقد بكفاءة عالية	يوجد فقد في المعلومات

تقريبًا كل خوارزميات الضغط الشائعة في الممارسة هي "ترميز هجين" — أولًا تُزال أنماط التكرار عبر LZ77، ثم يُضغط الباقي بالتردد عبر Huffman. وDEFLATE هو التركيب الكلاسيكي لـ LZ77 + Huffman، ويُستخدم على نطاق واسع في ZIP وGZIP وPNG.

ثانيًا: شرح تفصيلي لمبدأ خوارزمية LZ77

جوهر LZ77 هو آلية النافذة المنزلقة. تنقسم النافذة إلى جزأين: المخزن المؤقت للبحث (البيانات التاريخية المعالجة) والمخزن الأمامي (البيانات المستقبلية المراد معالجتها). عند الترميز تُؤخذ قطعة من المخزن الأمامي، ويُبحث عن أطول تطابق في المخزن المؤقت للبحث، فإذا وُجد التطابق تُخرج الثلاثية، وإلا يُخرج الحرف الأصلي.

1. بنية النافذة المنزلقة

يحدد حجم النافذة المنزلقة أثر الضغط مباشرة — كلما كانت النافذة أكبر، زادت البيانات التاريخية القابلة للرجوع، وارتفع احتمال التطابق. وتتفاوت أحجام النوافذ بين الخوارزميات تفاوتًا كبيرًا.

الخوارزمية	المخزن المؤقت للبحث	المخزن الأمامي	أقصى طول تطابق	السيناريو النموذجي
LZ77 الأصلية	بضعة كيلوبايت	عشرون بايتًا	16 بايت	مثال تعليمي
DEFLATE	32KB	258 بايت	258 بايت	ZIP/GZIP/PNG
LZMA	8MB (قابل للتكوين)	273 بايت	273 بايت	أرشيف 7z/xz
LZ4	64KB	بلا حد	بلا حد	ضغط في الزمن الحقيقي
ZSTD	8MB (بحد أقصى 1GB)	بلا حد	بلا حد	عامة حديثة

2. تنسيق ترميز الثلاثية

وحدة الإخراج في LZ77 هي الثلاثية (distance, length, next_char)، وفيما يلي معاني الحقول الثلاثة.

الحقل	المعنى	نطاق القيم (DEFLATE)	عدد البتات	مثال
distance	مسافة الرجوع (كم حرفًا للوراء للبحث عن التطابق)	1–32768	15 بت	distance=10 → 10 أحرف للخلف
length	طول التطابق (كم حرفًا متتاليًا تطابق)	3–258	8 بت	length=5 → تطابق 5 أحرف
next_char	الحرف التالي بعد التطابق	0–255	8 بت	next_char='d' → ASCII 100

البراعة في الثلاثية هي: بعد انتهاء التطابق يُخرَج next_char إضافي، مما يضمن أن المُرمِّز يتقدم دائمًا خطوة واحدة على الأقل، فلا يتوقف. إذا لم يُعثر على أي تطابق (length=0)، يكون كل من distance وlength صفرًا، ويُخرج next_char فقط — أي ينحسر إلى تخزين الحرف الأصلي.

3. استراتيجية البحث عن التطابق

البحث عن التطابق هو عنق الزجاجة في أداء LZ77 — تُؤخذ قطعة من المخزن الأمامي، ويُبحث عن أطول تطابق في المخزن المؤقت للبحث. البحث العنيف ذو تعقيد O(n×m)، لكن التطبيقات العملية تسرّعه عبر جداول التجزئة أو شجرة اللواحق.

استراتيجية البحث	بنية البيانات	تعقيد البحث	التكلفة المكانية	التطبيق النموذجي
البحث العنيف	بلا	O(n×m)	بلا	مثال تعليمي
سلسلة التجزئة	جدول تجزئة + قائمة مرتبطة	O(n) متوسط	منخفض	zlib (DEFLATE)
دلو التجزئة	جدول تجزئة + مصفوفة	O(1) متوسط	متوسط	LZ4
شجرة اللواحق	شجرة لاحقة / مصفوفة لاحقة	O(n) في أسوأ الحالات	عالٍ	LZMA

ثالثًا: دراسة حالة عملية — عرض ترميز "abracadabra"

نُرمِّز "abracadabra" (11 حرفًا) عبر LZ77 بشكل كامل. في الحالة الابتدائية يكون المخزن المؤقت للبحث فارغًا، والمخزن الأمامي هو السلسلة بأكملها. نمسح موضعًا تلو الآخر، ونبحث عن أطول تطابق في البيانات التاريخية.

النص الأصلي: a b r a c a d a b r a

عملية الترميز:

الخطوة	الموضع الحالي	المحتوى الأمامي	البحث في المخزن المؤقت	الثلاثية المُخرَجة	الوصف
1	الموضع 1	abracadabra	فارغ، بلا تطابق	(0, 0, 'a')	الحرف الأول، إخراج مباشر
2	الموضع 2	bracadabra	"a"، لا يوجد تطابق لـ "b"	(0, 0, 'b')	ظهور أول، إخراج مباشر
3	الموضع 3	racadabra	"ab"، لا يوجد تطابق لـ "r"	(0, 0, 'r')	ظهور أول، إخراج مباشر
4	الموضع 4	acadabra	وُجد "a" في "abr"	(0, 0, 'a')	"a" موجود لكن ما بعده لا يتطابق
5	الموضع 5	cadabra	لا يوجد "c" في "abra"	(0, 0, 'c')	ظهور أول، إخراج مباشر
6	الموضع 6	adabra	وُجد "a" في "abrac"	(0, 0, 'a')	"a" يتطابق لكن ما بعده لا
7	الموضع 7	dabra	لا يوجد "d" في "abraca"	(0, 0, 'd')	ظهور أول، إخراج مباشر
8	الموضع 8	abra	بالرجوع 7 وُجد تطابق "abra"	(7, 4, end)	تطابق 4 أحرف "abra"

مقارنة كفاءة الترميز:

طريقة الترميز	عدد وحدات الإخراج	بت لكل وحدة	إجمالي البتات	التوفير مقارنة بالأصلي
ASCII الأصلي	11 حرفًا	8	88	— (مرجعي)
LZ77 (بدون تحسين المطابقة)	8 ثلاثيات	31 (متوسط)	248	-182% (تضخم)
LZ77 (تحسين بت العلم)	8 وحدات	12 (متوسط)	96	-9% (تضخم طفيف)
LZ77 + Huffman	8 وحدات	4.5 (متوسط)	36	59%

تحليل النتيجة: LZ77 الصافية قد تتسبب في تضخم النصوص القصيرة (الثلاثية تشغل مساحة أكبر من الحرف الأصلي)، ولهذا تُجمع LZ77 عادةً مع ترميز Huffman — وDEFLATE هو LZ77 + Huffman. في حالة "abracadabra"، فإن تطابق "abra" في الموضع 8 (distance=7, length=4) هو نقطة الضغط الجوهرية، إذ يُمثَّل 4 أحرف بثلاثية واحدة. أما النصوص الأطول ذات الأنماط المتكررة (كالكود والسجلات)، فإن أثر ضغط LZ77 يكون أوضح بكثير.

رابعًا: متغيرات LZ77 وتطورها الحديث

منذ أن طُرحت LZ77 عام 1977، تفرعت منها متغيرات كثيرة، كل منها يُحسّن بُعدًا محددًا لسيناريو معين. يقارن الجدول التالي أبرز أعضاء عائلة LZ77.

الخوارزمية	التحسين الجوهري	نسبة الضغط	سرعة الضغط	سرعة فك الضغط	التطبيق النموذجي
LZ77 (الأصلية)	ترميز الثلاثية	منخفضة	بطيئة	متوسطة	تعليم
LZSS	بت علم للتمييز بين التطابق والحرف الحرفي	متوسطة	متوسطة	سريعة	أنظمة مبكرة
DEFLATE	LZSS + Huffman بمرحلتين	متوسطة–عالية	متوسطة	سريعة	ZIP/GZIP/PNG
LZMA	نافذة كبيرة + ترميز فاصل + تحليل أمثل	عالية	بطيئة	متوسطة	أرشيف 7z/xz
LZ4	التضحية بنسبة الضغط مقابل السرعة القصوى	منخفضة	سريعة جدًا	سريعة جدًا (4GB/s)	الزمن الحقيقي / النواة
LZW	جدول قاموس صريح (ليست نافذة منزلقة)	متوسطة	سريعة	سريعة	GIF/TIFF
ZSTD	متغير LZ77 + FSE + إعدادات قاموس مسبقة	عالية	سريعة	سريعة جدًا	عامة حديثة

من منظور التطور، الخوارزميات الحديثة (ZSTD، brotli) رفعت السرعة بشكل كبير مع الحفاظ على نسبة ضغط عالية، وبدأت تحل تدريجيًا محل DEFLATE بوصفها المعيار الجديد. لكن الفكرة الجوهرية لـ LZ77 — إشارة القاموس عبر النافذة المنزلقة — لم تتغير، فجميع المتغيرات تبنى على هذا الأساس.

السيناريو	الخوارزمية الموصى بها	السبب	نسبة الضغط المرجعية
أرشفة الملفات	LZMA (xz)	أعلى نسبة ضغط، لا تهتم بالسرعة	70%–85%
ضغط عام	ZSTD	توازن بين الضغط والسرعة	60%–80%
نقل في الزمن الحقيقي	LZ4	سرعة فك ضغط 4GB/s، زمن انتقال منخفض جدًا	50%–65%
نقل عبر الويب	DEFLATE/GZIP	أفضل توافقية، مدعوم في كل المتصفحات	50%–70%
صيغ الصور	DEFLATE (PNG)	ضغط غير فاقد، مناسب للرسوميات	50%–75%
بيانات في الذاكرة	LZ4	استهلاك CPU منخفض، مناسب للضغط المتكرر	50%–65%

للتطبيق الفعلي لـ DEFLATE في صيغة PNG، يمكنك الرجوع إلى شرح تفصيلي لمبدأ ضغط PNG. وللفرق بين الضغط غير الفاقد والفاقد، يمكنك الرجوع إلى الضغط غير الفاقد مقابل الفاقد: الفرق الجوهري.

خامسًا: الأسئلة الشائعة

س1: ما هي خوارزمية LZ77؟

LZ77 هي خوارزمية ضغط قواميس قائمة على النافذة المنزلقة، اقترحها Lempel وZiv عام 1977. الفكرة الجوهرية: استخدام البيانات المعالجة سابقًا كقاموس، وعند مواجهة محتوى مكرر تستبدله بثلاثية (distance, length, next_char)، حيث distance تشير إلى مسافة الرجوع، وlength إلى طول التطابق، وnext_char إلى الحرف التالي بعد التطابق. LZ77 هي المكون الأساسي لـ DEFLATE (ZIP/GZIP/PNG)، وهي أيضًا سلف الخوارزميات الحديثة مثل LZSS/LZMA/LZ4.

س2: ما المقصود بالنافذة المنزلقة في LZ77؟

النافذة المنزلقة هي بنية البيانات الجوهرية في LZ77، وتنقسم إلى المخزن المؤقت للبحث (البيانات التاريخية المعالجة) والمخزن الأمامي (البيانات المستقبلية المراد معالجتها). عند الترميز تُؤخذ قطعة من المخزن الأمامي، ويُبحث عن أطول تطابق في المخزن المؤقت للبحث. حجم النافذة النموذجي 32KB (معيار DEFLATE)، وكلما زاد حجم النافذة زاد احتمال التطابق لكن ازداد استهلاك الذاكرة. يحدد حجم النافذة الحد الأعلى لمسافة الرجوع distance.

س3: ما الفرق بين LZ77 وLZ78؟

LZ77 تستخدم نافذة منزلقة كقاموس ضمني، والمحتوى المتطابق يُشار إليه مباشرة في البيانات التاريخية دون تخزين قاموس مستقل؛ أما LZ78 فستخدم جدول قاموس صريح، تخزن فيه السلاسل المرئية كأرقام في القاموس، وعند الترميز تُخرج فهرس القاموس. LZ77 أنسب للبيانات ذات التكرار المحلي (كالنصوص)، وLZ78 أنسب للبيانات ذات التكرار الشامل. في الممارسة، خلفاء LZ77 (DEFLATE/LZMA/LZ4) أكثر شيوعًا بكثير من خلفاء LZ78 (LZW).

س4: أيهم أعلى نسبة ضغط: LZ77 أم LZMA أم LZ4؟

ترتيب نسبة الضغط: LZMA > LZ77 (DEFLATE) > LZ4. LZMA تستخدم نافذة أكبر (افتراضيًا 8MB) وخوارزمية مطابقة أمثل وترميز فاصل، فأعلى نسبة ضغط لكن الأبطأ؛ DEFLATE نافذة 32KB + Huffman، فنسبة ضغط متوسطة وسرعة متوسطة؛ LZ4 تضحي بنسبة الضغط مقابل السرعة القصوى، فأقل نسبة ضغط لكن سرعة فك الضغط تصل إلى 4GB/s. الاختيار يعتمد على السيناريو: للأرشفة LZMA، وللاستخدام العام DEFLATE/ZSTD، وللزمن الحقيقي LZ4.

الخلاصة

LZ77 هي رائدة خوارزميات ضغط القاموس، ومبدأها الجوهري هو "النافذة المنزلقة + إشارة الثلاثية": استخدام البيانات التاريخية كقاموس ضمني، وعند مواجهة محتوى مكرر تُخرج ثلاثية (distance, length, next_char). LZ77 الصافية قد تتسبب في تضخم النصوص القصيرة، لكنها مع ترميز Huffman (DEFLATE) أصبحت مخطط الضغط القياسي لـ ZIP/GZIP/PNG. تسعى المتغيرات الحديثة LZMA إلى أعلى نسبة ضغط، وLZ4 إلى أعلى سرعة، وZSTD إلى التوليفة المثلى.

ثلاث نقاط أساسية لفهم LZ77: أولًا النافذة المنزلقة تحدد نطاق المطابقة (DEFLATE 32KB، LZMA 8MB)، وثانيًا الثلاثية هي وحدة الترميز الأساسية (الرجوع + الطول + الحرف التالي)، وثالثًا استراتيجية البحث عن التطابق تحدد الأداء (سلسلة التجزئة الأسرع، شجرة اللواحق الأمثل). الترميز الهجين LZ77 + Huffman هو المعيار الذهبي للضغط غير الفاقد الحديث.