الباب الثامن: ضغط البيانات

كيف نخزن الكثير من البيانات في مساحة أصغر


قرأنا في الدرس الفارط عن المؤشر Pointer الذي يشير إلى بداية البيانات (خاصة النصوص)،

و كيف يمكننا تغييره لنغير مكان بداية النص، بشكل يسمح لنا بوضع نصوص أكثر.

لكن رأينا أيضا أن هناك حدودا لتلك الطريقة.

كيف نتعامل معها... و بالأحرى، كيف تعامل المبرمجون معها عند إعداد ألعابهم؟


بسبب صغر حجم بطاقات الألعاب، كان من الضروري على المبرمجين إيجاد طريقة لوضع بيانات كبيرة

في بطاقة من المفروض أنها لا تسع الحجم الحقيقي لتلك البيانات.

و لذلك الغرض أتت طرق عديدة لإعادة كتابة البيانات في مساحة صغيرة.

هذه الطرق لا بد أنكم إستعملتموها، لو كنتم استخدمتم ملفات Zip و Rar من قبل.

و هي تسمى ضغط البيانات Compression (أو أيضا الإختزال).


توجد عديد الطرق لضغط البيانات.

في النهاية، ستكون البيانات مثل النصوص و الصور بعد ضغطها غير مفهومة بتاتا،

و لا يمكننا رؤيتها في برامج الهيكس أو التايل (إما جزئيا، أو كليا).

لكن كونها "غير مفهومة" ليس القصد الأساسي – الضغط يكون لإنقاص الحجم أساسا.


عندما يكون ذلك متعمدا، فنحن إذن نتحدث عن طرق أخرى، و تسمى التشفير Encryption،

و هدفها عادة لإخفاء بعض الأشياء (مثل برمجة مكافحة القرصنة مثلا).

مثلا – برمجة مكافحة القرصنة في Gimmick على النيس كلها مشفرة بتشفير خاص كي لا يراه أحد بسهولة

(حجمه يساوي الحجم الأصلي، إذن الهدف منه لم يكن إنقاص الحجم).


نعود للحديث عن ضغط البيانات.

عندما تكون البيانات مضغوطة، في الغالب لا نستطيع تعديلها و هي في تلك الحالة.

يفترض بنا أولا أن نقوم بفك الضغط Decompression عنها (بعد معرفة طريقة الضغط طبعا)،

و ذلك لتعود لحالتها و حجمها الأصلي و تظهر محتوياتها بالواضح. عندها نستطيع تعديلها.


ثم بعد ذلك، نعمل لها الضغط Compression من جديد،

نضعها في مكانها في الروم (مع التأكد أن حجمها بعد الضغط لم يكبر، و إلا فسيفسد البيانات بعده،

و لو أن هناك حلا لتلك المواقف و هو تغيير المؤشر كالعادة)،

و حينها ستفتحها الروم من جديد – بما أن الروم تتوقع بيانات مضغوطة.


اللعبة عندما تعمل، تقوم دائما هي نفسها بفك الضغط عن البيانات المضغوطة و تضعها في الرام RAM.

لأنها تحتاج إلى تلك البيانات واضحة و جاهزة للإستعمال.

لهذا السبب، هناك محاكيات بها وظائف تشخيص اللعبة Debug

و هي تسمح بإستراق النظر إلى محتويات الرام،

و إلى سطور البرمجة التي تنفذها اللعبة – خاصة أثناء فك ضغط هذه البيانات.

و عندما نكتشف هذه الطريقة السرية لفك الضغط،

نستطيع نسخها إلى لغة برمجة للحاسب مثل C و استخدامها لفك ضغط أي شيء نريده في تلك اللعبة.


أما العملية العكسية... كيف نرجع تلك البيانات إلى الروم بعد أن عدلناها...

يجب أن نرجعها مضغوطة كي تقرأها اللعبة.

لأن اللعبة تريد بيانات مضغوطة و هي تنفذ عليها فك ضغط و تستعملها.

يعني يجب أن نفكر في صنع برنامج يضغطها بطريقة تقرأها اللعبة

(و أحيانا قد نتفوق على الشركة و يكون حجم الملف نفسه أصغر من الأصلي بأسلوبنا الجديد!)


لكن في عدة حالات، هناك من عندما وجد هناك مساحة فارغة في الروم،

إختار ببساطة وضع البيانات كما هي بدون ضغطها من جديد، و بدون صنع برنامج ضغط جديد،

و عوض ذلك غير برمجة اللعبة (بالأسمبلي) ليجبرها على قراءة تلك البيانات الجديدة.

هذا الأمر قد يكون أسهل و قد يكون أصعب بكثير...



الآن، لنبدأ الحديث عن أبرز أساليب ضغط البيانات.


فئة ضغط القواميس


نتفق على كون بايت معين يمثل سلسلة أطول من الرموز.

قائمة بايتات الإختصار هذه تسمى القاموس.

من بين أنواع هذا الضغط:


القاموس الثابت: و نحتاج أن نرفقه مع النص.

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

الضغط متعدد التايل (أو ترميز أزواج البايت): رمز واحد يعوض أكثر من حرف،

أو بصفة عامة، سلسلة رموز قصيرة تعوض سلسلة رموز طويلة.


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

من أبرز أشكاله: ضغط LZ77 و LZ78.

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


فئة ضغط الصور بمساحات كبيرة من لون واحد


ضغط طول التشغيل (RLE) يستعمل أساسا مع الصور.

كلما وجدنا رمزا متكررا عديد المرات، نختصر تلك السلسلة الطويلة

بكتابة ذلك الرمز + عدد مرات التكرار.


خريطة التايل (Tilemap) في حالة الألعاب ثنائية الأبعاد،

أو بيانات وضع الخامة (Texture) على الموديل ثلاثي الأبعاد،

لو كان فيها لون واحد متكرر على مساحة كبيرة،

فيخزن من ذلك اللون مربع واحد، و الخريطة تأمر بتكراره.


فئة ضغط الترميز على أقل من بايت


البايت مكون من 8 بت.

و عادة، يكون كل رمز في النص من بايت واحد على الأقل.

بعض الألعاب تقوم بالتخزين على أقل من بايت (أقل من 8 بتات) لتقليص حيز النص.


قد يكون طول الرموز متساويا (مثلا، كلها 7 بتات).

و قد يكون غير متساوي.


و أبرز نوع غير متساوي هو ضغط هافمان (Huffman) و هو ناجع جدا،

و يكون عدم تساوي الرموز مقصودا، كي تكون الرموز الشائعة أقصر، و النادرة أطول.

لكنه يحتاج إلى إرفاق جدول معادل كل رمز (و يسمى شجرة هافمان).


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


هناك أنواع ضغط أخرى تستعمل هي نفسها الترميز على أقل من بايت،

و من بينها بعض أفراد عائلة ضغط LZ77 و LZ78 المذكورين لاحقا.


فئة الضغط بالتوقع


تكتب الجملة جزئيا و فك الضغط يتوقع كيف تنتهي، حسب قوانين معينة.

من بين الأنواع البدائية لهذا الضغط:


الإختزال الصرفي: استعمل لتخزين نصوص المصحف الإلكتروني (1986) لكمبيوتر صخر.

كل كلمة عربية مشتقة من جذر ثلاثي أو رباعي كتبت جزئيا (3/4 حروف + معلومة صرف) و البرنامج صرفها و أعاد تكوين النص.


ضغط دلتا للأصوات: الأصوات تضغط هكذا. نظرا أنها مخزنة على شكل موجات،

فهذا يعني أن كل نقطة ستكون قريبة جدا من النقطة السابقة، و الفرق فقط صعود أو نزول بمقدار صغير. تكتب إذن فقط هذه المقادير.

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


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

الطريقة تطبيق متطور أكثر لخاصية موجودة في محركات البحث التي تتوقع بقية الجملة التي تكتبها. و هي من بين أنجع الطرق الحالية للضغط لكن المكلفة أكثر من ناحية الذاكرة الحية.



بعض أنواع الضغط هذه تستخدم امكانيات الجهاز ليقوم بفك الضغط.

سواء كان بشريحة مضافة لبطاقة اللعبة (كما كان الحال مع Star Ocean, Tengai Makyou Zero

و الألعاب التي استخدمت Super-FX مثل Star Fox و Yoshi’s Island...)

أو كون وحدة المعالجة المركزية بالجهاز هي نفسها التي تقوم بفك الضغط

كما في كوديك MPEG المدمج في البلاي 1 و الساتورن لرؤية الفيديوهات،

أو بعض أنواع الضغط مثل ضغط LZ الأدفانس و الدي اس، و ضغط prx على البي اس بي.


ترميز عدة حروف على بايت واحد

(قاموس لا يتغير)

الصعوبة: سهل (لا تحتاج تفحص البرمجة)


أمثلة استخدام:

بايت = حرفين: فاينال فانتازي 1/2/4، سيكرت أوف مانا (غير مستعمل)، مونستر وورلد 3 ...

بايت = عدة حروف: داك تيلز 2 (بكثافة)، لوفيا 2 (الانكليزية)، زيلدا 3، زيلدا الأوراكل (بكثافة)،

تايني تونز (سوبر نيس)، تيرانيغما، فاينال فانتازي 6، كرونو تريغر، ...


معروف أيضا بإسم الترميز متعدد التايل MTE (Multi-Tile Encoding).

أو في حالة ما كان البايت يعوض حرفين، الترميز ثنائي التايل DTE (Dual-Tile Encoding).


في هذا النوع من الضغط، نستطيع أن نستخدم بايت واحد في النص كي نكتب حرفين أو أكثر.

النتيجة أن نصا معينا ينقص عدد البايتات المستعمل فيه.

لكن كي تعرف اللعبة كيف تقوم بتأويل هذه البايتات التي تعوض مجموعات الحروف،

سنجد في الروم أيضا قائمة بالحروف التي تعادل كل رمز، و هي القاموس.


على سبيل المثال، في لعبة Final Fantasy الأولى:

عملنا بحثا بالمقارنة باستخدام بعض النصوص.

في كثير من الحالات فشلت محاولاتنا، لكن بعض الكلمات ساعدتنا.

مثلا من هذا الحوار، كلمة LIGHT WARRIOR غير مضغوطة و يمكن البحث عنها.



نستطيع استنتاج الحروف A-Z a-z بهذه الطريقة و صنع ملف التيبل... لكن سنجد النص هكذا:



نحن متأكدون أننا عثرنا على الجملة التي نريدها.

لكنها مازالت غير واضحة كليا.

ما يعني أن ملف التيبل الذي لدينا مازال منقوصا و يجب أن نكمله.

نبدأ بالبايت وسط كلمة K*g التي هي King، و هو البايت 1F.

هذا البايت يعطينا الحرفين in

إذن نضيف سطرا في ملف التيبل و نكتب فيه 1F=in


نواصل إكمال التيبل بمقارنة النص في الهيكس بالصورة في اللعبة.

1A=e_

26=ou

50=_y

(حيث _ نكتبها فراغ في ملف التيبل)

و هكذا...

و بعد أن ننتهي من الصورة، نحاول تجربة وضع بايتات أخرى غير التي في هذا النص.


