كمية متغيرة الطول

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

الكمية ذات الطول المتغير ( VLQ ) هي شفرة عالمية تُستخدم في تطبيقات متنوعة منذ عام 1983. تستخدم هذه الشفرة سلسلة من البايتات الثنائية (ثمانية بتات ) لتمثيل عدد صحيح غير مُوَقَّع كبير الحجم. تُعتبر VLQ في جوهرها تمثيلًا أساسه 128 لعدد صحيح غير مُوَقَّع، مع إضافة بت ثامن لكل مجموعة من سبعة بتات للدلالة على استمرارية سلسلة البايتات. ترتيب البايتات في VLQ هو الترتيب الكبير (Big Endian) ، أي أن البتات الأكثر أهمية تُرسَل أولًا في سلسلة البايتات. يوجد أيضًا نوع آخر يُسمى LEB128، وهو مطابق تمامًا لـ VLQ باستثناء ترتيب البايتات .

إنّ ربط القيم الصحيحة برموز VLQ ليس فريدًا، إذ يمكن أن تكون جميع بتات الحمولة السبعة في البايتات الأكثر أهمية مساويةً للصفر (إلا إذا كان استخدام بايتات مساوية لـ 0x80 محظورًا في التطبيق). وبالتالي، يمكن تمثيل عدد صحيح باستخدام عدد بايتات أكبر من الحد الأدنى اللازم. يُزيل أحد التعديلات المستخدمة في Git هذا التكرار ويُوسّع نطاق الأرقام التي يمكن تمثيلها بكل طول رمز متعدد البايتات.

توجد أيضًا اختلافات لدعم الأعداد الصحيحة الموقعة، باستخدام بت الإشارة مع تمثيل الإشارة والمقدار أو تمثيل المكمل الثنائي .

التطبيقات والتاريخ

يُعرف ضغط Base-128 بالعديد من الأسماء - VB (Variable Byte)، VByte ، Varint ، VInt ، EncInt ، إلخ. [ 1 ] 

تم تعريف كمية متغيرة الطول ( VLQ ) لاستخدامها في تنسيق ملف MIDI القياسي ، [ 2 ] الإصدار 1.0 الذي تم نشره في عام 1983. كما يتم استخدامه أيضًا في تنسيق الموسيقى القابل للتوسيع (XMF) اللاحق ، والذي تم نشره لأول مرة في عام 2001.

يُستخدم نظام Base-128 أيضًا في ترميز ASN.1 BER لترميز أرقام العلامات ومعرّفات الكائنات (نُشر لأول مرة عام 1984). [ 3 ] كما يُستخدم في بيئة WAP ، حيث يُطلق عليه اسم عدد صحيح غير مُوقّع ذو طول متغير أو uintvar . يُعرّف RFC  6256 نفس التنسيق ويُشير إليه باسم قيمة عددية ذاتية التحديد أو SDNV . [ 4 ] يُعرّف تنسيق تصحيح الأخطاء DWARF [ 5 ] صيغةً مُختلفة تُسمى LEB128 (أو ULEB128 للأعداد غير المُوقّعة)، حيث تُرمّز المجموعة الأقل أهمية المكونة من 7 بتات في البايت الأول، بينما تُرمّز البتات الأكثر أهمية في البايت الأخير (أي أنه يُشابه VLQ في نظام little-endian). تستخدم بروتوكولات جوجل تنسيقًا مشابهًا لتمثيل القيم العددية بشكل مضغوط، [ 6 ] كما هو الحال في تنسيق أوراكل المحمول للكائنات (POF) [ 7 ] وإطار عمل مايكروسوفت .NET "العدد الصحيح المشفر 7 بت" في فئتي BinaryReader و BinaryWriter . [ 8 ] 

كما يُستخدم على نطاق واسع في متصفحات الويب لرسم خرائط المصدر - التي تحتوي على الكثير من عمليات ربط أرقام الأسطر والأعمدة الصحيحة - للحفاظ على حجم الخريطة عند الحد الأدنى. [ 9 ]

