إل زد 77 وإل زد 78

تُعدّ خوارزميتا ال زد 77 و ال زد 78 من خوارزميتان الرائدة في مجال لضغط البيانات بدون فقدان، وقد نُشرتا في ورقتين بحثيتين للعالمين أبراهام ليمبل وجاكوب زيف في عامي 1977  و 1978  على التوالي. يُشار إليهما أيضًا باسم Lempel-Ziv 1 (LZ1) و Lempel-Ziv 2 (LZ2) [3]. هاتان الخوارزميتان هما الأساس الذي بُنيت عليه العديد من الخوارزميات اللاحقة والمشتقة، بما في ذلك LZWو LZSSو LZMA وغيرها. وبالإضافة إلى أهميتهما الأكاديمية، فقد شكلت هاتان الخوارزميتان النواة الأساسية للعديد من أنظمة الضغط واسعة الانتشار، مثل تنسيق GIFوخوارزمية DEFL ATEالمستخدمة في تنسيقات PNG وZIP.

كلاهما من الناحية النظرية مبرمجان للقواميس . يحافظ LZ77 على نافذة انزلاقية أثناء الضغط. وقد تبين لاحقًا أن هذا يعادل القاموس الصريح الذي تم إنشاؤه بواسطة LZ78 - ومع ذلك، فإنهما متكافئان فقط عندما يكون المقصود فك ضغط البيانات بالكامل. من الناحية النظرية، تعتمد كلتا الخوارزميتين على مبدأ بناء مبرمجان للقواميس أثناء عملية الضغط. يحتفظ LZ77 بنافذة انزلاقية لتتبع البيانات الحديثة. وقد أُثبت لاحقًا أن هذه الآلية تعادل استخدام قاموس صريح كما هو الحال في LZ78، إلا أن هذا التكافؤ لا يتحقق إلا عند فك ضغط البيانات بشكل كامل.

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

حظيت هاتان الخوارزميتان بتكريم تسميتهما "معلمًا بارزًا في الهندسة الكهربائية وهندسة الحاسبات" من قبل معهد مهندسي الكهرباء والإلكترونيات (IEEE Milestone) في عام 2004. وفي عام 2021، مُنح جاكوب زيف وسام الشرف من معهد مهندسي الكهرباء والإلكترونيات من IEEE تقديرًا لمساهمته في تطويرهما. 

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

رسميًا، (نظرية 13.5.2  ).

تنطبق نظريات مماثلة على الإصدارات الأخرى من خوارزمية LZ.

 ال زد 77 
تحقق خوارزميات ال زد 77 ضغط البيانات عن طريق استبدال التكرارات المتتالية للبيانات بالإشارة إلى نسخة سابقة من تلك البيانات في تدفق البيانات الأصلي غير المضغوط. يتم تمثيل هذا التطابق بزوج من الأرقام يُعرف بزوج الطول والمسافة، وهو ما يعني ببساطة أن "كل حرف من الأحرف التالية التي يبلغ عددها 'الطول' مطابق تمامًا للأحرف التي تسبق الموقع الحالي بمسافة 'المسافة' في التدفق الأصلي". (يُشار إلى المسافة أحيانًا بالإزاحة).

لتحديد التطابقات، يجب على برنامج التشفير تتبع كمية معينة من أحدث البيانات، مثل آخر 2 كيلوبايت، أو 4 كيلوبايت، أو 32 كيلوبايت. يُطلق على الهيكل الذي تُحفظ فيه هذه البيانات اسم "نافذة منزلقة"، ولهذا السبب يُشار إلى LZ77 أحيانًا باسم "ضغط النافذة المنزلقة". يحتاج برنامج التشفير إلى الاحتفاظ بهذه البيانات للبحث عن تطابقات، بينما يحتاج برنامج فك التشفير إلى الاحتفاظ بها لتفسير التطابقات التي يشير إليها برنامج التشفير. كلما كانت نافذة الانزلاق أكبر، زاد طول المسار الذي يبحث فيه برنامج التشفير عند إنشاء المراجع.

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

هناك منظور آخر للأمر وهو كالتالي: أثناء عملية الترميز، ولكي يستمر مؤشر البحث في العثور على الأزواج المتطابقة بعد تجاوز نهاية نافذة البحث، يجب أن تحتوي جميع الأحرف بدءًا من أول تطابق عند الإزاحة D وحتى نهاية نافذة البحث على تسلسل مطابق. هذه الأحرف (التي تمت رؤيتها سابقًا) تشكل وحدة تشغيل واحدة بطول L R يجب أن يساوي D. بعد ذلك، عندما يتقدم مؤشر البحث متجاوزًا نافذة البحث، وطالما استمر نمط التشغيل في التكرار في البيانات المدخلة، سيظل مؤشرا البحث والإدخال متزامنين ومتطابقين للأحرف حتى يتوقف نمط التشغيل. وعند هذه النقطة، يكون قد تم تطابق إجمالي L حرفًا، حيث L أكبر من D، ويكون الرمز الناتج هو [D, L, c].

عند فك تشفير التسلسل [D, L, c]، فإن D يمثل L R. وعندما تتم قراءة أول L R حرف في المخرجات، فإن ذلك يمثل وحدة تشغيل واحدة تُضاف إلى المخزن المؤقت للإخراج. في هذه المرحلة، يمكن تصور مؤشر القراءة على أنه يحتاج فقط إلى الرجوع بمقدار الجزء الصحيح من (L / L R) بالإضافة إلى 1 إذا كان باقي قسمة L على L R لا يساوي صفر، وذلك إلى بداية وحدة التشغيل المؤقتة المفردة، ثم قراءة L R حرف (أو أقل في الرجوع الأخير)، وتكرار هذه العملية حتى تتم قراءة إجمالي L حرف. ولكن في عملية فك الترميز، ونظرًا لأن النمط متكرر، فإن مؤشر القراءة يحتاج فقط إلى التتبع المتزامن مع مؤشر الكتابة بمسافة ثابتة تساوي طول التشغيل L R حتى يتم نسخ L حرف إلى الإخراج بشكل كامل.

بناءً على ما سبق، وخاصةً في الحالات التي يُتوقع فيها أن يكون ضغط تكرارات البيانات (runs) هو السائد، يجب أن يبدأ البحث في النافذة من نهايتها ويتجه للخلف. يتيح هذا النهج العثور على أنماط التكرار أولاً، إن وجدت، مما يسمح بإنهاء البحث. يمكن أن يكون الإنهاء مطلقًا في حال الوصول إلى الحد الأقصى لطول تسلسل التطابق الحالي، أو حكيمًا في حال الوصول إلى طول كافٍ. أخيرًا، هناك احتمال بسيط مفاده أن البيانات الأحدث قد تكون أكثر ارتباطًا بالإدخال التالي.

 الكود الزائف 