عندما يكون لدينا ملف تيبل كامل،

فبرنامج الهيكس يعطينا نتائج أفضل بكثير...



الجملة الأصلية كانت هكذا بطول 81 رمزا:

The King is looking for|the LIGHT WARRIORS. You|do not happen to be them|do you?#


الجملة الجديدة بطول 63 بايتا فقط عوض 81 حرفا –

اختصر هذا الضغط حوالي 30% من الطول الأصلي!

Th#K#g##look#g##|th#LIGHT WARRIORS. Y#|do no##pp##o###em|do##?#


في برنامج WindHex، تحت Edit من الضروري تفعيل Enable DTE Inserting عند تغيير هذه النصوص،

كي يغيرها باستعمال هذا الأسلوب من الضغط.

على سبيل المثال، بتفعيل هذه الخاصية، كلمة them سترمز باستعمال 3 بايتات فقط

(th مضغوطة على شكل بايت واحد)، لكن بدونها سوف تكتب بصفة عادية أي 4 بايتات.


لو ننظر للقيم الموجودة في جدول التيبل لضغط ترميز متعدد البايت،

سنلاحظ أنها مخصصة للإنكليزية.

و علينا تغييرها.


كيف نختار القاموس – أي الحروف و الثنائيات تتواتر أكثر في العربية؟

تغيير القاموس ليناسب النص العربي أمر لا مفر منه لو أردنا أن يكون تشفيرا ناجعا أصلا.

لأن إختيار هذه الثنائيات أمر يجب أن يراعي خصوصية كل لغة.

عدا اللغة، قد يكون النص نفسه لديه خصوصيات و مصطلحات معينة تظهر أكثر،

تلك أيضا يجب أن تظهر في القاموس.


بصفة عامة، بالنسبة للغة العربية، هناك ثنائيات تظهر بكثرة نظرا أنها مرتبطة بالنحو.

من بين أكثرها شهرة نجد الآتية:


ال التعريف

حروف النحو

تصريف افعال

ضمائر

الـ / الا / للـ

من / في / لم / لن / و_ / لا_ / ثم / هل / أيـ / لكـ / ن_ / ما / ذا / ان

انـ / ننـ / تنـ / ينـ / اتـ / نتـ / تتـ / يتـ / اسـ / نسـ / تسـ / يسـ / ون / ات / ممـ /

تم / هو / هي / هم / ني / نا / ـه_/ها/

هنـ/اك/ذي/تي/


أما ترتيب الحروف العربية من أكثرها ظهورا إلى أقلها ظهورا،

فهو كالآتي حسب عديد الإحصائيات على عدة نصوص عربية تتقارب نتائجها كالآتي –

مرتبة من الأكثر ظهورا إلى الأقل ظهورا:

ا ل ن م ي و ه

ب ر ع

أ ف ق د ت س ك ح

ة ى ج ص إ ذ ث خ ش ز ط ض غ ء ئ ظ آ ؤ


هذا يعني أننا سنعطي الأولوية لدخول القاموس

للثنائيات التي بها حروف من السطور الثلاثة الأولى.


هناك برامج تفحص نصك مثل DTESeek و MTE Search

و تعطيك قاموسا على المقاس يعطيك نصا قصيرا قدر المستطاع.


تغيير هذه الرموز في القاموس أمر سهل.

في الروم يوجد قاموس لتعديل قيم هذا الترميز.

في حالة الفاينال فانتازي 1، قيم الترميز هي كالآتي،



و يمكننا أن نجدها في قاموس في الروم.

في حالة الفاينال فانتازي هناك جدولان،

واحد مخصص للحرف الأول، و الآخر للحرف الثاني.



لكن في أكثر الحالات، نجد الألعاب تخزن قاموسها بكتابة كل محتوياته متتالية،

هكذا على سبيل المثال بالنسبة لمثالنا السابق.

ليست هذه الطريقة التي استعملتها سكوير في الفاينال فانتازي 1،

بل بالأحرى في السيكرت أوف مانا.



هذه الطريقة أساسها أن برمجة اللعبة عندما تصل لذلك البايت في النص

تنفذ أمرا خاصا بجلب حرفين للشاشة.

هناك الكثير من المترجمين يعدل برمجة اللعبة لإضافتها عندما يتعامل مع أجهزة ذاكرتها محدودة جدا.


الأسلوب اليصري

يمكننا القيام بأمر مشابه لهذا بدون تغيير البرمجة.

و في أي لعبة نريدها (طالما المساحة في الخط تسمح).

و ذلك ما نسميه ضغط متعدد التايل باستخدام صورة الخط.


الفكرة في عدة ألعاب أن بعض الحروف و الرموز صغيرة جدا،

و بالتالي يمكننا حشر رمزين في نفس التايل.

و بما أن "رمز" ذلك التايل (الذي في الواقع يحتوي رسمه رمزين) يستهلك فقط 1 بايت، نكون ربحنا حيزا لا بأس به.


مثلا، في النسخة الإنكليزية من Crystalis على النيس، هذا هو خط اللعبة.

تم تلوين التايلات التي تستخدم أسلوب الضغط الذي نتحدث عنه.




الأسلوب هنا غير محسن كثيرا.

لو نلاحظ، فالخط لا يتناسق مع الخط الرئيسي،

و استعماله اقتصر على مصطلحات شاشة العدة أي بعض الكلمات فقط:



نلاحظ أيضا أن هناك بعضا من هذه الكلمات كان كتلة كبيرة مقسمة على عدة تايلات،

مثلا Sword (في الأصل 5 حروف) على 3 تايلات.

لو أردنا اكمال ملف التيبل، لكنا وضعنا هنا مثلا:

0A0B0C=Sword

نجد هذا أيضا في ألعاب مثل Super Mario World و Whirlo، حتى بعد النيس.


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

و في حالة الألعاب اليابانية، جميع علامات التنقيط (النقطة، الفاصل) مخزن معها فراغ في التايل.


هناك تطبيق مربح أكثر و متناسق بصريا لهذا الضغط،

فكرته الحفاظ على جمالية الخط و الاقتصار على حشر الرموز الصغيرة فقط، من قبيل


ti

fi

li

il

ll

v

t

s

l

m


مثلا، في إحدى ترجمات الهواة للعبة Castlevania 3 للنيس:



يمكننا تطبيق هذه الطريقة في أي ترجمة عربية نريدها.

و في الواقع، هذا أمر محبذ و بدونه قد لا نتمكن من إدراك هدفنا.

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

كانت تخصيص رمز ليحتوي [الـ] ، و إن أمكن أيضا [للـ].

هذان الرمزان فقط بهذا الضغط يختصران علينا الكثير.


لو كان الخط فيه الكثير من الحروف المتوفرة (خاصة في الألعاب اليابانية المصدر)

نستطيع استخدام هذه الطريقة بكثافة و الحصول على نتائج مبهرة.


مثلا، هذه ترجمة محسن للكابتن ماجد 4 (سوبر نيس).

الثنائيات في هذه الحالة كان هدفها الأساسي كتابة أسماء اللاعبين في حيز أقصر،

لكنها مفيدة أيضا للنصوص العربية. طبعا هذا الإختيار يتغير حسب طبيعة النص و أي الكلمات تظهر أكثر فيه.



أما ترجمة عادل للفاير إمبلم 1 (نيس)، فكان توزيع الثنائيات فيها مختلفا،

و متناسقا أكثر مع طبيعة النص الروائية:



مثال من الألعاب التي تستخدم بكثافة القواميس

سنأخذ على سبيل المثال لعبة تستعمل القواميس بكثافة غير معهودة.

لنختر لعبة الزلدا للجيم بوي كولور Oracle of Ages لأنها نموذج ممتاز.

اللغة الإسبانية غير مضغوطة لسبب ما، لكننا سنعمل على نسخة إنكليزية أمريكية.


أول شيء نفكر به هو البحث عن التيبل، أي قيم الحروف.

لو استخدمنا برنامج بحث نسبي مثل monkeymoore قد نجد ظالتنا.

طبعا، لو كان لدينا كلمة مثل Sword في البحث و هي في القاموس، ستظهر لنا مرة واحدة.

السبب أنها كتبت مرة واحدة في الروم (في القاموس) و في بقية النص عوضت باختصار لها.


قد تقولون، هذا الأمر غير جديد و معروف و رأيناه.

المشكل، أن هناك بعض نوعيات القواميس تخزن أجزاء من الكلمات.

و هذه في الحقيقة من أفضل أنواع القواميس.

و بالتالي يصبح النص مقطع أشلاء و لو بحثت عن كلمة قد لا تجدها.

يختلف الأمر طبعا بين الألعاب التي يظل النص الرئيسي واضح المعالم فيها نوعا ما (مثل الزيلدا 3 على السوبر فاميكوم)

و ألعاب يطمس فيها هذا الضغط جميع معالم النص الأصلي (مثل Sword of Mana أو النسخ الأوروبية من Ducktales 2).


ما العمل في هذه الحالات؟

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

هذا المكان قد يكون الروم (و قد نحاول مع عدة كلمات إلى أن نجد كلمة غير مضغوطة – عادة الصرخات)

و قد يكون ... الرام RAM، أو الذاكرة الحية أثناء عمل اللعبة.

يمكنكم العودة لأول درس لرؤية كيف نجد التيبل باستخدام شاشات إختيار الأسماء.

عندما أقول الرام، هناك أيضا رام ملف حفظ اللعبة SRAM الذي يكون فيه اسم الشخصية...

و عادة هذا الاسم نجده مكتوبا غير مضغوط.

إلا... لو كان ملف SRAM نفسه مشفرا (مثال: الألعاب التي بها جمع وحوش و لعب جماعي)،

و حتى التشفير له حلول (المحاكيات التي بها أدوات فحص سطور البرمجة أثناء تنفيذها Debuggers،

مع العلم أن أدوات فحص البرمجة Debuggers موجودة لبرامج الكمبيوتر أيضا

و هذا ما يطابق الرؤية الشعبية للناس الذين يهكرون البرامج).



ابتعدنا قليلا عن صلب الموضوع...

و هناك سبب جعلني أختار هذه اللعبة هو لأنها بترميز ASCII،

يعني لا حاجة للبحث عن التيبل، و برنامج الهيكس سيظهر لنا النص مباشرة بالتيبل الصحيح (A=41, a=61).

مع ذلك أنصحكم بعمل هذا التيبل لأننا سنضيف له أمورا أخرى.


كالعادة، ننطلق من اللعبة.

نفتح اللعبة (نحرص أن تكون النسخة الأمريكية من Oracle of Ages تحديدا)

و نختار نصا نبحث عنه في الروم. في حالتنا هذه اخترنا هذا النص.

كان بإمكاننا البحث عن نصوص أفضل من هذه (خاصة التي تستعمل حروفا كبيرة كثيرة للصراخ،

أو كلمات تظهر مرة واحدة في اللعبة، نظرا أنه من المستبعد أن تكون مضغوطة بالقاموس) و بالطبع لكم الإختيار.



عند البحث عن هذه الجملة في برنامج الهيكس، سنجد أن أغلبها مضغوط بالفعل.

