ضغط بدون فقدان للبيانات

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

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

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

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

يُستخدم ضغط البيانات بدون فقدان في العديد من التطبيقات. على سبيل المثال، يُستخدم في تنسيق ملف ZIP وفي أداة GNU gzip . كما يُستخدم غالبًا كمكون ضمن تقنيات ضغط البيانات مع فقدان (مثل المعالجة المسبقة الاستريو المشترك بين المسارين الأوسط والجانبي بدون فقدان بواسطة مُشفِّرات MP3 وغيرها من مُشفِّرات الصوت مع فقدان). [ 2 ]

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

التقنيات

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

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

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

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

الوسائط المتعددة

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

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

تُطبَّق العديد من هذه الأساليب في أدوات مفتوحة المصدر وأخرى احتكارية، لا سيما خوارزمية LZW ومشتقاتها. بعض الخوارزميات مسجلة ببراءات اختراع في الولايات المتحدة ودول أخرى، ويتطلب استخدامها القانوني ترخيصًا من صاحب براءة الاختراع. ونظرًا لبراءات الاختراع الخاصة بأنواع معينة من ضغط LZW ، ولا سيما ممارسات الترخيص التي تتبعها شركة Unisys، صاحبة براءة الاختراع، والتي اعتبرها العديد من المطورين تعسفية، شجع بعض مؤيدي المصادر المفتوحة على تجنب استخدام تنسيق تبادل الرسومات (GIF) لضغط ملفات الصور الثابتة، لصالح تنسيق رسومات الشبكة المحمولة (PNG)، الذي يجمع بين خوارزمية deflate القائمة على LZ77 ومجموعة مختارة من مرشحات التنبؤ الخاصة بكل مجال. مع ذلك، انتهت صلاحية براءات اختراع LZW في 20 يونيو 2003. [ 4 ]

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

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

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

طُرق

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

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

إعلان عام

صوتي

رسومات نقطية

الرسومات ثلاثية الأبعاد

  • OpenCTM – ضغط بدون فقدان لشبكات المثلثات ثلاثية الأبعاد

فيديو

اطلع على قائمة برامج ترميز الفيديو بدون فقدان للجودة

علم التشفير

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

علم الوراثة وعلم الجينوم

خوارزميات الضغط الجيني (لا ينبغي الخلط بينها وبين الخوارزميات الجينية ) هي أحدث جيل من الخوارزميات غير الفاقدة للبيانات، والتي تضغط البيانات (عادةً تسلسلات النيوكليوتيدات) باستخدام كلٍ من خوارزميات الضغط التقليدية وخوارزميات مُخصصة للبيانات الجينية. في عام 2012، نشر فريق من العلماء من جامعة جونز هوبكنز أول خوارزمية ضغط جيني لا تعتمد على قواعد بيانات جينية خارجية. صُممت خوارزمية HAPZIPPER خصيصًا لبيانات HapMap ، وتحقق ضغطًا يزيد عن 20 ضعفًا (انخفاض بنسبة 95% في حجم الملف)، مما يوفر ضغطًا أفضل بمقدار 2 إلى 4 أضعاف وبسرعة أكبر بكثير من برامج الضغط العامة الرائدة. [ 10 ]

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

الملفات التنفيذية

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

المعايير

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

يسرد مات ماهوني ، في طبعة فبراير 2010 من الكتيب المجاني " شرح ضغط البيانات" ، ما يلي أيضًا: [ 12 ]

  • لم يعد يُستخدم على نطاق واسع سجل كالجاري الذي يعود تاريخه إلى عام 1987 نظرًا لصغر حجمه. وقد أشرف مات ماهوني على تحدي كالجاري للضغط، الذي أنشأه وأشرف عليه ليونيد أ. بروخيس في الفترة من 21 مايو 1996 إلى 21 مايو 2016.
  • يستخدم كل من معيار ضغط النصوص الكبيرة وجائزة هوتر المماثلة مجموعة بيانات ويكيبيديا XML UTF-8 المقتطعة .
  • يختبر معيار الضغط العام ، الذي يديره مات ماهوني، ضغط البيانات التي تولدها آلات تورينج العشوائية .
  • قام سامي رونساس (مطور برنامج NanoZip) بتطوير برنامج Compression Ratings، وهو معيار مشابه لاختبار Maximum Compression متعدد الملفات، ولكن مع متطلبات سرعة دنيا. وقد وفر البرنامج حاسبة تُمكّن المستخدم من تحديد أهمية السرعة ونسبة الضغط. وتفاوتت البرامج الرائدة بشكل ملحوظ بسبب متطلبات السرعة. في يناير 2010، كان برنامج NanoZip هو البرنامج الرائد، يليه FreeArc ، ثم CCM ، ثم flashzip ، وأخيراً 7-Zip .
  • اختبرت أداة "وحش الضغط" التي طورتها نانيا فرانشيسكو أنطونيو ضغط 1 جيجابايت من البيانات العامة ضمن مهلة زمنية مدتها 40 دقيقة. في ديسمبر 2009، كان برنامج NanoZip 0.07a هو الأفضل في مجال الأرشفة، بينما كان برنامج ccmx 1.30c هو الأفضل في مجال ضغط الملفات الفردية.

نشر موقع Compression Ratings الإلكتروني ملخصًا بيانيًا لـ "الحدود" في نسبة الضغط والوقت. [ 13 ]

سيليزيا كوربوس

مجموعة سيليزيا هي مجموعة من الملفات أُنشئت عام ٢٠٠٣ كبديل لمجموعتي كانتربري وكالجاري ، وذلك بسبب مخاوف بشأن مدى تمثيلهما للملفات الحديثة. تحتوي هذه المجموعة على أنواع بيانات متنوعة، بما في ذلك مستندات نصية كبيرة، وملفات تنفيذية، وقواعد بيانات. [ ١٤ ] وهي تُستخدم على نطاق واسع في أبحاث ضغط البيانات. [ ١٥ ]

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

نظرة عامة على الملفات وأحجامها وأوصافها وأنواع بياناتها
ملفالمقاس (ب)وصفنوع البيانات
ديكنز10192446أعمال تشارلز ديكنزنص إنجليزي
موزيلا51220480ملفات تنفيذية لموزيلا 1.0ملف تنفيذي
السيد9970564صور الرنين المغناطيسيصورة ثلاثية الأبعاد
المعهد الوطني للسرطان33553445قاعدة بيانات للهياكل الكيميائيةقاعدة البيانات
مكتب6152192مكتبة مشتركة من أوبن أوفيسملف تنفيذي
osdb10085684قاعدة بيانات MySQL نموذجية من معيار قواعد البيانات مفتوحة المصدرقاعدة البيانات
ريمونت6625583نص كتاب Chłopi للكاتب Władysław Reymontملف PDF باللغة البولندية
سامبا21606400شفرة المصدر لـ Samba  2-2.3ملف تنفيذي
ساو7251944كتالوج نجوم SAOقاعدة بيانات ثنائية
ويبستر41458703قاموس ويبستر غير المختصر لعام 1913HTML
ملف XML5345280ملفات XML المجمعةXML
الأشعة السينية8474240صورة أشعة سينية طبيةصورة
المجموع211938580

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

القيود

