قائمة المتنوعات و الشهادات > المزيد...

ضغط البيانات و خوارزميات الإستبدال النصي

الكاتب:


http://i-infected.com

بسم الله الرحمن الرحيم

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

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

لكي تأخذ نظرة عامة عن ضغط البيانات راجع هذا الموضوع:

مقدمة تاريخية عن نظرية المعلومات و ضغط البيانات

توطئة: هذا النوع من الخوارزمات و المعروف بـالإستبدال النصي (Textual Substitution) أو ما يعرف بـDictionary-Based Compression أكتشف من قبل الباحيثن لمبل و زيف في الورقة البحثية المعروفة[5]، و التي شرحت فكرة عمل الخوارزمية LZ77، ثم تلتها ورقة بحثية أخرى وبفكرة أخرى تشرح فكرة عمل الخوارزمية LZ78 إذ أن هاتين الخوارزميتين تمثلان الأصل في فكرة عمل هذا النوع من الضغط ، وسنشرح اليوم طريقة عمل النوع الاول LZ77، والجدير بالذكر أن الورقة البحثية التي تشرح فكرة عمل الخوارزمية عالية التعقيد و التنظير لكن لبداهة فكرتها إنتشرت على نطاق واسع، فلقد كتب فيها الكثير لتبسيط عملها ونقلها من النظري إلى التطبيبقي، هذه الخوارزمية استعملت بكثرة خاصة في المودمات و الفاكسات و أجهزة التوجيه في الشبكة ومازالت تستعمل اليوم في كثير من البرامج، وأشهر خوارزمية في هذه العائلة هي LZSS، ولكي نزيل اللبس فإن هذه الخوارزمية غالبا ما يشار لها على أنها LZ77 كونها لا تختلف عنها في الطريقة، بالإضافة إلى أنها أقرب إلى البداهة عن سابقتها.


صورة 1- عائلة خوارزميات الضغط عن طريق الإستبدال النصي أو الضغط عن طريق القواميس[1]

1-مقدمة:

في البداية……السؤال هو: لما الحاجة إلى ضغط البيانات؟ وما الداعي إلى إستعامل هذه التقنية؟

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

ماهي البيانات
ماهو ضغط البيانات
بيانات قابلة للضغط
بيانات غير قابلة للضغط

البيانات:يجب أن نفرق بين المعلومات و البيانات و الترميزات (Information, Data, Codes)، فالمعلومة هي الشيئ الذي يحصل الإنسان من خلاله على المعرفة أما البيانات فهي الوسيط الذي يحمل المعلومة.
فعلى سبيل المثال وحدة البيانات هاته “-30 °C” تحمل المعلومة ”الجو بارد” ويمكن أن تُحمل هذه المعلومة في صورة للثرمومتر بتمثيل صوري (Image) أو تكتب على الشكل التالي “ثلاثون درجة مؤية تحت الصفر” بتمثيل نصي (Text) او حتى بتحذير صوتي (Sound)، لذلك عندما نتحدث عن البيانات في علوم الحاسب فهي أي شكل رقمي للمعلومة و التي يمكن أن تعالج ببرنامج كمبيوتر[2]، اما الترميز فهو التمثيل الذي يعتمده نظام المعلومات لمعالجة البيانات (ASCCI, 8-bit Fixed length, Morse code…..etc).

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

وبما أننا نتحدث في موضوعنا هذا عن تقنية الإستبدال النصي (Textual Substitution) أو كما يسميها البعض تقنية الضغط عن طريق القواميس (Dictionary-based compression) سنشير إلى عملية الضغط “بعملية حذف التكرارات”.
على ضوء التعريف السابق يمكن لنا أن نقول أن البيانات القابلة للضغط هي البيانات التي بها تكرارات، وكلما كانت التكرارات كثيرة كلما زادت قابلية ضغط هذه البيانات، وغالبا ما يشيار إليها على أنها درجة الإنتظام وغياب الفوضى في توزيع البيانات، وهذا ما يفسر قابلية ضغط اللغات الطبيعية لإحتوائها على درجة كبيرة من الإنتظام و التكرارية.
بالمقابل نقول عن بيانات أنها غير قابلة للضغط كلما زادت درجة العشوائية وإنعدمت درجة التكرارية فيها.
مثا عن بيانات غير قابلة للضغط:

