إل زد 77 وإل زد 78

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

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

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

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

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

رسميًا، (نظرية 13.5.2 ^[7] ). If ${\textstyle X}$ is a binary source that is stationary and ergodic, then $${\displaystyle \limsup _{n}{\frac {1}{n}}l_{LZ78}(X_{1:n})\leq h(X)}$$ with probability 1. Here ${\textstyle h(X)}$ is the entropy rate of the source. تنطبق نظريات مماثلة على الإصدارات الأخرى من خوارزمية LZ.

تحقق خوارزميات ال زد 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) هو السائد، يجب أن يبدأ البحث في النافذة من نهايتها ويتجه للخلف. يتيح هذا النهج العثور على أنماط التكرار أولاً، إن وجدت، مما يسمح بإنهاء البحث. يمكن أن يكون الإنهاء مطلقًا في حال الوصول إلى الحد الأقصى لطول تسلسل التطابق الحالي، أو حكيمًا في حال الوصول إلى طول كافٍ. أخيرًا، هناك احتمال بسيط مفاده أن البيانات الأحدث قد تكون أكثر ارتباطًا بالإدخال التالي.

في حين أن الإدخال ليس فارغًا،افعل ذلك
  match := أطول تكرار لتكرار الإدخال الذي يبدأ في النافذة
  إذا كان

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

تعتمد خوارزميات LZ78 في ضغط البيانات المتسلسلة على إنشاء قاموس لتسلسلات الرموز المستخلصة من البيانات المدخلة. بعد ذلك، تستبدل هذه الخوارزميات أي ظهور ثانٍ أو لاحق لتلك التسلسلات في تدفق البيانات بمرجع يشير إلى الإدخال المقابل في القاموس. وتعتمد هذه التقنية على ملاحظة مفادها أن عدد التسلسلات المتكررة يُعد مؤشرًا جيدًا على مدى عدم عشوائية البيانات. تمثل هذه الخوارزميات القاموس على شكل شجرة ذات n فروع، حيث يمثل n عدد الرموز المستخدمة في تكوين التسلسلات. يأخذ كل إدخال في القاموس الشكل = {index,dictionary[...] = {index, token}، حيث يشير index إلى فهرس إدخال قاموس سابق يمثل تسلسلًا سبق ظهوره، بينما يمثل token الرمز التالي من البيانات المدخلة الذي يجعل هذا الإدخال فريدًا في القاموس. تجدر الإشارة إلى أن هذه الخوارزمية ذات طبيعة جشعة.وبالتالي لا تتم إضافة أي شيء إلى الجدول حتى يتم العثور على رمز صنع فريد. تتمثل الخوارزمية في تهيئة آخر فهرس مطابق = 0 والمؤشر المتاح التالي = 1، ثم بالنسبة لكل رمز من تدفق الإدخال، يبحث القاموس عن تطابق: {last matching index, token} . إذا تم العثور على تطابق، فسيتم تعيين آخر مؤشر مطابق إلى مؤشر الإدخال المطابق، ولا يتم إخراج أي شيء، ويبقى آخر مؤشر مطابق يمثل الإدخال حتى الآن. سيتم معالجة الإدخال حتى لا يتم العثور على تطابق. ثم يتم إنشاء إدخال قاموس جديد، dictionary[next available index] = {last matching index, token} ، وتقوم الخوارزمية بإخراج آخر مؤشر مطابق، متبوعًا بالرمز، ثم إعادة تعيين آخر مؤشر مطابق = 0 وزيادة المؤشر المتاح التالي. على سبيل المثال، ضع في اعتبارك تسلسل الرموز AABBA التي من شأنها تجميع القاموس؛

0 {0,_}
1 {0,A}
2 {1,B}
3 {0,B

}

سيكون تسلسل البيانات المضغوطة الناتج هو 0A1B0B. تجدر الإشارة إلى أن الحرف الأخير 'A' لم يتم تمثيله بعد في الناتج المضغوط، وذلك لأن الخوارزمية لا تستطيع التنبؤ بما سيأتي بعده في التسلسل الأصلي. في التطبيقات العملية، تُضاف عادةً علامة نهاية الملف (EOF) إلى البيانات المدخلة، مثل AABBA$ على سبيل المثال. ومن الملاحظ أيضًا أنه في هذا المثال المحدد، يكون الناتج المضغوط 0A1B0B1$ أطول من المدخل الأصلي. ومع ذلك، تتحسن نسبة الضغط بشكل كبير كلما اتسع القاموس، وفي الأنظمة الثنائية، لا يلزم تمثيل الفهارس بأكثر من الحد الأدنى لعدد البتات المطلوب.

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

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

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

• "The LZ77 algorithm". Data Compression Reference Center: RASIP working group. Faculty of Electrical Engineering and Computing, University of Zagreb. 1997. مؤرشف من الأصل في 2013-01-07. اطلع عليه بتاريخ 2012-06-22.

• "The LZ78 algorithm". Data Compression Reference Center: RASIP working group. Faculty of Electrical Engineering and Computing, University of Zagreb. 1997. مؤرشف من الأصل في 2013-01-07. اطلع عليه بتاريخ 2012-06-22.

• "The LZW algorithm". Data Compression Reference Center: RASIP working group. Faculty of Electrical Engineering and Computing, University of Zagreb. 1997. مؤرشف من الأصل في 2013-01-07. اطلع عليه بتاريخ 2012-06-22.