ترميز غولومب

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

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

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

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

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

1. قم بتثبيت قيمة المعامل M على قيمة عددية صحيحة.
2. بالنسبة لـ N ، الرقم المراد ترميزه، أوجد
   1. الناتج = q = الجزء الصحيح من ( N / M )
   2. الباقي = r = N modulo M
3. توليد كلمة المرور
   1. صيغة الكود  : <رمز الناتج><رمز الباقي>، حيث
   2. رمز القسمة (في الترميز الأحادي )
      1. اكتب سلسلة بطول q مكونة من 1 بت (أو بدلاً من ذلك، من 0 بت)
      2. اكتب بت 0 (أو بت 1 على التوالي)
   3. رمز الباقي (في ترميز ثنائي مختصر )
      1. يترك${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$
         1. لو${\displaystyle r<2^{b+1}-M}$كتابة الرمز r في التمثيل الثنائي باستخدام b بت.
         2. لو${\displaystyle r\geq 2^{b+1}-M}$رمز الرقم${\displaystyle r+2^{b+1}-M}$في التمثيل الثنائي باستخدام b + 1 بت.

فك التشفير:

1. فك شفرة التمثيل الأحادي لـ q (عدّ عدد مرات ظهور الرقم 1 في بداية الشفرة)
2. تجاهل الفاصل 0
3. يترك${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$
   1. فسّر البتات b التالية كرقم ثنائي r' . إذا${\displaystyle r'<2^{b+1}-M}$يثبت، ثم الباقي${\displaystyle r=r'}$
   2. وإلا، ففسّر b + 1 بت كعدد ثنائي r' ، والباقي يُعطى بواسطة${\displaystyle r=r'-2^{b+1}+M}$
4. الحوسبة${\displaystyle N=q*M+r}$

لنفترض أن M = 10. وبالتالي${\displaystyle b=\lfloor \log _{2}(10)\rfloor =3}$الحد الفاصل هو${\displaystyle 2^{b+1}-M=16-10=6}$.

ترميز جزء القسمة q بتات الإخراج 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 ${\displaystyle \vdots }$ ${\displaystyle \vdots }$ شمال ${\displaystyle \underbrace {111\cdots 111} _{N}0}$

ترميز الجزء المتبقي ر إزاحة ثنائي بتات الإخراج 0 0 0000 ٠٠٠ 1 1 ٠٠٠١ 001 2 2 ٠٠١٠ 010 3 3 0011 011 4 4 0100 100 5 5 0101 101 6 12 1100 1100 7 13 1101 1101 8 14 1110 1110 9 15 1111 1111

على سبيل المثال، باستخدام ترميز رايس-غولومب باستخدام المعامل M = 10 ، سيتم تقسيم العدد العشري 42 أولاً إلى q = 4 و r = 2، وسيتم ترميزه على النحو التالي: qcode( q ),rcode( r ) = qcode(4),rcode(2) = 11110,010 (لا تحتاج إلى ترميز الفاصلة في دفق الإخراج، لأن الصفر في نهاية رمز q يكفي لتحديد متى ينتهي q ويبدأ r ؛ كل من qcode و rcode محدد ذاتيًا).

لاحظ أن p و 1 – p معكوسة في هذا القسم مقارنة بالاستخدام في الأقسام السابقة.

بافتراض وجود أبجدية مكونة من رمزين، أو مجموعة من حدثين، P و Q ، باحتمالات p و ( 1 − p ) على التوالي، حيث p ≥ 1/2 ، يمكن استخدام ترميز غولومب لترميز سلاسل من صفر أو أكثر من P مفصولة بحدث Q واحد . في هذا التطبيق، أفضل قيمة للمعامل M هي أقرب عدد صحيح إلى${\displaystyle -{\frac {1}{\log _{2}p}}}$عندما تكون قيمة p تساوي 1/2، وقيمة M تساوي 1، فإن رمز غولومب يُقابل ترميزًا أحاديًا ( حيث n ≥ 0، ويتم ترميز P ′s متبوعًا بـ Q على أنه n من الآحاد متبوعًا بصفر). إذا رُغِبَ في رمز أبسط، فيمكن تعيين مُعامل غولومب-رايس b (أي مُعامل غولومب).${\displaystyle M=2^{b}}$) إلى أقرب عدد صحيح${\displaystyle -\log _{2}(-\log _{2}p)}$على الرغم من أنها ليست دائمًا أفضل معيار، إلا أنها عادةً ما تكون أفضل معيار لرايس، وأداء ضغطها قريب جدًا من أداء كود غولومب الأمثل. (اقترح رايس نفسه استخدام أكواد مختلفة لنفس البيانات لتحديد الأفضل. واقترح باحث لاحق في مختبر الدفع النفاث طرقًا مختلفة لتحسين أو تقدير معيار الكود. ^{[ 3 ]} )

