ترميز دلتا إلياس

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

شفرة إلياس دلتا أو شفرة إلياس دلتا هي شفرة عالمية تشفر الأعداد الصحيحة الموجبة، وقد طورها بيتر إلياس . [ 1 ] : 200

التشفير

لترميز رقم X  ≥ 1:

  1. ليكن N = ⌊log 2 X ⌋؛ أعلى قوة للعدد 2 في X ، لذا 2 N ≤ X < 2 N +1 .
  2. ليكن L = ⌊log 2 N + 1⌋ أعلى قوة للعدد 2 في N + 1، لذا فإن 2 L ≤ N + 1 < 2 L +1 .
  3. اكتب L أصفارًا، متبوعة بـ
  4. التمثيل الثنائي المكون من ( L + 1) بت للعدد N + 1، متبوعًا بـ
  5. جميع البتات باستثناء البت الرئيسي (أي آخر N بت) من X.

طريقة مكافئة للتعبير عن نفس العملية:

  1. قم بفصل X إلى أعلى قوة للعدد 2 التي يحتويها (2 N ) والأرقام الثنائية المتبقية N.
  2. قم بترميز N + 1 باستخدام ترميز جاما إلياس .
  3. أضف الأرقام الثنائية المتبقية N إلى هذا التمثيل لـ N + 1.

لتمثيل رقمx{\displaystyle x}يستخدم إلياس دلتا (δ)⌊سجل2⁡(x)⌋+2⌊سجل2⁡(⌊سجل2⁡(x)⌋+1)⌋+1{\displaystyle \lfloor \log _{2}(x)\rfloor +2\lfloor \log _{2}(\lfloor \log _{2}(x)\rfloor +1)\rfloor +1}بتات. [ 1 ] : 200. يُعد هذا مفيدًا للأعداد الصحيحة الكبيرة جدًا، حيث يكون عدد بتات التمثيل المشفر الإجمالي أقل مما يمكن الحصول عليه باستخدام ترميز غاما إلياس ، وذلك بسببسجل2⁡(⌊سجل2⁡(x)⌋+1){\displaystyle \log _{2}(\lfloor \log _{2}(x)\rfloor +1)}جزء من التعبير السابق.

يبدأ الكود باستخدامγ′{\displaystyle \gamma '}بدلاً منγ{\displaystyle \gamma }:

رقمشمالن + 1ترميز دلتاالاحتمال الضمني
1 = 2 0011نصف
2 = 2 1 + 01201001/16
3 = 2 1 + 11201011/16
4 = 2 2 + 023011001/32
5 = 2 2 + 123011011/32
6 = 2 2 + 223011101/32
7 = 2 2 + 323011111/32
8 = 2 3 + 034001000001/256
9 = 2 3 + 134001000011/256
10 = 2 3 + 234001000101/256
11 = 2 3 + 334001000111/256
12 = 2 3 + 434001001001/256
13 = 2 3 + 534001001011/256
14 = 2 3 + 634001001101/256
15 = 2 3 + 734001001111/256
16 = 2 4 + 0450010100001/512
17 = 2 4 + 1450010100011/512

لفك تشفير عدد صحيح مشفر باستخدام خوارزمية دلتا إلياس:

  1. اقرأ وعدّ الأصفار من التدفق حتى تصل إلى أول صفر. سمِّ هذا العدد من الأصفار L.
  2. باعتبار الرقم 1 الذي تم الوصول إليه هو أول رقم في عدد صحيح، وقيمته 2L ، اقرأ الأرقام L المتبقية من هذا العدد. سمِّ هذا العدد N + 1 ، واطرح منه واحدًا لتحصل على N.
  3. ضع الرقم واحد في الموضع الأول من الناتج النهائي، والذي يمثل القيمة 2N .
  4. اقرأ الأرقام N التالية وأضفها إلى المعادلة .

مثال: 001010011

  1. صفران في بداية الرقم 001
  2. اقرأ بتتين إضافيتين، أي 00101
  3. فك تشفير N + 1 = 00101 = 5
  4. احصل على N = 5 − 1 = 4 بتات متبقية للرمز الكامل، أي 0011
  5. الرقم المشفر = 2 + 4 + 3 = 19

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

مثال على التعليمات البرمجية

التشفير

void eliasDeltaEncode ( const ByteBuffer & source , ByteBuffer & dest ) { IntReader intreader ( source ); BitWriter bitwriter ( dest ); while ( intreader . hasLeft ()) { int num = intreader . getInt ();int len ​​= 1 + std :: floor ( std :: log2 ( num ) ) ; int lengthOfLen = std :: floor ( std :: log2 ( len )); for ( int i = lengthOfLen ; i > 0 ; --i ) { bitwriter.outputBit ( 0 ) ; } for ( int i = lengthOfLen ; i > = 0 ; --i ) { bitwriter.outputBit ( ( len >> i ) & 1 ) ; } for ( int i = len - 2 ; i > = 0 ; --i ) { bitwriter.outputBit ( ( num >> i ) & 1 ) ; } }bitwriter.close ( ) ; intreader.close ( ) ; }

فك التشفير

void eliasDeltaDecode ( const ByteBuffer & source , ByteBuffer & dest ) { BitReader bitreader ( source ); IntWriter intwriter ( dest ); while ( bitreader.hasLeft ( ) ) { int num = 1 ; int len ​​= 1 ; int lengthOfLen = 0 ;// قد يكون هذا خطيرًا مع الملفات التالفة. while ( ! bitreader . inputBit ()) { ++ lengthOfLen ; } for ( int i = 0 ; i < lengthOfLen ; ++ i ) { len <<= 1 ; if ( bitreader . inputBit ()) { len |= 1 ; } } for ( int i = 0 ; i < len - 1 ; ++ i ) { num <<= 1 ; if ( bitreader . inputBit ()) { num |= 1 ; } }intwriter.putInt ( num ) ; // كتابة القيمة } bitreader.close ( ) ; intwriter.close ( ) ; }

التعميمات

لا يقوم ترميز دلتا إلياس بترميز الصفر أو الأعداد الصحيحة السالبة. إحدى طرق ترميز جميع الأعداد الصحيحة غير السالبة هي إضافة 1 قبل الترميز ثم طرح 1 بعد فك الترميز. إحدى طرق ترميز جميع الأعداد الصحيحة هي إنشاء تقابل ، يربط جميع الأعداد الصحيحة (0، 1، -1، 2، -2، 3، -3، ...) بالأعداد الصحيحة الموجبة تمامًا (1، 2، 3، 4، 5، 6، 7، ...) قبل الترميز. يمكن تنفيذ هذا التقابل باستخدام ترميز "ZigZag" من بروتوكول بافرز (لا يُخلط بينه وبين ترميز Zigzag ، ولا مع ترميز إنتروبيا JPEG zigzag ).

انظر أيضاً

مراجع

  1. 1 2 إلياس، بيتر (مارس 1975). "مجموعات الكلمات المشفرة العالمية وتمثيلات الأعداد الصحيحة". معاملات IEEE في نظرية المعلومات . 21 (2): 194-203 . doi : 10.1109/tit.1975.1055349 .

للمزيد من القراءة