ضغط بيانات

من أرابيكا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
ضغط بيانات

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

في مجال معالجة الإشارات الرقمية، يشير مصطلح ضغط البيانات (Data Compression)، أو الترميز المصدري (Source Coding)،[1] أو خفض معدّل البيانات إلى ترميز المعلومات باستخدام قدر أقل من النبضات الثنائية من التمثيل الأصلي.[2] يمكن أن يكون ضغط البيانات إمّا ضغط منقوص أو ضغط البيانات غير المضيع بالإنجليزية (Lossy) و (Lossless Compression) على الترتيب. الضغط غير المنقوص يخفض من عدد النبضات الثنائية (البت) اللازمة للتعبير عن البيانات عن طريق التعرف على التكرارية الإحصائية.ولا تفقد أي معلومات نتيجة لضغط البيانات. ومن أمثلة هذا النوع البرامج التي تستخدم لضغط ملفات الحاسوب مثل برامج ليتم تخزينها في صيغة (*.rar)أو في صيغة (*.zip).ويتم استعادة ملفات الحاسب أيًا كان نوعها بالكامل بعد فك الضغط. أمّا في حالة الضغط المنقوص فيتم تقليل النبضات الثنائية من خلال التعرف على المعلومات غير الهامة أو غير اللازمة وإزالتها.[3] ومن أمثلة هذا النوع ما يحدث عند تخزين الصور ومقاطع الفيديو بصيغ تقلل الحجم، حيث يتم ضغط حجم الملفات عن طريق تقليل جودة الصورة مثلاً بقدر غير محسوس، مثال: تحويلها من صيغة (*.bmp) الكاملة إلى صيغة (*.jpg) المضغوطة. وكذلك الحال عند تحويل صيغة (*.avi) الكاملة إلى صيغ أخرى مثل (*.mp4) المضغوطة. ولا يمكن استرجاع «المعلومات» المفقودة عند الضغط بهذه الأساليب.

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

يعتبر ضغط البيانات أمرًا مفيدًا نظرًا لأنه يساعد على خفض استخدام الموارد، مثل وسط التخزين أو سعة الإرسال أو حيز التردد. ونظرًا لأن البيانات المضغوطة لابد من فك ضغطها لكي تصبح صالحة للاستخدام، فإن عمليات المعالجة الإضافية هذه تضع قيودًا حسابية أو تكلفة من نوع آخر لعملية فك الضغط، وبالتالي فإن هذه العملية ليست بلا ثمن!. ويتطلب فك ضغط البيانات الموازنة بين الوقت/حيز التخزين من ناحية وبين التعقيد من ناحية أخرى. فعلى سبيل المثال، عند استخدام أحد أساليب ضغط الفيديو، يتطلب الأمر إمّا أجهزة مكلّفة لكي تتمكن من فك ضغط الفيديو أثناء المشاهدة (وهو ما يزيد التعقيد)، أو أن يتم فك الضغط بالكامل قبل المشاهدة وهو ما يكلِّف وقتًا (في أنظمة الإرسال/الاستقبال) ويتطلب أيضًا حيز تخزين كبير يستوعب الفيديو الذي تم فكّه. ويعتمد تصميم أنظمة ضغط البيانات على الموازنة بين عدة عوامل مختلفة، والتي تشمل درجة الضغط، وكمية التشويه (Distortion) التي يمكن احتمالها (وذلك عند استخدام أنظمة الضغط المنقوص)، وكمية الموارد الحسابية المطلوبة لفك ضغط البيانات.[5] وتجدر الإشارة إلى أن نظرية المعلومات هي العلم الذي يبحث في كلا نوعي ضغط البيانات، كما سيأتي تفصيله لاحقًا، حيث يهدف الضغط غير المنقوص إلى تمثيل البيانات بعدد من النبضات الثنائية يكافئ بالضبط الإنتروبية بينما يؤدي الضغط المنقوص إلى تمثيل البيانات بأقل من الإنتروبية، وبالتالي يحدث فقد في المعلومات (تشويه) وتبحث النظرية حينئذٍ في تحقيق أقصى استفادة مناظرة لهذا التشويه.

ضغط البيانات غير المنقوص

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

ضغط البيانات المنقوص

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

تشفير

أبسط طريقة لضغط الرسائل وتعتمد على تعويض البايتات بعدد تكرارها (5اصفار 6وحدات...)

