مرجع
آخر الزيارات

ترميز هوفمان المتكيف

610 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: طريقة ترميز هوفمان المتكيف (يسمى كذلك ترميز هوفمان الديناميكي) وهو عبارة عن طريقة الترميز المتكيف Adaptive coding الذي يعتمد على ترميز هوفمان. في هذه المقالة قسمان: «خوارزميات ترميز هوفمان المتكيف» و«خوارزمية فيتر Vitter algorithm».
المحتويات
  1. خوارزميات ترميز هوفمان المتكيف
  2. خوارزمية فيتر Vitter algorithm

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

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

خوارزميات ترميز هوفمان المتكيف

هناك الكثير من الخوارزميات من ابرزها "FGK" وخوارزمية فيتر.

خوارزمية فيتر Vitter algorithm

علاوةً على ذلك، - هنا أصبح الرمز الثنائي لحرف "b" هو 1 , و "a" هو 01 , وهو ما يعكس معدل تكرارهما.

شرح المثال:

في هذا الإطار، 4- ان لم تكن هذه العقدة هي الجذر، اذهب إلى الاب وبعدها اذهب إلى الخطوة رقم 2 , اما إذا كانت الجذر، انتهت.

  • عندما نقوم بنقل رمز NYT , يجب علينا إحالة رمز ثنائي له وليتم تعميمه.
  • كل رمز "symbol" مدخل من قبل في الشجرة، يجب علينا احالة رمز "code" لاستدعائه.
  • لكل رمز "symbol" يتم نقله من المرسل أو المتلقي، يجب ان يتخد هذه الإجراءات

3- زيادة الوزن للعقدة الحالية.

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

من جانب آخر، 2- إذا كانت هذه العقدة لا تمتلك اعلى رقم في الكتلة، يجب المبادلة بينها وبين العقدة التي تمتلك اعلى رقم، ما عدا عقدة الجذر.

-تبدأ شجرة فارغة.

كذلك، فمثلًا إذا كان "A" هو اب للعقدة "B" و "C" هي أحد أبناء "B", فإن وزن "A"> وزن "B"> وزن "C".

-أصبح الرمز الثنائي ل "a" المرتبط بعقدة 255 هو 1

من جانب آخر، نحن بحاجة الآن لطريقة أعم ومباشرة لنقل الرمز الذي «لم يرسل حتى الآن» (NYT) مثلًا نقل رمز ثنائي لكل رمز في الابجدية.

ومن ناحية أخرى، -لنقل ثالث حرف "b" وهو 01 , علينا الذهاب إلى العقدة 253 وهنا نجد انه هناك كتلة من العقد تمتلك نفس الوزن وهو "1" والرقم الأكبر في هذه الكتلة هو 255 , لذلك نقوم بالمبادلة بين الوزن والرمز للعقدة 253 مع 255 إلى جانب زيادة الوزن وبعدها الذهاب إلى الجذر وزيادة وزنه.

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

من جهة ثانية، ملاحظة: المبادلة بين العقد تعني المبادلة بالاوزان والرموز المقابلة، ولكن ليس الأرقام.

إضافةً إلى ذلك، 1- إذا كان الرمز الحالي هو NYT , نقوم بإضافة ابنين تابعين لل NYT بحيث يكون واحد منهما هو NYT الجديد والاخر يكون للرمز المدخل، والوزن يتم زيادته للرمز المدخل و NYT القديمة، ومن ثم الانتقال إلى الخطوة رقم 4 , وإذا لم تكن NYT يجب الذهاب إلى العقدة الطرفية.

مجموعة العقد التي تمتلك اوزان مشابهة تشكل «كتلة».

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

وفي هذا الصدد، التشفير وفك التشفير يبدأ بالجذر (root) الذي يملك اعلى رقم. وأيضا بالبداية تكون العقدة البدائية للشجرة هي (NYT).

في هذا الإطار، وبالتالي فان الوزن هو عد الرموز المنقولة التي ترتبط مع ابناءها مت تلك العقدة.

وفي السياق ذاته، -لنقل أول حرف "a" نقوم بإنزال عقدتين من NYT القديمة: 255 و 254 مع زيادة وزن الجذر ليصبح "1"

وفي هذا الصدد، -لنقل تاني حرف وهو "b" إلى الرمز الثنائي نقوم بإنزال عقدتين (أبناء) لل NYT هما 252 خاصة ب NYT الجديدة و 253 لحرف "b" مع زيادة وزن 254 و253 والجذر واصبح هنا الرمز الثنائي ل "b" هو 01

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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