اسم مخطط الترميز الثنائي للأرقام الصحيحة

Question

لقد وجدت مرة واحدة على ويكيبيديا تقنية لطيفة لترميز $ k \ in (2 ^ {n-1}، 2 ^ n) $ الأرقام الصحيحة الموزعة بشكل موحد معأقل ثم $ \ log_2n $ متوسط البتات / الرمز، بفضل بسيطة لحساب رمز طول المتغير.أساسا تستخدم $ \ log_2n $ لبعض الرموز و $ \ log_2n - 1 $ لبعض الآخرين.

لسوء الحظ، فشلت إلي كل ما عندي من googling.أذكر شيئا مشابها ل "طول المتغير ثنائي"، لكنني أظل إنهاء VLQ وهو وحش مختلف.منذ أن أعرف ذاكرتك أفضل من الألغام، هل يمكنك مساعدتي؟

Answer 1

تم وصف فكرة التقنية بشكل مثالي في إجابة Filmus Yuval.حتى لو كان مختلفا قليلا، فإنه يسمى ترميز ثنائي مقطوع في ويكيبيديا.لم أستطع العثور على مصدر أصلي لذلك، بصرف النظر عن ذكر في براءة اختراع في هذا كتاب ، أو في هذا google api

Answer 2

افترض $ k= 2 ^ ^ {n-1} + t ، حيث $ 0 \ leq t <2 ^ {n-1} $ . استخدم ما يلي لتشفير $ z \ in \ {0، \ ldots، k-1 \} $ :

• إذا $ z <2 ^ {n-1} {span> ثم ترميز $ z $ $ (n-1) $ ترميز -bit.
• li> خلاف ذلك، اكتب $ z= 2 ^ ^ {n-1} -t + 2 \ delta + \ epsilon $ ، حيث $ \ delta \ in \ {0، \ LDOTS، T-1 \} $ و $ \ epsilon \ in \ {0،1 \} $ . تشفير $ z $ في $ (n-1) $ (n-1) $ الترميز $ 2 ^ ^ {n-1} -t + \ delta $ تليها $ \ Epsilon $ .

هنا هو مثال. دع $ k= 11= 2 ^ 3 + 3 $ . الترميز هو كما يلي:

• $ 0 \ إلى 000 $ .
• $ 1 $ \ 001 $ .
• $ 2 \ to 010 $ .
• 3 دولارات $ 011 $ .
• $ 4 \ to 100 $ .
• $ 5 \ to 1010 $ .
• $ 6 \ to 1011 $ .
• $ 7 \ to 1100 $ .
• 8 دولارات $ 1101 $ .
• 9 دولارات $ .
• 10 دولارات (إلى 1111 دولارا) .