Golomb coding

ترميز غولومب منهج لضغط البيانات بدون فقدان

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

ترميز رايس

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

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

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

نظرة عامة

مثال لترميز غولومب لمصدر x بتوزيع هندسي، مع معلمة p(0) = 0.2، باستخدام ترميز غولومب مع M = 3. يتم استخدام ترميز الثنائي 2 بت 00 بنسبة 20% من الوقت؛ يتم استخدام ترميزات الثنائي 3 بت 010، 011، و100 بنسبة تزيد عن 38% من الوقت؛ يتم استخدام 4 بت أو أكثر في حالات قليلة. لهذا المصدر، انتروبي = 3.610 بت؛ لهذا الترميز مع هذا المصدر، معدل = 3.639 بت؛ لذلك فائض = 0.030 بت، أو كفاءة = 0.992 بت لكل بت.

بناء الترميزات

يستخدم ترميز غولومب معلمة قابلة للضبط M لتقسيم قيمة المدخل x إلى جزئين: q، نتيجة قسمة على M، وr، الباقي. يتم إرسال الحاصل في ترميز ثنائي، يليه الباقي في ترميز ثنائي مقطوع. عندما M = 1، يكون ترميز غولومب مكافئاً للترميز الثنائي.

يمكن التفكير في ترميزات غولومب-رايس على أنها ترميزات تشير إلى عدد عن طريق موضع "السلة" (q)، و"الإزاحة" داخل "السلة" (r). يوضح الشكل المثالي موضع q وإزاحة r لترميز عدد صحيح x باستخدام معلمة غولومب-رايس M = 3، مع احتمالات المصدر التي تتبع توزيع هندسي مع p(0) = 0.2.

بشكل رسمي، يتم إعطاء الجزئين بالتعبير التالي، حيث x هو العدد الصحيح غير السالب الذي يتم ترميزه:

$q=\left\lfloor {\frac {x}{M}}\right\rfloor$

و

$r=x-qM$.

توضح هذه الصورة الفائض بالبت، لترميز غولومب، عند اختيار M بشكل مثالي، لـ 1 − p(0) ≥ 0.45

سيتم ترميز كل من q وr باستخدام عدد متغير من البتات: q بترميز ثنائي، وr بترميز ثنائي مقطوع. إذا كان r < 2^(b+1) - M، فإن يتم استخدام b بت لترميز r؛ وإلا يتم استخدام b + 1 بت لترميز r. بوضوح، b = log2(M) إذا كان M قوة من العدد 2 ويمكننا ترميز جميع قيم r باستخدام b بت.

العدد الصحيح x الذي تم معالجته بواسطة غولومب هو طول التشغيل لعملية برنولي، التي تتبع توزيع هندسي يبدأ من 0. أفضل خيار للمعلمة M هو دالة للعملية برنولي المقابلة، التي يتم تمثيلها بـ p = P(x=0) احتمالية النجاح في محاولة برنولي معينة. M إما متوسط التوزيع أو المتوسط ±1. يمكن تحديده بواسطة هذه المتباينات:

$(1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M},$

التي تم حلها بواسطة

$M=\left\lceil -{\frac {\log(2-p)}{\log(1-p)}}\right\rceil$.

للمثال مع p(0) = 0.2:

$M=\left\lceil -{\frac {\log(1.8)}{\log(0.8)}}\right\rceil =\left\lceil 2.634\right\rceil =3$.

ترميز غولومب لهذا التوزيع مكافئ لترميز هافمان لنفس الاحتمالات، إذا كان من الممكن حساب ترميز هافمان لمجموعة لانهائية من قيم المصدر.

الاستخدام مع الأعداد الصحيحة الموقعة

تم تصميم مخطط غولومب لترميز تسلسلات الأعداد غير السالبة. ومع ذلك، يمكن توسيعه بسهولة لقبول تسلسلات تحتوي على أعداد سالبة باستخدام مخطط "تداخل وتشابك"، حيث يتم إعادة تعيين جميع القيم إلى عدد صحيح موجب بطريقة فريدة وقابلة للعكس. تبدأ التسلسل بـ: 0، -1، 1، -2، 2، -3، 3، -4، 4، وغيرها. يتم تعيين القيمة السالبة الـ n (أي -n) إلى العدد الفردي الـ n (2n-1)، ويتم تعيين القيمة الموجبة الـ m إلى العدد الزوجي الـ m (2m). يمكن تعبير عن ذلك رياضياً كما يلي: يتم تعيين قيمة موجبة x إلى (x' = 2|x| = 2x، x ≥ 0)، ويتم تعيين قيمة سالبة y إلى (y' = 2|y| - 1 = -2y - 1، y < 0). يمكن استخدام مثل هذا الترميز للبساطة، حتى لو كان غير مثالي. ترميزات أخرى مثالية للتوزيعات الهندسية ثنائية الجانب تشمل متغيرات مختلفة من ترميز غولومب، اعتماداً على معلمات التوزيع، بما في ذلك هذا.

خوارزمية بسيطة

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

1. ثبت المعلمة M على قيمة صحيحة.
2. لـ N، العدد الذي يتم ترميزه، ابحث عن

الباقي = r = N modulo M

1. أنشئ كلمة الترميز