WHzUOPNssb3RGeV1fHpFXkVitFkJI8L!H4W8swZpyZJW7KhwgO NZutsfdgVEfqTEfIq7
8YrQScsyq2K5RY4R1YhoXR7x18fkLuwFnHQpg8ZQjsSvxV7Kvr KksMik8kZ!VhJziPqOY

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


صورة 2- نص ذو طبيعة تكرارية[3]

هذا النص يحتوي على الكثير من من التكرارات، فعلى سبيل المثال الكلمات Algorithm,Statistical,Compression مكررة بكثرة.

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

Statistical compression use a statistical model of the data, which is why the quality of compression they achieve

الكلمات الملونة بالأحمر هي التكرارات و و الكلمات الملونة بالأزرق هي الكلمات الأصلية.

وغرض حذف التكرارات سنقوم بالتالي:

Statistical compression use a s(0,9) model of the data, which is why the quality of (12,11) they achieve

حيث (12,11) و (0,9) تمثل المؤشرات، 0 أو 12 تمثل موقع أول حرف من الكلمة الأصلية و 9 أو 11 تمثل طول الكلمة (الترقيم يبدأ من الصفر) غالبا ما يطلق على هذا المؤشر بـ(Code-Word).

ربما يتبادر إلى ذهنك تساؤل عن كيفية وضعنا للمؤشر بهذا الشكل وهذا ما سنشرحه لاحقا.

ملاحظة:لم نأخذ كلمة Statistical كاملة لأن عملية الضغط حساسة لحالة الأحرف فهناك فرق يبن S و s، بالإضافة إلى أننا لم نأخذ المساحة بين الكلمات بعين الإعتبار في حين أنها محسوبة وسنعتمدها لا حقا.

3-مستوى التفكير 1:
الآن لننتقل إلى مستى أعلى من التفكير……

قلنا أن الضغط يتم على البيانات وكلنا يعرف أن الملفات هي وعاء للبيانات لكن على شكل تمثيل معين وقد تختلف الملفات في الأنواع بين صوت أو صورة أو نص لكن في النهاية البيانات تمثل بمجموعة متسلسلة ومرتبة من البايتات Bytes ومنذ الآن سنتعامل مع البيانات وعملية الضغط ومفهوم التكرارا على مستوى الأحرف أو البايتات (chars or bytes).

مثال:

AABBBCG AABBBDLLLFOKLLLJ

لو تلاحظ جيدا لوجدت أن النص لا يحتوي تكرارات على مستوى الكلمات (فهمي مختلفة كليا من حيث المعنى ومن حيث التركيب) لكن إذا نظرنا على مستوى Bytes أو الأحرف للاحظنا أن التكرارات واضحة وجلية وهي موضحة بالألوان في المثال التالي:

AABBBCG AABBBDLLLFOKLLLJ

ومن أجل هذا الغرض فإن Compressor سيتعامل مع البيانات عن طريق Array او جدول:



صورة 3- جدول او مصفوفة أحادية البعد بها البيانات المراد ضغطها

وهذا سيبسط علينا العملية برمتها، في البداية سيقوم compressor بالبحث عن التكرارات عن طريق المقارنة بايت بايت، بحيث أنه سيبحث في البايات التي قد مر بها (الماضي أو Last byte Seen)، فلنفرض أن Compressor موجود في الموضع رقم 8، سيقوم compressor بالبحث في البايتات التي مر بها وهي التي تبدأ من الموضع 0 حتى الموضع 7، في أدبيات خوارزمية الإستبدال النصي تسمى هذه بنافذة البحث (Search Window) نافذة البحث غالبا ما يكون حجمها 4096 او 8192 بايت (سنعتمد 4096) وعندما تملأ نافذة البحث يحصل لها إزاحة، لذلك الإسم الصحيح لنافذة البحث هي Sliding Window أو النافذة المنزلقة، نافذة البحث هذه يضاف إليها البايتات بشكل دوري حتى تملأ وبعد امتلائها تبدأ بالإنزلاق:



صورة 4- النافذة المنزلقة(الملونة بالأزرق) وهي غير مكتملة الطول (طولها الآن 8 بايت).

