• 0
telltalkwael

Data Compression ضغط البيانات

سؤال

ضغط البيانات Data Compression

بحث عملي عن طرق ضغط البيانات المتكامل (Lossless) مع امثلة تطبيقية بلغة السي

تمهيد

بعد حمد الله والصلاة والسلام علي رسوله الكريم..

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

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

تم عرض جميع الأمثلة الواردة بالبحث بلغة السي نظراً لانتشارها فضلاً عن امكاناتها الهائلة و سهولة تتبع أوامرها.وعليه فيلزم القاريء ان يكون ملماً باساسيات هذه اللغة.

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

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

اشتملت مقدمة البحث علي تعريف "ضغط البيانات" وتوضيح بعض الحقائق عن هذا العلم.

اهتم البحث بنوع واحد من ضغط البيانات وهو النوع المتكامل "Lossless" ، كما لم يتعرض إلا للخورزميات التالية من هذا النوع:-

·المبحث الأول Run-Length Encoding

·المبحث الثاني Huffman Coding

·المبحث الثالث Adaptive Huffman Coding

·المبحث الرابع Arithmatic Coding

·المبحث الخامس Dictionary-Based Coding ويشمل :- Lz77 ، Lzss ، LzW

·المبحث السادس More Source Codes واحتوي علي :- Lz-Arith ، Lz-Huf ، CarMan ، CarManGUI.

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

اتبع الباحث الاسلوب التالي في عرض موضوعه:-

·يبدأ كل مبحث بتعريف مختصر للغاية عن الموضوع دون الإخلال بالمادة قيد الشرح.

·يلي ذلك مثال عملي مكتوب بلغة السي مكون من ملف واحد فقط وبأقل عدد من التعليقات.

·يتم الشرح من خلال المثال العملي بتوضيح وظيفة كل دالة ظهرت به.

·يتم التصريح عن مصادر الموضوع في نهاية كل مبحث بحيث يمكن للقاريء ان يستزيد من المصدر مباشرة قبل ان ينتقل الي المبحث التالي.

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

-------------------------------------------------------------------------

* إذا قام القاريء الان بكتابة Data compression في أي محرك بحث فستكون النتائج عبارة عن مئات المواقع التي تعني بهذا الموضوع، بينما إذا كرر الأمر ولكن بكتابة "ضغط البيانات" فستكون النتيجة مئات المواقع التي تعني ببيع برامج تقوم بضغط البيانات مثل الwinzip والwinRar وليس مواقع عربية تشرح هذا الموضوع كما في الحالة الأولي؟!!. ويمكن القول إما بفقرالمكتبة العربية من مقالات او أبحاث فضلاً عن أمثلة عملية في هذا الباب أوانه توجد مشاركات بالفعل من ابناء الوطن العربي سقطت بالتقادم أو أن كتاب هذه المقالات لم يهتموا بتعريب مصطلحات هذا العلم لذا لم يهتدي إليها محرك البحث. تجدر الاشاره هنا إلي ان الباحث قد لا يستطيع تقديم تعريب كامل ومعتمد لبعض المطلحات الأجنبية ليس هذا بالطبع لفقر اللغة العربية لمثل هذه المعاني وإنما لعجز الباحث عن ذلك ليس أكثر.

المقدمة

يمكن تعريف مصطلح "ضغط البيانات"علي أنه :-

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

ومن التعريف السابق يتبين الاتي:-

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

قم بكتابة برنامج يقوم بطباعة الحروف من 0 حتي 255 داخل أي ملف ليصبح حجم الملف النهائي 256 بايت بعد ذلك قم بمحاولة ضغط هذا الملف بأفضل برنامج ضغط علمته وليكن WinRar ستجد ان حجم الملف أصبح 325 بايت (بفرض ان اسم الملف مكون من حرف واحد) أي أن الحجم قد زاد ب69 بايت والحقيقة ان الفرق في الحجم هو حجم الهيدر أو البيانات الرأسية التي يكتبها البرنامج للتعرف علي محتويات الأرشيف.

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

ينقسيم ضغط البيانات الي نوعين :-

الضغط المتكامل:(LosslessCompression) وفيه يكون خرج البيانات عند اعادة فك الضغط مطابق تماماً للبيانات قبل الضغط بلا أدني فقد.

الضغط مع الفاقد:(LossyCompression) ومن اسمه فان خرج البيانات عند فك الضغط سيكون مختلفا قليلا عن المصدر.

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

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

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

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

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

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

تستخدم بعض المصطلحات في هذا الباب - ضغط البيانات - لتؤدي نفس المعني رغم اختلاف معاني هذه المصطلحات في أبواب اخري من أبواب العلم، فعلي سبيل المثال لا الحصرتستخدم المصطلحات التالية بمعني واحد وهو "الضغط":-

Compression , Compressing , Encoding

بينما تستخدم المصطلحات التالية بمعني "فك الضغط" :-

UnCompressing, Extracting , Expanding , Decoding

انتهت المقدمة ويلها المبحث الأول Run-Length Encoding

4

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

1 إجابات على هذا السؤال .

  • 0

جزاك الله خيراً فعلاً المكتبة العربية فقيرة جداً في مجال ضغط البيانات .

بانتظار المبحث الأول

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .