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

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

ترميز هوفمان التكيفي (يُسمى أيضًا ترميز هوفمان الديناميكي ) هو تقنية ترميز تكيفية تعتمد على ترميز هوفمان . يسمح هذا الترميز ببناء الشفرة أثناء إرسال الرموز، دون معرفة مسبقة بتوزيع المصدر، مما يتيح ترميزًا أحادي المرور والتكيف مع الظروف المتغيرة في البيانات. [ 1 ]

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

الخوارزميات

هناك عدد من تطبيقات هذه الطريقة، وأبرزها خوارزمية FGK ( Faller - Gallager - Knuth ) وخوارزمية Vitter .

خوارزمية FGK

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

نظراً لأن خوارزمية FGK بها بعض العيوب المتعلقة بتبديل العقدة أو الشجرة الفرعية، فقد اقترح فيتر خوارزمية أخرى لتحسينها.

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

بعض المصطلحات والقيود المهمة  :-

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

ترتبط الكتل ببعضها البعض بترتيب تصاعدي لأوزانها.

تسبق كتلة الأوراق دائمًا كتلة داخلية من نفس الوزن، وبالتالي تحافظ على الثابت.

NYT (لم يتم نقلها بعد) هي عقدة خاصة تستخدم لتمثيل الرموز التي "لم يتم نقلها بعد" .

يبدأ انزلاق العقدة الطرفية (Slide_And_Increment(leaf node)). P هي عقدة طرفية.
Slide_And_Increment(leaf node) خطوة الانزلاق 2. بما أن P هي عقدة ورقية، فإنها تنزلق أمام عقد الكتلة التالية ذات الوزن المتساوي.
Slide_And_Increment(leaf node) خطوة الانزلاق 3. هنا نزيد الوزن الحالي بمقدار 1.
الخطوة الرابعة من عملية الانزلاق (العقدة الطرفية): Slide_And_Increment(leaf node). تنتهي العملية. P هو الأصل الجديد.
يبدأ الانزلاق (العقدة الداخلية) Slide_And_Increment. P هي عقدة داخلية.
Slide_And_Increment(internal node) slide step 2. Node P slides in front of next block of leaves nodes, with weight wt+1.
Slide_And_Increment(internal node) خطوة الانزلاق 3. الآن نزيد الوزن إلى 9. وبالتالي يتم الحفاظ على الثابت لأن العقدة الحالية هي عقدة داخلية ويجب أن تظهر أمام العقد الورقية ذات الوزن المتساوي لأننا قمنا بزيادة الوزن.
Slide_And_Increment(العقدة الداخلية) خطوة الانزلاق 4. الآن يشير 'P' إلى الأصل السابق (كما هو الحال في العقدة الداخلية وفقًا للخوارزمية)
خوارزمية إضافة رمز هي leaf_to_increment := NULL p := مؤشر إلى عقدة الورقة التي تحتوي على الرمز التالي إذا كان ( p هو صحيفة نيويورك تايمز) قم بتوسيع p عن طريق إضافة طفلين يصبح الابن الأيسر هو صحيفة نيويورك تايمز الجديدة، ويصبح الابن الأيمن هو عقدة ورقة الرمز الجديدة p := الأصل لعقدة ورقة الرمز الجديدة leaf_to_increment := Right Child of p آخر استبدل p مع قائد كتلته إذا (كانت الصفحة الجديدة شقيقة لصحيفة نيويورك تايمز ) leaf_to_increment := p p := والد p بينما (p ≠ NULL) نفّذ Slide_And_Increment(p) إذا كان (leaf_to_increment != NULL) فقم بتنفيذ Slide_And_Increment(leaf_to_increment)
الدالة Slide_And_Increment(p) هي previous_p := parent of pإذا كانت (p عقدة داخلية) قم بتحريك النقطة p في الشجرة إلى مستوى أعلى من عقد الأوراق ذات الوزن wt + 1 قم بزيادة وزن p بمقدار 1، وإلا فإن p := previous_p  قم بتحريك p في الشجرة إلى أعلى من العقد الداخلية ذات الوزن wt زيادة وزن p بمقدار 1، p := الأصل الجديد لـ p .

