ترميز النطاق

لنفترض أننا نريد ترميز الرسالة "AABA<EOM>"، حيث <EOM> هو رمز نهاية الرسالة. في هذا المثال، يُفترض أن المُفكِّك يعلم أننا نعتزم ترميز خمسة رموز بالضبط في النظام العشري (مما يسمح بـ 10 ^{^5} تركيبة مختلفة من الرموز ضمن النطاق [0, 100000) ) باستخدام التوزيع الاحتمالي {A: 0.60; B: 0.20; <EOM>: 0.20}. يقوم المُشفِّر بتقسيم النطاق [0, 100000) إلى ثلاثة نطاقات فرعية:

أ: [ 0، 60000) ب: [ 60000، 80000) <نهاية الصفحة>: [ 80000، 100000)

بما أن رمزنا الأول هو الحرف A، فإن ذلك يُقلّص نطاقنا الأولي إلى [0, 60000] . يُتيح لنا اختيار الرمز الثاني ثلاثة نطاقات فرعية من هذا النطاق. نعرضها بعد الحرف 'A' المُشفّر مسبقًا.

AA: [ 0، 36000) AB: [ 36000، 48000) A<EOM>: [ 48000، 60000)

بعد ترميز رمزين، أصبح نطاقنا الآن [0، 36000] ، ويؤدي الرمز الثالث إلى الخيارات التالية:

AAA: [ 0, 21600) AAB: [ 21600, 28800) AA<EOM>: [ 28800, 36000)

هذه المرة، الخيار الثاني من بين خياراتنا الثلاثة هو الذي يُمثل الرسالة التي نريد تشفيرها، ويصبح نطاقنا [21600، 28800] . قد يبدو تحديد النطاقات الفرعية أصعب في هذه الحالة، ولكنه في الواقع ليس كذلك: يمكننا ببساطة طرح الحد الأدنى من الحد الأعلى لنحدد أن هناك 7200 رقمًا في نطاقنا؛ وأن أول 4320 رقمًا منها تُمثل 0.60 من المجموع، والـ 1440 رقمًا التالية تُمثل 0.20 التالية، والـ 1440 رقمًا المتبقية تُمثل 0.20 المتبقية من المجموع. بإضافة الحد الأدنى مرة أخرى، نحصل على نطاقاتنا.

AABA: [21600، 25920) AABB: [25920، 27360) AAB<EOM>: [27360، 28800)

وأخيرًا، بعد تضييق نطاقنا إلى [21600، 25920] ، لم يتبقَّ لدينا سوى رمز واحد للترميز. وباستخدام نفس الأسلوب السابق لتقسيم النطاق بين الحد الأدنى والحد الأعلى، نجد أن النطاقات الفرعية الثلاثة هي:

AABAA: [21600، 24192) AABAB: [24192، 25056) AABA<EOM>: [25056، 25920)

وبما أن <EOM> هو رمزنا الأخير، فإن نطاقنا النهائي هو [25056, 25920] . ولأن جميع الأعداد الصحيحة المكونة من خمسة أرقام والتي تبدأ بـ "251" تقع ضمن نطاقنا النهائي، فإن أحد البادئات المكونة من ثلاثة أرقام التي يمكننا إرسالها هو الذي سينقل رسالتنا الأصلية بوضوح. (وجود ثماني بادئات من هذا النوع يشير إلى وجود بعض أوجه القصور، والتي نتجت عن استخدامنا للأساس 10 بدلاً من الأساس 2 ).

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