لا تضمن خوارزميات ضغط البيانات غير الفاقد للبيانات ضغط جميع مجموعات البيانات المدخلة. بعبارة أخرى، في أي خوارزمية ضغط بيانات غير فاقد للبيانات، ستكون هناك مجموعة بيانات مدخلة لا يقل حجمها عند معالجتها بواسطة الخوارزمية، وفي أي خوارزمية ضغط بيانات غير فاقد للبيانات تُصغّر حجم ملف واحد على الأقل، سيكون هناك ملف واحد على الأقل يزيد حجمه. يمكن إثبات ذلك بسهولة باستخدام الرياضيات الأساسية من خلال مبدأ التوزيع ، كما يلي: [ 17 ] [ 18 ]

  • افترض أن كل ملف يتم تمثيله كسلسلة من البتات ذات طول عشوائي.
  • لنفترض أن هناك خوارزمية ضغط تحول كل ملف إلى ملف إخراج لا يزيد طوله عن الملف الأصلي، وأن ملفًا واحدًا على الأقل سيتم ضغطه إلى ملف إخراج أقصر من الملف الأصلي.
  • ليكن M أصغر عدد بحيث يوجد ملف F بطول M بت يمكن ضغطه إلى ملف أقصر. وليكن N طول النسخة المضغوطة من F (بالبت) .
  • بما أن N < M ، فإن كل ملف بطول N يحتفظ بحجمه أثناء الضغط. يوجد 2^ N ملفًا ممكنًا من هذا النوع. بالإضافة إلى F ، ينتج عن ذلك 2 ^N + 1 ملفًا يتم ضغطها جميعًا في واحد من 2^ N ملفًا بطول N.
  • لكن 2N أصغر من 2N +1، لذا وفقًا لمبدأ التوزيع، لا بد من وجود ملف بطول N يُمثل في الوقت نفسه ناتج دالة الضغط على مدخلين مختلفين. لا يمكن فك ضغط هذا الملف بشكل موثوق (أيّ الملفين الأصليين يجب أن ينتج؟)، وهو ما يتناقض مع افتراض أن الخوارزمية لا تُفقد أي بيانات.
  • لذلك يجب أن نستنتج أن فرضيتنا الأصلية (أن وظيفة الضغط لا تجعل الملف أطول) غير صحيحة بالضرورة.

تُوفّر معظم خوارزميات الضغط العملية آلية "الخروج" التي تُتيح تعطيل الترميز العادي للملفات التي يزداد حجمها نتيجةً للترميز. نظريًا، يكفي إضافة بت واحد فقط لإبلاغ المُفكِّك بتعطيل الترميز العادي للمُدخلات بأكملها؛ إلا أن معظم خوارزميات الترميز تستخدم بايتًا كاملًا واحدًا على الأقل (وأحيانًا أكثر من ذلك) لهذا الغرض. على سبيل المثال، لا تحتاج الملفات المضغوطة بتقنية deflate إلى زيادة حجمها بأكثر من 5 بايتات لكل 65,535 بايت من المُدخلات.

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

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

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

على وجه الخصوص، لا يمكن ضغط ملفات البيانات العشوائية بشكل متسق بواسطة أي خوارزمية ضغط بيانات غير قابلة للفقد يمكن تصورها؛ في الواقع، تُستخدم هذه النتيجة لتعريف مفهوم العشوائية في تعقيد كولموغوروف . [ 19 ]

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

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

الخلفية الرياضية

بصورة مجردة، يمكن اعتبار خوارزمية الضغط دالةً على متواليات (عادةً ما تكون من ثمانيات). ينجح الضغط إذا كانت المتوالية الناتجة أقصر من المتوالية الأصلية (ومن تعليمات خريطة فك الضغط). ولكي تكون خوارزمية الضغط غير ضائعة، يجب أن تشكل خريطة الضغط تحويلاً من متواليات البتات "العادية" إلى متواليات البتات "المضغوطة". يمنع مبدأ التوزيع التقابل بين مجموعة المتواليات ذات الطول N وأي مجموعة جزئية من مجموعة المتواليات ذات الطول N -1. لذلك، لا يمكن إنتاج خوارزمية غير ضائعة تقلل حجم كل متوالية إدخال ممكنة. [ 21 ]

نقاط التطبيق في نظرية الضغط الحقيقي

يُقرّ مصممو خوارزميات الضغط الحقيقية بأنّ تدفقات البيانات ذات الإنتروبيا العالية لا يُمكن ضغطها، ولذلك يُضمّنون آلياتٍ لاكتشاف هذه الحالة ومعالجتها. إحدى الطرق الواضحة لاكتشافها هي تطبيق خوارزمية ضغط أولية واختبار ما إذا كان حجم مُخرَجها أصغر من حجم مُدخَلها. أحيانًا، يتم الاكتشاف باستخدام أساليب استدلالية ؛ على سبيل المثال، قد يعتبر تطبيق الضغط الملفات التي تنتهي أسماؤها بـ ".zip" أو ".arj" أو ".lha" غير قابلة للضغط دون الحاجة إلى أي اكتشاف أكثر تعقيدًا. من الطرق الشائعة لمعالجة هذه الحالة تضمين المُدخَل، أو الأجزاء غير القابلة للضغط منه، في المُخرَج، مما يُقلّل من عبء الضغط. على سبيل المثال، يُحدّد تنسيق بيانات zip "طريقة الضغط" على أنها "مُخزّنة" لملفات الإدخال التي تم نسخها إلى الأرشيف حرفيًا. [ 22 ]