لكن لحسن الحظ لو بحثنا عن كلمة Accept من بين باقي الكلمات سنجد الجملة،

التي لم يبق منها الكثير عدا بعض علامات التنقيط:



للتوضيح، سأستعمل المطة السفلية "_" لتعويض الفراغات.

الفراغ غير مرئي و هذا لا يناسبنا لو كنا نريد أن نفهم.


نلاحظ أن هناك بايتات خاصة تعوض بعض الكلمات.

و في حالتنا هذه هي على شكل 04XX (حيث XX بايت واحد) ...


نحتاج لإضافة جميع الإحتمالات الممكنة لهذه الرموز "كلمات القواميس" إلى ملف التيبل

كي يكون رؤية النص و تعديله أمرا ممكنا من الأساس.


رمز العودة للسطر غير موجود في هذه الجملة.

يعني أن الحكاية أمر من إثنين:

إما أن اللعبة تقوم أحيانا بالعودة للسطر تلقائيا عندما يكون عدد الحروف في السطر كبيرا،

و إما أن رمز العودة للسطر موجود لكنه داخل القاموس (و هذا أمر مستبعد لكنه ممكن).

نحن لا نستطيع هنا قطع الشك.


سنبدأ بما نحن متأكدون منه. الجزء الأخضر.

كل ما بين الفاصلة و نقطة التعجب أي _hero رمز له بالهيكس بالبايتين 0408.

ما يعني أنه بإمكاننا اضافة السطر التالي لملف التيبل:


0408=_hero


نلاحظ أن الكلمة في القاموس قد تحتوي أيضا عدا الحروف حتى رموز أخرى مثل الفراغات.

و الآن نجرب تعويض الجزء الأخضر بالبايت 04B9 (و هو نفسه الأزرق) لنعرف معناه.

و نفتح اللعبة للتجربة و رؤية ماذا تغير.



النتيجة كانت كالآتي:



نستطيع اضافة السطر التالي لملف التيبل أيضا:


04B9=quest


نجرب هذه المرة التعويض بالبايت 040E لمعرفة معناه، و النتيجة ظهرت على 3 سطور هكذا:



لو نرمز للفراغ هكذا _

و للعودة للسطر هكذا /

فيمكننا القول بناء على المكان الذي رسمت فيه نقطة التعجب،

أن العودة للسطر جزء من الكلمة التي يناديها البايت 040E من القاموس.

و نستطيع اضافة السطر التالي لملف التيبل أيضا


040E=_our/


هناك أمر قد... يتعبنا قليلا.

قاموس هذه اللعبة ضخم جدا.

هناك البايتات 04XX و 05XX و غيرها للنداء على كلمات القاموس،

و كل زوج بايت منها يشير الى 256 كلمة (عندما تكون XX بين 00 و FF).


سنجرب البحث عن القاموس في الروم.

هذه المرة سنبحث عن كلمة من الكلمات التي اختفت من الجملة.

مثل our و quest و hero.

نبدأ مع hero البحث، و سنجد الكلمة على الغالب قبل النص الرئيسي (حيث نحن الآن نبدل هذه الجملة).

في الحقيقة سنجدها 3 مرات، مرة بفراغ قبلها و مرة بدونه و هذا غباء (سأعود لهذه النقطة لاحقا) لكن نحن نريد المرة الثانية

نظرا أننا سنجد أيضا بعدها بقليل كلمة our (بين 08 و 0E بالست عشري فقط 6 مراتب)


نلاحظ أن القاموس يحتوي في داخل الكلمة التي فيها our بايت التحكم 01 (العودة للسطر).




و الآن لو عدنا للجملة السابقة و غيرنا الجزء الأخضر الى 0409 ماذا سنجد؟



عوض أن نضيف الكلمات بالسطر بالسطر إلى ملف التيبل،

لكن لماذا نكتب هذا كله و الحال أن لدينا قاموسا جاهزا به كل شيء؟


لو نتذكر الدرس السابق حول المؤشر، و بالتحديد فقرة استخراج النصوص،

سنستخرج كامل القاموس.

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


نلقي نظرة أين يبدأ القاموس و أين ينتهي بالنسبة لكلمات القاموس التي تنادى ب 04XX

أولا، الكلمة التي يعطيها 0400 هي (نعرفها بعد أن نجرب تعويضها في النص)

eedling

و الكلمة التي يعطيها 04FF هي

Heh heh


يمكننا أن نجد الكلمة الأولى في القاموس هنا ابتداء من العنوان 0770C1

هناك قاموس قبلها و هو على الأرجح يخص القيم المرموز لها ب 03XX

لكن لن نهتم به الآن، و يمكننا العودة له لاحقا عندما نريد انهاء كامل التيبل.



و الكلمة الأخيرة في القاموس تنتهي قبل العنوان 077780

هناك قاموس بعدها و يخص القيم 05XX على الأرجح، نعود له فيما بعد.



هناك أمر نلاحظه، و هو أن كلمات القاموس يفصل بينها البايت 00

إذن نعمل نسخة من ملف التيبل الذي لدينا مخصصة لاستخراج القاموس،

الفرق الوحيد بينها و التيبل الأصلي هو أننا أضفنا هذا السطر:


00=\n=


حيث \n هو تعليمة لبرنامج Cartographer ليعود للسطر.

و بعد ذلك يكتب علامة مساواة. و بالطبع هذا كله يقوم به لتعويض أي بايت 00.


نستعمل إذن برنامج Cartographer لاستخراج النصوص،

لكن بالتعليمات التالية.


#GAME NAME: Zelda OOA (GBC)


#BLOCK NAME: 04XX MTE (RAW)

#TYPE: NORMAL

#METHOD: RAW

#POINTER TABLE START: $0770C1

#POINTER TABLE STOP: $077780

#TABLE: zelda_ooa.tbl

#COMMENTS: No

#END BLOCK


و فيه:

نضع هذا في ملف نص اسمه ta3limat.txt مثلا.


نحن الآن نفعل هذا لإعداد التيبل كي نقرأ النص الأصلي فحسب.

لاحقا، عندما نقرر تعريب اللعبة فإن القاموس الأصلي لن يناسبنا، و سنحتاج تغييره،

أي أننا سنعيد حينئذ استخراج القاموس على الأصول باستعمال المؤشرات.


و الآن لنستخرج النص (هذا كلام نسخ و لزق من الدرس الفارط على فكرة)

نذهب لبرنامج Notepad لصنع ملف نص فارغ. نكتب في هذا الملف الآتي.

هذه التعليمات تأمر البرنامج باستخدام الملفات المذكورة لصنع ملف نص اسمه nass فيه النص المستخرج.


cartographer zeldaooa.gbc ta3limat.txt nass -m


pause


عندما نسجل ملف النص هذا، نغير له اسمه و امتداده بحيث يكون بامتداد .bat

مثلا نسميه istikhraj.bat أو شيء كهذا.

المهم أن نسجله في نفس مجلد برنامج cartographer

و نفس المجلد يحتوي ملف الروم (.gbc أو أي جهاز آخر)، ملف التعليمات (.txt) و ملف التيبل (.tbl).


ننقر مرتين فوق ملف istikhraj.bat و سيفتح لنا برنامج Cartographer

الذي سيستخرج النص أو يظهر لنا رسالة خطأ يشتكي فيها أمرا ما.

النتيجة في النهاية أنه سيصنع لنا ملف نص مثل هذا:


eedling<$09>

(…)

=Maybe

=e of/

= hero

=power

=! The

=carry

=ding

=just

= our/

= it to

=ncient

=I came

=promise

=protect

(…)

=eft and

=ctually

=Goodbye

=Heh heh



(البايت 09 لم نعرف معناه بعد لذلك هو يظهر هكذا عند استخراج النص).


و الآن نضع قبل كل كلمة رمز الهيكس الذي يعوضها.

مثلا السطر الذي فيه = hero يصبح 0409= hero و هكذا

و عندها نكون تحصلنا على ملف تيبل يظهر لنا النص كاملا في برنامج الهيكس.

طبعا هو غير كامل بعد، لأنه مازال لدينا قيم أخرى مثل 03XX و 02XX و 05XX يجب إنهاء قواميسها.


على أية حال.

القاموس الذي استخدمته النينتندو كان فيه بعض الغباء.

لا أتحدث عن اللغة الاسبانية لهاته اللعبة التي عملوا لها قاموسا ثم نسوا استخدامه.

كان لدينا مثال و هو كلمة hero التي تظهر 3 مرات في القاموس:


$073F02:_hero

$077106:_hero

$0779D2:hero


السبب الأول للغباء: أن هناك طريقة لكتابة الكلمة كررت مرتين و هي hero مسبوقة بفراغ.

كان بإمكانهم استخدامها لوضع كلمة أخرى و تقليص النص أكثر.

السبب الثاني للغباء: أن القاموس يستعمل المؤشرات ليشير لبداية كل كلمة.

كان بإمكانهم كتابة _hero مرة واحدة.

و استخدام مؤشرين، واحد يشير إلى الفراغ (النتيجة في اللعبة ستظهر _hero )

و واحد يشير إلى h (النتيجة في اللعبة ستظهر hero )


هذا ما يسمى تحسين القاموس بالمؤشرات.

و هناك ألعاب عديدة قامت بذلك. مثلا لو كان لدينا هذه الكلمات الثلاثة:


Sword

Light Sword

Ultra Light Sword


ببساطة نكتب Ultra Light Sword فقط في القاموس،

و نضع 3 مؤشرات، كل واحد يشير إلى بداية كل من الكلمات الثلاثة (واحد إلى U، واحد إلى L و واحد إلى S).


هناك عدة أنواع من المؤشرات، لكن طالما نحن مع النوع العادي، و لا نستطيع سوى الاشارة لبداية الكلمات،

فهذا يعني أنه لو كان الجزء المشترك بين الكلمات في البداية

فلا يمكننا استعمال المؤشرات لتفادي تكراره.

أي أن كلمات مثل Thunder و Thundera و Thunderaga يجب أن نكتب كل واحدة بمفردها.


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

بيد أن بعض الألعاب تسمح لنا بكتابة كلمات داخل القاموس

هي نفسها تنادي على كلمات في القاموس (سواء نفس القاموس أو قاموس آخر،

و طبعا تكون تلك الكلمة الثانوية مكتوبة كاملة غير مضغوطة هناك).

هذه الطريقة ليست موجودة في كل الألعاب لكنها خاصية ممتازة، و تسمح باختصار النص بنسبة مهمة جدا.


لكن عندما نريد الترجمة و وضع نص عربي،

وجب علينا تغيير القاموس و عمل قاموس جديد يناسب النص الجديد.

يمكنكم العودة لمثال الفاينال فانتازي على النيس أعلاه لمعرفة كيف نفعل ذلك،

و العودة للدرس السابق حول المؤشرات لمعرفة كيف نستخرج و ندخل القاموس بغية تحديثه للعربية.


ضغط المؤشر

في بعض الأحيان، عوض أن تنادي اللعبة على رقم سطر من أسطر القاموس،

فهي تطلب (في وسط النص!) عنوانا في الروم فيه نص، و تعطي مؤشرا نحوه.