تستخدم الأعداد الصحيحة ذات العرض المتغير في LLVM مبدأً مشابهًا. تكون أجزاء التشفير بنظام little-endian، ولا يشترط أن يكون  حجمها 8 بتات. يصف توثيق LLVM حقلًا يستخدم أجزاءً بحجم 4 بتات، حيث يتكون كل جزء من  بت واحد للاستمرار و3  بتات للحمولة. [ 10 ]

فوائد

تتمثل الفوائد الرئيسية لترميز VLQ في صغر حجمه ومرونته لدعم أي نطاق من القيم.

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

في الوقت نفسه، يمكن لترميز VLQ تمثيل أعداد صحيحة كبيرة جدًا، على عكس تمثيلات طول الكلمة الثابتة مثل البايتات ذات 8 بت، والكلمات ذات 16 بت، والأعداد الصحيحة ذات 32 بت، أو الأعداد الصحيحة الطويلة ذات 64 بت. لا يوجد حد أقصى متأصل لنطاق القيم التي يمكن تمثيلها بواسطة ترميز VLQ. في المقابل، عادةً ما يكون لتمثيلات الأعداد الصحيحة ذات الطول الثابت نطاق غير كافٍ من القيم القابلة للتمثيل إذا تم استخدام طول كلمة قصير، أو قد تستخدم كمية كبيرة جدًا من البيانات لتمثيل كل عدد صحيح إذا تم استخدام طول كلمة أطول.

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

الهيكل العام

يفترض الترميز وجود ثمانية بتات (بايت مكون من 8 بتات) حيث يتم حجز البت الأكثر أهمية (MSB)، والمعروف أيضًا باسم بت الإشارة ، للإشارة إلى ما إذا كانت هناك ثمانية بتات أخرى من نوع VLQ تليها.

ثمانية VLQ
76543210
2 72 62 52 42 32 22 12 0
أب ن

إذا كانت قيمة A تساوي 0، فهذا هو آخر ثمانية بتات من نوع VLQ للعدد الصحيح. أما إذا كانت قيمة A تساوي 1، فسيتبعها ثمانية بتات أخرى من نوع VLQ.

يمثل B عددًا مكونًا من 7 بتات [0x00, 0x7F]، و n هو موضع ثماني بتات VLQ حيث B 0 هو الأقل أهمية . يتم ترتيب ثمانيات VLQ من الأكثر أهمية إلى الأقل في التدفق.

المتغيرات

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

ترميز متغير المجموعة

طوّرت جوجل ترميز Group Varint Encoding (GVE) بعد ملاحظة أن ترميز VLQ التقليدي يُسبب العديد من عمليات تفرع المعالجة المركزية أثناء فك الضغط. يستخدم GVE بايتًا واحدًا كرأس لأربع قيم uint32 متغيرة الطول. يحتوي بايت الرأس على أربعة أرقام ثنائية (2 بت) تُمثل طول التخزين لكل قيمة من القيم الأربع التالية uint32. يُلغي هذا التصميم الحاجة إلى فحص وإزالة بتات استمرار VLQ. يمكن نسخ بايتات البيانات مباشرةً إلى وجهتها. يُقلل هذا التصميم من عمليات تفرع المعالجة المركزية ، مما يجعل GVE أسرع من VLQ على وحدات المعالجة المركزية الحديثة ذات البنية الأنبوبية. [ 11 ]

يُعدّ PrefixVarint تصميمًا مشابهًا، لكن بحد أقصى uint64. ويُقال إنه "اُخترع عدة مرات بشكل مستقل". [ 12 ] ويمكن تحويله إلى نسخة متسلسلة ذات عدد لا نهائي من الاستمراريات.

الأرقام الموقعة

بت الإشارة

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

