ضغط البيانات بدون فقدان. خوارزمية هوفمان

ميزة مميزةمعظم أنواع البيانات خاصة بهم وفرة. تعتمد درجة تكرار البيانات على نوع البيانات.
على سبيل المثال، بالنسبة لبيانات الفيديو، تكون درجة التكرار أكبر بعدة مرات من البيانات الرسومية، ودرجة التكرار في البيانات الرسومية، بدورها، أكبر من درجة التكرار في البيانات النصية.

عامل آخر، التأثير على درجة التكرار هو نظام الترميز المعتمد. ومن أمثلة أنظمة الترميز لغات التواصل العادية، وهي ليست أكثر من أنظمة لترميز المفاهيم والأفكار للتعبير عن الأفكار. وبالتالي، فقد ثبت أن تشفير البيانات النصية باستخدام اللغة الروسية يوفر، في المتوسط، تكرارًا بنسبة 20-25٪ أكثر من تشفير البيانات المماثلة باستخدام اللغة الإنجليزية.

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

لو يتم تطبيق أساليب ضغط البيانات على الملفات النهائيةفغالبًا ما يستخدم مصطلح "أرشفة البيانات" بدلاً من مصطلح "ضغط البيانات"، مضغوطيُطلق على إصدار البيانات اسم أرشيف، و برمجةوالتي تطبق أساليب الضغط تسمى أرشيفات.

اعتمادًا على الكائن الذي توجد به البيانات المراد ضغطها، هناك:

· ضغط (أرشفة) الملفات: يستخدم لتقليل حجم الملفات عند إعدادها للإرسال عبر قنوات الاتصال أو للنقل إلى وسائل الإعلام الخارجيةحاوية صغيرة

· ضغط (أرشفة) المجلدات: يستخدم كوسيلة لتقليل حجم المجلدات قبل التخزين طويل الأمد، على سبيل المثال، عندما دعم;

· ضغط (ضغط) الأقراص: يستخدم لزيادة كفاءة استخدام مساحة القرص عن طريق ضغط البيانات عند كتابتها على وسيط تخزين (عادةً باستخدام نظام التشغيل).

هناك العديد من العملية خوارزمياتضغط البيانات، ولكنها كلها تعتمد على ثلاثةالطرق النظرية للحد من تكرار البيانات.

الطريقة الأولى هي يتغيرمحتوى البيانات,

· ثانيا – في التغيير الهياكلبيانات،

· الثالث - في التغيير المتزامنكل من هيكل ومحتوى البيانات.

في حالة حدوث ضغط البيانات يتغيرمحتوياتها إذن طريقة الضغطمُسَمًّى لا رجعة فيه، أي عند استعادة (إلغاء أرشفة) البيانات من الأرشيف، التعافي الكاملمعلومة. غالبا ما تسمى هذه الأساليب طرق الضغط مع فقدان المعلومات الخاضعة للرقابة. من الواضح أنه لا يمكن استخدام هذه الأساليب إلا لأنواع البيانات التي لا يؤدي فقدان جزء من محتواها إلى تشويه كبير للمعلومات. تتضمن هذه الأنواع من البيانات بيانات الفيديو والصوت والرسومات. توفر طرق الضغط التي يتم التحكم فيها بالخسارة نسبة ضغط أعلى بكثير، ولكنها ممنوعتنطبق على بيانات نصية. تتضمن أمثلة تنسيقات الضغط المفقودة ما يلي:

· JPEG - للبيانات الرسومية.

· ميلا في الغالون - لبيانات الفيديو.

· MP3 - للبيانات الصوتية.

إذا حدث ضغط البيانات فقط تغيير في الهيكلبيانات،
الذي - التي طريقة الضغطمُسَمًّى تفريغ. وفي هذه الحالة، من الممكن استعادة المعلومات بالكامل من الأرشيف. يمكن تطبيق أساليب الضغط العكسي على أي نوع من البيانات، لكنها مفيدة أقلنسبة الضغط مقارنة بطرق الضغط التي لا رجعة فيها. أمثلة على تنسيقات الضغط بدون فقدان المعلومات:

· GIF، TIFF - للبيانات الرسومية.

· AVI - لبيانات الفيديو.

· الرمز البريدي، ARJ، RAR، CAB، LH - ل أنواع تعسفيةبيانات.

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

· RLE (تشغيل طول الترميز) خوارزمية.

· خوارزميات مجموعة KWE (ترميز الكلمات الرئيسية).

· خوارزمية هوفمان.

خوارزمية RLE

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

1 1 1 1 2 2 3 4 4 4

تقترح خوارزمية RLE استبدالها بالبنية التالية: 1 4 2 2 3 1 4 3، حيث يكون الرقم الأول من كل زوج من الأرقام هو رمز البيانات، والثاني هو عامل التكرار. إذا تم تخصيص بايت واحد لتخزين كل عنصر بيانات في تسلسل الإدخال، فإن التسلسل بأكمله سيشغل 10 بايت من الذاكرة، بينما سيشغل تسلسل الإخراج (النسخة المضغوطة) 8 بايت من الذاكرة. نسبة الضغط، التي تميز درجة الضغط، يتم حسابها باستخدام الصيغة.

كيف أقلقيمة نسبة الضغط، أكثر فعاليةطريقة الضغط. ومن الواضح أن خوارزمية RLE سوف تعطي أفضل تأثيرالضغط لتسلسلات البيانات المتكررة لفترة أطول. في حالة المثال الذي تمت مناقشته أعلاه، إذا كان تسلسل الإدخال يبدو كما يلي: 1 1 1 1 1 1 3 4 4 4، فستكون نسبة الضغط 60%. في هذا الصدد، يتم تحقيق كفاءة أكبر لخوارزمية RLE عند ضغط البيانات الرسومية (خاصة للصور أحادية اللون).

خوارزميات مجموعة KWE

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

هناك عدد لا بأس به من تطبيقات هذه الخوارزمية، من بينها الأكثر شيوعًا خوارزمية Lempel-Ziv (خوارزمية LZ) وتعديلها، خوارزمية Lempel-Ziv-Welch (خوارزمية LZW). القاموس في هذه الخوارزمية عبارة عن قائمة لا حصر لها من العبارات. تبدأ الخوارزمية بقاموس فارغ تقريبًا يحتوي على سلسلة مشفرة واحدة فقط، تسمى السلسلة NULL. عند قراءة الحرف التالي من تسلسل بيانات الإدخال، تتم إضافته إلى السطر الحالي. وتستمر العملية حتى الخط الحالييطابق بعض العبارات من القاموس. ولكن عاجلاً أم آجلاً يتوقف السطر الحالي عن التوافق مع بعض عبارات القاموس. عند النقطة التي يمثل فيها السطر الحالي آخر تطابق في القاموس بالإضافة إلى حرف الرسالة الذي تمت قراءته للتو، ينتج برنامج التشفير رمزًا يتكون من فهرس التطابق والحرف التالي الذي أدى إلى كسر تطابق السطر. تتم إضافة عبارة جديدة، تتكون من فهرس المطابقة والحرف التالي، إلى القاموس. في المرة التالية التي تظهر فيها هذه العبارة في الرسالة، يمكن استخدامها لإنشاء عبارة أطول، مما يزيد من درجة ضغط المعلومات.

تم إنشاء خوارزمية LZW حول جدول العبارات (القاموس) الذي يستبدل سلاسل الأحرف الخاصة بالرسالة المضغوطة إلى رموز ذات طول ثابت. يحتوي الجدول على ما يسمى بالخاصية المتقدمة، أي لكل عبارة في القاموس تتكون من عبارة معينة w والرمز K، يتم أيضًا إدخال العبارة w في القاموس. إذا تم ملء جميع أجزاء القاموس بالكامل، فسيتوقف التشفير عن التكيف (يحدث التشفير بناءً على العبارات الموجودة بالفعل في القاموس).

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

خوارزمية هوفمان

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

رئيسي فكرةكما يلي: كلما تكرر ظهور الرمز، قل عدد البتات المشفرة فيه. يتم إدخال نتيجة التشفير في القاموس المطلوب لفك التشفير.

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

تشغيل طريقة ترميز الطول

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

مثال. وباستخدام طريقة ترميز طول السلسلة يمكن تمثيل التسلسل: 11111111100000000000000000 – بالشكل التالي: 10.

طريقة الترميز النسبي

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

مثال. باستخدام طريقة الترميز النسبي، يكون تسلسل الأرقام هو: 1476؛ 1473؛ 1480؛ 1477 - يمكن تمثيله بالشكل التالي: 1476؛ -3؛ +7؛ -3.

الترميز المعتمد على التردد

تستخدم طريقة ضغط البيانات هذه تشفيرًا يعتمد على التردد، حيث يتناسب طول نمط البت الذي يمثل عنصر البيانات عكسًا مع تكرار استخدام ذلك العنصر. يتم تضمين هذه الرموز في مجموعة الرموز ذات الطول المتغير، أي. يتم تمثيل عناصر البيانات في هذه الرموز بأنماط بت ذات أطوال مختلفة. إذا أخذنا نصًا إنجليزيًا مشفرًا باستخدام الطريقة المعتمدة على التردد، فسيتم تمثيل الأحرف الأكثر تكرارًا [e, t, a, i] بمجموعات بتات قصيرة، وتلك الأحرف التي تحدث بشكل أقل سيتم تمثيلها بتات أطول مجموعات. والنتيجة هي تمثيل أقصر للنص بأكمله من استخدام التعليمات البرمجية العادية مثل Unicode أو ASCII. يُعزى بناء الخوارزمية المستخدمة بشكل شائع في تطوير الرموز المعتمدة على التردد إلى ديفيد هوفمان، ولهذا السبب غالبًا ما تسمى هذه الرموز برموز هوفمان. معظم الرموز المعتمدة على التردد المستخدمة اليوم هي رموز هوفمان.