في الغالب هذا مستعمل عادة للحوارات التي فيها عدة اختيارات مثل نعم/لا.

لكن هناك حالات يكون هذا لغاية اختصار النص بمناداة كلمة أخرى في مكان آخر من النص.


على سبيل المثال نأخذ Lufia 2 للسوبر فاميكوم.

هناك مجموعة بايتات تدل على أسلوب الضغط هذا:

A0 XX YX

A0 تعلن عن بداية الضغط، و تكون متبوعة ب 2 بايت.

هاذان البايتان مخزنان بالطرف الأصغر low endian،

لنعرف حقيقتهما نقلب ترتيبهما: YX XX

Y هو النصف الأول من أول بايت (يعني 4 بت) و يقول كم رمزا نكتبه من الكلمة التي يناديها.

أما 0X XX فهو مؤشر نقطة بداية الكلمة التي سنأتي بها.


هذا المؤشر نسبي و يبدأ الحساب من نفسه.

و هو في حالتنا هذه يبدأ الحساب نحو الوراء.

يعني لو كان البايت A0 في العنوان 34100

و كان لدينا A0FFCF (بالطرف الأصغر) أي يعود FFF و يقرأ C (12 بالعشري) رمزا.

فهو سيكتب 12 رمزا انطلاقا من البايت في العنوان 034100-FFF أي 033101


و هناك حالات أخرى يظهر فيها مؤشرات في داخل النص.

مثلا Terranigma فيها شيء كهذا، لكنه مخصص للحوارات التي فيها عدة إختيارات (مثل نعم/لا).

برنامج Atlas لادخال النصوص خصص EMBEDDEDPOINTER خصوصا لهذه النوعية من المؤشرات،

لكني لست متمكنا من هذا الأمر بعد.

على كل بما أننا نتحدث عن الضغط، ألا نلاحظ هنا أننا رأينا استعمال نصف بايت فقط؟

بما أن البايت هو مكون 8 بتات فهذا الأمر ممكن. و نتحدث عنه في الفقرة التالية...


الترميز على غير 8 بتات

(على جزء من البايت)

الصعوبة: صعب


أمثلة استخدام:

(*) وجب التنويه أن هذه الطريقة مستخدمة في داخل مبدأ طرق ضغط أخرى مثل LZW و هافمان.

كابكوم (نيس) – نصوص Bionic Commando (10 بت عوض 16)

هادسون (سوبر نيس) – نصوص تنغاي ماكيو زيرو (12 بت عوض 16)

أسميك (نيس) – نصوص Battle of Olympus (5 بت عوض 8)

كونامي (نيس) – نصوص Lagrange Point (6 بت عوض 8)


كما نعلم، فكل بايت byte يعادل 8 بتات bit.

حيث البت هو إما 1 و إما 0.

و أغلب برامج الهيكس العادية تظهر فقط البايتات و ليس البتات.


مثلا البايت FF (255 بالعشري) نستطيع أن نكتبه (بالثنائي) مجموعة 8 بتات 1111 1111.

و البايت 80 (128 بالعشري) نستطيع كتابته 1000 0000

أي ما معناه

1×128 + 0×64 + 0×32 + 0×16 +

0×8 + 0×4 + 0×2 + 0×1


لكن لو فرضنا مثلا أن اللعبة بها أقل من 128 حرفا.

أي أن القيم متراوحة بين 00 الذي يكتب بالبايتات 0000 0000

و 7F (127 بالعشري) الذي يكتب بالبايتات 0111 1111

هناك بايت في النهاية على أقصى اليسار سيظل دائما صفرا. هل نحتاج إليه؟ لا.


لذلك السبب قررت بعض الألعاب أن تكتب رموز حروفها باستعمال أجزاء أقل من البايت (8 بت) الكامل.


مثلا، أخذنا مثلا ملف التيبل الذي لدينا،

و كتبنا كل بايت (عدد ست عشري XX بين 00 و FF (أي 255) و يعادل 8 بت)

بالنظام الثنائي لكن باستعمال 5 بت فقط.

يعني أن هناك 3 بت أصفار على اليسار نحذفها.


على سبيل المثال B=01 (كتابة ست عشرية)

لو كتبناها بالثنائي على 8 بت نحصل على 00000001

لكن لو نريد كتابتها على 5 بت، نحذف آخر ثلاثة اصفار على اليسار و نحصل على 00001

و لو طبقنا هذا على كامل التيبل، نحصل على الآتي:


00000=A

00001=B

00010=C

00011=D

00100=E

00101=F

00110=G

00111=H

01000=I

01001=J

01010=K

01011=L

01100=M

01101=N

01110=O

01111=P

10000=Q

10001=R

10010=Q

10011=R

10100=S

10101=T

10110=U

10111=V

11000=W

11001=X

11010=Y

11011=Z

11100=_

11111=<END>

00=A

01=B

02=C

03=D

04=E

05=F

06=G

07=H

08=I

09=J

0A=K

0B=L

0C=M

0D=N

0E=O

0F=P

10=Q

11=R

12=Q

13=R

14=S

15=T

16=U

17=V

18=W

19=X

1A=Y

1B=Z

1C=_

1F=<END>


لنكتب هذه الجملة باستخدام التيبل الجديد حيث كل حرف 5 بت فقط.

أشرت بالأحمر إلى المسافات بين الحروف، و رمز نهاية الجملة (END).

للتوضيح وضعت مطات بين معادل كل حرف. تلك المطات غير موجودة، و البتات كلها متتالية.


ANA_

OHIB_

ALBATATA

00000-01101-00000-11100

01110-00111-01000-00001-11100

00000-01011-00001-00000-10101-00000-10101-00000-11111


بما أن برامج الهيكس لا تظهر لنا سوى البايت الكامل (8 بت).

ليس هذا فقط، بل حتى الألعاب نفسها في برمجتها عندما تريد أن تشير إلى عنوان في الذاكرة،

فهي تستعمل البايت الكامل (8 بت).


نأخذ سلسلة بتات الأصفار و الواحد. و نجمعها هذه المرة مجموعات مجموعات،

كل مجموعة فيها 8 بت و تمثل بايت كامل.

هناك مجموعة في النهاية ناقصة فيها 2 بت فقط.

أضيف أصفارا (بالأزرق) بعدها لأكمل مجموعة 8 بت الأخيرة.


00000011-01000001-11000111-00011101-00000001-11100000-00010110-00010000-01010100-00010101-00000111-11000000


الآن، كل مجموعة من البت أحولها من النظام الثنائي إلى النظام الست عشري.

للتذكير، مع أنه يمكنكم استخدام الآلة الحاسبة للويندوز للغرض (انزعوا المطات لأنه يظنها علامة طرح).

فإن الأعداد الثنائية (بالصفر و الواحد، مثل البت) تعادل هذه الأعداد بالنظام الست عشري و العشري:


1100=C=12

1101=D=13

1110=E=14

1111=F=15

1000=8=8

1001=9=9

1010=A=10

1011=B=11

0100=4=4

0101=5=5

0110=6=6

0111=7=7

0000=0=0

0001=1=1

0010=2=2

0011=3=3


و النتيجة بعد التحويل هي هكذا،

و هكذا ستظهر لنا هذه الجملة مضغوطة في برنامج الهيكس –

تقريبا يستحيل التعرف عليها دون مراقبة برمجة اللعبة نفسها.


03 41 C7 1D 01 E0 16 10 54 15 07 C0


لدينا 12 بايت في النص المضغوط.

لو كنا كتبنا النص الأصلي غير مضغوط

(يعني بطريقة عادية، وكل حرف مخزن على 8 بت) لكان عندنا 18 بايت.

الربح كان حوالي بايت على كل 3 حروف، و هذا أمر مذهل كلما طال النص.


مثلا، في حالة Battle of Olympus (الانكليزية) على النيس، نجد هذا الضغط على 5 بتات.

كما نجد ضغطا على 7 بتات في لعبة Lagrange Point الحصرية لليابان على الفاميكوم.


هناك ألعاب يابانية تستخدم بكثافة الكانجي.

بما أن الكانجي أكثر من 255 رمزا، فهم مضطرون لترميز الرموز على أكثر من بايت واحد (8 بت).

في العادة، هذا يعني أن كل رمز كانجي أو حتى كل حرف (في حالة Shift-JIS)

سيكون على 2 بايت (16 بت). أي 65535 إمكانية مختلفة للرموز نظريا

(أقل عمليا، نظرا أن هناك ثنائيات "محرمة"...

عمليا بالنسبة للرموز الصينية و اليابانية مجتمعة تأخذ بضعة آلاف الخانات و 12 ألف على أقصى تقدير)


عادة تكتفي الألعاب بترميز هذه الحروف باستعمال 2 بايت.

لكن أتت حالات عديدة كانت فيها الحاجة أم الإختراع:

مجموعة ظروف – بطاقة بسعة قصوى، لعبة تستزف حدود الجهاز، نصوص طويلة جدا...

و عدد الرموز الكلي لا يكاد يصل 900 رمز أصلا.


في هكذا حالات، 2 بايت لكل رمز هو كثير، مبالغ فيه، هدر لمساحة الذاكرة.

إذن ... بايت و نصف يكفينا. 12 بت لكل رمز.

يكون لدينا إذن شيء مثل هذا:


021=A

0000 0010 0001 = A


هذه من بين الحالات القليلة التي يكون فيها هذا النوع من الضغط

مرئيا في برنامج الهيكس (لو نظرنا لخانة الهيكس).

مع أني لحد اللحظة لم أجد برنامج هيكس يقبل ملف تيبل بأنصاف البايت.


من بين أبرز الألعاب التي تستخدم هذا الأسلوب،

هناك Bionic Commando على النيس، أو نسختها اليابانية التي تتحدث عن هتلر و فيها كانجي كثير.

إضافة إلى Tengai Makyou Zero على السوبر فاميكوم،

و بطاقة اللعبة تخطيط ذاكرتها غريب جدا و صعب التوسيع ما يشرح استعمالهم هذا الأسلوب.


لكن هذا الضغط غير مستعمل بالكثرة التي نتصورها.

و السبب، أن ترك البت غير المستعمل لديه فوائد أكثر من اسقاطه بالكامل،

حيث يمكنه أن يشير إلى "هذا نص" ان كان 0 مثلا، و "هذه تعليمة برمجة " ان كان 1.

خصوصا أن أساليب ضغط LZ و RLE تكون خليطا من النصوص و التعليمات

و كثيرا ما تحتاج لهذا البت للتمييز بينهما.

س: ما هو LZ و RLE هذا؟

ج: هذه المرة لن ننتظر الإجابة في الدرس القادم – لست متأكدا إن بقي هناك شيء للدرس القادم أصلا :P


ضغط LZ

(قاموس متغير حسب النص)

الصعوبة: متوسط


أمثلة إستخدام:

نينتندو (سوبر نيس): أنواع LZ من نفس العائلة لصور سوبر ماريو وورلد، زيلدا 3، سوبر ميترويد .. (الأدوات)

هال (نيس، سوبر نيس، جيم بوي): أنواع LZ لصور جل ألعاب الكيربي، الماثر 2، ... (الأدوات)

كونامي: LZKN للصور للميغادرايف (الأدوات) و السوبر نيس (الأدوات)

كويست: LZSS صور أوغر باتل الملكة السوداء (الأدوات)

سكوير (سوبر نيس) – LZ ثم LZSS لصور عدة ألعاب، مثل فاينال فانتازي 6 و كرونو تريغر.

تم استحداث نوع أحدث لسوبر ماريو اربيجي و لآخر ألعاب سكوير للجهاز لاحقا

(الأدوات LunarCompress للأنواع البدائية، أدوات مختصة للبقية مثل هذه)

كوينتت (سوبر نيس) – LZSS لصور عدة ألعاب مثل Illusion of Gaia و غيرها. تغير النوع مع تيرانيغما قليلا. (الأدوات)


سيغا (ميغادرايف) – Kosinski متعدد الاستعمالات (صور/نص/خرائط تايل) سونيك 2 (الأدوات)

وستون (ميغادرايف) – صور مونستر وورلد 3/4 (الأدوات)

ضغط LZToshio (ميغادرايف) – عدة ألعاب، مثل Soleil و Ranger-X (الأدوات)


تري ايس (بلاي 1، بلاي 2) – ملفات SLZ في ستار أوسيان 2، فالكيري بروفايل ... (الأدوات)


نينتندو (جيم بوي أدفانس، دي اس) – ضغط LZ77 شائع جدا لصور الأدفانس (الأدوات)

نينتندو (ضغط بيوس: أدفانس، دي اس) – أنواع ضغط LZ مع نوع خاص بملفات الأوفرلاي (overlay تحت ftc) في العاب الدي اس (الأدوات)


و العديد العديد من الحالات الأخرى.

أداة عامة لفك ضغط LZ77 (الأدوات)


مثال من ضغط LZ77: ضغط LZSS

هذا الترميز مستوحى من الضغط بالقواميس. لكن هناك فرق هام.

القاموس ليس مجموعة كلمات ثابتة لا تتغير في مكان ما في الروم.

بل هو قاموس متغير و متحرك، ينادي كلمات من أجزاء سابقة من نفس الجملة التي نكتبها حاليا.

و هدفه منع التكرار.


على سبيل المثال،

مع العلم أن أول حرف في هذه الجملة هو (ح)، و ترتيبه 0،

لدينا هذا المثال (الفراغات معوضة بمطات، و هناك أخطاء نحوية لكن لا يهم).

هذه الجملة قبل الضغط:



بعد الضغط بأسلوب LZSS، تصبح الجملة على هذا الشكل.

كل تكرار يعوض بالآتي: (مكان بداية الجزء المكرر الأصلي) (طول الجزء الأصلي)


جزء من كلمة "نزلتم" يعوض بتعليمة نداء على 4 رموز متتالية إنطلاقا من الرمز 2 (ل في حللتم).

جزء من كلمة "سهلن" يعوض بتعليمة نداء على 3 رموز إنطلاقا من الرمز 8 (ه في أهلن).

بالطبع نلاحظ أن هذين الجزئين ظهرا بالفعل في أول الجملة غير مضغوطين، لكن مرة واحدة.


و في الحالتين، هذه الأجزاء استعملت 2 بايت عوض كامل الجزء المعوض المكرر:

بايت فيه مؤشر الحرف الأول للجزء المكرر، و بايت فيه عدد الحروف المتكررة.



أحيانا تكون هناك عدة امكانيات لعمل اختصارات،

و من أهم خاصيات LZSS أنه يتفادي عمل أي إختصار لا يستحق.


أنواع أخرى من LZ77

LZ77 الأصلي

هو مختلف قليلا.

يتم وضع أصفار "قبل الجملة" و يمكن أن تعتبر هذه الأصفار أجزاء "أصلية" مكررة.

كل تكرار يعوض بالآتي: (مكان بداية الجزء المكرر الأصلي) (طول الجزء الأصلي) (أول رمز بعد التكرار)

و كل رمز جديد يعوض أيضا بنفس الطريقة مع وضع 0 في مكان البداية، و في طول الجزء الأصلي.


شرط (أول رمز بعد التكرار) قد يتسبب في ضغط غير ناجع للجمل،

حيث قد نفوت على أنفسنا بسببه عدة تكرارات. و LZSS أتى ليحل هذه المشكلة في الأساس.


كذلك، ففي حين أن LZSS كثيرا ما يحافظ على تقسيم 8 بتات

و يميز بين اشارات المكان/الطول و رموز النص بتغبير بيت واحد فحسب بالنسبة للإشارات.

و بالتالي يمكننا رؤية أجزاء من النصوص المضغوطة بطريقة LZSS في برامج الهيكس.

إلا أن LZ77 يخزن (مكان بداية الجزء المكرر) و (طول الجزء) بالبتات،

و فقط البتات اللازمة (أي أقل من 8 بت – مثلا العدد 6 أي 110 بالثنائي، لا يحتاج أكثر من 3 بت، كأن يكتب 00000110 على 8 بت مثلا).

و بذلك يطمس معالم النصوص في برامج الهيكس.


LZR و LZH و LZB – لحل مشكلة قصر النظر أثناء البحث عن التكرار

في LZ77 و LZSS هناك مدى معين نستطيع أن ننظر فيه للوراء بحثا عن التكرارات.

هذا المدى المعين كبير جدا في حالة LZR و يغطي كامل النص المضغوط.

بما أن اشارات المكان ستكون طويلة، يتم الترميز لها باشارات متفاوتة الطول بالبت حسب الحاجة.


أما LZB فهو طريقة بتفاصيل كثيرة،

لترميز مؤشرات النصوص الأصل، و أطوالها، على اشارات متفاوتة الطول.


LZH هو ضغط وسط ضغط – حيث تكون مؤشرات أمكنة النصوص الأصلية المكررة،

هي نفسها مضغوطة، بطريقة ضغط هافمان (التي سنتحدث عنها لاحقا).


مثال من ضغط LZ88: ضغط LZW

هذا أيضا مستوحى من الضغط بأسلوب القواميس،

لكن على نقيض LZSS (من عائلة LZ77)

الذي يستعمل فقط أجزاء سابقة (إلى حد معين) من الجملة

عوض القاموس.

فإن ضغط LZW لديه قاموس.

لكنه قاموس يتغير باستمرار.


هذا القاموس فيه في البداية قائمة جميع الرموز الممكنة في الجملة التي نريد ضغطها.

إضافة إلى رمز يأمر بمسح القاموس

(هذا مهم جدا، لأن القاموس سوف يكبر و يكبر عند تغيره و يجب أن نضع حدا لذلك)

و رمز يقول أن الجملة إنتهت.


على سبيل المثال، لدينا الجملة التالية.


ANA-OHIBO-ALHALWA-WA-LAHM-ALKHAROF#


و القاموس سوف يحتوي في البداية جميع الرموز الممكنة.

نعطي الخانة 0 من القاموس لرمز نهاية الجملة،

الخانة 1 إلى 26 للحروف من A إلى Z،

و الخانة 27 للمسافة بين الحروف.


هذه الخانات أقل من 32،

يعني يمكن كما رأينا في السابق ترميزها على أقل من بايت كامل،

على 5 بت في حالتنا هذه.


هناك طريقتان في عمل هذا الضغط.


الأولى: طول الرمز لا يتغير – أن نجعل جميع الرموز و خانات القاموس بدون استثناء مرمزة على 12 بت (بايت و نصف).

لماذا 12 بت... لأنه بصفة عامة سنجد الرموز بين 00 و FF (255) في البيانات الأصلية

و لذلك يضاف 4 بتات اضافية ليصل العدد إلى FFF (4095)

و نستعمل الإمكانيات من 256 إلى 4095 لخانات القاموس الذي سيعمل مثل قاموس MTE أعلاه

(و إلا ما الفائدة من أسلوب الضغط هذا؟).


الثانية: طول الرمز يتغير – أن نجعل طول الحرف متغيرا،

بحيث في حالتنا بدأ القاموس ب 28 قيمة فقط (أقل من 32)، فنحتاج فقط 5 بت لكل رمز من القاموس.

نبدأ بالضغط. القاموس سوف يكبر تدريجيا.

عندما يصل إلى 32 خانة، جميع الرموز في النص المضغوط من هنا فصاعدا تصبح تستعمل 6 بت.

بالطبع بما أن القاموس قد يكبر إلى ما لا نهاية، و هذا أمر لا يصب في صالحنا،

نضع حدا لنمو القاموس عند 4095 خانة (أي عندما نستنفذ ما نستطيع كتابته ب 12 بت).


سنتفق على استعمال طول رمز متغير في حالتنا هذه.

القاموس هكذا في البداية: قائمة الرموز المستعملة.

في العادة يكون 00 إلى FF للبايت في البيانات العادية،

لكن هنا لدينا حروف فقط و نستطيع أن نكتفي ب 26 زائد رمز للمسافة.

نضيف رمز نهاية الجملة طبعا.


القاموس

00: نهاية الجملة [00000]

01: A [00001]

02: B [00010]

...

26: Z [11010]

27: مسافة بين الحروف (-) [11011]

فقط.


نستطيع أن نرمز هذا على 5 بت كما رأينا أعلاه.

إذن نقوم بذلك بالضبط.

نبدأ الآن بقراءة الجملة و ضغطها.


لنتحدث عن الميزة الرئيسية لهذا الضغط و هو القاموس –

هذا القاموس يستطيع أن يتغير و يضاف له خانات جديدة.

عندما نبدأ عملية الضغط، نقرأ النص و نبحث انطلاقا من النقطة التي نقرأ مها

عن سلسلة رموز موجودة في إحدى خانات القاموس.

قد تكون حرفا، قد تكون حرفين من تلك النقطة لو وجدا معا في خانة من القاموس...


لو وجد أن الرمز التالي بعدها لو جمع بعدها معها يعطينا شيئا ليس في القاموس،

فهو يضيف هذا التركيب الجديد لخانة جديدة في القاموس.


نحاول مع جملتنا.


ANA-OHIBO-ALHALWA-WA-LAHM-ALKHAROF#


A هو أول حرف. لا شيء قبله.

هذا أطول شيء لدينا يبدأ ب A و موجود في القاموس.

إذن هذه سلسلتنا.

نكتبها إلى النص المضغوط كما تظهر في القاموس أي 00001 بالبت (أو 1 بالعشري).


N هو الحرف بعد هذه السلسلة.

هل هناك AN في القاموس؟ لا.

إذن نضيفها لأول خانة فارغة في القاموس. يضاف إليه إذن:

28: AN


السلسلة الآن

الرمز التالي

يكتب للجملة المضغوطة (بت)

معناه (عشري)

يضاف للقاموس

A

N

00001

1 (A)

28 : AN



نمر الآن إلى الحرف التالي و هو N، و نواصل...


السلسلة الآن

الرمز التالي

يكتب للجملة المضغوطة (بت)

معناه (عشري)

يضاف للقاموس

N

A

01110

14 (N)

29 : NA

A

-

00001

1 (A)

30 : A-

-

O

11011

27 (-)