في تنسيق البيانات الخاص بحزم Unreal المستخدمة في محرك Unreal Engine ، يُستخدم نظام ترميز كمي متغير الطول يُسمى المؤشرات المدمجة [ 13 ] . والفرق الوحيد في هذا الترميز هو أن أول ثمانية بتات في نظام VLQ تحتوي على البت السابع محجوزًا للإشارة إلى ما إذا كان العدد الصحيح المُرمّز موجبًا أم سالبًا. وتتبع أي ثمانية بتات متتالية في نظام VLQ البنية العامة نفسها.

توقيع رائع بجودة منخفضة للغاية
أول ثمانية VLQثمانيات أخرى منخفضة الجودة
7654321076543210
2 72 62 52 42 32 22 12 02 72 62 52 42 32 22 12 0
Sأب ٠أب ن ( ن > 0)

إذا كانت قيمة S تساوي صفرًا، فإن VLQ يمثل عددًا صحيحًا موجبًا. أما إذا كانت قيمة S تساوي واحدًا، فإن VLQ يمثل عددًا سالبًا .

إذا كانت قيمة A تساوي 0، فهذا هو آخر ثمانية بتات من نوع VLQ للعدد الصحيح. أما إذا كانت قيمة A تساوي 1، فسيتبعها ثمانية بتات أخرى من نوع VLQ.

يمثل B الجزء الرقمي المراد ترميزه، و n هو موضع ثماني VLQ حيث B 0 هو الأقل أهمية . يتم ترتيب ثمانيات VLQ من الأقل أهمية إلى الأقل في التدفق.

ترميز متعرج

هناك طريقة بديلة لترميز الأعداد السالبة وهي استخدام البت الأقل أهمية للإشارة. يُستخدم هذا الأسلوب بشكل خاص في بروتوكول جوجل بافرز، ويُعرف باسم ترميز الزجزاج للأعداد الصحيحة الموقعة . [ 14 ] يمكن ترميز الأعداد بحيث يُقابل الصفر المُرمّز 0، والواحد -1، والعشرة 10، والواحد 11 -2 ، والمئة 2، وهكذا: يتناوب العد التصاعدي بين الأعداد غير السالبة (بدءًا من الصفر) والأعداد السالبة (لأن كل خطوة تُغير البت الأقل أهمية، وبالتالي الإشارة)، ومن هنا جاء اسم "ترميز الزجزاج". عمليًا، يتم تحويل العدد الصحيح كما هو الحال مع الأعداد الصحيحة ذات k(n << 1) ^ (n >> k - 1) بت الثابتة . وهذا يُؤدي إلى:

  • ربط الأعداد الموجبة بمضاعفاتها للعدد اثنين: n << 1يكافئ n x 2. مثال: يتم ربط 0، 1، 2، 3 بـ 0، 2، 4، 6.
  • ربط الأعداد السالبة بالأعداد الفردية الموجبة. العدد الصحيح السالب ذو 32 بت له شكل 1xxx...، لذا n >> 31يتم ملء جميع البتات بالرقم 1. عملية XOR لعدد سالب بنظام المتمم الثنائي مع جميع البتات 1 تجعله موجبًا وتطرح منه 1. وتذكر أننا ضربنا العدد الأصلي في 2 باستخدام n << 1. لذا يتم ربط -1، -2، -3 بالأعداد 1، 3، 5.

متمم الاثنين

يستخدم نظام LEB128 نظام المتمم الثنائي لتمثيل الأعداد الموقعة. في هذا النظام، تُشفّر n  بت نطاقًا من -2n إلى 2n -  1  ، وتبدأ جميع الأعداد السالبة بالرقم 1 في البت الأكثر أهمية. في نظام LEB128 المُوَقَّع، يُوسَّع المدخل بحيث يكون طوله من مضاعفات 7  بت. ومن ثمّ، تستمر عملية التشفير كالمعتاد. [ 15 ]

في LEB128، يتم ترتيب التدفق من الأقل أهمية إلى الأول. [ 15 ]

إزالة التكرار

باستخدام ترميز VLQ الموصوف أعلاه، يمكن ترميز أي رقم يمكن ترميزه باستخدام N بايت بأكثر من N بايت ببساطة عن طريق إضافة 0x80 بايت إضافية كحشو أصفار. على سبيل المثال، يمكن ترميز الرقم العشري 358 باستخدام VLQ 0x8266 (بايتين)، أو يمكن ترميز الرقم 0358 باستخدام VLQ 0x808266 (ثلاثة بايتات)، أو يمكن ترميز الرقم 00358 باستخدام VLQ 0x80808266 (أربعة بايتات)، وهكذا.

مع ذلك، فإن تنسيق VLQ المستخدم في Git [ 16 ] يزيل هذا التكرار في البداية ويوسع نطاق تمثيل VLQs الأقصر بإضافة إزاحة إلى VLQs المكونة من 2 أوكتيت أو أكثر، بحيث تصبح أصغر قيمة ممكنة لـ VLQ مكون من ( N  +  1) أوكتيت أكبر بواحد بالضبط من أكبر قيمة ممكنة لـ VLQ مكون من N أوكتيت. على وجه الخصوص، بما أن VLQ المكون من 1 أوكتيت يمكنه تخزين قيمة قصوى تبلغ 127، فإن أصغر VLQ مكون من 2 أوكتيت (0x8000) يُخصص له القيمة 128 بدلاً من 0. وعلى العكس من ذلك، فإن أكبر قيمة لـ VLQ مكون من 2 أوكتيت (0xFF7F) هي16511 بدلاً من مجرد16383. وبالمثل، فإن الحد الأدنى لقيمة VLQ المكونة من 3 بايتات (0x808000) هو 16383 .16512 بدلاً من الصفر، مما يعني أن الحد الأقصى لـ VLQ المكون من 3 بايتات (0xFFFF7F) هو2 113 663 بدلاً من مجرد2 097 151 .

وبهذه الطريقة، يوجد ترميز واحد فقط لكل عدد صحيح، مما يجعل هذا ترقيمًا تقابليًا أساسه 128 .

أمثلة

رسم توضيحي لكيفية التحويل106903 من التمثيل العشري إلى تمثيل uintvar

إليك مثال محلول للعدد العشري 137 :

  • قم بتمثيل القيمة بالصيغة الثنائية (على سبيل المثال، 137 كـ 10001001)
  • قسّم العدد إلى مجموعات من 7 بتات بدءًا من البت الأقل أهمية (مثلاً 137 كـ 0000001  0001001). هذا يُعادل تمثيل العدد في النظام العددي ذي الأساس  128.
  • خذ أقل 7 بتات، وهذا يعطيك البايت الأقل أهمية ( 00001001 )  . يأتي هذا البايت في النهاية.
  • بالنسبة لجميع المجموعات الأخرى المكونة من 7 بتات (في المثال، 000  0001)، نضبط البت الأكثر أهمية (MSb) على 1 (مما يعطي 1 000  0001 في مثالنا). وبالتالي، يصبح العدد 137 هو 1 000  0001 0 000 1001، حيث تمثل البتات المكتوبة بخط غامق بتات مضافة. تشير هذه البتات المضافة إلى ما إذا كان هناك بايت آخر يليها أم لا. لذا، بحسب التعريف، سيكون البايت الأخير من عدد صحيح متغير الطول هو 0 كبت الأكثر أهمية (MSb) .  

هناك طريقة أخرى للنظر إلى هذا وهي تمثيل القيمة في الأساس 128 ثم تعيين البت الأكثر أهمية لجميع الأرقام باستثناء الرقم الأخير في الأساس 128 إلى 1.

يقدم معيار تنسيق ملف MIDI المزيد من الأمثلة: [ 2 ] [ 17 ]

عدد صحيح (عشري)عدد صحيح (ثنائي)كمية متغيرة الطول (ثنائية)عدد صحيح (سداسي عشري)كمية متغيرة الطول (سداسي عشري)
0
00000000 00000000 00000000 00000000
 00000000
00000000٠٠
127
00000000 00000000 00000000 01111111
 01111111
0000007F7F
128
00000000 00000000 00000000 10000000
 10000001 00000000