ترميز الباقي (في الترميز الثنائي المقطوع)

دع b = floor(log2(M))

إذا r >= 2^(b+1)-M فقم بترميز العدد r+2^(b+1)-M في تمثيل ثنائي باستخدام b + 1 بت.

فك الترميز:

1. فك ترميز التمثيل الثنائي لـ q (عد عدد 1 في بداية الترميز)
2. تخطي المحدد 0
3. دع b = floor(log2(M))

وإلا فسر b + 1 بت كعدد ثنائي r'. الباقي يتم تقديمه بـ r = r' - 2^(b+1) + M

1. حسب N = q * M + r

مثال

افترض M = 10. لذلك b = floor(log2(10)) = 3. القطع هو 2^(b+1) - M = 16 - 10 = 6.

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

ترميز جزء الباقي r الإزاحة الثنائي بتات الإخراج 0 0 0000 000 1 1 0001 001 2 2 0010 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؛ كل من ترميز q وترميز r ذاتي الحدود).

الاستخدام لترميز طول التشغيل

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

بافتراض أبجدية من رمزين، أو مجموعة من حدثين، P وQ, باحتمالات p و(1 – p) على التوالي، حيث p ≥ 1/2، يمكن استخدام ترميز غولومب لترميز تشغيلات صفر أو أكثر من P مفصولة بـ Q واحدة. في هذا التطبيق، أفضل إعداد للمعلمة M هو العدد الصحيح الأقرب إلى $-{\frac {1}{\log _{2}p}}$. عندما p = 1/2، M = 1، ويكون ترميز غولومب مكافئاً للترميز الثنائي (n ≥ 0 P متبوعة بـ Q واحدة يتم ترميزها كـ n أواني تليها صفر). إذا كان مطلوباً ترميز أبسط، يمكن تعيين معلمة غولومب-رايس b (أي، معلمة غولومب M = 2^b) إلى العدد الصحيح الأقرب إلى $-\log _{2}(-\log _{2}p)$; على الرغم من أنه ليس دائماً المعلمة الأفضل، إلا أنه غالباً ما يكون المعلمة الأفضل لرايس وأداء ضغطه قريب جداً من الترميز غولومب الأمثل. (اقترح رايس استخدام ترميزات مختلفة لنفس البيانات لمعرفة الأفضل. اقترح باحث لاحق في مختبر الدفع النفاث (JPL) طرق مختلفة لتحسين أو تقدير معلمة الترميز.)

افترض استخدام ترميز رايس بجزء ثنائي يحتوي على b بتات لترميز طول التشغيل لتسلسلات حيث P لها احتمال p. إذا كان $\mathbb {P} [{\text{bit is part of }}k{\text{-run}}]$ هو احتمال أن يكون البت جزءاً من تشغيل k-بت (k-1 P وQ واحدة) و$({\text{compression ratio of }}k{\text{-run}})$ هو نسبة الضغط لهذا التشغيل، فإن النسبة المتوقعة للضغط هي

${\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}}$

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

ترميز غولومب-رايس تكيفي لطول التشغيل

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

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

التطبيقات

نسب ضغط تجربة خوارزمية ترميز غولومب-رايس

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

يستخدم عدة مشفرات صوت بدون فقدان، مثل Shorten، FLAC، Apple Lossless، وMPEG-4 ALS، ترميز رايس بعد مرحلة التنبؤ الخطي (تسمى "فلتر FIR تكيفي" في Apple Lossless). يتم استخدام ترميز رايس أيضاً في مشفر الصور بدون فقدان FELICS.

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

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

يتم استخدام النسخة التكيفية من ترميز غولومب-رايس، مشفر RLGR [١]، لترميز محتوى الشاشة في الآلات الافتراضية في مكون RemoteFX من بروتوكول سطح المكتب البعيد من مايكروسوفت.

انظر أيضاً

• Elias delta coding
• Variable-length code

للقراءة الإضافية

• Golomb, Solomon W. (1966). Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401
• Robert F. Rice (1979), "Some Practical Universal Noiseless Coding Techniques", Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79--22, March 1979.
• Witten, Ian Moffat, Alistair Bell, Timothy. "Managing Gigabytes: Compressing and Indexing Documents and Images." Second Edition. Morgan Kaufmann Publishers, San Francisco CA. 1999 (ردمك 1-55860-570-3)
• David Salomon. "Data Compression",(ردمك 0-387-95045-1).
• H. S. Malvar, Adaptive run-length/Golomb–Rice encoding of quantized generalized Gaussian sources with unknown statistics, Proc. Data Compression Conference, 2006.
• RLGR Entropy Encoding, Microsoft MS-RDPRFX Open Specification, RemoteFX codec for Remote Desktop Protocol.
• S. Büttcher, C. L. A. Clarke, and G. V. Cormack. Information Retrieval: Implementing and Evaluating Search Engines نسخة محفوظة 2020-10-05 على موقع واي باك مشين.. MIT Press, Cambridge MA, 2010.

📰 Article(s) of the same category(ies)

• جيش الموحدين
• الشيخ محمد سرور
• سحب القوات الأمريكية من السعودية
• كبانة
• عصا الملك السامي
• وادي باصور
• أبو عمر الباحث

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

Read or create/edit this page in another language

• Golomb coding in English