31 : -O

O

H

01111

15 (O)

32 : OH


الآن وصلنا إلى 32 خانة في الجدول، يعني سوف نتحول للترميز ب 6 بت.

من هنا فصاعدا، يصبح كل ما يكتب للجملة المضغوطة ب 6 بت.


السلسلة الآن

الرمز التالي

يكتب للجملة المضغوطة (بت)

معناه (عشري)

يضاف للقاموس

H

I

001000

8 (H)

33 : HI

I

B

001001

9 (I)

34 : IB

B

O

000010

2 (B)

35 : BO

O

-

001111

15 (O)

36 : O-

-

A

011011

27 (-)

37 : -A

A

L

000001

1 (A)

38 : AL

L

H

001100

12 (L)

39 : LH

H

A

001000

8 (H)

40 : HA


لحد الآن كل حرف يكتب كما هو تقريبا بدون ضغط.

هذا يذكرنا بما رأيناه قبل قليل في LZ77.

لكن ماذا يحصل في الأثناء؟ القاموس يكبر تدريجيا.

و الآن سنبدأ في رؤية مفعوله المباشر.


الحرف التالي هو A الثانية في ALHALWA

لكن... أضفنا منذ قليل بالفعل السلسلة AL إلى القاموس.

هذه المرة إذن، سلسلتنا ستكون AL.

البرنامج سيتساءل، لو أضفت الحرف التالي (W) لهذه السلسلة،

هل هذا (ALW) موجود في القاموس؟ لا، إذن تتم إضافة ALW إلى القاموس.


السلسلة الآن

الرمز التالي

يكتب للجملة المضغوطة (بت)

معناه (عشري)

يضاف للقاموس

AL

W

100110

38(AL)

41 : ALW

W

A

010111

23(W)

42 : WA

A-

W

011110

30(A-)

43 : A-W

WA

-

101010

42(WA)

44 : WA-

-

L

011011

27(-)

45 : -L

L

A

001100

12(L)

46 : LA

A

H

000001

1(A)

47 : AH

H

M

001000

8(H)

48 : HM

M

-

001101

27(-)

49 : M-

-A

L

100101

37(-A)

50 : -AL

L

K

001100

12(L)

51 : LK

K

H

001011

11(K)

52 : KH

HA

R

101000

40(HA)

53 : HAR

R

O

010001

18(R)

54 : RO

O

F

001111

15 (O)

55 : OF


كل السطور البرتقالية هي استعمالات القاموس لضغط أكثر من حرف على رمز واحد.

التحسين ملحوظ! و كلما واصلنا قراءة النص، كلما تحسن القاموس أكثر.


سنقوم قريبا بالانتقال لاستعمال 7 بت لكل حرف،

عندما نصل للخانة 63 من القاموس...

لكننا سنتوقف هنا، بما أن الجملة شارفت على النهاية.

الرمز # (و قيمته في القاموس هي 0) هو ما يشير لنهاية الجملة.


عندما نكون بصدد تكوين سلسلة و نرى هذا الرمز، نوقف كل شيء،

و نكتب ما بقي لدينا من السلسلة إلى النص المضغوط.


السلسلة الآن

الرمز التالي

يكتب للجملة المضغوطة (بت)

معناه (عشري)

يضاف للقاموس

F

#

000110

6(F)

لا شيء

#

لا يوجد

000000

