ترميز هوفمان

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
مثال على شجرة الترميز لهوفمان مطبقة على النص التالي:
"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. (1997-06-11). كتب في 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.4726Freely accessible. ISBN 0-8186-8132-2. doi:10.1109/SEQUEN.1997.666911. اطلع عليه بتاريخ 2016-02-09. 
  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. 



Computer.svg
هذه بذرة مقالة عن الحاسوب أو العاملين في هذا المجال بحاجة للتوسيع. شارك في تحريرها.