انظر أيضاً

مراجع

  1. ↑ "الوحدة 4، المختبر 4: تمثيل البيانات وضغطها" . BJC.EDC.org . ص  6. تم الاطلاع عليه في 9 أبريل 2022 .
  2. ↑ برايس، آندي (3 مارس 2022). "البث بدون فقدان - مستقبل الصوت عالي الدقة" . أوديو ميديا ​​إنترناشونال . تم الاطلاع عليه في 25 أكتوبر 2025 .
  3. 1 2 أونزر، م.؛ بلو، ت. (2003). "الخصائص الرياضية لمرشحات الموجات الصغيرة JPEG2000" (ملف PDF) . معاملات IEEE في معالجة الصور . 12 (9): 1080-1090 . Bibcode : 2003ITIP...12.1080U . doi : 10.1109/TIP.2003.812329 . PMID 18237979 . 
  4. ↑ "معلومات براءات اختراع LZW" . حول شركة يونيسيس . يونيسيس. مؤرشف من الأصل في 2 يونيو 2009.
  5. ↑ سوليفان، غاري (8-12 ديسمبر 2003). "الخصائص العامة واعتبارات التصميم لترميز الفيديو الزمني الفرعي" . الاتحاد الدولي للاتصالات - تقييس الاتصالات . مجموعة خبراء ترميز الفيديو . تم الاطلاع عليه في 13 سبتمبر 2019 .
  6. ↑ بوفيك، آلان سي. (2009). الدليل الأساسي لمعالجة الفيديو . دار النشر الأكاديمية . ص 355. ISBN  9780080922508.
  7. ↑ أحمد، ناصر ؛ مانديام، جيريدهار د.؛ ماجوترا، نيراج (17 أبريل 1995). رودريغيز، أرتورو أ.؛ سافرانيك، روبرت ج.؛ ديلب، إدوارد ج. (محررون). "مخطط قائم على تحويل جيب التمام المنفصل لضغط الصور بدون فقدان". ضغط الفيديو الرقمي: الخوارزميات والتقنيات 1995. 2419. الجمعية الدولية للبصريات والضوئيات: 474-478 . Bibcode : 1995SPIE.2419..474M . doi : 10.1117/12.206386 .
  8. ↑ كوماتسو، ك.؛ سيزاكي، ك. (1998). "تحويل جيب التمام المنفصل العكسي". وقائع المؤتمر الدولي لعام 1998 التابع لمعهد مهندسي الكهرباء والإلكترونيات حول الصوتيات والكلام ومعالجة الإشارات، ICASSP '98 (رقم التصنيف 98CH36181) . المجلد 3. الصفحات 1769-1772 . doi : 10.1109/ICASSP.1998.681802 . ISBN   0-7803-4428-6.
  9. ↑ مينيز، ألفريد جيه؛ فان أورشوت، بول سي؛ فانستون، سكوت أ. (16 أكتوبر 1996). دليل التشفير التطبيقي . مطبعة سي آر سي. رقم ISBN 978-1-4398-2191-6.
  10. ↑ شاندا، ب.؛ إلهايك، إ.؛ بدر، ج. س. (2012). "HapZipper: أصبح تبادل مجموعات HapMap أسهل" . مجلة أبحاث الأحماض النووية . 40 (20): e159. doi : 10.1093/nar/gks709 . PMC 3488212. PMID 22844100 .  
  11. ↑ براتاس، د.؛ بينهو، أ. ج.؛ فيريرا، ب. ج. س. ج. (2016). ضغط فعال لتسلسلات الجينوم (ملف PDF) . مؤتمر ضغط البيانات. سنوبيرد، يوتا.
  12. ↑ ماهوني، مات (2010). "شرح ضغط البيانات" (ملف PDF) . الصفحات 3-5 . 
  13. ↑ "ملخص" . 1 سبتمبر 2016. مؤرشف من الأصل في 1 سبتمبر 2016.
  14. 1 2 ديوروفيتش، سيباستيان. خوارزميات ضغط البيانات الشاملة بدون فقدان (ملف PDF) (أطروحة). جامعة سيليزيا للتكنولوجيا. الصفحات 93-95 . مؤرشفة من الأصل (ملف PDF) في 28 أغسطس 2024. 
  15. ↑ موليدينا، أليشا بوتي؛ ويجايا، راشيل أناستاسيا؛ مازيل، كيمبرلي؛ أسترياني، ماريا سيرافينا (2024). "دراسة مقارنة لخوارزميات ضغط البيانات: Zstandard وzlib وLZ4". العلوم، والهندسة، والإدارة، وتكنولوجيا المعلومات . اتصالات في علوم الحاسوب والمعلومات. 2198 : 394-406 . doi : 10.1007/978-3-031-72284-4_24 . ISBN 978-3-031-72283-7.
  16. ↑ غوبتا، أبورف؛ بانسال، أمان؛ خاندوجا، فيدي (22 فبراير 2017). "تقنيات الضغط الحديثة غير الفاقد للبيانات: مراجعة ومقارنة وتحليل". المؤتمر الدولي الثاني لعام 2017 حول التقنيات الكهربائية والحاسوبية والاتصالات (ICECCT) . معهد مهندسي الكهرباء والإلكترونيات. الصفحات 1-8 . doi : 10.1109/ICECCT.2017.8117850 . ISBN  978-1-5090-3239-6.
  17. ↑ سيود 2002 ، ص 41.
  18. 1 2 بيل، تيم (2015). "علوم الحاسوب المدهشة". المعلوماتية في المدارس. المناهج والكفاءات والمسابقات . سلسلة محاضرات في علوم الحاسوب. المجلد 9378. الصفحات 1-11 . doi : 10.1007/978-3-319-25396-1_1 . ISBN   978-3-319-25395-4.انظر على وجه الخصوص الصفحتين 8-9 .
  19. ↑ سيود 2002 ، ص 38.
  20. ^ لي مينغ. فيتاني، بول (1993). مقدمة لتعقيد كولموجوروف وتطبيقاته . نيويورك: سبرينغر. ص. 102. ردمك  0-387-94053-7النظرية 2.6 الدالةج(x){\displaystyle C(x)}ليست دالة تكرارية جزئية.
  21. ↑ جوشي، مارك (2015). "مبدأ خانة الحمام". أنماط البرهان . ص 19-23 . doi : 10.1007/978-3-319-16250-8_3 . ISBN  978-3-319-16249-2.
  22. ↑ "مواصفات تنسيق ملف .ZIP" . PKWARE, Inc. الفصل الخامس، القسم J.