int low = 0 ; int range = 100000 ;void Run () { Encode ( 0 , 6 , 10 ); // A Encode ( 0 , 6 , 10 ); // A Encode ( 6 , 2 , 10 ); // B Encode ( 0 , 6 , 10 ); // A Encode ( 8 , 2 , 10 ); // <EOM>// إصدار الأرقام النهائية - انظر أدناه while ( range < 10000 ) EmitDigit ();low += 10000 ; EmitDigit (); }void EmitDigit () { Console . Write ( low / 10000 ); low = ( low % 10000 ) * 10 ; range *= 10 ; }void Encode ( int start , int size , int total ) { // اضبط النطاق بناءً على فاصل الرموز range /= total ; low += start * range ; range *= size ;// تحقق مما إذا كان الرقم الموجود في أقصى اليسار هو نفسه في جميع أنحاء النطاق بينما ( الرقم الأدنى / 10000 == ( الرقم الأدنى + النطاق ) / 10000 ) EmitDigit ();// إعادة ضبط النطاق - انظر السبب أدناه إذا كان ( النطاق < 1000 ) { إرسال رقم (); إرسال رقم (); النطاق = 100000 - الحد الأدنى ; } }

لإتمام العملية، قد نحتاج إلى إضافة بعض الأرقام. lowربما يكون الرقم العلوي صغيرًا جدًا، لذا نحتاج إلى زيادته، ولكن يجب التأكد من عدم تجاوزه الحد المسموح به low+range. لذلك، علينا أولًا التأكد من rangeأن هذا الحد كبير بما يكفي.

// إخراج الأرقام النهائية بينما ( النطاق < 10000 ) EmitDigit ();low += 10000 ; EmitDigit ();

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

على سبيل المثال، تخيل أن دفق الإدخال قد أوصل المُشفِّر إلى الفترة المفتوحة من اليمين [59888، 60188]، أي [59888، 60188] low = 59888. range = 300تكمن الحيلة في تضييق هذه الفترة إلى [59888، 60000] = [ 59888 ، 59999 ]، مما يسمح للمُشفِّر بإصدار رقمين من أقصى اليسار من low[598800، 99999]، ثم إعادة ضبط الفترة إلى [88800، 99999] = [88800، 100000]، أي [88800، 100000 low = 88800] range = 100000 - low.

سيتبع جهاز فك التشفير نفس الخطوات، لذا سيعرف متى يحتاج إلى القيام بذلك للحفاظ على التزامن.

// يُوضع هذا السطر قبل نهاية دالة Encode() أعلاه مباشرةً. إذا كان ( النطاق < 1000 ) { EmitDigit (); EmitDigit (); النطاق = 100000 - الحد الأدنى ؛ }

استُخدم النظام العشري في هذا المثال، لكن التطبيق العملي سيستخدم النظام الثنائي، مع النطاق الكامل لنوع بيانات الأعداد الصحيحة الأصلي. بدلاً من ذلك، 10000ستستخدم 1000على الأرجح ثوابت سداسية عشرية مثل 0x1000000و 0x10000. بدلاً من إرسال رقم واحد في كل مرة، سترسل بايتًا واحدًا في كل مرة، وستستخدم عملية إزاحة بايت بدلاً من الضرب في 10.

تستخدم عملية فك التشفير نفس الخوارزمية تمامًا، مع إضافة ميزة تتبع codeالقيمة الحالية المكونة من الأرقام المقروءة من وحدة الضغط. بدلًا من إخراج الرقم العلوي، lowيتم تجاهله، ولكن يتم أيضًا إزاحة الرقم العلوي codeوإدخال رقم جديد مقروء من وحدة الضغط. استخدم AppendDigitما يلي بدلًا من EmitDigit.

int code = 0 ; int low = 0 ; int range = 1 ;void InitializeDecoder () { AppendDigit (); // في هذا المثال البرمجي، نحتاج إلى واحد فقط من هذه الأسطر AppendDigit (); AppendDigit (); AppendDigit (); AppendDigit (); }void AppendDigit () { code = ( code % 10000 ) * 10 + ReadNextDigit (); low = ( low % 10000 ) * 10 ; range *= 10 ; }void Decode ( int start , int size , int total ) // فك التشفير هو نفسه التشفير مع استبدال EmitDigit بـ AppendDigit { // اضبط النطاق بناءً على فاصل الرموز range /= total ; low += start * range ; range *= size ;// تحقق مما إذا كان الرقم الموجود في أقصى اليسار هو نفسه في جميع أنحاء النطاق بينما ( الرقم الأدنى / 10000 == ( الرقم الأدنى + النطاق ) / 10000 ) أضف رقمًا ();// إعادة ضبط النطاق - انظر السبب أدناه إذا كان ( النطاق < 1000 ) { إضافة رقم (); إضافة رقم (); النطاق = 100000 - الحد الأدنى ; } }

من أجل تحديد فترات الاحتمالية التي يجب تطبيقها، يحتاج جهاز فك التشفير إلى النظر في القيمة الحالية codeضمن الفترة [low, low+range) وتحديد الرمز الذي يمثله هذا.

void Run () { int start = 0 ; int size ; int total = 10 ; InitializeDecoder (); // يجب أن يكون النطاق/المجموع أكبر من 0 while ( start < 8 ) // التوقف عند استلام EOM { int v = GetValue ( total ); // في أي نطاق رمزي يوجد الكود؟ switch ( v ) // تحويل القيمة إلى رمز { case 0 : case 1 : case 2 : case 3 : case 4 : case 5 : start = 0 ; size = 6 ; Console.Write ( " A" ) ; break ; case 6 : case 7 : start = 6 ; size = 2 ; Console.Write ( "B" ) ; break ; default : start = 8 ; size = 2 ; Console.WriteLine ( " " ) ; } Decode ( start , size , total ) ; } }دالة GetValue ( عدد صحيح total ) { return ( الرمز - الحد الأدنى ) / ( المدى / الإجمالي )؛ }

بالنسبة للمثال AABA<EOM> أعلاه، فإن هذا سيعيد قيمة في النطاق من 0 إلى 9. القيم من 0 إلى 5 ستمثل A، و6 و7 ستمثل B، و8 و9 ستمثل <EOM> .