غير المنقوص

عادة ما يستخدم ضغط البيانات غير المنقوص خوارزمات تستغل statistical redundancy لتمثيل البيانات بطريقة أكثر إيجازًا وبدون فقد معلومات، بحيث يمكن أن تكون عملية الضغط قابلة للفك بنفس الطريقة. ويمكن إجراء عملية الضغط غير المنقوص نظرًا لأن معظم البيانات في الحقيقة تتمتع بقدر من التكرارية الإحصائية. على سبيل المثال، قد تكون هناك مناطق ذات لون واحد في الصورة لا تتغير على مدار أكثر من بكسل (نقطة)؛ فبدلاً من ترميزها باعتبارها «نقطة حمراء، نقطة حمراء...» يمكن ترميز البيانات على هيئة «279 نقطة حمراء» وهذا مثال مبسط عن أسلوب يعرف باسم ترميز طول التشغيل؛ وهناك العديد من الأساليب التي تقلل من حجم الملف عن طريق إلغاء التكرار. ومن بين أكثر طرق الضغط شيوعًا خوارزم ليمبل زيف Lempel–Ziv (LZ) والتي تستخدم في أوساط التخزين.[6] بينما يعتبر خوارزم أحد الصور المنبثقة من LZ وهو خوارزم تم تصميمه لتحقيق أقصى مواءمة بين سرعة فك ضغط البيانات وبين نسبة الضغط، ولكن عملية الضغط ذاتها قد تكون بطيئة. ويستخدم خوارزم DEFLATE في برنامج PKZIP، وجي زيب وPNG. بينما يستخدم خوارزم خوارزمية لامبل-زيف-ويلش (Lempel–Ziv–Welch) في صور جي آي إف. وجدير بالذكر أيضًا أن خوارزم LZR (Lempel-Ziv–Renau)، يعد أساسًا لطريقة Zip. وتستخدم طرق LZ نموذجًا لضغط البيانات يعتمد على جدول، حيث يتم التعويض عن مدخلات الجدول بدلاً من القيم المكررة من سلاسل البيانات. وبالنسبة لمعظم أساليب LZ، يتم توليد هذا الجدول بصورة ديناميكية من البيانات التي سبق إدخالها. وعادة ما يتم ترميز الجدول ذاته باستخدام طريقة ترميز هوفمان (مثل SHRI، LZX). ويعد نظام الترميز LZX من بين أنظمة الترميز ذات الأداء الجيد والتي تعتمد على خوارزمات LZ وهو مستخدم في صيغة CAB الخاصة بشركة مايكروسوفت. وتستخدم أفضل أساليب ضغط البيانات الحديثة نماذج احتمالية، مثل prediction by partial matching (التنبو من خلال المطابقة الجزئية).

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

الضغط المنقوص

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

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

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

أمّا في ضغط الصوت المنقوص، فتستخدم أساليب علم النفس السماعي، psychoacoustics لإزالة المكونات غير المسموعة (أو الأقل تأثيرًا في السمع) من الإشارة الصوتية. وعادة ما يتم ضغط الصوت البشري باستخدام طرق أكثر تخصصًا؛ حيث يمكن تمييز عملية ترميز الكلام (تشفير المحادثة) أو ترميز الصوت الآدمي، باعتبارها مجالاً بحثيًا مختلفًا عن «ضغط الصوت». وهناك العديد من النظم القياسية لضغط الصوت والكلام وهي متضمنة في صيغ ترميز الصوت (audio coding format)، كما يستخدم «ضغط الصوت» في هواتف الإنترنت، ويستخدم ضغط الصوت على سبيل المثال في تخزين الصوت على الاسطوانات المدمجة (CD).[8]

النظرية

توفِّر نظرية المعلومات الأساس النظري لعملية الضغط (وهي ترتبط ارتباطًا وثيقًا بنظرية المعلومات الخوارزمية algorithmic information theory) في حالة الضغط غير المنقوص بينما ترتبط بنظرية السرعة-التشويه (rate–distortion theory بالنسبة للضغط المنقوص). وكان صاحب السبق في فتح هذه المجالات للدراسة هو كلود شانون، والذي نشر بعض الأوراق البحثية الأساسية في هذا الموضوع في أواخر الأربعينات وأوائل الخمسينات من القرن العشرين. كما ترتبط هذه الموضوعات بنظرية الترميز (نظرية الترميز). وتتصل فكرة ضغط البيانات اتصالاً وثيقًا بالاستقراء الإحصائي (استدلال إحصائي.[9])

