ترميز الإنتروبيا

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

وبشكل أدق، تنص نظرية ترميز المصدر على أنه بالنسبة لأي توزيع مصدر، فإن طول الكود المتوقع يحقق ما يلي: $\operatorname {E} _{x\sim P[\ell (d(x))]\geq \operatorname {E} _{x\sim P[-\log _{b}(P(x))]$ ، أين $\ell$ هي الدالة التي تحدد عدد الرموز في كلمة التشفير، $d$ هي وظيفة الترميز، $b$ يمثل عدد الرموز المستخدمة لإنشاء رموز الإخراج و $P$ يمثل احتمال رمز المصدر. تحاول خوارزمية ترميز الإنتروبيا الاقتراب من هذا الحد الأدنى. ^{[ 2 ]}^{[ 3 ]}

من أكثر تقنيات ترميز الإنتروبيا شيوعًا ترميز هوفمان والترميز الحسابي . ^{[ 4 ]}^{[ 5 ]} إذا كانت خصائص الإنتروبيا التقريبية لتدفق البيانات معروفة مسبقًا (خاصةً لضغط الإشارات )، فقد يكون استخدام ترميز ثابت أبسط مفيدًا. تشمل هذه الترميزات الثابتة الترميزات الشاملة (مثل ترميز إلياس غاما أو ترميز فيبوناتشي ) ورموز غولومب (مثل الترميز الأحادي أو ترميز رايس ). ^{[ 5 ]}

منذ عام 2014، بدأت برامج ضغط البيانات باستخدام عائلة أنظمة الأرقام غير المتماثلة (ANS) من تقنيات ترميز الإنتروبيا، والتي تتيح الجمع بين نسبة ضغط الترميز الحسابي وتكلفة معالجة مماثلة لترميز هوفمان . ^{[ 6 ]}^{[ 1 ]} وقد اعتمدت برامج الضغط التي طورتها شركات مثل فيسبوك ( Zstandard ) وآبل ( LZFSE ) وجوجل (Draco)، وغيرها، تقنية ANS. ^{[ 6 ]}

شرح بديهي

يستغل ترميز الإنتروبيا حقيقة أن بعض الرموز تظهر بتردد أكبر من غيرها. عندما تكون احتمالات الرموز غير متساوية، تصبح بعض النتائج أكثر قابلية للتنبؤ، ويمكن استخدام هذه القابلية للتنبؤ لتمثيل البيانات بعدد أقل من البتات. في المقابل، عندما تكون جميع الرموز متساوية الاحتمال، يحمل كل رمز أقصى قدر ممكن من المعلومات، ولا يمكن إجراء أي ضغط. ^{[ 3 ]}^{[ 2 ]}

عندما يتعذر الضغط: سلسلة من عمليات رمي عملة معدنية عادلة ومستقلة، حيث يكون احتمال ظهور كل من الصورة والكتابة 0.5، تمتلك إنتروبيا مقدارها بت واحد لكل رمز، وهو بالضبط تكلفة تخزين رقم ثنائي واحد. بما أن كل رمز يشغل بالفعل الحد الأدنى من المساحة الممكنة، فلا يوجد تكرار يمكن استغلاله، ولا يمكن لأي طريقة ترميز إنتروبيا أن تجعل البيانات أصغر حجمًا في المتوسط. ينطبق المبدأ نفسه على الأبجديات الأكبر: الرموز الثلاثية المستقلة (0، 1، 2) التي يكون احتمال ظهور كل منها 1/3، تمتلك إنتروبيا تبلغ حوالي 1.585 بت لكل رمز، وهي القيمة القصوى لأبجدية مكونة من ثلاثة رموز، وهي أيضًا غير قابلة للضغط. ^{[ 3 ]}^{[ 2 ]}

عندما يكون الضغط ممكنًا: إذا أنتج المصدر الثنائي نفسه 1 باحتمالية 0.9 و0 باحتمالية 0.1، فإن الإنتروبيا تنخفض إلى حوالي 0.469 بت لكل رمز. وهذا أقل بكثير من تكلفة التخزين لبت واحد، لأن غلبة 1 تجعل كل رمز قابلًا للتنبؤ جزئيًا. يمكن لمُشفِّر الإنتروبيا، مثل التشفير الحسابي، استغلال هذه القابلية للتنبؤ لتحقيق نسبة ضغط تبلغ حوالي 2.1:1 عن طريق تخصيص رموز أقصر للرمز الأكثر شيوعًا. ^{[ 3 ]}^{[ 5 ]}

مثال عملي: تتكون الأبجدية الإنجليزية من حوالي 27 حرفًا (26 حرفًا بالإضافة إلى مسافة). إذا تكررت جميع الأحرف بنفس القدر، فسيحتاج كل حرف إلى حوالي 4.75 بت. مع ذلك، نظرًا لاختلاف ترددات الأحرف بشكل كبير (يظهر الحرف 'e' أكثر بكثير من الحرف 'z')، ولأن الأحرف ليست مستقلة (يأتي الحرف 'u' دائمًا تقريبًا بعد الحرف 'q')، فقد قُدِّرت الإنتروبيا الحقيقية للغة الإنجليزية بحوالي 1.0 إلى 1.5 بت لكل حرف. هذا التفاوت الكبير هو ما يجعل النص الإنجليزي قابلًا للضغط بدرجة كبيرة. ^{[ 7 ]}^{[ 3 ]}

الإنتروبيا كمقياس للتشابه

إلى جانب استخدام ترميز الإنتروبيا كوسيلة لضغط البيانات الرقمية، يمكن أيضًا استخدام مُشفِّر الإنتروبيا لقياس درجة التشابه بين تدفقات البيانات وفئات البيانات الموجودة مسبقًا. ويتم ذلك عن طريق إنشاء مُشفِّر/ضاغط إنتروبيا لكل فئة من فئات البيانات؛ ثم تُصنَّف البيانات غير المعروفة بتغذية البيانات غير المضغوطة لكل ضاغط، ثم يُحدَّد أي ضاغط يُحقق أعلى ضغط. غالبًا ما يكون المُشفِّر ذو أفضل ضغط هو المُشفِّر الذي تم تدريبه على البيانات الأكثر تشابهًا مع البيانات غير المعروفة. ^{[ 8 ]} يستند هذا النهج إلى مفهوم مسافة الضغط المُعَيَّرة ، وهي مقياس تشابه عالمي لا يعتمد على أي معلمات، ويعتمد على الضغط، ويُقارب مسافة المعلومات المُعَيَّرة غير القابلة للحساب . ^{[ 8 ]}^{[ 9 ]}

انظر أيضاً

مراجع

1 2 دودا، جاريك؛ طهبوب، خالد؛ جادجيل، نيراج ج.؛ ديلب، إدوارد ج. (مايو 2015). "استخدام أنظمة الأرقام غير المتماثلة كبديل دقيق لترميز هوفمان" . ندوة ترميز الصور 2015 (PCS) . الصفحات 65-69 . doi : 10.1109/PCS.2015.7170048 . ISBN 978-1-4799-7783-3. S2CID 20260346 .
1 2 3 4 شانون، كلود إي. (1948). "نظرية رياضية للاتصالات". مجلة بيل سيستم التقنية . 27 (3): 379-423 . Bibcode : 1948BSTJ...27..379S . doi : 10.1002/j.1538-7305.1948.tb01338.x .
1 2 3 4 5 كوفير، توماس م.؛ توماس، جوي أ. (2006). عناصر نظرية المعلومات (الطبعة الثانية ). جون وايلي وأولاده. ISBN 978-0-471-24195-9.
↑ هوفمان، ديفيد (1952). "طريقة لإنشاء رموز الحد الأدنى من التكرار". وقائع معهد مهندسي الكهرباء والإلكترونيات (IEEE ). 40 (9). معهد مهندسي الكهرباء والإلكترونيات (IEEE): 1098-1101 . رمز Bibcode : 1952PIRE...40.1098H . doi : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .
1 2 3 سيود، خالد (2017). مقدمة في ضغط البيانات (الطبعة الخامسة ). مورغان كوفمان. ISBN 978-0-12-809474-7.
1 2 دودا، جاريك (2013). "أنظمة الأرقام غير المتناظرة: ترميز الإنتروبيا الذي يجمع بين سرعة ترميز هوفمان ومعدل ضغط الترميز الحسابي". arXiv : 1311.2540 [ cs.IT ].
↑ شانون، كلود إي. (1951). "التنبؤ والإنتروبيا في اللغة الإنجليزية المطبوعة". مجلة بيل سيستم التقنية . 30 (1): 50-64 . Bibcode : 1951BSTJ...30...50S . doi : 10.1002/j.1538-7305.1951.tb01366.x .
1 2 سيليبراسي، رودي؛ فيتاني، بول إم بي (2005). "التجميع بالضغط". معاملات IEEE في نظرية المعلومات . 51 (4): 1523-1545 . Bibcode : 2005ITIT...51.1523C . doi : 10.1109/TIT.2005.844059 . S2CID 911 .
^ فيتاني، بول م.ب. بالباخ، فرانك J .؛ سيليبراسي، رودي إل؛ لي مينغ (2009). "مسافة المعلومات الطبيعية" . نظرية المعلومات والتعلم الإحصائي . سبرينغر. دوى : 10.1007/978-0-387-84816-7_3 . رقم ISBN 978-0-387-84816-7.

روابط خارجية

يقدم كتاب "نظرية المعلومات والاستدلال وخوارزميات التعلم" لديفيد ماكاي (2003) مقدمة لنظرية شانون وضغط البيانات، بما في ذلك ترميز هوفمان والترميز الحسابي .
ترميز المصدر ، بقلم تي. ويغاند وإتش. شوارتز (2011).

[Duda2015-1] 1 2 دودا، جاريك؛ طهبوب، خالد؛ جادجيل، نيراج ج.؛ ديلب، إدوارد ج. (مايو 2015). "استخدام أنظمة الأرقام غير المتماثلة كبديل دقيق لترميز هوفمان" . ندوة ترميز الصور 2015 (PCS) . الصفحات 65-69 . doi : 10.1109/PCS.2015.7170048 . ISBN 978-1-4799-7783-3. S2CID 20260346 .

[Shannon1948-2] 1 2 3 4 شانون، كلود إي. (1948). "نظرية رياضية للاتصالات". مجلة بيل سيستم التقنية . 27 (3): 379-423 . Bibcode : 1948BSTJ...27..379S . doi : 10.1002/j.1538-7305.1948.tb01338.x .

[CoverThomas-3] 1 2 3 4 5 كوفير، توماس م.؛ توماس، جوي أ. (2006). عناصر نظرية المعلومات (الطبعة الثانية ). جون وايلي وأولاده. ISBN 978-0-471-24195-9.

[Huffman1952-4] هوفمان، ديفيد (1952). "طريقة لإنشاء رموز الحد الأدنى من التكرار". وقائع معهد مهندسي الكهرباء والإلكترونيات (IEEE ). 40 (9). معهد مهندسي الكهرباء والإلكترونيات (IEEE): 1098-1101 . رمز Bibcode : 1952PIRE...40.1098H . doi : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .

[Sayood2017-5] 1 2 3 سيود، خالد (2017). مقدمة في ضغط البيانات (الطبعة الخامسة ). مورغان كوفمان. ISBN 978-0-12-809474-7.

[Duda2013-6] 1 2 دودا، جاريك (2013). "أنظمة الأرقام غير المتناظرة: ترميز الإنتروبيا الذي يجمع بين سرعة ترميز هوفمان ومعدل ضغط الترميز الحسابي". arXiv : 1311.2540 [ cs.IT ].

[Shannon1951-7] شانون، كلود إي. (1951). "التنبؤ والإنتروبيا في اللغة الإنجليزية المطبوعة". مجلة بيل سيستم التقنية . 30 (1): 50-64 . Bibcode : 1951BSTJ...30...50S . doi : 10.1002/j.1538-7305.1951.tb01366.x .

[Cilibrasi2005-8] 1 2 سيليبراسي، رودي؛ فيتاني، بول إم بي (2005). "التجميع بالضغط". معاملات IEEE في نظرية المعلومات . 51 (4): 1523-1545 . Bibcode : 2005ITIT...51.1523C . doi : 10.1109/TIT.2005.844059 . S2CID 911 .

[Vitanyi2009-9] فيتاني، بول م.ب. بالباخ، فرانك J .؛ سيليبراسي، رودي إل؛ لي مينغ (2009). "مسافة المعلومات الطبيعية" . نظرية المعلومات والتعلم الإحصائي . سبرينغر. دوى : 10.1007/978-0-387-84816-7_3 . رقم ISBN 978-0-387-84816-7.

[

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]