ترميز هوفمان

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
مثال على شجرة الترميز لهوفمان مطبقة على النص التالي:
"this is an example of a huffman tree"
كل الترددات مدون كل حرف أدناه

في نظرية المعلومات والمعلوماتية، ترميز هوفمان (بالإنجليزية: Huffman coding)‏ يعتبر من ترميز انتروبي يستخدم في الضغط غير الفاقد للبيانات، حيث يعتمد على ترميز متغير الطول لرموز المصدر بما يتناسب مع احتمال ظهورها.[1][2][3] طور ديفيد هوفمان هذا الترميز عندما كان طالب دكتوراه في جامعة MIT ونشره عام 1952 في ورقة بحث بعنوان A Method for the Construction of Minimum-Redundancy Codes (طريقة إنشاء ترميز بفائض أصغري).

تاريخ[عدل]

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

مصطلحات[عدل]

يستخدم ترميز هوفمان طريقة محددة لاختيار ما يمثل كل رمز حيث أن ما يتم اختياره لتمثيل رمز معين لا يتم استخدامه لتمثيل رمز غيره .ترميز هوفمان مرادف ل "prefix code " حتى إذا الرمز لم ينتج من خلال استخدام خوارزمية هوفمان.

التقنية الأساسية[عدل]

الضغط[عدل]

هذه التقنية تعمل من خلال خلق شجرة ثنائية ويمكن تخزينها في مجموعة منتظمة, حيث يعتمدالحجم على عدد من الرموز N .العقدة يمكن أن تكون عقدة ورقة(أي آخر عقدة) أو عقدة داخلية

انظر أيضاً[عدل]

مراجع[عدل]

  1. ^ Abrahams, J. (11 يونيو 1997)، كتب في Arlington, VA, USA، Division of Mathematics, Computer & Information Sciences, Office of Naval Research (ONR)، "Code and Parse Trees for Lossless Source Encoding"، Compression and Complexity of Sequences 1997 Proceedings، Salerno: معهد مهندسي الكهرباء والإلكترونيات، : 145–171، CiteSeerX 10.1.1.589.4726، doi:10.1109/SEQUEN.1997.666911، ISBN 0-8186-8132-2، مؤرشف من الأصل في 01 مارس 2016، اطلع عليه بتاريخ 09 فبراير 2016.
  2. ^ Gallager, R.G.؛ van Voorhis, D.C. (1975)، "Optimal source codes for geometrically distributed integer alphabets"، IEEE Transactions on Information Theory، 21 (2): 228–230، doi:10.1109/TIT.1975.1055357.
  3. ^ Huffman, D. (1952)، "A Method for the Construction of Minimum-Redundancy Codes" (PDF)، Proceedings of the IRE، 40 (9): 1098–1101، doi:10.1109/JRPROC.1952.273898، مؤرشف من الأصل (PDF) في 28 ديسمبر 2018.