التعلم الآلي

هناك علاقة وثيقة بين التعلم الآلي وبين ضغط البيانات: فالنظام الذي يمكنه التنبؤ بالاحتمالات اللاحقة لتسلسل من القيم بمعلومية القيم السابقة بالكامل يمكن أن يفيد في ضغط البيانات بطريقة مُثلى (باستخدام على التوزيع الاحتمالي الخارج) كما يمكن أن يستخدم ضاغط البيانات الجيد للتنبؤ (عن طريق البحث عن الرمز الذي يحقق أعلى معامل ضغط، بمعلومية القيم السابقة). وقد استخدم هذا التناظر بين التطبيقين كوسيلة لقياس «الذكاء العام.»[10]

تفرِقة البيانات

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

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

نظرة مستقبلية والإمكانيات غير المستخدمة حاليًا

تشير التقديرات إلى أن إجمالي كم البيانات المخزنة في جميع أجهزة التخزين في العالم يمكن ضغطها أكثر باستخدام خوارزمات ضغط البيانات الموجودة بالفعل بمعامل متبقي يبلغ 4.5:1. كما تشير التقديرات إلى أن السعة التكنولوجية المجمّعة على تخزين المعلومات يمكنها تخزين 1300 exabyte من الأرقام المخزنة في الأجهزة في عام 2007، ولكن حين يتم ضغط المحتوى بالصورة المُثلى نجد أن هذا الرقم لا يتخطي 295 إكسا بايت من معلومات شانون.[13]

الاستخدامات

الصوت

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

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

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

الفيديو

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

تستخدم معظم خوارزمات ضغط الفيديو الضغط المنقوص. حيث يتطلب الفيديو غير المضغوط معدل بيانات ‏ مرتفع للغاية. وعلى الرغم من أن مرمِّزات (Codecs) الفيديو غير المنقوصة video compression ‏ تؤدي إلى معامل ضغط يبلغ نحو 3 مرات، إلا أنه من المعتاد أن يبلغ معامل ضغط فيديو بأسلوب إم بي إي جي - 4 المنقوص ما بين 20 إلى 200.[15]

الخط الزمني

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

تاريخ النظم القياسية لضغط الفيديو
العام النظام القياسي الناشر أكثر عمليات تنفيذ هذه الخوارزمات شيوعًا.
1984 H.120 الاتحاد الدولي للاتصالات
1988 H.261 الاتحاد الدولي للاتصالات المؤتمرات المرئية، الهاتف المرئي
1993 مبيج-1 المنظمة الدولية للمعايير، اللجنة الكهروتقنية الدولية Video-CD
1995 H.262/MPEG-2 Part 2 المنظمة الدولية للمعايير، اللجنة الكهروتقنية الدولية، الاتحاد الدولي للاتصالات دي في دي، قرص بلو راي، بث فيديو رقمي، SVCD
1996 H.263 الاتحاد الدولي للاتصالات المؤتمرات المرئية، الهاتف المرئي، الفيديو على الهواتف المحمولة (ثري جي بي)
1999 MPEG-4 Part 2 المنظمة الدولية للمعايير، اللجنة الكهروتقنية الدولية الفيديو على شبكة الإنترنت (ديف إكس، Xvid ...)
2003 أتش 264 سوني، باناسونيك، سامسونج، المنظمة الدولية للمعايير، اللجنة الكهروتقنية الدولية، الاتحاد الدولي للاتصالات قرص بلو راي، أسطوانات الفيديو الرقمية فائقة الدقة، بث فيديو رقمي، آي بود كلاسيك، أبل تي في، videoconferencing
2009 VC-2 (Dirac) ‏ جمعية مهندسي الصور المتحركة والتلفزيون الفيديو على شبكة الإنترنت، HDTV broadcast، UHDTV
2013 ترميز الفيديو عالي الفعالية المنظمة الدولية للمعايير، اللجنة الكهروتقنية الدولية، الاتحاد الدولي للاتصالات

انظر أيضاً