مثال. يجب أن يكون مطلوبًا تشفير التسلسل αγααβααγααβαρααβαβαβαβαα باستخدام طريقة تعتمد على التردد، والتي تتكون من أربعة رموز α وβ وγ وα. علاوة على ذلك، في هذا التسلسل، تتكرر α 15 مرة، β - 6 مرات، γ - 2 مرات و lect - 1 مرة.

دعونا نختار، وفقا لطريقة هوفمان، ما يلي الكود الثنائيلتمثيل الشخصيات:

أ - 1
ب - 01
γ - 001
lect - 000

طريقة ليمبل زيف

تمت تسمية هذه الطريقة على اسم مبتكريها، أبراهام ليمبل وجاكوب زيف. تستخدم أنظمة الترميز Lempel-Ziv تقنية ترميز القاموس التكيفي. في في هذا السياقيشير مصطلح القاموس إلى مجموعة من الكتل البرمجية الإنشائية التي يتم إنشاء رسالة مضغوطة منها. إذا تم ضغط النص الإنجليزي، فقد تكون الكتل البرمجية الإنشائية عبارة عن أحرف أبجدية. إذا كنت بحاجة إلى تقليل حجم البيانات المخزنة على جهاز الكمبيوتر الخاص بك، فيمكن أن تصبح الكتل البرمجية الإنشائية أصفارًا وواحدًا. أثناء عملية ترميز القاموس التكيفي، قد يتغير محتوى القاموس. على سبيل المثال، عند ضغط النص الإنجليزي، قد يكون من المفيد إضافة النهاية ing والمقالة the إلى القاموس. في هذه الحالة، يمكن تقليل المساحة التي تشغلها النسخ المستقبلية من النهاية والمقال عن طريق كتابتها كمراجع فردية بدلاً من مجموعة من ثلاثة مراجع مختلفة. تستخدم أنظمة تشفير Lempel-Ziv أساليب متطورة وعالية الكفاءة لتكييف القاموس أثناء عملية التشفير أو الضغط. على وجه الخصوص، في أي لحظة من عملية الترميز، سيتكون القاموس من تلك المجموعات التي تم ترميزها [مضغوطة] بالفعل.

على سبيل المثال، فكر في كيفية ضغط الرسائل باستخدام نظام طريقة Lempel-Ziv معين يُعرف باسم LZ77. تبدأ العملية بإعادة كتابة الجزء الأول من الرسالة عمليًا، ولكن في لحظة معينةيتم الانتقال إلى تمثيل الأجزاء المستقبلية باستخدام ثلاثة توائم، يتكون كل منها من عددين صحيحين متبوعين بحرف واحد من النص. يصف كل ثلاثي كيفية بناء الجزء التالي من الرسالة. على سبيل المثال، اجعل النص الذي تم فك حزمته يبدو كما يلي:

αβααβλβ

السلسلة αβααβлβ هي الجزء الذي تم فك حزمه بالفعل من الرسالة. لفك ضغط بقية نص الرسالة، يجب عليك أولاً توسيع السطر عن طريق إلحاق الجزء الذي يظهر فيه بالفعل. يشير الرقم الأول في الثلاثي إلى عدد الأحرف التي يجب عدها بشكل عكسي في السلسلة للعثور على الحرف الأول من المقطع المراد إضافته. في هذه الحالة، من الضروري عد 5 أحرف، وسوف نصل إلى الحرف الثاني من يسار السلسلة التي تم تفكيكها بالفعل. يحدد الرقم الثاني في الثلاثي عدد الأحرف المتتالية الموجودة على يمين الحرف الأولي التي تشكل المقطع المراد إضافته. في مثالنا هذا الرقم هو 4، وهذا يعني أن القطعة المراد إضافتها ستكون ααβл. نقوم بنسخه إلى نهاية السطر ونحصل على القيمة الجديدة للجزء غير المعبأ من الرسالة: αβααβlectβαβα.

أخيراً، العنصر الأخير[في حالتنا، هذا هو الحرف α] يجب وضعه في نهاية السلسلة الموسعة، مما يؤدي إلى ظهور رسالة غير مضغوطة بالكامل: αβααβlectααβα.

ضغط الصورة

