• 0
DATA_SNIPER

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

سؤال

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

I have made this letter longer than usual because i lack the time to make it shorter

blaise Pascal

مقدمة:

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

الشرارة

في سنة 1883 كان إكتشاف شفرة مورس من قبل العالم صامويل مورس مظهرا من مظاهر التطور في عملية الإتصال،ومدخلا غير مباشر لعلم ضغط اليبانات كوسيلة لتسريع عملية الإرسال،إن القيود الطبيعية التي تشوب عملية الإرسال أو الإتصال من بطئ وقابلية للضياع يستدعي الحاجة إلى تغيير الترميز وذلك بترميز آخر أقل حجما ويحمل نفس المعلومات،مما سيسرع من عملية الإرسال ويقلل من إحتمال الضياع و ورود الأخطاء،كان فكرة صامويل مورس أن يمثل الأحرف المتكررة برموز قصيرة وبالتالي فإن النص الذي يحتوي على "حرف متكرر بشكل كبير سيعطيه تمثيل صغيرا" وعلى النقيض من ذلك فلو أعطاه ترميز عادي فسيستهلك مساحة و وقت اطول،وقد بنى مورس فكرته على اللغة الإنجليزية وكون جدولا يضم الأحرف الإنجليزية وما يقابلها من الترميز المناسب وكان وضع الترميز وفق Frequency of occurence لكل حرف حيث يتم إسناد الترميز الأقل للحرف المتكرر بشكل اكبر،فنلاحظ مثلا أنه أعطى للحرف E ترميز النقطة وهو أقل ترميز في الجدول وهذا يرجع لطبيعة الحرف E في اللغة الإنجليزية كونه يتكرر بشكل كبير جدا.

morse_code.jpg

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

ومن الأمور التي سرعت في إنتاج تلكم القواعد و النظريات التطور التكنولوجي و الثورة التي حصلت في علوم الكمبيوتر وكان ذلك في سنة 1937 حيث ظهرت آلة تورينج ونموذج فون نيومن سنة 1945 وتطورت مفاهيم علوم الكمبيوتر بشكل كبير وملفت.

بداية الطريق

في سنة 1948 نشر شانون بحثا هاما بعنوان "A Mathematical Theory of Communication" وكان الأساس في بناء نظرية المعلومات،ومما يجب التنويه اليه ان شانون لم يكن وحده الرقم الصعب في نظرية

المعلومات بل كان هنالك من العلماء الأفذاذ الذين نشروا أبحاثا ساهمت في تطوير هذه النظرية من بينهم نكويست في بحثه الذي تحدث فيه عن العوامل المؤثرة في سرعة التيليغراف "Certain factors affecting telegraph speed" وبحثه الثاني الذي نشر في عام 1928 بعنوان "Certain Topics in Telegraph Transmission Theory"، وكان على الجبهات الأخرى علماء لهم إسهامات كثيرة مثل

"Ralph Hartley" و "Robert M. Fano" بما عرف بـ "Shannon–Fano coding" و "Andrey Kolmogorov" بما عرف بـ"Kolmogorov complexity" و "Norbert Wiener" وغيرهم.

إن نظرية المعلومات وكغيرها من العلوم اعتمدت على المعادلات و النماذج الرياضيات لوضع قواعد قوية وراسخة، وهذا مما ثبت أوتادها بين جميع العلوم في مجال علوم الكمبيوتر ، وهي تصنف كفرع من "Theoretical Computer Science" و كفرع في الرياضيات التطبيقية.

ومما احتوته نظرية المعلومات وادخله شانون الى قاموس الاتصالات مفهوم القنوات ذات الضجيج "Noisy channels" و الذي أسست للـ Coding Theory الذي ساهم في تطور Error Correcting Codes و الذي كان من أشهرها Hamming code.

في حين أنه أدخل مفهوم عجيب جدا وقوي في نفس الوقت يستعمل في قياس "متوسط كمية المعلومات الموجدة في رسالة ما" وهذا ما سمي بـأنتروبيا شانون أو "Shanon Entropy"و الذي كان له تأثير كبير في مجال Data compression خاصة Lossless Compression حيث يعبر عن القيمية الحقيقية او الدنيا الذي يمكن أن تسند لترميز ما.

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

بإختصار فإن ضغط البينات هو:

"The art of representing Data in Compact Form"

وعندما نقول فن، فإنه فن بكامل ما تحمله الكملة من معنى.

قد يصحب عملية الضغط ضياع في البيانات وذلك ما نسميه بـ Lossy Data compression وهذا طبعا إن كان لا يؤثر بشكل كبير على اليبانات، مثال:ضغط الصور، ضغط الصوت، او الفيديو، فالتغيير في بيسكل واحد من الآلآف من البكسلات لن يؤثر على الصورة او استبدال مجموعة من البكسلات بـالمتوسط الحسابي لهم لن يؤثر، فغالبا مايستثمر هذا النوع من الضغط ضعف الحس البصري أو السمعي لدى الإنسان في تمييز الفروق الضئيلة.

وقد يصحبها عدم ضياع في البيانات والذي نسميه Lossless data compression وهذا غالبا يكون في ضغط النصوص فلا يمكن أن تضغط كلمة "Printf" فتصبح "Scanf" وبالتلي تضغط شفرة مصدرية وتنتج شفرة مصدرية آخرى،وهذا التقسيم أدى إلى توسع أكثر وإنتاج غزير في علم ضغط البيانات.

الاكتشاف

في سنة 1951 وذلك بعد إكتشاف ترميز شانون-فانون "Shannon–Fano coding" قام David A. Huffman بطرح Huffman Encoding وهي طريقة لإيجاد أقصر تمثيل بحيث يكون Optimal prefix-code وهو تمثيل يكون فيه Code-words او مخرجات Compressor ليس لها علاقة ببعض اي لا تكون prefix of each other وبالتالي هذا سيضمن عملية Decoding بطريقة غير ملتبسة، وقد إعتمد هافمن على Trees Data Structure كبنية تساعد في هذه العملية، بالإضافة إلى التوزيع الإحصائي للحروف او ما يسمى بـFrequency of Occurence ليحديد إلى من يسند الترميز الأقصر.

وكانت بعده وقبله ممن اسسوا لهذا العلم ومنهم Leon G. Kraft المعروف بـKraft's inequality و التي تحدد إمكانية وجود uniquely decodable code لأطوال Code-Words محددة،وهي تحدد بطريقة أخرى إمكانية وجود Prefix-Code لأطوال محددة.

ان الاعتماد على مفهوم التكرار و الإحتمالية و الاحصاء أنشأ ما يسمى بـ Statistcal Data Compression Approches لكن هذا النوع من ضغط البيانات يحتاج موارد كبيرة و وقت معتبر لإجراء عمليات الحساب و الضغط،وبالتالي بقي هذا العلم بعيدا عن البداهة و التلقائية في استثمار Redundancy او التكرار وكيفية التغلب عليه.

لكن في سنة 1977 جاء JACOB ZIV و ABRAHAM LEMPEL واقترحوا نموذجا بسيطا جدا والذي سمي بعدها بـ Dictionary-Based Compression Approches وكان من البداهة بمكان، مما جعله ينتشر بكثرة ويستعمل في انظمة الفاكس و Modems.

إن هذا المفهوم منتشر ومعروف ولا يحتاج لشرح فأنت مثلا عوض أن تكتب التاريخ "16 فيفري 2011" تكتب "2011/02/16" و عوض أن تكتب Internet Information Services فإننا نكتب IIS لكن السؤال هو كيف اعرف التعبير المناسب، لماذا لا اختار International Information System ؟ الحل هو ما نسميه بـDictionary ،حيث أن القاموس يحتوي على الكلمات المقابلة وا ختصاراتها فمثلا لو رجعنا إلى كود مورس لوجدنا أنه يعتمد على قاموس فيه الأحرف وما يقابلها من تمثيل، لكن هذه التمثيل الثابت أو Static ليس مرنا ولا يمكن له حل جميع مشاكل الضغط، فماذا لو وجدنا نصا لا يحتوي على تلكم الكلمات أصلا، فالحل هو أن نضطر إلى بناء نموذج تلاؤمي adaptive او Dynamic يتأقلم مع نوع المدخلات وينتج ضغط أحسن، وهذا ما قام به JACOB ZIV و ABRAHAM LEMPEL بعد نشر ورقة بحثية بعنوان "A Universal Algorithm for Sequential Data Compression" حيث يتم فيها استبدال النصوص المكررت بمراجع (indexes or references) للكلمة الأصل اي اننا سنتخدم Dictionary فيه الكلمات التي تكررت و Code-Words الخاصة به:

LZ777.JPG

فكلمة Dictionary مكررة أكثر من مرتين،الطريقة الذي اقترحها زيف ولامبل هو أن نقوم بإستبدال التكرار برقم او علامة مميزة (ما نسميه بـCode-Word) بحيث يكون أقل من حجما من التمثيل السابق فمثلا كلمة Dictionary بها

عشر بايتات وبالتالي 80 بت ولضغطها سنقوم بإستبدالها الكلمة المكررة بالرقم 13 و الذي يمثل موقع الكلمة الأولى في الجملة مع عدم الأخذ بعين الإعتبار الفراغات و العلامات المميزة ،وقد عرفت هذه الخوارزمية بـLZ77.

الطريقة الثانية و التي اقترحها نفس الباحثان كانت سنة 1978 وهي طريقة مغايرة عن LZ77 لكنها تبقة مصنفة مع عائلة Dictionary-Compression.

الشيئ الذي يميز هذه الخوارزميات سرعتها ونسبة الضغط المقبولة التي تنتجها وهذا مما ساعد في انتشارها، وكما ذكرنا سابقا انها استعملت في المودمات و الفاكس والكثير من Real Time Systems.

الثورة

لكن ما يميز الخوارزميات التي تعتمد على Statistics و Probabilities هو فعاليتها في جانب الضغط حيث تعطي نتائج باهرة، فبعد تطور الهاردوير وظهور المعالجات القوية لم يعد مشكل الآداء و الموارد مشكلا مستعصيا.

ففي سنة 1976 اقترح R. Pasco and Jorma J. Rissanen طريقة فعالة جدا تقترب من Entropy وتقلل الحجم بشكل ملحوظ ولم يكتفى هذا النوع من تقنيات الضغط بهذا فقط، بل تعدى حتى إلى استعمال نماذج رياضية بارعة مثل Markov Chaines او ما يسمى بـ Finite-Context Models.

وأثناء ذلك ظهر نوع آخر من التقنيات يمكن أن يصنف كنوع يستخدم في كليهما وهو مايسمى بPreprocessor او Transformers حيث يقوم بتحويل البيانات من شكلها الطبيعي إلى شكل يجعلها تحتوي على تكرارت و بالتالي قابلة للضغط،بالطبع فإن عملية Transformation تكون وفق قواعد قابلة للعكس اي Decodable، ومن بينها Move to Front و Burrows–Wheeler transform و Run-Length .

في الآونة الأخير ظهرت تقينات زاوجت بين كفائة Statistical Data Compression وسرعة Dictionary-Based Compression بالإضافة إلى استعمال Models و التي تساعد في تمثيل احسن للمعطيات.ومن بينها الخوارزمية الشهيرة LZMA وهي اختصار لـLempel–Ziv–Markov chain algorithm والمستخدمة في برنامج 7zip وخوارزمية LZP الذي زاوجت بين LZ77 و Finte-Context Model.

مع هذا فإن Data Compression شأنه كشأن كل علم لا ينتهي آخره حتى يبدأ أوله من جديد.

والسلام عليكم ورحمة الله تعالى وبركاته.

____________________________________________________________

المراجع:

كتاب مقدمة إلى نظرية المعلومات الرموز الإشارة و الضجيج للمؤلف جون ر بيرس.

وكيبيديا.

الصورة الثانية من كتاب Text Compression.

تم تعديل بواسطه DATA_SNIPER
4

شارك هذا الرد


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

3 إجابة على هذا السؤال .

  • 0

i don't understand the part of Lossless data compression, plz explain to me

تم تعديل بواسطه Linfo
0

شارك هذا الرد


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

شكرا جزيلا، مقدمه مفيده

0

شارك هذا الرد


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

شكرا على مجهودك اخي الكريم

0

شارك هذا الرد


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

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

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



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

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

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