0000008081 00
8192
00000000 00000000 00100000 00000000
 11000000 00000000
00002000C0 00
16383​
00000000 00000000 00111111 11111111
 11111111 01111111
00003FFFFF 7F
16384​
00000000 00000000 01000000 00000000
 10000001 10000000 00000000
0000400081 80 00
2097151​​
00000000 00011111 11111111 11111111
 11111111 11111111 01111111
001FFFFFFF FF 7F
2097152​​
00000000 00100000 00000000 00000000
10000001 10000000 10000000 00000000
0020000081 80 80 00
134 217 728
00001000 00000000 00000000 00000000
11000000 10000000 10000000 00000000
08000000C0 80 80 00
268 435 455
00001111 11111111 11111111 11111111
11111111 11111111 11111111 01111111
0FFFFFFFFFF FF FF 7F

مراجع

  1. ↑ جيانغوو وانغ؛ تشونبين لين؛ يانيس باباكونستانتينو؛ ستيفن سوانسون. "دراسة تجريبية لضغط الصور النقطية مقابل ضغط القوائم المعكوسة". مؤرشف بتاريخ 7 ديسمبر 2019 في أرشيف الإنترنت . 2017. doi : 10.1145/3035918.3064007 .
  2. 1 2 تنسيق ملف MIDI: كميات متغيرة .
  3. ↑ «توصية الاتحاد الدولي للاتصالات X.690 (ISO/IEC 8825-1): تكنولوجيا المعلومات - قواعد ترميز ASN.1: مواصفات قواعد الترميز الأساسية (BER) وقواعد الترميز المتعارف عليها (CER) وقواعد الترميز المميزة (DER)» . الاتحاد الدولي للاتصالات . فبراير 2021.
  4. ↑ إيدي، ويسلي م.؛ ديفيز، إلوين (مايو 2011). استخدام القيم العددية ذاتية التحديد في البروتوكولات . فريق عمل أبحاث الإنترنت . doi : 10.17487/RFC6256 . ISSN 2070-1721 . RFC 6256 . معلوماتي.
  5. ↑ معيار الأقزام .
  6. ↑ بروتوكول جوجل بافرز .
  7. ↑ تم أرشفة تنسيق الكائنات المحمولة من أوراكل (POF) في 27-12-2013 على موقع Wayback Machine .
  8. ↑ طريقة System.IO.BinaryWriter.Write7BitEncodedInt(int) وطريقة System.IO.BinaryReader.Read7BitEncodedInt() .
  9. ↑ مقدمة إلى خرائط مصدر جافا سكريبت .
  10. ↑ "تنسيق ملف LLVM Bitcode"، قسم "أعداد صحيحة ذات عرض متغير" . تاريخ الوصول: 1 أكتوبر 2019.
  11. ↑ جيف دين. "تحديات بناء أنظمة استرجاع المعلومات واسعة النطاق" (ملف PDF) . ص 58. تاريخ الاسترجاع: 30 مايو 2020 . 
  12. ^ أولسن ، جاكوب ستوكلوند (31 مايو 2020). "ستوكلوند/فارينت" . مؤرشفة من الأصلي في 19 نوفمبر 2020 . تم الاسترجاع في 9 يوليو 2020 .
  13. ↑ "حزم غير واقعية" . 21-07-1999. مؤرشف من الأصل في 20-08-2010 . تم الاسترجاع في 29-08-2021 .
  14. ↑ بروتوكول بافرز: التشفير: الأعداد الصحيحة الموقعة .
  15. 1 2 مجموعة المعايير الحرة (ديسمبر 2005). "مواصفات تنسيق معلومات تصحيح الأخطاء DWARF، الإصدار 3.0" (ملف PDF) . صفحة 70. تاريخ الاسترجاع: 19 يوليو 2009 . 
  16. ↑ "Git – نظام تحكم في الإصدارات سريع وقابل للتوسع وموزع" . 28 أكتوبر 2021.
  17. ↑ مواصفات تنسيق ملفات MIDI القياسية 1.1