التنسيق النقطي المستخدم في الحديث المحولات الرقميةالصور، تتضمن ترميز الصور بتنسيق ثلاث بايت لكل بكسل، مما يؤدي إلى إنشاء صور ضخمة وغير مريحة للاستخدام الملفات النقطية. تم تطوير العديد من أنظمة الضغط خصيصًا لهذا التنسيق، وهي مصممة لتقليل المساحة التي تشغلها هذه الملفات على القرص. أحد هذه المخططات هو تنسيق GIF، تم تطويره بواسطة CompuServe. والطريقة التي تستخدمها هي تقليل عدد ألوان البكسل إلى 256، بحيث يمكن تمثيل لون كل بكسل ببايت واحد بدلاً من ثلاثة. باستخدام جدول يسمى لوحة الألوان، يرتبط كل لون من ألوان البكسل الصالحة ببعض مجموعات الألوان الأحمر والأخضر والأزرق. من خلال تغيير اللوحة المستخدمة، يمكنك تغيير الألوان التي تظهر في الصورة.

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

مثال آخر لنظام ضغط الصور هو تنسيق JPEG. هذا معيار تم تطويره من قبل مجموعة خبراء التصوير المشترك [ومن هنا اسم هذا المعيار] داخل منظمة ISO. أثبت تنسيق JPEG أنه وسيلة فعالة لعرض الصور الفوتوغرافية الملونة. بالضبط لهذا السبب هذا المعيارالمستخدمة من قبل الشركات المصنعة للكاميرات الرقمية الحديثة. ومن المتوقع أن يكون له تأثير كبير على مجال التصوير الرقمي في المستقبل.

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

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

والسبب في هذا التمييز بين اللون والسطوع هو أن العين البشرية أكثر حساسية للتغيرات في السطوع من الألوان. لنأخذ على سبيل المثال مستطيلين أزرقين موحدي اللون ومتطابقين تمامًا باستثناء أن أحدهما يحتوي على نقطة مضيئة صغيرة، بينما يحتوي الآخر على نقطة خضراء صغيرة بنفس سطوع الخلفية الزرقاء. سيكون من الأسهل على العين اكتشاف نقطة مضيئة بدلاً من النقطة الخضراء. يستغل الوضع "الأساسي" لمعيار JPEG هذه الميزة عن طريق تشفير مكون النصوع لكل بكسل، ولكن مع حساب متوسط ​​مكونات اللون عبر كتل مكونة من أربعة بكسلات وتسجيل مكونات اللون لتلك الكتل فقط. ونتيجة لذلك، يحتفظ تمثيل الصورة النهائية بالتغيرات المفاجئة في السطوع، لكنه يترك التغييرات المفاجئة في اللون غير واضحة. وميزة هذا المخطط هي أن كل كتلة مكونة من أربعة بكسلات يتم تمثيلها بستة قيم فقط [أربعة نصوع ولونان]، بدلاً من الاثني عشر التي يتطلبها نظام ثلاثة لكل بكسل.

النظرية والاستراتيجية لعرض البيانات

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

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

ما المقصود بضغط البيانات؟ باختصار، يزيل الضغط وفرة; ومن حيث نظرية المعلومات، فإن الضغط يزيد من إنتروبيا النص المضغوط. ومع ذلك، فإن كلا هذين البيانين صحيحان بشكل أساسي بحكم تعريف المفاهيم نفسها. يمكن التعبير عن التكرار بأشكال عديدة ومختلفة. النوع الأول هو سلسلة من البتات المتكررة (11111111). والثاني هو سلسلة من البايتات المتكررة (XXXXXXXXX). ومع ذلك، في كثير من الأحيان يتجلى التكرار في المزيد على نطاق واسعويتم التعبير عنها إما عن طريق أنماط في مجموعة بيانات مأخوذة ككل، أو عن طريق تسلسلات ذات أطوال مختلفة لها سمات مشتركة. بشكل أساسي، الهدف من ضغط البيانات هو إيجاد تحويلات خوارزمية لتمثيلات البيانات التي ستنتج تمثيلات أكثر إحكاما لمجموعات البيانات "النموذجية". قد يبدو هذا الوصف غامضًا إلى حد ما، لكننا سنحاول الكشف عن جوهره باستخدام الأمثلة العملية.

ضغط ضياع وضياع

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

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

مجموعة بيانات العينة