الجدير بالذكر أن الـCompressor يبحث عن أطول تطابق، لذلك فإنه لن يكتفي بـAAB الموجودة في الموضع 8 حتى 10 (لأنها بطبيعة الحال مكررة وهي موجودة في الموضع 0 حتى 2 ) بل سيواصل البحث حتى يجد إختلاف، فعلى سبيل المثال: هذا النص AABBB وهو أطول تشابه أو أطول تكرار لأن البايت الذي يليه هو D و البايت الذي يلي الأصل هو C وهما غير متشابهين او مغير متطابقين، لذلك يعتبر AABBB أطول تكرار موجود في النافذة المنزلقة.

الآن بعد أن وجد التكرار سيقوم بضغطه مباشرة والنتيجة ستكون:

(AABBBCG (0,5

طبعا هذه النتيجة ستكتب في ملف أو مساحة ذاكرة أخرى غير التي نبحث فيها عن التكرارات، بعد ذلك يقوم Compressor بإضافة AABBB الموجودة في الموضع 8 حتى 12 إلى النافذة المنزلقة، لاحظ الشكل التالي:



صورة 5- النافذة المنزلقة بعد توسعها وإضافة البايتات لها.

العملية المقبلة ستبحث في نافذة منزلقة ذات طول جديد و التي تبدأ من 0 حتى 12 ، الأمر الذي يجب التنبيه له هو أن الـCompressor يبحث في البايتات التي مضت ولا يمكن له بأي طريقة من الطرق أن يبحث فيما هو آت، لأن العملية متعلقة بالDecompression فكل ما يعرفه الـDecompressor هو ما مضى من البيانات.

يقارن الـCompressor البايت الموجود في الموضع 13 وهو ‘D’ مع البايت الموجودة في النافذة المنزلقة وكما يبدوا فإنه لن يجد شيئا لعدم تواجد ’D’ في النافذة المنزلقة، الـCompressor بعدها يقوم بإضافة الحرف D إلى النافذة المنزلقة ليصبح طولها من 0 حتى 13 و يصبح محتواها:

AABBBCG AABBBD

الآن لنختصر العملية فبعد إكمال عملية البحث و الضغط النتيجة ستكون:

AABBBCG (0,5)DLLLFOK(14,3)J

أما عملية الضفط فستكون عكسية وتخض للقانون التالي:

يبدأ الـDecompressor بقراءة البيانات المضغوطة بايت بايت فإذا تعرف على Code-Word (و الذي هو عبارة عن ثنائية الموضع و الطول التي تميز التكرار والذي تم إيجاده أثناء عملية الضغط ) فإنه سيقوم بالتالي:

الذهاب للموضع الذي يشيير إليه الـCode-Word وينسخ عدد بايتات بنفس الطول الذي يحويه الـCode-Word

لكن السؤال هو كيف يفرق Decompressor بين Code-Word و الأحرف العادية وماهو تمثيل وحجم هذا الـCode-Word؟

4-مستوى التفكير 2:

الآن سننتقل إلى مستوى أعلى من التفكير…..

من البديهي أن تكون المؤشرات (Code-Words) أقل حجما من الكلمات التي حلت مكانها وإلا لما كان هذا ضغطا للبيانات، لذلك سنقوم بتحديد حجم ثابت للمؤشرات (الحجم بالـBits) وسيكون 16 بت.

إنتبه: ربما يتبادر إلى ذهنك أن المؤشر به القوسين و الفاصلة ولن تكفيه 16 بت لذلك، أقول أن تلك الكتابة وضعت للتوضيح فقط، ففي عالم Bits لا وجود إلا لـ0 و 1.

إذن التمثيل الحقيقي للمؤشر هو على الشكل التالي:



حيث يمثل اللون الأحمر “الموضع”و اللون الأزرق “طول التشابه أو التكرار”.

القيمة 000000000111 هي 7 في النظام العشري، و 0011 هي 2 في النظام العشري أي أن المؤشر هو (7,2)،ولقد تم إختيار حجم الموضع (12 Bits) و الطول (4 Bits) وفق الشروط التالية:

الطول حجمه 4 بت وهذا يعني إمكانية تمثيل طول أقصاه 15 بايت (لأن 2 مرفوع للقوى 4 ناقص 1 يساوي 15) وهو طول تكرار مقبول لأنه من النادر أن تجد تكرار بطول اكثر من 15.

الموضع لا يمكن له أن يشير إلى رقم أكبر من النافذة المنزلقة (Sliding Window) ونحن نعلم أن النافذة المنزلقة طولها 4096 بايت ولكي نحصل على عدد البايتات اللازمة لتمثيل هذا العدد فإننا نستعمل الوغاريتم العشري ذو القاعدة 2.





Ceil هي دالة التي ترجع لك العدد الصحيح الأكبر من x مباشرة.

بعد أن عرفنا التمثيل الحقيقي للمؤشر بقي لنا تلخيص مخرجات Compressor:

إذا وجد الـCompressor تكرار فإنه سيستبدله بـمؤشر (Code-Word)،وإذا لم يجد تكرار أو تشابه فإنه سيخرج الحرف كما هو (وهذا هو الحال مع الحرف ’D’ الموجود في الموضوع 13) ففي أدبيات الخوارزمية يسمى الحرف ‘literal) ‘D) ولكي يستطيع الـDecompressor التفريق بينهما (Code-word و Literal) فإن الـCompressor يضع ما يسمى بالـراية (Flag) في مقدمة كل مخرج، هذه الراية (Flag) عبارة عن بت (Bit) إما يكون صفر أو واحد وهو يحدد نوع البيانات التي سيقابلها لـDecompressor:



جدول 6- دلالة بت الراية [4]

وهذه الصورة توضح التمثيل الثنائي للنص المراد ضغطه.



صورة 7- النص وتمثيله الثنائي

بعد الضغط يكون النص على الشكل التالي على مستوى Bits:



صورة 8- التمثيل الثنائي المضغوط للسلسلة النصية مع توضيح لبنية المخرجات

الرايات (Flags) ملونة بالأحمر
الأحرف الغير مضغوطة (Literal) موجودة بين كل راية وراية من نفس القيمة (1)
المؤشرات (Code-Words) موضحة براية قيمتها صفر، هذه المؤشرات ملونة باللونين الأزرق و البرتقالي:
الأزرق:يمثل الموضع.
البرتقالي: يمثل طول التكرار.

5-خاتمة:

في النهاية أتمنى أنكم استفدتم من الموضوع ولا تترددوا بطرح تساؤلاتكم عن الموضوع، الجيدر بالذكر أن الموضوع لم يشر إلى بعض المواضيع التقنية التي يمكن أن تشرح في مواضيع منفصلة مثل Bit Manipulation وهي مسؤولة عن إعطائك إمكانية التعامل مع Bits من كتابة إلى قراءة، ومفاهيم أخرى مثل Adaptive and Static Dictionary و Entropy و Parsing وغيرها، والشفرة المصدرية للخوارزمية.

6-ملحق:

1-6)للإستزادة:

http://www.mattmahoney.net/dc/dce.html

http://www.mattmahoney.net/dc/dce.html#Section_52

http://michael.dipperstein.com/lzss/

http://www.binaryessence.com/dct/en000139.htm

http://en.wikipedia.org/wiki/Lempel–...orer–Szymanski

http://www.arturocampos.com/ac_lz77.html

http://en.wikipedia.org/wiki/Binary_logarithm

2-6) قائمة الكلمات التقنية باللغة الفرنسية:

Textual Substitution = Substitution textuelle
Dictionary-Based Compression = Compression basée sur le Dictionare
Data = Données
Byte = Octet
Char = Caractère
Compressor = Compresseur
Decompressor = Decompresseur
Search Window = Fenêtre de recherche
Sliding Window = Fenêtre glissante
Code-Word = Mot-code
Flag =Drapeau
Literal = Littérale
Entropy = Entropie

7-المراجع:

[1] David Salomon, Giovanni Motta, Handbook of Data Compression 4th edition, Springer, California, 2009.

[2] Ida Mengyi Pu, Fondamental Data Compression, Butterworth -Heinemann, Burlington, MA, 2006.

[3] Christina Zeeh, The Lempel Ziv Algorithm, Seminar ”Famous Algorithms”, University of Stuttgart, Stuttgart, January 16, 2003.

[4] Abdallah Arioua (كاتب المقالة), abdallah ahmedbey,Adel Djidel,Implementation of L.Z.S.S algorithm for Text compression based on dictionary approach, License Dissertation,University of M’sila,2010.

[5] Ziv, J., And Lempel, A. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory 23 (1977).