للمزيد من القراءة

  • سيود، خالد (27 أكتوبر 2017). مقدمة في ضغط البيانات . سلسلة مورغان كوفمان في معلومات وأنظمة الوسائط المتعددة (  الطبعة الخامسة). مورغان كوفمان . ISBN 978-0-12809474-7.
  • سيود، خالد، محرر. (18 ديسمبر 2002). دليل ضغط البيانات بدون فقدان (الاتصالات والشبكات والوسائط المتعددة) (  الطبعة الأولى). دار النشر الأكاديمية . رقم ISBN 978-0-12390754-7.
  • فامدو، نام. "نظرية ضغط البيانات" . ضغط البيانات . مؤرشف من الأصل في 8 مايو 2016.
  • "مقارنة بدون فقدان للبيانات" . قاعدة معارف Hydrogenaudio . 5 يناير 2015. تم الاطلاع عليه في 25 أكتوبر 2025 .
  • "معيار ضغط الصور" . مؤرشف من الأصل في 10 فبراير 2013.نظرة عامة على
    • براءة الاختراع الأمريكية رقم 7,096,360 مؤرشفة في 2 فبراير 2017 في Wayback Machine ، "[a]an "Frequency-Time Based Data Compression Method" تدعم ضغط وتشفير وفك ضغط وفك تشفير واستمرار العديد من الأرقام الثنائية من خلال الترددات حيث يمثل كل تردد العديد من البتات."