LZ77 و LZ78

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 4 صور
الموسوعة الحرة

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

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

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

تم تصنيف هذه الخوارزميات كمعلم بارز من قبل معهد مهندسي الكهرباء والإلكترونيات (IEEE) في عام 2004. [ 5 ] وفي عام 2021، مُنح جاكوب زيف وسام الشرف من معهد مهندسي الكهرباء والإلكترونيات (IEEE) لمساهمته في تطويرها. [ 6 ]

الكفاءة النظرية

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

رسميًا، (النظرية 13.5.2 [ 8 ] ).

LZ78 عالمي وفوضوي — إذاX{\textstyle X}إذا كان مصدرًا ثنائيًا ثابتًا وإرجوديًا،ليم سوبن1نللZ78(X1:ن)≤ح(X){\displaystyle \limsup _{n}{\frac {1}{n}}l_{LZ78}(X_{1:n})\leq h(X)}باحتمالية 1. هناح(X){\textstyle h(X)}يمثل معدل الإنتروبيا للمصدر.

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

LZ77

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

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

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

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

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

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

الشفرة الزائفة

الشفرة الزائفة التالية هي نسخة طبق الأصل من خوارزمية ضغط LZ77 ذات النافذة المنزلقة.

طالما أن المدخلات ليست فارغة، نفّذ التطابق := أطول تكرار للإدخال الذي يبدأ في النافذة إذا وُجد تطابق ، د := المسافة إلى بداية المباراة l := طول التطابق c := char following match in input آخر د := 0 l := 0 c := الحرف الأول من المدخلات نهاية الشرطالناتج (د، ل، ج) تجاهل الحرف رقم l + 1 من مقدمة النافذة s := احذف l + 1 حرفًا من بداية المدخلات أضف s إلى الجزء الخلفي من النافذة يكرر

التطبيقات

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

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

LZ78

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

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

وستكون سلسلة مخرجات البيانات المضغوطة كالتالي:0A1B0Bلاحظ أن الأخيرألم يتم تمثيلها بعد، لأن الخوارزمية لا تستطيع معرفة ما سيأتي لاحقًا. عمليًا، تتم إضافة علامة نهاية الملف إلى المدخلات:AABBA$على سبيل المثال. لاحظ أيضًا أنه في هذه الحالة يكون الناتج0A1B0B1$يكون أطول من المدخلات الأصلية، لكن نسبة الضغط تتحسن بشكل كبير مع نمو القاموس، وفي النظام الثنائي لا يلزم تمثيل الفهارس بأكثر من الحد الأدنى من البتات. [ 11 ]

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

LZW

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

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

انظر أيضاً

مراجع

  1. ↑ زيف، جاكوب ؛ ليمبل، أبراهام (مايو 1977). "خوارزمية شاملة لضغط البيانات المتسلسلة". معاملات IEEE في نظرية المعلومات . 23 (3): 337-343 . CiteSeerX 10.1.1.118.8921 . doi : 10.1109/TIT.1977.1055714 . S2CID 9267632 .  
  2. ↑ زيف، جاكوب ؛ ليمبل، أبراهام (سبتمبر 1978). "ضغط التسلسلات الفردية عبر ترميز المعدل المتغير". معاملات IEEE في نظرية المعلومات . 24 (5): 530-536 . CiteSeerX 10.1.1.14.2892 . doi : 10.1109/TIT.1978.1055934 . 
  3. ↑ براءة اختراع أمريكية رقم 5532693: نظام ضغط بيانات تكيفي بمنطق مطابقة السلاسل الانقباضية
  4. ↑ "ضغط البيانات بدون فقدان: LZ78" . cs.stanford.edu .
  5. ↑ "معالم بارزة: خوارزمية ضغط البيانات ليمبل-زيف، 1977" . شبكة التاريخ العالمي التابعة لمعهد مهندسي الكهرباء والإلكترونيات . معهد مهندسي الكهرباء والإلكترونيات . 22 يوليو 2014. تاريخ الاطلاع: 9 نوفمبر 2014 .
  6. ↑ جوانا، جودريتش. "ميدالية الشرف من معهد مهندسي الكهرباء والإلكترونيات تُمنح لرائد ضغط البيانات جاكوب زيف" . مجلة IEEE Spectrum: أخبار التكنولوجيا والهندسة والعلوم . تاريخ الاسترجاع: 18 يناير 2021 .
  7. ↑ بيتر شور (14 أكتوبر 2005). "ملاحظات ليمبل-زيف" (ملف PDF) . مؤرشف من الأصل (ملف PDF) في 28 مايو 2021. تم الاطلاع عليه في 9 نوفمبر 2014 .
  8. ↑ كوفير، توماس م.؛ توماس، جوي أ. (2006). عناصر نظرية المعلومات ( الطبعة الثانية). هوبوكين، نيوجيرسي: وايلي-إنترساينس. ISBN  978-0-471-24195-9.
  9. ↑ "ضغط نظام الملفات QFS (RefPack)" . ويكي نيوتسو . تم الاطلاع عليه بتاريخ 9 نوفمبر 2014 .
  10. ↑ فيلدسبار، أنتايوس (23 أغسطس 1997). "شرح خوارزمية الضغط" . مجموعة أخبار الضغط . zlib.net . تم الاطلاع عليه في 9 نوفمبر 2014 .
  11. ^ ميشيل جويمانز (27 أبريل 2015). "رموز Lempel-Ziv" (PDF) . معهد ماساتشوستس للتكنولوجيا الرياضيات .
  • "خوارزمية LZ78" . مركز مرجعية ضغط البيانات: مجموعة عمل RASIP . كلية الهندسة الكهربائية والحوسبة، جامعة زغرب. 1997. تاريخ الاطلاع: 22 يونيو 2012 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )
  • "خوارزمية LZW" . مركز مرجعية ضغط البيانات: مجموعة عمل RASIP . كلية الهندسة الكهربائية والحوسبة، جامعة زغرب. 1997. تاريخ الاطلاع: 22 يونيو 2012 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )