كيف يعمل ضغط البيانات بدون فقدان | مجلة كوانتا

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

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

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

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

ومع ذلك ، فإن شفرة مورس غير فعالة أيضًا. بالتأكيد ، بعض الرموز قصيرة والبعض الآخر طويل. ولكن نظرًا لاختلاف أطوال الشفرة ، لا يمكن فهم الرسائل في شفرة مورس ما لم تتضمن فترات قصيرة من الصمت بين إرسال كل حرف. في الواقع ، بدون هذه التوقفات المكلفة ، لن يكون لدى المستلمين أي طريقة للتمييز بين شرطة Morse message dot-dash-dot-dot-dot dash dot ("trite") من شرطة dot-dash-dot dot-dot-dash dot ("صحيح" ).

لقد حل فانو هذا الجزء من المشكلة. لقد أدرك أنه يمكنه استخدام رموز ذات أطوال متفاوتة دون الحاجة إلى مسافات باهظة الثمن ، طالما أنه لم يستخدم أبدًا نفس نمط الأرقام ككود كامل وبداية رمز آخر. على سبيل المثال ، إذا كان الحرف S شائعًا جدًا في رسالة معينة لدرجة أن Fano خصص له الرمز القصير للغاية 01 ، فلن يتم تشفير أي حرف آخر في هذه الرسالة بأي شيء يبدأ بـ 01 ؛ سيتم حظر جميع الرموز مثل 010 أو 011 أو 0101. ونتيجة لذلك ، يمكن قراءة الرسالة المشفرة من اليسار إلى اليمين ، دون أي لبس. على سبيل المثال ، مع الحرف S المعين 01 ، والحرف A المعين 000 ، والحرف M المعين 001 ، والحرف L المعين 1 ، فجأة يمكن ترجمة الرسالة 0100100011 على الفور إلى كلمة "صغير" على الرغم من أن L يتم تمثيلها بواحد رقم ، S برقمين ، والحروف الأخرى بثلاثة أرقام.

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

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

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

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

ضع في اعتبارك رسالة يتعثر فيها نهج فانو. في "schoolroom" ، تظهر O أربع مرات ، وتظهر S / C / H / L / R / M مرة واحدة. يبدأ نهج الموازنة الخاص بـ Fano من خلال تخصيص حرف O وحرف آخر إلى الفرع الأيسر ، مع استخدامات إجمالية الخمسة لتلك الأحرف لموازنة المظاهر الخمسة للأحرف المتبقية. تتطلب الرسالة الناتجة 27 بت.

على النقيض من ذلك ، يبدأ هوفمان بحرفين غير مألوفين - على سبيل المثال ، R و M - ويجمعهما معًا ، ويعامل الزوجين كحرف واحد.

ثم يقدم له مخطط التردد المحدث الخاص به أربعة خيارات: O الذي يظهر أربع مرات ، وعقدة RM المدمجة الجديدة التي يتم استخدامها وظيفيًا مرتين ، والحروف المفردة S و C و H و L. (قل) H مع L.

يتم تحديث المخطط مرة أخرى: لا يزال وزن O 4 و RM و HL الآن بوزن 2 ، والحرفان S و C مستقلان. يواصل Huffman من هناك ، في كل خطوة يقوم بتجميع الخيارين الأقل تكرارًا ثم تحديث كل من الشجرة ومخطط التردد.

في النهاية ، "حجرة الدراسة" تصبح 11101111110000110110000101 ، مما يقلل قليلاً من نهج Fano من أعلى إلى أسفل.

قد لا يبدو البت الواحد كثيرًا ، ولكن حتى المدخرات الصغيرة تنمو بشكل هائل عند زيادة حجمها بمليارات الجيجابايت.

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

ليس سيئًا لمشروع كان الدافع في الأصل هو رغبة طالب دراسات عليا في تخطي الاختبار النهائي.