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

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


قرأنا في الدرس الفارط عن المؤشر 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 على البي اس بي.


نمر لشرح أبرز أنواع الضغط...


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

اضطررت نظرا لمحدودية ما أعرفه أن أقتصر على الأنواع الشائعة فحسب.

ما يعني أن الضغط بالجبر arithmetic coding (و هو من شاكلة هافمان)

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

و غيرها من الأنواع الملمح لها أعلاه ... لن يكون لها محل في هذا الدرس،

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


1 – ترميز عدة حروف على بايت واحد (قاموس لا يتغير)

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

3 – ترميز ضغط LZ (قاموس يتغير حسب النص) (*)

4 – ترميز ضغط RLE أو طول التشغيل (السلسلة المكررة تعوض بعدد المرات)

5 – ترميز ضغط هافمان (طول كل رمز حسب ندرته في النص)


(*) مع حديث بسيط عن أنواع ضغط الدي اس. لم أذكر كل أنواع LZ78 ايضا (ما يعني أنه غير كامل، و الكمال لله).


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

نظرا أنه سهل، لا يحتاج معرفة بالبرمجة لتطبيقه،

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


بالنسبة لبقية الأجزاء، فهي ليست ضرورية بعد الآن طالما لا نعرف البرمجة.


فربما لا تنفعنا الآن كثيرا في التنفيذ

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

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

و ثانيا لإيجاد حلول لجعلها تفتح صورنا و نصوصنا المعدلة.


لكن هذه الأبواب قد تنفعنا لفهم الفكرة وراء كل نوع ضغط، كي لا تظل العملية لغزا تاما.

طريق الألف ميل يبدأ بخطوة،

و وجب أولا فهم الفكرة، و فهم كيف يتم الضغط.

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

و لو أن هذا ... غير محبذ.


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

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

الإستثناء هو الأدوات عامة الإستعمال، مثل أدوات ضغط بيوس الأدفانس و الدي اس.


عدا ذلك، هذه الأدوات قد تطلب منكم أن تعطوها شيئا.

من قبيل، من أين أبدأ فك الضغط؟ و أين أتوقف؟

نحتاج إذن عنوان البيانات المضغوطة.

و أفضل وسيلة لإيجاده هي، مرة أخرى... العودة لبرمجة اللعبة.


عدد من هذه الأدوات يتطلب MS-DOS.

يمكنكم عمل ملف bat كما رأينا مع Cartographer أو Atlas و هما أيضا يتطلبان MS-DOS.

هناك منها الاسكريبتات التي تتطلب ان تكون نصبت برنامج مثل python، أو QuickBMS حسب نوع الاسكريبت.

ربما، لا أدري متى، أضع شرحا لهذه البرامج، لو لم يسبقني أحد لذلك.


لكن.

بعد أن يتعلم القراء المزيد عن الأسمبلي (لغة برمجة الآلة) لأجهزة الكونسول

و يدركوا أنها ليست مخيفة للدرجة التي تبدو لهم من أول وهلة،

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

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


حاولت اختصار و تبسيط هذه الشروح.

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

جزء من ذلك بدافع الكسل...

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

فاللعبة أيضا تحتاج للبيانات في شكل مقروء!