ضع في اعتبارك استخدام رمز رايس بجزء ثنائي يحتوي على b بت لترميز طول التشغيل للتسلسلات حيث يكون لـ P احتمال p . إذا${\displaystyle \mathbb {P} [{\text{bit is part of }}k{\text{-run}}]}$هي احتمالية أن يكون البت جزءًا من سلسلة مكونة من k بت (${\displaystyle k-1}$(P s وواحد Q ) و${\displaystyle ({\text{نسبة ضغط }}k{\text{-run}})}$إذا كانت نسبة الضغط لتلك العملية هي ، فإن نسبة الضغط المتوقعة هي $${\displaystyle {\begin{aligned}\mathbb {E} [{\text{compression ratio}}]&=\sum _{k=1}^{\infty }({\text{compression ratio of }}k{\text{-run}})\cdot \mathbb {P} [{\text{bit is part of }}k{\text{-run}}]\\&=\sum _{k=1}^{\infty }{\frac {b+1+\lfloor 2^{-b}(k-1)\rfloor }{k}}\cdot kp^{k-1}(1-p)^{2}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \sum _{i=j2^{b}+1}^{(j+1)2^{b}}p^{i-1}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \left(p^{2^{b}j}-p^{2^{b}(j+1)}\right)\\&=(1-p)\cdot \left(b+\sum _{m=0}^{\infty }p^{2^{b}m}\right)\\&=(1-p)\cdot \left(b+{\left(1-p^{2^{b}}\right)}^{-1}\right)\\\end{aligned}}}$$

غالباً ما يتم التعبير عن الضغط من حيث${\displaystyle 1-\mathbb {E} [{\text{compression ratio}}]}$، النسبة المضغوطة. لـ${\displaystyle p\approx 1}$ينتج عن أسلوب ترميز طول التشغيل نسب ضغط قريبة من الإنتروبيا . على سبيل المثال، باستخدام رمز رايس${\displaystyle b=6}$ل${\displaystyle p=0.99}$العائدنسبة الضغط 91.89% ، بينما حد الإنتروبيا هو91.92 %

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

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

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

تستخدم العديد من برامج ترميز الصوت غير المضغوطة ، مثل Shorten وFLAC ^و Apple ^Lossless و MPEG - ⁴ ALS ^{، ترميز} Rice بعد خطوة التنبؤ الخطي (المسماة "مرشح FIR التكيفي" في Apple ^Lossless ). كما يُستخدم ترميز Rice في برنامج ترميز الصور FELICS غير المضغوط.

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

يستخدم مخطط JPEG-LS خوارزمية رايس-غولومب لترميز بقايا التنبؤ.

النسخة التكيفية RLGR من ترميز غولومب-رايس المذكورة أعلاهيُستخدم هذا الأسلوب لترميز محتوى الشاشة في الأجهزة الافتراضية ضمن مكون RemoteFX من بروتوكول سطح المكتب البعيد من مايكروسوفت. كما يُستخدم أيضًا في معيار G-PCC MPEG الأخير ISO/IEC 23090-9 لضغط سمات السحابة النقطية.

• ترميز دلتا إلياس
• رمز متغير الطول
• ترميز أسي-غولومب

• غولومب، سولومون و. (1966). ترميزات طول التشغيل. معاملات IEEE في نظرية المعلومات، IT-12(3):399-401
• رايس، روبرت ف.؛ بلاونت، ر. (1971). "ترميز متغير الطول تكيفي لضغط بيانات التلفزيون من المركبات الفضائية بكفاءة". معاملات IEEE في الاتصالات . 16 (9): 889-897 . Bibcode : 1971ITCoT..19..889R . doi : 10.1109/TCOM.1971.1090789 .
• روبرت ف. رايس (1979)، " بعض تقنيات التشفير العالمية العملية عديمة الضوضاء "، مختبر الدفع النفاث، باسادينا، كاليفورنيا، منشور JPL 79-22، مارس 1979.
• ويتن، إيان موفات، أليستير بيل، تيموثي. "إدارة الجيجابايت: ضغط وفهرسة المستندات والصور". الطبعة الثانية. دار مورغان كوفمان للنشر، سان فرانسيسكو، كاليفورنيا. 1999. رقم ISBN 1-55860-570-3
• ديفيد سالومون. "ضغط البيانات"، رقم ISBN 0-387-95045-1.
• HS Malvar، ترميز طول التشغيل التكيفي / Golomb-Rice لمصادر Gaussian المعممة الكمية ذات الإحصائيات غير المعروفة ، وقائع مؤتمر ضغط البيانات، 2006.
• ترميز إنتروبيا RLGR ، المواصفات المفتوحة لـ Microsoft MS-RDPRFX، برنامج الترميز RemoteFX لبروتوكول سطح المكتب البعيد.
• إس. بوتشر، سي إل إيه كلارك، وجي في كورماك. استرجاع المعلومات: تنفيذ وتقييم محركات البحث. مؤرشف بتاريخ 2020-10-05 في أرشيف الإنترنت . مطبعة معهد ماساتشوستس للتكنولوجيا، كامبريدج، ماساتشوستس، 2010.