> lz77 | sliding | window <
// LZ77 - ضغط بنافذة منزلقة مع مراجع قاموسية
ترميز قائم على القاموس
يستخدم مراجع (إزاحة وطول) لإعادة استخدام الأنماط المتكررة.
نافذة منزلقة
يحافظ على نافذة متحركة للبحث عن أطول تطابق.
أساس الخوارزميات الحديثة
يمثل الأساس لـ ZIP و GZIP و DEFLATE و PNG.
>> معلومات تقنية
كيف يعمل LZ77:
يحافظ LZ77 على نافذة منزلقة من البيانات التي تمت رؤيتها مؤخراً. عند كل موضع يبحث عن أطول سلسلة مطابقة داخل النافذة. عند العثور على تطابق، يخرج مرجعاً (إزاحة، طول، الحرف التالي). إذا لم يوجد تطابق، يخرج حرفاً مباشراً (0،0،الحرف). بهذه الطريقة تُستبدل الأنماط المتكررة بمراجع قصيرة مما يحقق الضغط دون فقدان.
مثال LZ77:
Text: "ABCABCABC" Window=4, Lookahead=4 Position 0: 'A' - no match → (0,0,A) Position 1: 'B' - no match → (0,0,B) Position 2: 'C' - no match → (0,0,C) Position 3: 'ABC' - matches at offset 3 → (3,3,A) Position 7: 'BC' - matches at offset 3 → (3,2,) Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)
لماذا نستخدم LZ77؟:
- ▸ضغط بيانات بدون فقدان
- ▸لا يحتاج إلى معرفة مسبقة بنوع البيانات
- ▸يتكيف مع خصائص البيانات
- ▸تنفيذ بسيط نسبياً
- ▸أساس لخوارزميات الضغط الحديثة
>> أسئلة شائعة
ما هو LZ77؟
LZ77 خوارزمية ضغط بيانات دون فقدان نُشرت عام 1977 بواسطة أبراهام ليمبل ويعقوب زيف. تستبدل الخوارزمية التكرارات في الدفق بمراجع إلى نسخة واحدة ظهرت سابقاً في البيانات غير المضغوطة.
كيف تعمل النافذة المنزلقة؟
تنقسم النافذة المنزلقة إلى مخزن بحث يحتوي على البيانات المعالجة حديثاً، ومخزن مسبق يحتوي على البيانات التي سيتم ضغطها. يبحث LZ77 في مخزن البحث عن أطول تطابق مع بداية المخزن المسبق ثم يخرج مرجعاً أو حرفاً مباشراً.
ما الفرق بين LZ77 والضغط الحديث؟
يُعد LZ77 أساس العديد من خوارزميات الضغط الحديثة. يجمع DEFLATE المستخدم في ZIP و GZIP بين LZ77 وترميز هوفمان. تحسن LZSS كفاءة LZ77، بينما تبني LZ78 و LZW القاموس بطريقة مختلفة مع الحفاظ على نفس الفكرة العامة.
ما هي أحجام النوافذ المثلى؟
تتراوح أحجام النوافذ النموذجية بين 32 كيلوبايت و 64 كيلوبايت للبيانات العامة. النوافذ الأكبر تجد مزيداً من التطابقات لكنها تستهلك ذاكرة ووقتاً أكثر. يستخدم DEFLATE نافذة بحجم 32 كيلوبايت، ويكون حجم المخزن المسبق عادة 256–512 بايت. يعتمد الحجم الأفضل على نمط التكرار في بياناتك.
// مثال محلول
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// أمثلة برمجية
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> المزيد من الأسئلة
س: ماذا يعني الثلاثي (الإزاحة، الطول، الحرف)؟
ج: تحدد الإزاحة مقدار الرجوع في النافذة المرئية سابقاً، والطول عدد البايتات المنسوخة، والحرف هو البايت الجديد التالي. يعيد فاك الترميز بناء المخرجات خطوة بخطوة.
س: لماذا يجوز أن يتداخل النسخ؟
ج: إذا كانت الإزاحة أصغر من الطول فإن النسخ يقرأ بايتات كتبها للتو، فتنشأ التكرارات: (1, 5, x) تنتج الحرف السابق خمس مرات.
س: أين يُستخدم LZ77؟
ج: يشكّل LZ77 أساس DEFLATE (gzip وzlib وPNG وZIP) وتوجد منه متغيرات في LZ4 وSnappy وZstandard وBrotli. يحدد حجم النافذة واستراتيجية البحث نسبة الضغط والسرعة.