تم النشر اليوم 06-12-2025 | ترميز هوفمان المتكيف ترميز ديفيد هوفمان هوفمان المتكيف

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

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

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

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

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

بداية يتم تمثيل الرمز كبنية شجرة حيث ان كل عقدة لها وزن معين و رقم فريد من نوعه ويتم وضع الأرقام من الأعلى إلى الأسفل ومن اليمين إلى اليسار. الوزن يجب الاخذ بعين الاعتبار بشأن وضع الأوزان عند الاخوة من نفس الاب , حيث ان القاعدة تنص على انه يجب ان توضع العقدة حسب تسلسل متناقص للأوزان مع العقدة المجاورة لها من شقيقاتها . فعلى سبيل المثال إذا كان A هو اب للعقدة B و C هي أحد ابناء B , فإن وزن A > وزن B > وزن C . وبالتالي فان الوزن هو عد الرموز المنقولة التي ترتبط مع ابناءها مت تلك العقدة . مجموعة العقد التي تمتلك اوزان مشابهة تشكل كتلة . للحصول على رمز لكل عقدة , في حالة ان الشجرة ثنائية , نقوم فقط بتتبع الطريق من الجذر إلى العقدة المطلوبة وذلك من خلال وضع رقم 1 اذا ذهبنا إلى الابن الموجود على اليمين و 0 اذا ذهبنا إلى الابن الموجود على اليسار . نحن بحاجة الآن لطريقة أعم ومباشرة لنقل الرمز الذي لم يرسل حتى الآن (NYT) على سبيل المثال نقل رمز ثنائي لكل رمز في الابجدية . التشفير وفك التشفير يبدأ بالجذر (root) الذي يملك اعلى رقم . وأيضا بالبداية تكون العقدة البدائية للشجرة هي (NYT). عندما نقوم بنقل رمز NYT , يجب علينا إحالة رمز ثنائي له و ليتم تعميمه . كل رمز symbol مدخل من قبل في الشجرة , يجب علينا احالة رمز code لاستدعائه .

لكل رمز symbol يتم نقله من المرسل او المتلقي , يجب ان يتخد هذه الإجراءات

1- اذا كان الرمز الحالي هو NYT , نقوم بإضافة ابنين تابعين لل NYT بحيث يكون واحد منهما هو NYT الجديد و الاخر يكون للرمز المدخل , والوزن يتم زيادته للرمز المدخل و NYT القديمة , ومن ثم الانتقال إلى الخطوة رقم 4 , واذا لم تكن NYT يجب الذهاب إلى العقدة الطرفية . 2- اذا كانت هذه العقدة لا تمتلك اعلى رقم في الكتلة , يجب المبادلة بينها وبين العقدة التي تمتلك اعلى رقم , ما عدا عقدة الجذر . 3- زيادة الوزن للعقدة الحالية . 4- ان لم تكن هذه العقدة هي الجذر , اذهب إلى الاب وبعدها اذهب إلى الخطوة رقم 2 , اما اذا كانت الجذر , انتهت. ملاحظة المبادلة بين العقد تعني المبادلة بالاوزان والرموز المقابلة , ولكن ليس الأرقام . adaptive huffman.png Developing adaptive Huffman tree شرح المثال -تبدأ شجرة فارغة. -لنقل اول حرف a نقوم بإنزال عقدتين من NYT القديمة 255 و 254 مع زيادة وزن الجذر ليصبح 1 -أصبح الرمز الثنائي ل a المرتبط بعقدة 255 هو 1 -لنقل تاني حرف وهو b إلى الرمز الثنائي نقوم بإنزال عقدتين (ابناء) لل NYT هما 252 خاصة ب NYT الجديدة و 253 لحرف b مع زيادة وزن 254 و253 والجذر واصبح هنا الرمز الثنائي ل b هو 01 -لنقل ثالث حرف b وهو 01 , علينا الذهاب إلى العقدة 253 وهنا نجد انه هناك كتلة من العقد تمتلك نفس الوزن وهو 1 و الرقم الأكبر في هذه الكتلة هو 255 , لذلك نقوم بالمبادلة بين الوزن والرمز للعقدة 253 مع 255 بالاضافة إلى زيادة الوزن وبعدها الذهاب إلى الجذر و زيادة وزنه. - هنا اصبح الرمز الثنائي لحرف b هو 1 , و a هو 01 , وهو ما يعكس معدل تكرارهما .