ستستخدم هذه المقالة تمثيلًا افتراضيًا مُعدًا خصيصًا للبيانات. دعونا نعطي مثالا سهل الفهم. بادئات أرقام الهاتف المستخدمة في جرينفيلد، ماساتشوستس، الولايات المتحدة الأمريكية هي 772- و773- و774-. (ملاحظة للقراء خارج الولايات المتحدة: في الولايات المتحدة، تتكون أرقام الهاتف المحلية من سبعة أرقام ويتم تمثيلها تقليديًا بالرمز ###-####؛ ويتم تعيين البادئات وفقًا للموقع الجغرافي.) لنفترض أيضًا أنه من بين البادئات الثلاث، يتم استخدام البادئة الأولى في أغلب الأحيان. يمكن أن تكون أجزاء اللاحقة أي أرقام أخرى ذات احتمالية متساوية تقريبًا. مجموعة البيانات التي نهتم بها موجودة في "قائمة جميع أرقام الهواتف المستخدمة حاليًا". يمكنك محاولة العثور على سبب يجعل هذا مثيرًا للاهتمام من وجهة نظر البرمجة، ولكن في هذه الحالة ليس مهمًا.

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

الجدول 1. تقرير متعدد الأعمدة

============================================================= 772-7628 772-8601 772-0113 773-3429 774-9833 773-4319 774-3920 772-0893 772-9934 773-8923 773-1134 772-4930 772-9390 774-9992 772-2314 [...]

ضغط المساحات الفارغة

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

في حالة المثال المقدم، يمكن إزالة جزء صغير فقط من المعلومات من التقرير الموصوف. لا يحمل سطر الرموز "=" الموجود على طول الحافة العلوية للتقرير أي محتوى وظيفي؛ وينطبق الشيء نفسه على الأحرف "-" في الأرقام والمسافات بين الأرقام. كل هذا مفيد لمن يقرأ التقرير الأصلي، لكن ليس له أي معنى إذا اعتبرنا هذه الأحرف بمثابة "بيانات". ما نقوم بإزالته ليس بالضبط "مساحة فارغة" بالمعنى التقليدي، ولكنه في الأساس كذلك.

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

ترميز المجموعة

يعد ترميز المجموعة (RLE) أبسط طرق الضغط غير المفقودة شائعة الاستخدام. مثل ضغط المسافات البيضاء، فهو غير مكلف، خاصة لفك التشفير. الفكرة وراء هذه الطريقة هي أن العديد من تمثيلات البيانات تتكون في الغالب من سلاسل من البايتات المتكررة. يعد تقريرنا النموذجي أحد طرق عرض البيانات هذه. يبدأ بسلسلة من الأحرف "=" المتكررة ويحتوي على أسطر من المسافات فقط متناثرة في جميع أنحاء التقرير. بدلاً من تمثيل كل حرف بالبايت الخاص به، تتضمن طريقة RLE (أحيانًا أو دائمًا) تحديد عدد التكرارات، متبوعًا بالحرف الذي سيتم تشغيله هذا العدد من المرات.

إذا كان تنسيق البيانات الجاري معالجته يهيمن عليه البايتات المتكررة، فقد يكون من المناسب القيام بذلك الاستخدام الفعالخوارزمية تشير فيها بايتة واحدة أو أكثر إلى عدد التكرارات، متبوعة بالحرف المراد تكراره. ومع ذلك، إذا كان لديك سلاسل أحرف بطول الوحدة، فسوف يستغرق الأمر بايتين (أو أكثر) لترميزها. بمعنى آخر، قد يتطلب حرف ASCII "X" من تدفق الإدخال تدفق بتات إخراج يبلغ 00000001 01011000 . من ناحية أخرى، فإن تشفير مائة حرف "X" متتالي سيستخدم نفس عدد البتات: 01100100 01011000، وهو أمر فعال للغاية.

غالبًا ما تستخدم المتغيرات المختلفة لـ RLE البايتات بشكل انتقائي للإشارة إلى عدد التكرارات، بينما تمثل البايتات المتبقية نفسها ببساطة. ولهذا الغرض، يجب حجز قيمة بايت واحدة على الأقل، والتي يمكن إزالتها من الإخراج إذا لزم الأمر. على سبيل المثال، في نموذج تقرير رقم الهاتف الخاص بنا، نعلم أن جميع المعلومات الموجودة في تدفق الإدخال تتكون من معلومات بسيطة أحرف ASCII. على وجه الخصوص، كل هذه الأحرف لها البت الأول من قيمة ASCII يساوي 0. يمكننا استخدام بت ASCII الأول للإشارة إلى أن البايت يشير إلى عدد التكرارات بدلاً من الحرف العادي. يمكن استخدام البتات السبعة التالية من بايت المكرر للإشارة إلى عدد التكرارات، ويمكن أن تحتوي البايتة التالية على الحرف الذي يتم تكراره. لذلك، على سبيل المثال، يمكننا تمثيل السلسلة "YXXXXXXXXX" على النحو التالي:

"ص" ايتر(8) "س" 01001111 10001000 01011000

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

ترميز هوفمان

يعامل ترميز هوفمان جدول الرموز كمجموعة كاملة من البيانات. يتم الضغط من خلال إيجاد "أوزان" كل حرف في مجموعة البيانات. يتم استخدام بعض الأحرف أكثر من غيرها، لذا يفترض تشفير هوفمان أنه يجب تشفير الأحرف المتكررة بعدد بتات أقل من الأحرف الأقل شيوعًا. يخرج خيارات مختلفةترميز هوفمان، لكن النسخة الأصلية (والأكثر استخدامًا) تتضمن العثور على الحرف الأكثر شيوعًا وترميزه ببت واحد، على سبيل المثال، 1. وإذا حدث 0 في التسلسل المشفر، فهذا يعني أن هناك حرفًا آخر مشفرًا في ذلك المكان كمية كبيرةقليل.

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

الجدول 2. نتائج الترميز هوفمان

رمز الترميز 1 7 010 2 011 3 00000 4 00001 5 00010 6 00011 8 00100 9 00101 0 00111 1

يمكن تشفير مجموعة الأحرف الأصلية (التي تتكون من أرقام) بسهولة (بدون ضغط) على شكل تسلسلات ذات 4 بتات (يقضم). سيستخدم ترميز هوفمان التالي ما يصل إلى 5 بتات للأحرف في أسوأ الحالات، وهو ما يعد بوضوح أسوأ من تشفير nibble. ومع ذلك، في أفضل الأحوال، كل ما هو مطلوب هو 1 قليل؛ ومن المعروف أنها أفضل حالة سيتم استخدامها في أغلب الأحيان (نظرًا لأن هذا هو الرمز الذي يظهر غالبًا في البيانات). لذلك يمكننا تشفير رقم هاتف محدد مثل هذا:

772 7628 --> 1 1 010 1 00010 010 00011

عندما يتم ترميزها باستخدام nibbles، يتم تمثيلها رقم التليفونسيستغرق 28 بت، وفي حالتنا يستغرق التشفير 19 بت. تتم إضافة المسافات في المثال فقط من أجل فهم أفضل؛ ليس من الضروري وجودها في الرموز المشفرة، لأنه من الممكن دائمًا التحديد من جدول الرموز ما إذا كان قد تم الوصول إلى نهاية الرمز المشفر أم لا (ومع ذلك، لا يزال من الضروري تتبع الموضع الحالي في البيانات ).

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

الضغط باستخدام خوارزمية Lempel-Ziv

ربما تكون طريقة الضغط غير المفقودة الأكثر أهمية هي خوارزمية Lempel-Ziv. في هذه المقالة سنتحدثحول متغير LZ78، لكن LZ77 والمتغيرات الأخرى تعمل بطريقة مماثلة. الفكرة وراء خوارزمية LZ78 هي تشفير سلسلة من البايتات باستخدام جدول ديناميكي. في بداية ضغط تدفق البتات، يتم ملء جدول LZ بمجموعة الأحرف الفعلية، بالإضافة إلى بعض الفتحات الفارغة. تستخدم الخوارزمية الجداول مقاسات مختلفةولكن في هذا المثال مع أرقام الهواتف (مع ضغط المساحة الفارغة) يتم استخدام جدول مكون من 32 عنصرًا (يكفي لـ هذا المثال، ولكنها قد لا تكون كافية لأنواع البيانات الأخرى). أولاً، نقوم بملء الخانات العشرة الأولى بأحرف الأبجدية المستخدمة (الأرقام). عند وصول بايتات جديدة، يتم أولاً استرداد قيمة الجدول المقابلة لأطول تسلسل مطابق، ثم تتم كتابة تسلسل الطول N+1 إلى الفتحة التالية المتاحة. في أسوأ الحالات، نستخدم 5 بتات بدلاً من 4 لحرف واحد، لكن في معظم الحالات يمكننا استخدام 5 بتات لعدة أحرف. دعونا نلقي نظرة على مثال لكيفية عمل هذه الخوارزمية (يُشار إلى فتحة الجدول في أقواس مربعة):

7 --> بحث: تم العثور على 7 --> لا شيء لإضافته --> مواصلة البحث 7 --> بحث: 77 لم يتم العثور عليه --> إضافة "77" إلى --> عرض =00111 2 --> بحث: 72 ليس تم العثور عليه --> إضافة "72" إلى --> عرض =00111 7 --> بحث: 27 غير موجود --> إضافة "27" إلى --> عرض =00010 6 --> بحث: 76 غير موجود --> أضف "76" إلى --> عرض =00111 2 --> بحث: لم يتم العثور على 62 --> أضف "62" إلى --> عرض =00110 8 --> بحث: لم يتم العثور على 28 --> أضف "28" إلى --> الإخراج =00010

لم نحصل على أي فائدة من هذا حتى الآن، ولكن دعونا ننتقل إلى رقم الهاتف التالي:

7 --> بحث: 87 لم يتم العثور عليه --> إضافة "87 إلى --> عرض =00100 7 --> بحث: تم العثور على 77 --> لا شيء لإضافته --> مواصلة البحث 2 --> بحث: 772 غير موجود - -> إضافة "772" إلى --> الإخراج =01011 8 --> البحث: تم العثور على 28 --> لا يوجد شيء لإضافته --> مواصلة البحث 6 --> البحث: لم يتم العثور على 286 --> إضافة "286" إلى --> الناتج = 10000 ....

يجب أن تكون العمليات المذكورة أعلاه كافية لتوضيح تشغيل النموذج. على الرغم من أنه لم يتم تحقيق ضغط ملحوظ حتى الآن، إلا أنه يمكن ملاحظة أننا قمنا بإعادة استخدام الفتحتين 11 و16، وترميز رمزين لكل منهما برمز إخراج واحد. بالإضافة إلى ذلك، قمنا بالفعل بتجميع تسلسل مفيد للغاية من البايتات 772 في الفتحة 18، ​​والذي سيظهر لاحقًا بشكل متكرر في الدفق.

تملأ خوارزمية LZ78 جدول رموز واحدًا بإدخالات مفيدة (من المفترض)، ثم تكتب هذا الجدول، وتمسحه، وتبدأ بجدول جديد. في مثل هذه الحالة، قد لا يكون الجدول المكون من 32 حرفًا كافيًا، حيث سيتم مسحه قبل أن نتمكن من استخدام تسلسلات بشكل متكرر مثل 772 وما شابه. ومع ذلك، بمساعدة جدول صغير، يكون من الأسهل توضيح عمل الخوارزمية.

في مجموعات البيانات النموذجية، تحقق الأشكال المختلفة لطريقة Lempel-Ziv إنجازات أكبر بكثير احتمالات عاليةالضغط من أساليب هوفمان و RLE. من ناحية أخرى، تنفق متغيرات طريقة Lempel-Ziv موارد كبيرة على التكرارات، ويمكن أن تشغل جداولها مساحة كبيرة من الذاكرة. تستخدم معظم أدوات الضغط والمكتبات الموجودة مزيجًا من أساليب Lempel-Ziv وHuffman.

بيان المشكلة الصحيح

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

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

يعد هذا الحل المستند إلى الصورة النقطية مثاليًا من جميع وجهات النظر. يتطلب بالضبط 3750 بايت لتمثيل مجموعة البيانات؛ أساليب مختلفةستستخدم عمليات الضغط حجمًا متفاوتًا اعتمادًا على عدد أرقام الهاتف الموجودة في الاتصال وكفاءة الضغط. ومع ذلك، إذا كان 10000 من 30000 رقم هاتف محتمل نشطًا، وحتى إذا كنت طريقة فعالةيتطلب الضغط عدة بايتات لكل رقم هاتف، ومن ثم تفوز الصورة النقطية بالتأكيد. فيما يتعلق بمتطلبات وحدة المعالجة المركزية، فإن الصورة النقطية ليست فقط متفوقة على أي من طرق الضغط التي تمت مناقشتها، ولكنها أيضًا أفضل منها الطريقة العاديةتمثيل أرقام الهاتف كسلاسل (بدون ضغط). يمكن إجراء اجتياز الصورة النقطية وزيادة عداد رقم الهاتف الحالي بكفاءة حتى في ذاكرة التخزين المؤقت المدمجة للمعالجات الحديثة.

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

مخصص لذكرى كلود شانون.

مبادئ ضغط المعلومات

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

تتضمن أي طريقة لضغط المعلومات تحويلين عكسيين:

• تحويل الضغط
• تحويل الضغط.

يضمن تحويل الضغط الحصول على رسالة مضغوطة من الرسالة الأصلية. يضمن إلغاء الضغط الحصول على الرسالة الأصلية (أو تقريبها) من الرسالة المضغوطة.

تنقسم جميع طرق الضغط إلى فئتين رئيسيتين

• دون خسارة،
• مع الخسائر.

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

خصائص خوارزميات الضغط وقابلية التطبيق

نسبة الضغط

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

ك = سس/ سج،

أين ك- نسبة الضغط، س o هو حجم البيانات غير المضغوطة، و سج - الحجم المضغوط . وبالتالي، كلما ارتفعت نسبة الضغط، كانت الخوارزمية أفضل. يجب ملاحظة ذلك:

• لو ك= 1، فإن الخوارزمية لا تقوم بالضغط، أي أنها تتلقى رسالة إخراج بحجم يساوي حجم الإدخال؛
• لو ك < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

الوضع مع ك < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной نالنمط: E: بت هو بالضبط 2 ن. ثم عدد الرسائل المختلفة التي يقل طولها عن أو يساوي ن(إذا كان هناك رسالة واحدة على الأقل ذات طول أقصر) ستكون أقل من 2 ن. وهذا يعني أنه من المستحيل تعيين كافة الرسائل الأصلية بشكل فريد إلى رسالة مضغوطة: إما أن بعض الرسائل الأصلية لن تحتوي على تمثيل مضغوط، أو أن العديد من الرسائل الأصلية سيكون لها نفس التمثيل المضغوط وبالتالي لا يمكن تمييزها.

يمكن أن تكون نسبة الضغط إما معاملًا ثابتًا (بعض الخوارزميات لضغط الصوت والصورة وما إلى ذلك، على سبيل المثال قانون A، قانون μ، ADPCM)، أو متغيرًا. وفي الحالة الثانية يمكن تعريفه إما لأي رسالة محددةأو يتم تقييمها وفق بعض المعايير:

• متوسط ​​(عادةً عبر بعض مجموعات بيانات الاختبار)؛
• الحد الأقصى (حالة أفضل ضغط)؛
• الحد الأدنى (حالة أسوأ ضغط)؛

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

التسامح مع الخسائر

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

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

ومع ذلك، يسمح الضغط مع فقدان البيانات بنسب ضغط أعلى بكثير من خلال التخلص من المعلومات غير ذات الصلة التي لا يتم ضغطها بشكل جيد. لذلك، على سبيل المثال، تسمح لك خوارزمية ضغط الصوت بدون فقدان FLAC، في معظم الحالات، بضغط الصوت بمقدار 1.5-2.5 مرة، في حين أن خوارزمية Vorbis، اعتمادًا على معلمة الجودة المحددة، يمكنها ضغط ما يصل إلى 15 مرة مع الحفاظ على جودة صوت مقبولة .

متطلبات نظام الخوارزمية

قد تتطلب خوارزميات مختلفة كميات مختلفةموارد نظام الحوسبة، والتي يتم تنفيذها:

• ذاكرة الوصول العشوائي (للبيانات المتوسطة)؛
• الذاكرة الدائمة (لكود البرنامج والثوابت)؛
• وقت وحدة المعالجة المركزية.

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

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

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

أنظر أيضا

مؤسسة ويكيميديا. 2010.

تعرف على معنى "ضغط المعلومات" في القواميس الأخرى:

ضغط المعلومات- ضغط المعلومات - [إل جي سومينكو. قاموس إنجليزي روسي في مجال تكنولوجيا المعلومات. م: مؤسسة الدولة TsNIIS، 2003.] المواضيع تكنولوجيا المعلوماتبشكل عام مرادفات تقليل المعلومات EN تقليل المعلومات ...

ضغط المعلومات- (ضغط البيانات) تمثيل المعلومات (البيانات) بعدد أقل من البتات مقارنة بالأصل. على أساس القضاء على التكرار. هناك S. و. دون فقدان المعلومات ومع فقدان بعض المعلومات غير الضرورية للمهام التي يتم حلها. ل… … القاموس الموسوعي لعلم النفس والتربية

ضغط المعلومات التكيفي بدون فقدان- - [إل جي سومينكو. قاموس إنجليزي روسي في مجال تكنولوجيا المعلومات. M.: State Enterprise TsNIIS, 2003.] موضوعات تكنولوجيا المعلومات بشكل عام EN ضغط البيانات التكيفي بدون فقدان ALDC ... دليل المترجم الفني

ضغط / ضغط المعلومات- - [إل جي سومينكو. قاموس إنجليزي روسي في مجال تكنولوجيا المعلومات. M.: State Enterprise TsNIIS, 2003.] موضوعات تكنولوجيا المعلومات بشكل عام EN الضغط ... دليل المترجم الفني

ضغط المعلومات الرقمية- - [إل جي سومينكو. قاموس إنجليزي روسي في مجال تكنولوجيا المعلومات. M.: State Enterprise TsNIIS, 2003.] موضوعات تكنولوجيا المعلومات بشكل عام ضغط EN ... دليل المترجم الفني

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

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

ضغط المعلومات الخرائطية الرقمية- معالجة المعلومات الخرائطية الرقمية من أجل تقليل حجمها، بما في ذلك إزالة التكرار ضمن الدقة المطلوبة في عرضها. [GOST 28441 99] موضوعات رسم الخرائط الرقمية مصطلحات عامة الأساليب والتقنيات... ... دليل المترجم الفني

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

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

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

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

رموز البادئة

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

رمز البادئة هو رمز لا توجد فيه كلمة مشفرة هي بداية كلمة مشفرة أخرى.

اقترح شانون وفانو خوارزمية لبناء رموز ضغط متغيرة الطول (خوارزمية شانون-فانو). ومع ذلك، في بعض الحالات، أعطت الخوارزمية حلاً دون المستوى الأمثل.

كود هوفمان

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

دعونا نبني كود هوفمان للنص "بالقرب من الجرس"

1. نقوم ببناء قائمة بالعقد المجانية، مرتبة بترتيب تنازلي لتكرار ظهور الحرف.
2. دعونا نختار الحرفين الأقل احتمالاً ونبني لهما عقدة سلف ("حرف زائف") بتردد يساوي مجموع ترددات العقد التابعة.
3. نخصص 1 للحرف الأقل احتمالًا، و0 للحرف الأكثر احتمالًا (في المسار التالي نتبع ترتيب وضع 0 و1).
4. نقوم بإزالة كلا الحرفين من القائمة، وترك عقدة أسلافهم.
5. نكرر الخطوات بدءاً من النقطة رقم 2 حتى تبقى عقدة واحدة ("الحرف المعدني"). سيتم اعتبار هذه العقدة جذر الشجرة.

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

• س – 00
• ك – 01
• ل – 10
• الفضاء – 110
• أ - 111