يبدأ كل من المُشفِّر والمُفكِّك بالعقدة الجذرية فقط، والتي تحمل الرقم الأقصى. في البداية، تكون هذه العقدة هي عقدة نيويورك تايمز الأولية.

عندما نقوم بإرسال رمز NYT، يتعين علينا إرسال رمز لعقدة NYT، ثم رمزها العام.

لكل رمز موجود بالفعل في الشجرة، علينا فقط إرسال رمز لعقدة الورقة الخاصة به.

مثال

ترميز "abb" يعطي 01100001 001100010 11.

الخطوة 1:

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

بالنسبة لـ "أ"، قم بإرسال رمزها الثنائي.

الخطوة الثانية:

تُنشئ NYT عقدتين فرعيتين: 254 و255، وكلاهما بوزن 0. قم بزيادة وزن العقدة الجذرية والعقدة 255. رمز "a"، المرتبط بالعقدة 255، هو 1.

بالنسبة لـ "b"، أرسل 0 (لعقدة NYT) ثم رمزها الثنائي.

الخطوة 3:

يُنشئ NYT عقدتين فرعيتين: 252 لـ NYT و253 للعقدة الطرفية، وكلاهما بوزن 0. يجب زيادة أوزان العقد 253 و254 والجذر. وللحفاظ على قاعدة فيتر التي تنص على أن جميع العقد الطرفية ذات الوزن w تسبق (في الترقيم الضمني) جميع العقد الداخلية ذات الوزن w، يجب تبديل الفرع الذي يبدأ بالعقدة 254 (من حيث الرموز والأوزان، وليس ترتيب الأرقام) مع العقدة 255. رمز "b" هو 11.

بالنسبة للحرف "ب" الثاني، أرسل 11.

ولتسهيل الشرح، فإن هذه الخطوة لا تتبع خوارزمية فيتر بالضبط، [ 2 ] ولكن التأثيرات مكافئة.

الخطوة الرابعة:

انتقل إلى العقدة الطرفية 253. لاحظ وجود كتلتين بوزن 1. العقدتان 253 و254 تشكلان كتلة واحدة (تتكون من أوراق)، والعقدة 255 تشكل كتلة أخرى (تتكون من عقد داخلية). بالنسبة للعقدة 253، فإن أكبر رقم في كتلتها هو 254، لذا بدّل أوزان ورموز العقدتين 253 و254. الآن، تحقق العقدة 254 والفرع المنطلق منها شرط SlideAndIncrement [ 2 ] ، وبالتالي يجب تبديلهما. أخيرًا، زد وزن العقدتين 255 و256.

الرمز المستقبلي لـ "b" هو 1، ولـ "a" هو الآن 01، وهو ما يعكس ترددها.

مراجع

  1. ↑ زي-نيان لي؛ مارك إس. درو؛ جيانغتشوان ليو (9 أبريل 2014). أساسيات الوسائط المتعددة . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-3-319-05290-8.
  2. 1 2 "الترميز التكيفي لهوفمان" . Cs.duke.edu . تم الاطلاع عليه بتاريخ 26-02-2012 .
  • الورقة الأصلية لفيتر: JS Vitter، " تصميم وتحليل رموز هوفمان الديناميكية "، مجلة ACM، 34(4)، أكتوبر 1987، ص 825-845.
  • JS Vitter، "الخوارزمية 673 ترميز هوفمان الديناميكي"، معاملات ACM في البرمجيات الرياضية، 15(2)، يونيو 1989، ص 158-167. يظهر أيضًا في مجموعة خوارزميات ACM.
  • دونالد إي. كنوث، "الترميز الديناميكي لهوفمان"، مجلة الخوارزميات، 6(2)، 1985، ص 163-180.