0(#)

نوقف الضغط


و الآن، كل ما كتبناه تحت "يكتب للجملة المضغوطة"،

هي بتات سوف ننظمها إلى مجموعات 8 بت (بايت كامل) كما رأينا في الفقرات السابقة.

و هكذا نكون تحصلنا على النص المضغوط.


لفك الضغط، يجب التمكن من هذه الفكرة، و على الأقل معرفة التيبل الأصلي للرموز المستعملة.

يتم بعد ذلك عمل فك ضغط نحرص فيه في الأثناء على بناء القاموس من جديد،

تكون فيه بعض الحروف مجهولة و ليس أمامنا الا التنظير ماذا يمكن أن تكون،

و لا نتأكد من نظرياتنا هذه إلا مع مواصلة فك الضغط.


أنواع أخرى من LZ78

LZ78 الأصلي

كان مختلفا قليلا عن LZW في ناحية صغيرة.


فضغط LZ88 سيبدأ بقاموس فارغ.

سيفحص الجملة تدريجيا متقدما، كل مرة، في نقطة معينة منها،

و يبحث في القاموس عن أطول سلسلة انطلاقا من تلك النقطة،

ثم سيكتب إلى الجملة المضغوطة:

يكتب هنا (خانة القاموس رقم كذا) متبوعة [بالرمز الوحيد كذا].

و يضيف إلى القاموس خانة جديدة فيها: تلك السلسلة متبوعة بذلك الرمز الوحيد.

ثم يواصل قراءة الجملة في النقطة في الرمز بعد ذلك الرمز التالي.


و لو كان الرمز في تلك النقطة رمزا غير موجود في القاموس،

يضيفه هو وحيدا إلى القاموس، و يكتب للجملة المضغوطة (0)[الرمز].


لو كان لدينا نص مثل هذا، فهكذا سيرمز :


AKALAT-ALKALAMA-WA-KALAT#

أين يقرأ

يضاف للقاموس

يكتب إلى

الجملة المضغوطة

معناه

AKALAT-

1 : A

(0)[A]

A ليس بالقاموس

AKALAT-

2 : K

(0)[K]

K ليس بالقاموس

AKALAT-

3 : AL

(1)[L]

خانة قاموس 1 (A) + L

AKALAT-

4 : AT

(1)[T]

خانة قاموس 1 (A) + T

AKALAT-

5 : -

(0)[-]

- ليس بالقاموس

ALKALAMA-

6 : ALK

(3)[K]

خانة قاموس 3 (AL) + K

ALKALAMA-

7 : ALA

(3)[A]

خانة قاموس 3 (AL) + A

ALKALAMA-

8 : M

(0)[M]

M ليس بالقاموس

ALKALAMA-

9 : A-

(1)[-]

خانة قاموس 1 (A) + -

WA-KALAT#

10 : W

(0)[W]

ليس بالقاموس بعد

WA-KALAT#

11 : A-K

(9)[K]

خانة 9 (A-) متبوعة ب K

WA-KALAT#

12 : ALAT

(7)[T]

خانة 7 (ALA) متبوعة ب T

WA-KALAT#

لا شيء

[#]

رمز نهاية النص

0A0K1L1T0-3K3A0M1-0W9K7T#


طبعا، وجب الملاحظة أن ما أشرنا به بالأرقام (مؤشرات القاموس) تكتب في الواقع بالبتات.

و بأقل عدد ممكن من البتات.

يعني أن رقم الخانة 0 (رمز جديد أضيف للقاموس) و رقم الخانة 1 (خانة 1 في القاموس) يكتبان على بت واحد.

أرقام الخانة 2 (بالثنائي 10) و الخانة 3 (بالثنائي 11) يكتبان على 2 بت.

أرقام الخانة 4 (بالثنائي 100) إلى 7 (بالثنائي 111) يكتبان على 3 بت ... و هكذا.

يعني أن النص سيظهر أقصر بكثير مما يبدو لنا في الجدول أعلاه،

و الأهم، أنه في برامج الهيكس سيستحيل علينا التمييز بين الحروف (برامج الهيكس تقسم كل شيء الى 8 بت)...


الخلل في ضغط LZ78 أن القاموس يكبر و يكبر و لا يوجد شيء يحد من ذلك.

لذلك أتى ضغط LZW الذي تحدثنا عنه سابقا، ليحسنه بالصفة التي رأيناها سابقا.

و في الواقع كان ذلك التحسين ممتازا لدرجة أنه نال شعبية منقطعة النظير،

جعلت الكثيرين يسمون ضغط LZW هو ضغط LZ ببساطة

(مع أن تعميم هذه التسمية خطأ بسبب الإختلافات العديدة التي تحدثنا عنها قبل قليل!)


LZC

هذا تحسين لضغط LZW، و يتبع طريقته في ضغط الجمل.

الشكل الأصلي لضغط LZW كان يستعمل رموز قاموس ثابتة العرض،

و LZC أتى بالرموز التي يتغير عرضها حسب الحاجة (كما رأينا، مع نموذج "حديث" من LZW في مثالنا أعلاه).


لكن ما يتميز به LZC هو أنه عندما يمتلئ القاموس،

يتحول إلى ضغط تشفير بالقاموس MTE مثل أول و أبسط نوع ضغط MTE رأيناه في أعلى الدرس.

لكنه يراقب حجم الملف الأصلي و الملف المضغوط، و لو نزلت نسبة الضغط عن حد معين...

يأمر بحذف القاموس و يعيد بناءه من جديد.

بهذا يكون LZC يتجنب عيب LZ78 و LZW الأصليين،

حيث أنهما في حالة الملفات التي تختلف محتوياتها في عدة أجزاء منها،

يصبح الضغط رديئا، حيث أنه مصمم على مقاس الأجزاء في أول الملف...


LZT

هو LZC محسن أكثر، و يقوم بكثرة بالكتابة إلى الخانة الأقل استعمالا من القاموس

(طبعا يشير إلى ذلك كي يعرف برنامج فك الضغط ماذا يفعل).


LZMS

مع الأنواع السابقة، عندما كنا نجد في القاموس سلسلة من جملة،

نكتب إلى الخانة التالية من القاموس تلك السلسلة متبوعة بالرمز بعدها في تلك الجملة.

لكن ضغط LZMS يكتب لخانة القاموس فقط و دائما آخر سلسلتين كتبتا، متتاليتين و ملتصقتين.


هناك أيضا LZJ و LZFG و هي بدورها تضيف أفكارا مجددة بغاية تنظيف القاموس،

و الحديث يطول عنها. ربما أضيف لو أعدت نشر هذا الدرس أكثر تفاصيل عنهما.


المشاكل التي تسببت في انقطاع الشركات عن LZ88 في التسعينات بشكل مفاجئ

وجب معرفة أمر بسيط حول تاريخ هذا النوع من الضغط.

فهو كان محل سجال طويل لأن هناك شركات سجلت عليه براءة إختراع

هو و أنواع أخرى من ضغط LZ في أمريكا، و بدأت تطالب بإتاوة و ترفع قضايا ضد من لا يدفع،

و هو كان مستخدما جدا في بداية التسعينات خاصة في صور GIF مثلا

(هذه القضايا كانت سبب قيام هواة باختراع صيغة صور PNG التي لا تستخدم هذا الضغط).

لذلك، يستبعد إلا ما قل و ندر أن تجد مشتقات LZ88 مستعملة

في أي شيء صدر من 1994 الى 2003 (على خلاف LZ77 و هافمان)،

و لم يعد الإستعمال إلا بعد الألفية مع انتهاء صلاحية براءة الإختراع، و بصفة خجولة جدا.

مازال هناك بعض هذه البراءات على ما يبدو، لمشتقات معينة من LZ77 و LZ88.


الآن هناك براءات إختراع تضيق على أساليب ضغط مغايرة تماما تستعمل الأرقام بالفواصل لتخزين الجمل،

لكن بما أن هذا يعني أنها غير مستخدمة في الألعاب (بعد)

و أنه حتى إستعمالنا لها غير ممكن حاليا في أي شيء نبرمجه لديه عراقيل قانونية

بسبب جشع جامعي براءات الإختراع، لن نتطرق لذلك النوع في هذا الدرس أصلا.


عوض ذلك سنتحدث عن أسلوبي الضغط المستعملان بكثرة مع LZ في التسعينات إلى الآن.

مستعملان معه، يعني نأخذ شيئا مضغوطا بطريقة و نضيف فوقه ضغطا آخر.

و هما أسلوب RLE و أسلوب هافمان.

و مثل LZ77 فلا توجد براءات إختراع تعطل إستخدامهما، ما حقق لهم رواجا.

على سبيل المثال، ملفات ZIP تستعمل أسلوب إسمه Deflate هو تركيبة LZ و هافمان.

و ألعاب كونامي على الميغادرايف تستعمل ضغطا هو تركيبة من LZ و RLE،

أو هافمان منفردا في السوبر نيس، أو RLE منفردا في كمبيوتر صخر، و النيس.

مع بعض المحاولات لعدد من الشركات مع LZ و RLE على النيس.


ملاحظة بخصوص أنواع ضغط أوفرلاي الدي اس

في ألعاب الدي اس التي يمكن فتحها ببرنامج Tinke أو الكريستال تايل،

تحت ملف ftc هناك عدة ملفات متاح للجهاز قراءتها في الذاكرة بسرعة نسميها ملفات الأوفرلاي.

أهمها arm7 و arm9، و ملفات الأوفرلاي overlay و هي في الغالب متعلقة بال arm7 (هناك حالات نجد فيها التي تتبع 9)


ملف arm9.bin هو القلب النابض لتطبيق برنامج لعبة الدي اس.

(arm7 لديه علاقة أكثر بوظائف برمجة الجيم بوي أدفانس)

لكن للأسف عدة مطورين يخزنون فيه أشياء و يصعبون علينا حياتنا.


و يوجد ملفات y7 و y9 بهما قائمة ملفات الأوفرلاي السابقة من النوعين

و مكانهم و أحجامهم و ان كانت مضغوطة أم لا.

و بالطبع ملفات srl لكن تلك مستخدمة في البيانات المرسلة في اللعب الجماعي.


لأنه أحيانا تكون هذه الملفات مضغوطة، و هذا يشمل arm9.bin

ماذا نفعل في تلك الحالة؟


أبرز أنواع ضغط LZ للدي اس (لكن ليست الوحيدة)

هي ضغط 0x10 و ضغط 0x11 (نتعرف عليها بفتح الملف في برنامج الهيكس و رؤية أول بايت)،

و هناك نوع نادر ظهر مع غولدن سان 3 في 2010 اسمه 0x40.

(هناك أيضا نوع بالهافمان أول بايت هو 20، و نوع ب RLE أول بايت فيه هو 30)

لكن أنواع الضغط هذه تخص ملفات الدي اس العادية.

أما ملفات الأوفرلاي overlay فلديها نوعية ضغط LZ خاصة بها (هناك من يسميها BLZ اي LZ المقلوب).

أحسن برنامج لفك و اعادة ضغط هذه الملفات هو أدوات CUE التالية.


لكن المزعج في الأمر هو أننا نحتاج تعديل المؤشرات لإعادة إدخال ملفات الأوفرلاي هذه.

وجب إذن تغيير مؤشرات الملفين y7 و y9 حسب المطلوب.


و هناك حيلة لا توجد الا مع الدي اس: من لو اعترضه أوفرلاي مضغوط، يقوم بفكه، و تعديله...

لكن عندما يعيد ادخاله للروم، لا يقوم باعادة ضغطه من جديد.

بل يضع الأوفرلاي الجديد بدون ضغطه، و يقوم بفتح y9 في برنامج هيكس

و تعديل البايت الذي يقول ان كان الأوفرلاي مضغوطا أم لا.


(فقرة تحتاج الاكمال)



ضغط RLE أو ترميز طول التشغيل

(تعويض التكرار بعدد المرات)

الصعوبة: متوسط


أمثلة إستخدام:

كونامي (نيس/صخر) – RLE بسيط، ألعاب عديدة (الأدوات)

كابكوم (نيس) – RLE مبسط، صور داك تيلز 2

كابكوم (سوبر نيس) – RLE مبسط لأغلب اصدارات السوبر نيس

ضغط Nemesis (ميغادرايف، شائع) – RLE محسّن (الأدوات)

نينتندو (64، جيم كيوب، وي – شائع جدا) – yay0 و yaz0 (الأدوات N64Tool و ctools و هذا)،

مستعمل في المجلدات المضغوطة من نوع U8 (بما في ذلك كل اصدارات WiiWare)


مدمجا مع هافمان: طريقة DEFLATE

مستعمل بكثافة – ملفات zip أو zlib و كل ما هو مشتق عنها

رير (نينتندو 64) – دونكي كونغ 64 و أغلب ألعابهم على الجهاز (الأدوات)


هذا النوع مصمم للحالات التي يكرر فيها بايت معين عديد المرات بشكل متتال.

و هو يعوض التكرار بعدد مرات التكرار، و اسم البايت.

يعني لو وجد (ج) معادة تسعين مرة، فعوض أن نكتب 90 بايت،

نكتب فقط 2 بايت: عدد مرات التكرار، و البايت المتكرر.

طبعا هذا نظريا. عمليا تتغير طرق البرمجة،

في حالة النيس مثلا نجد 3 بايتات، حيث هناك أيضا بايت في البداية يعلن أن هناك تكرارا مضغوطا بطريقة RLE.

أما البايتات غير المتكررة، فعادة تكتب بدون ضغط.


مثلا:

ااااااااابببببببجدحطططططي#

تعوض بالآتي:

(كرر)[9][ا]

(كرر)[7][ب]

(كرر)[1][ج]

(كرر)[1][د]

(كرر)[1][ح]

(كرر)[5][ط]

(كرر)[1][ي]

#


(كرر)[9][ا] تكتب لنا 9 مرات الرمز التالي (ا).

لكن أليس من الغباء أن نكتب "كرر مرة واحدة"؟

الجملة تصبح أطول.

لهذا السبب هناك بايت طول خاص من نوع (عادي) أو skip ان كنتم تريدون البحث بالإنكليزي عنه في النت.

يقول لنا أن بعده بايتات جملة غير مضغوطة، و يعطينا طولها.

عندما ينتهي ذلك الطول، نعود إلى استعمال بايت آخر مثل (عادي) أو (كرر).

مثلا:

(عادي)[3][ج][د][ح] تكتب لنا بدون ضغط الثلاثة بايتات بعد بايت الطول "03 عادي".


الجملة السابقة يمكن أن نكتبها هكذا، من 25 بايت في الأصل إلى 12 بايت في ضغط RLE.

(كرر)[9][ا]

(كرر)[7][ب]

(عادي)[3][ج][د][ح]

(كرر)[5][ط]

(عادي)[1][ي]

#


و في الواقع، فإن (كرر) و (عادي) لا يحتلان بايت أو رمز كامل.

بل يكونان جزءا من بايت الطول نفسه.

مثلا، يكون هناك بت في بايت الطول مخصص لهما.

نقول على سبيل المثال (طرق البرمجة تختلف حسب اللعبة)

أن لدينا: (كرر)[9][ا]

بايت الطول بالهيكس سيكون 09 أو بالثنائي 0000 1001

من غير المرجح أن نجد بايتات طول تصل إلى 128 (بالهيكس 80 و بالثنائي 1000 0000)

نستخدم إذن ذلك البت الأخير.

عندما نريد أن يكون عندنا بايت (كرر) نجعله 1، و عندما يكون لدينا (عادي) نجعله 0،

و بقية البتات نستخدمها للطول.

فتصبح (كرر)[9] مكتوبة هكذا ببايت واحد 1000 1001


قلنا أنه من غير المرجح أن نجد بايتات طول تصل إلى 128...

لكن أحيانا تكون موجودة، لذلك يتم اللجوء لحيل

مثل تخصيص بايتات خاصة تدل على مضاعفة التكرار بمقدار معين...


لكن أي نص هذا هو الذي ستجد فيه حروفا معادة عشرات المرات؟

هذا الضغط لا يصلح كثيرا للنصوص (مع أن هناك بالفعل ألعاب نيس استعملته للنصوص، و هذا أمر محير).

لكن الصور تحتوي الكثير من المساحات الفارغة،

التي هي في الواقع بايت من لون معين مكرر عشرات المرات.

ما يجعل هذا الضغط مثاليا للصور أكثر من غيرها من أنواع البيانات.


الأمر الجيد في ضغط RLE أن الصور تحافظ نوعا ما على شكلها في برنامج الهيكس،

مشوها بطريقة مميزة لهذا النوع من الضغط.

على سبيل المثال، هذه شاشة عنوان و معها خط مضغوط بهذه الطريقة:



ضغط هافمان

(طول كل رمز حسب كثرته في النص)

الصعوبة: صعب


أمثلة إستعمال:

كونامي (سوبر نيس) – تعشق استعماله لسبب ما

(سوبر نيس) – Shadowrun (مستعمل بكثافة)

نينتندو (بيوس، دي اس) – نوعية ضغط هافمان متفق عليها (الأدوات)


لو نعود لطريقة ترميز كل رمز/حرف بأقل من بايت كامل (8 بتات)، فطريقة هافمان للضغط إمتداد لها.

حيث أن ضغط هافمان يفحص النص أولا و يحلل كم يظهر كل رمز/حرف.

الرمز/حرف الأكثر إستعمالا يرمز له بأقصر سلسلة بتات.

و كلما ندر الرمز/الحرف، كلما كانت سلسلة البتات التي تعادله أطول.

و لو لم نجد الحرف أصلا في النص، لا نتعب أنفسنا بوضع معادل له بالبتات.


هذه هي الفكرة العامة وراء ضغط هافمان.

ضغط LZSS يمكننا أن نراه في برنامج الهيكس (أجزاء من كلمات غير مضغوطة في بداية النص).

كذلك ضغط RLE يمكن أن نرى المعالم العامة للصورة المضغوطة به في برامج التايل.


لكن ضغط هافمان يطمس معالم البيانات المشفرة تماما.

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

هناك "شجرة" تدل على تواتر الحروف ستكون مرفقة مع النص المضغوط أيضا،

و ستكون ضرورية لفك ضغطه.

الطريقة المستخدمة في الغالب في ضغط هافمان في الألعاب ستستعمل شجرة جاهزة مثل هذه.


كيف يتم ضغط هافمان

المرحلة الأولى – نحسب و نرتب


الجملة المبتذلة التي ستكون الضحية الجديدة لتجاربنا هي:


KATKOT-ATTOT-FAOK-ALHOT#


ماذا كنا نقول قبل قليل.

أننا سنضغطها بطريقة هافمان.


يعني هناك حروف مقابلها قصير (الحروف الأكثر استعمالا)

و حروف مقابلها طويل (الحروف الأندر)

و حروف بدون مقابل نتجاهلها (التي لا تظهر في الجملة).

نحن إذا سنصنع جدول فيه ما هو مقابل كل حرف. يعني، سنصنع ملف تيبل.

مثل الذي في الدروس الأولى.

كيف نصنعه؟ الآن سنرى ذلك.


أولا في الجملة أعلاه، يجب أن نحسب بالنسبة لكل حرف كم يظهر من مرة.

لا ننسى الفراغات.

لا داعي للاهتمام برمز نهاية الجملة نظرا أنه إشارة نهاية الضغط أيضا.

النتيجة في حالتنا:


K

3

A

4

T

6

O

4

-

3

F

1

L

1

H

1


نقوم بترتيب هذا الجدول بالترتيب التنازلي، من أكثر الحروف/الرموز شيوعا إلى أندرها.

يمكن القول أن هذه مرحلة الفرز الأول.


الرتبة

العمود 1

عدد مرات الظهور

1

T

6

2

A

4

3

O

4

4

K

3

5

-

3

6

F

1

7

L

1

8

H

1


الآن، تحصلنا (بالأصفر) على أول عمود من "جدول هافمان".

نحن الآن بدأنا البحث عن "شجرة هافمان"، لكننا بدأنا من الأوراق.

في المرحلة التالية سنمر للأغصان إلى أن نصل للجذع الرئيسي.


هناك طرق أخرى لإيجاد هذه الشجرة الملعونة ربما أتحدث عنها و على الأرجح لن أفعل،

نظرا أن لدينا أمور أهم تنتظرنا.


الآن لنمر للأغصان (لو صح التعبير)...

تلك الرموز النادرة في آخر الجدول حالها يكسر الخاطر.

نأخذ إذن آخر رمزين (الأقل ظهورا) و نوحدهما في خانة واحدة.

الخانة ستحتويهما متتالين، (الأول و بعده الثاني، لكن حتى الثاني و بعده الأول صحيح أيضا)

و عدد مرات الظهور للرمز الموحد سيكون مجموع عدد المرات للرمزين.

ثم نعيد ترتيب الجدول تنازليا كالعادة.


في حالتنا، لدينا L (1 مرة) و H (1 مرة).

الرمز الجديد سيكون LH (2 مرة).

عندما نرتب الجدول، يصبح F (1 مرة) أقل من LH (2 مرة) و يتأخر لآخر الجدول.

يصبح لدينا:


الرتبة

العمود 2

عدد مرات الظهور

1

T

6

2

A

4

3

O

4

4

K

3

5

-

3

6

LH

2

7

F

1


نواصل و نكرر المرحلة السابقة.

للحصول على ثالث عمود، نوحد آخر خانتين:

و هما الخانتان LH (2 مرة) و F (1 مرة)

في خانة واحدة هي LHF (2+1=3 مرات).

نرتب الجدول (يبقى كما هو).


للحصول على رابع عمود، نوحد آخر خانتين:

و هما الخانتان – (الفراغ) (3 مرات) و LHF (3 مرات)

في خانة واحدة و هي –LHF (6 مرات)

نرتب الجدول و يتغير الترتيب بشكل كبير.


و هكذا...

جربوا القيام بهذا بأنفسكم لو شئتم.

أظن الصورة اتضحت نوعا ما... و بدأنا نرى شكل الشجرة.


رتبة

عمود 1

عمود 2

عمود 3

عمود 4

عمود 5

عمود 6

عمود 7

1

T 6

T 6

T 6

T 6

OK 7

-LHFA 10

OKT 13

2

A 4

A 4

A 4

-LHF6

T 6

OK 7

-LHFA 10

3

O 4

O 4

O 4

A 4

-LHF 6

T 6


4

K 3

K 3

K 3

O 4

A 4



5

- 3

- 3

- 3

K 3




6

F 1

LH 2

LHF 3





7

L 1

F 1






8

H 1








لا نحتاج لكتابة آخر جذع، أي OKT-LHFA (23 مرة).


المرحلة الثانية – نبحث عن شجرة نسب كل رمز

هذا هو إذن جدول هافمان، أو بالأحرى شجرة هافمان.

و تسمية الشجرة في محلها نوعا ما.

لأن جميع حروف هذه الجملة تتفرع من جذعين و هما OKT و –LHFA

الأول هو ثاني أندر خانة (13 مرة)، نعطيه إذن 1،

و الثاني هو أندر خانة (10 مرات)، نعطيه إذن 0.


نبدأ إذن بصناعة جدول مقابل الرموز، التيبل،

لكن ألم نقل أن الهافمان يرمز على أقل من بايت كامل (8 بت)؟

إذن سنبدأ كتابة مقابلات الحروف بالبت بالبت.

المقابلات التي تنحدر من سلالة الجذع القوي، نكتب لها أول بت 1،

أما السلالة الضعيفة، نكتب لها أول بت 0.


البداية تكون إذن هكذا في مثالنا هذا.

حيث نبدأ في البداية بالعمود الأخير (ثم نعود للوراء تدريجيا).

O تنحدر من OKT، نعطيها إذن 1...


O=1

K=1

T=1

-=0

L=0

H=0

F=0

A=0


نعود لجدول هافمان و ننظر هذه المرة للعمود 6.

أمام جميع الحروف المنحدرة من ثاني أندر سلالة OK (7 مرات) نضع 1.

أمام جميع الحروف المنحدرة من أندر سلالة T (6 مرات) نضع 0.

أمام بقية الحروف، لا نضع شيئا.


(السبب أن تلك الحروف المتبقية شائعة.

و ترميز هافمان هدفه جعل الحروف الشائعة هي الأقصر.)


يصبح التيبل هكذا:


O=11

K=11

T=10

-=0

L=0

H=0

F=0

A=0


نواصل، مع العمود 5،

نضيف 1 لثاني أندر سلالة، نضيف 0 لأندر سلالة، لا نضيف شيئا للباقي، و نواصل...

و نعود شيئا فشيئا إلى أن نصل العمود الأول.


O=111

K=110

T=10

-=011

L=01011

H=01010

F=0100

A=00


صار لدينا الجدول التالي.

و بالفعل، يمكننا أن نلاحظ أن الرموز الشائعة (مثل T الذي يظهر أكثر عدد من المرات: 6) هي الأقصر،

و الرموز النادرة (مثل L الذي يظهر في الجملة مرة واحدة) هي الأطول.


و لضغط الجملة، كل ما علينا فعله ببساطة هو كتابة الجملة السابقة بهذا التيبل،

مثلما فعلنا في أول الدروس!

يعني أن الجملة السابقة تصبح هكذا:


KATKOT-ATTOT-FAOK-ALHOT#

110 00 10 110 111 10 011

00 10 10 111 10 011

0100 00 111 110 011

00 01011 01010 111 10


بما أن هذا كله سيكتب إلى بايتات، و البايت هو 8 بت،

نجمع هذه الأصفار و الوحدان إلى مجموعات، ثمانية ثمانية.

و نحول للنظام الست عشري.


11000101 10111100 11001010 11110011

01000011 11100110 00101101 01011110


من غرائب مصادفات القدر أن جملتنا العجيبة عدد بتاتها بالضبط من مضاعفات 8.

عادة يكون آخر بايت غير كامل، فنملئه بأصفار لنكمله 8 بتات – قد تسبب مشاكل في القراءة،

بما أن برنامج فك التشفير قد يظن الأصفار رمزا آخر،

لذلك عادة يكون هناك بايت آخر يقول للبرنامج أين يتوقف عن القراءة. (كيف؟ حسب ذوق المبرمج)

و هذا في النهاية تفصيل تختلف طريقة تطبيقه حسب أذواق المبرمج.


إذن في النهاية، نحول للنظام الست عشري (بالآلة الحاسبة للويندوز مثلا)

و نتحصل على السلسلة التالية بالهيكس:


C5 BC CA F3 43 E6 2D 5E


جميع معالم الجملة الأصلية إختفت!


الطول الأصلي: 23 بايت (لو كان كل رمز هو بايت واحد)

الطول المضغوط: 8 بايت

أي أن الجملة الجديدة هي ثلث حجم الجملة الأصلية!


طبعا لاحتساب الشجرة يحبذ أن نبرمج أداة تقوم بذلك نيابة عنا، نظرا لبطئ العملية.

هناك مثلا هذا الموقع لو كنا على عجل.


تشفير هافمان ناجع جدا و استعمل كثيرا في السوبر نيس و الميغادرايف و بعدها من الأجهزة،

و يصلح لكل شيء سواء النصوص أو الصور،

عدا اقترانه بنظام DEFLATE الشهير المستخدم في جل صيغ ملفات zip.


لكن كي يتمكن البرنامج أو اللعبة من فك الضغط،

يحتاج إلى شجرة هافمان مرفقة مع البيانات المضغوطة.

لهذا السبب من يقوم باستخدام ضغط هافمان، مقابل أن يربح المساحة بفضل الضغط،

عليه أن يخسر مساحة لتخزين هذه الشجرة، ما قد يجعلها غير ملائمة لنصوص قصيرة.


هناك حل أبسط من إعادة بناء هذه الشجرة لكل نص،

و هو أخذ الإحصائيات العامة لتردد الحروف في كل لغة و استخدامها لعمل شجرة هافمان جاهزة

تصلح لجميع السياقات بشكل مقبول نسبيا.

على سبيل المثال، هذه شجرة هافمان تقريبية (ليست مثالية لكنها تصلح) لحروف اللغة العربية،

مع بعض علامات التنقيط (استعملت الاحصائيات الانكليزية لعلامات التنقيط،

نظرا أن معدل طول الكلمة بين الانكليزية و العربية متقارب و هو 5).


_ 100

ا 1111

ل 1110

ن 0100

م 0011

. 0010

ي 0000

, 11011

و 11010

ه 10110

ر 01111

ب 01110

ع 01100

أ 110011

ف 110010

ق 110000

د 101111

ت 101110

" 101010

س 101001

ك 011011

ح 010100

- 000101

# 000100

ة 1100011

ى 1010111

ج 1010110

ص 1010000

/ 0101100

) 0101011

( 0101110

إ 0110100

ذ 0001111

ث 0001110

خ 0001100

ش 11000101

ز 01101011

؟ 01010100

ط 01011111

ض 00011011

غ 110001001

ء 110001000

: 101000101

; 101000111

ئ 101000100

0 010110101

1 010110110

2 010101011

3 010101010

4 010110111

5 010111100

6 010111101

7 010110100

8 000110101

9 011010100

! 011010101

ظ 000110100

آ 1010001100

ؤ 10100011011

§ 10100011010


_ : الفراغ بين الكلمات

# : العودة للسطر

§ : نهاية النص

هناك من لديه توجه في العربية لتجنب الفاصلة المنقوطة (؛). يمكن استخدامها لترميز (ؤ) مثلا.


على ذكر العربية، فإن ترميز القواميس مع أنه ينفع لبعض الثنائيات (ال/لا/..)

إلا أن خصوصية اللغة العربية تجعل استعماله غير ناجع مثلما لو استعملناه مع اللغة الانكليزية،

و في المقابل يكون استخدام هافمان مع العربية أفضل بكثير.