2.3 من 5 (13 صوت)

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

http://i-infected.com

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



صورة 1-تمثيل توضيحي لشفرة مورس [1]

أن هذا التمثيل المتماسك أعطى دفعة قوية لنظرية المعلومات ومثل قفزة نوعية في ذلك الوقت،لكن ميكانيزم التمثيل الأقصر (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) و الذي كان له تأثير كبير في مجال ضغط البيانات خاصة ضغط البيانات دون ضياع (Lossless Compression) حيث تعبر الأنتروبيا عن القيمية الحقيقية او الدنيا الذي يمكن أن تسند لترميز ما.

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

“The art of representing Data in Compact Form”

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

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

الإكتشاف
__________________________________________________

في سنة 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 Occurren) ليحديد إلى من يسند الترميز الأقصر.

وكان بعده وقبله ممن اسسوا لهذا العلم ومنهم (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) وكان من البداهة بمكان، مما جعله ينتشر بكثرة ويستعمل في انظمة الفاكس و المودمات.

إن هذا المفهوم منتشر ومعروف ولا يحتاج لشرح فأنت مثلا عوض أن تكتب التاريخ “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 الخاصة به:



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

فكلمة 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 شأنه كشأن كل علم لا ينتهي آخره حتى يبدأ أوله من جديد.

مراجع
__________________________________________________

[1] Wikipedia, Morse_code, [Online document], 09 June 2011, Available at: http://en.wikipedia.org/wiki/Morse_code.

[2] Bell, T. C., Cleary, J. G., AND Witten, I. H. Text Compression, Prentice Hall, Upper Sadle River, NJ, 1990.

[3] John R.Pierce,An introduction to Information theory :symbols,Signals and Noise, ترجمة فايز فوق العادة, 1990.

للإستزادة يمكنك مراجعة كتاب An introduction to Information theory :symbols,Signals and Noise ولذي تم ترجمته للعربية تحت عنوان:

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