الكود الزائف التالي هو إعادة إنتاج لنافذة انزلاق خوارزمية الضغط ال زد 77.
 في حين أن الإدخال ليس فارغًا،افعل ذلك
   match := أطول تكرار لتكرار الإدخال الذي يبدأ في النافذة
   إذا كان 

 التطابق موجودًا ، إذن
     د := المسافة إلى بداية المباراة
     l := طول المباراة
     c := char بعد المطابقة في الإدخال
   آخر
     د := 0
     ل := 0
     c := الحرف الأول من المدخلات
   نهاية إذا
   الناتج (د، ل، ج)
   التخلص من l + 1 حرف من أمام النافذة
   s := pop l + 1 حرف من أمام الإدخال
   إضافة s إلى الجزء الخلفي من النافذة
 يكرر

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

 تقوم الخوارزمية الموضحة في مقال Lempel و Ziv الأصلي لعام 1977 بإخراج جميع بياناتها بثلاث قيم في المرة الواحدة: طول ومسافة أطول تطابق تم العثور عليه في المخزن المؤقت، والحرفي الذي تلا هذا التطابق. إذا كان من الممكن ترميز حرفين متتاليين في مجرى الإدخال كأحرف فقط، فسيكون طول زوج الطول والمسافة 0.
 يقوم LZSS بتحسين LZ77 من خلال استخدام علامة 1 بت للإشارة إلى ما إذا كانت القطعة التالية من البيانات عبارة عن حرفي أو زوج طول-مسافة، واستخدام الحرفي إذا كان زوج الطول-المسافة أطول.
 في تنسيق PalmDoc، يتم دائمًا ترميز زوج الطول والمسافة بواسطة تسلسل مكون من بايتين. من بين 16 بت التي تشكل هذين البايتين، تذهب 11 بت إلى ترميز المسافة، وتذهب 3 إلى ترميز الطول، ويتم استخدام البتتين المتبقيتين للتأكد من أن جهاز فك التشفير يمكنه تحديد البايت الأول كبداية لمثل هذا التسلسل المكون من بايتين.
 في التنفيذ المستخدم في العديد من الألعاب بواسطة Electronic Arts ،  يمكن تحديد الحجم بالبايتات لزوج الطول والمسافة داخل البايت الأول من زوج الطول والمسافة نفسه؛ اعتمادًا على ما إذا كان البايت الأول يبدأ بـ 0 أو 10 أو 110 أو 111 (عند القراءة في اتجاه البت الكبير )، يمكن أن يكون طول زوج الطول والمسافة بالكامل من 1 إلى 4 بايت.
  طريقة الضغط الأكثر شيوعًا القائمة على LZ77 هي DEFLATE ؛ فهي تجمع بين LZSS وترميز هوفمان .  تُجمع الحروف والأطوال ورمز يشير إلى نهاية كتلة البيانات الحالية في أبجدية واحدة. يمكن وضع المسافات بأمان في أبجدية منفصلة؛ لأن المسافة تظهر فقط بعد الطول مباشرةً، فلا يمكن الخلط بينها وبين أي نوع آخر من الرموز أو العكس.

 ال زد 78 
تعتمد خوارزميات LZ78 في ضغط البيانات المتسلسلة على إنشاء قاموس لتسلسلات الرموز المستخلصة من البيانات المدخلة. بعد ذلك، تستبدل هذه الخوارزميات أي ظهور ثانٍ أو لاحق لتلك التسلسلات في تدفق البيانات بمرجع يشير إلى الإدخال المقابل في القاموس. وتعتمد هذه التقنية على ملاحظة مفادها أن عدد التسلسلات المتكررة يُعد مؤشرًا جيدًا على مدى عدم عشوائية البيانات. تمثل هذه الخوارزميات القاموس على شكل شجرة ذات n فروع، حيث يمثل n عدد الرموز المستخدمة في تكوين التسلسلات. يأخذ كل إدخال في القاموس الشكل = {index,، حيث يشير index إلى فهرس إدخال قاموس سابق يمثل تسلسلًا سبق ظهوره، بينما يمثل token الرمز التالي من البيانات المدخلة الذي يجعل هذا الإدخال فريدًا في القاموس. تجدر الإشارة إلى أن هذه الخوارزمية ذات طبيعة جشعة.وبالتالي لا تتم إضافة أي شيء إلى الجدول حتى يتم العثور على رمز صنع فريد. تتمثل الخوارزمية في تهيئة آخر فهرس مطابق = 0 والمؤشر المتاح التالي = 1، ثم بالنسبة لكل رمز من تدفق الإدخال، يبحث القاموس عن تطابق:  . إذا تم العثور على تطابق، فسيتم تعيين آخر مؤشر مطابق إلى مؤشر الإدخال المطابق، ولا يتم إخراج أي شيء، ويبقى آخر مؤشر مطابق يمثل الإدخال حتى الآن. سيتم معالجة الإدخال حتى لا يتم العثور على تطابق. ثم يتم إنشاء إدخال قاموس جديد،  ، وتقوم الخوارزمية بإخراج آخر مؤشر مطابق، متبوعًا بالرمز، ثم إعادة تعيين آخر مؤشر مطابق = 0 وزيادة المؤشر المتاح التالي. على سبيل المثال، ضع في اعتبارك تسلسل الرموز  التي من شأنها تجميع القاموس؛
}
سيكون تسلسل البيانات المضغوطة الناتج هو . تجدر الإشارة إلى أن الحرف الأخير 'A' لم يتم تمثيله بعد في الناتج المضغوط، وذلك لأن الخوارزمية لا تستطيع التنبؤ بما سيأتي بعده في التسلسل الأصلي. في التطبيقات العملية، تُضاف عادةً علامة نهاية الملف (EOF) إلى البيانات المدخلة، مثل  على سبيل المثال. ومن الملاحظ أيضًا أنه في هذا المثال المحدد، يكون الناتج المضغوط  أطول من المدخل الأصلي. ومع ذلك، تتحسن نسبة الضغط بشكل كبير كلما اتسع القاموس، وفي الأنظمة الثنائية، لا يلزم تمثيل الفهارس بأكثر من الحد الأدنى لعدد البتات المطلوب.

تعتمد عملية فك الضغط على إعادة بناء القاموس تدريجيًا من التسلسل المضغوط. لنأخذ التسلسل المدخل  كمثال. يبدأ القاموس دائمًا بالرمز النهائي } الذي يمثل سلسلة فارغة {...}. عند معالجة المدخل الأول "1A"، يتم إنشاء الإدخال الأول في القاموس وهو }، ويُضاف الحرف "A" إلى المخرجات. ثم يُعالج المدخل الثاني ""، مما يؤدي إلى إنشاء الإدخال الثاني في القاموس وهو 2 ، ويُخرج الرمز "B" مسبوقًا بالسلسلة التي يمثلها الإدخال رقم 1 في القاموس. الإدخال رقم 1 هو "A" (متبوعًا بـ "الإدخال 0" الذي يمثل لا شيء)، لذا تُضاف السلسلة "AB" إلى المخرجات. بعد ذلك، يُضاف "0B" إلى القاموس باعتباره الإدخال التالي وهو }، ويُضاف الحرف "B" (الذي لا يسبقه شيء) إلى الإخراج. أخيرًا، يُنشأ إدخال قاموس لـ "1$" ويُخرج ""، مما يؤدي إلى فك الضغط إلى السلسلة "" أو "" بعد إزالة المسافات وعلامة نهاية الملف.

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

BTLZ هي خوارزمية مشتقة من LZ78 وقد طُورت خصيصًا للاستخدام في أنظمة الاتصالات التي تتطلب معالجة في الوقت الفعلي (مثل أجهزة المودم في الأصل)، وقد تم توحيدها من قبل CCITT/ITU تحت مسمى V.42bis. عندما يمتلئ القاموس المنظم ثلاثيًا لهذه الخوارزمية، تُستخدم آلية بسيطة لإعادة استخدام وإعادة تدوير الإدخالات لضمان قدرة القاموس على الاستمرار في التكيف مع البيانات المتغيرة. يعتمد هذا الأسلوب على عداد يتنقل عبر القاموس. وعند الحاجة إلى إضافة إدخال جديد، يتحرك العداد خلال القاموس حتى يعثر على عقدة ورقة (وهي عقدة ليس لها أي عقد فرعية). يتم حذف هذه العقدة وإعادة استخدام المساحة التي كانت تشغلها للإدخال الجديد. يُعتبر هذا النهج أسهل في التنفيذ مقارنة بخوارزميات LRU (الأقل استخدامًا مؤخرًا) أو LFU (الأقل استخدامًا تكرارًا) ويحقق أداءً مماثلًا.

 مراجع 

 روابط خارجية 







تصنيف:ضغط بيانات
تصنيف:اختراعات إسرائيلية
تصنيف:خوارزميات ضغط بيانات غير مضيعة