مراجع

  1. ^ Wade، Graham (1994). Signal coding and processing (ط. 2). Cambridge University Press. ص. 34. ISBN:978-0-521-42336-6. مؤرشف من الأصل في 2017-09-08. اطلع عليه بتاريخ 2011-12-22. الهدف العام من الترميز المصدري، هو إزالة التكرار الموجود في البيانات الخارجة من المصدر أو بمعنى آخر وبالتالي تخفيض معدل نقل البيانات المطلوب والذي يرمز له بالرمز R.
  2. ^ أ ب Mahdi، O.A.؛ Mohammed, M.A.؛ Mohamed, A.J. (نوفمبر 2012). "Implementing a Novel Approach an Convert Audio Compression to Text Coding via Hybrid Technique" (PDF). International Journal of Computer Science Issues. ج. 9 ع. 6, No. 3: 53–59. مؤرشف من الأصل (PDF) في 2018-12-28. اطلع عليه بتاريخ 2013-03-06.
  3. ^ Pujar، J.H.؛ Kadlaskar, L.M. (مايو 2010). "A New Lossless Method of Image Compression and Decompression Using Huffman Coding Techniques" (PDF). Journal of Theoretical and Applied Information Technology. ج. 15 ع. 1: 18–23. مؤرشف من الأصل (PDF) في 2018-12-28.
  4. ^ Salomon، David (2008). A Concise Introduction to Data Compression. Berlin: Springer. ISBN:9781848000728.
  5. ^ Tank، M.K. (2011). Implementation of Limpel-Ziv algorithm for lossless compression using VHDL. Thinkquest 2010: Proceedings of the First International Conference on Contours of Computing Technology. Berlin: Springer. ص. 275–283.
  6. ^ Navqi، Saud؛ Naqvi, R.؛ Riaz, R.A.؛ Siddiqui, F. (أبريل 2011). "Optimized RTL design and implementation of LZW algorithm for high bandwidth applications" (PDF). Electrical Review. ج. 2011 ع. 4: 279–285. مؤرشف من الأصل (PDF) في 2018-12-28.
  7. ^ Arcangel، Cory. "On Compression" (PDF). مؤرشف من الأصل (PDF) في 2018-12-28. اطلع عليه بتاريخ 2013-03-06.
  8. ^ Mahmud، Salauddin (مارس 2012). "An Improved Data Compression Method for General Data" (PDF). International Journal of Scientific & Engineering Research. ج. 3 ع. 3: 2. مؤرشف من الأصل (PDF) في 2018-12-28. اطلع عليه بتاريخ 2013-03-06.
  9. ^ Marak، Laszlo. "On image compression" (PDF). University of Marne la Vallee. مؤرشف من الأصل (PDF) في 2017-09-08. اطلع عليه بتاريخ 2013-03-06.
  10. ^ Mahoney، Matt. "Rationale for a Large Text Compression Benchmark". http://cs.fit.edu/~mmahoney/. Florida Institute of Technology. مؤرشف من الأصل في 2019-04-27. اطلع عليه بتاريخ 2013-03-05. {{استشهاد ويب}}: روابط خارجية في |عمل= (مساعدة)
  11. ^ Korn، D.؛ وآخرون. "RFC 3284: The VCDIFF Generic Differencing and Compression Data Format". Internet Engineering Task Force. مؤرشف من الأصل في 2019-05-02. اطلع عليه بتاريخ 2013-03-05.
  12. ^ Korn، D.G.؛ Vo، K.P. (1995)، B. Krishnamurthy (المحرر)، Vdelta: Differencing and Compression، Practical Reusable Unix Software، New York: John Wiley & Sons, Inc.
  13. ^ Hilbert، Martin؛ López, Priscila (1 أبريل 2011). "The World's Technological Capacity to Store, Communicate, and Compute Information". Science. ج. 332 ع. 6025: 60–65. Bibcode:2011Sci...332...60H. DOI:10.1126/science.1200970. PMID:21310967. مؤرشف من الأصل في 2016-01-07. اطلع عليه بتاريخ 2013-03-06.
  14. ^ "Video Coding". Center for Signal and Information Processing Research. Georgia Institute of Technology. مؤرشف من الأصل في 2017-09-08. اطلع عليه بتاريخ 2013-03-06.
  15. ^ Graphics & Media Lab Video Group (2007). Lossless Video Codecs Comparison (PDF). Moscow State University. مؤرشف من الأصل (PDF) في 2018-12-28.