ترميز هوفمان

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

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

تاريخ

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

مصطلحات

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

التقنية الأساسية

الضغط

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

انظر أيضاً

مراجع

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.4726 10.1.1.589.4726. doi:10.1109/SEQUEN.1997.666911. ISBN 0-8186-8132-2. مؤرشف من الأصل في 01 مارس 2016. اطلع عليه بتاريخ 09 فبراير 2016. الوسيط |CitationClass= تم تجاهله (مساعدة)
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. الوسيط |CitationClass= تم تجاهله (مساعدة)
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. الوسيط |CitationClass= تم تجاهله (مساعدة)

بوابة تقنية المعلومات
بوابة علم الحاسوب

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.4726 10.1.1.589.4726. doi:10.1109/SEQUEN.1997.666911. ISBN 0-8186-8132-2. مؤرشف من الأصل في 01 مارس 2016. اطلع عليه بتاريخ 09 فبراير 2016. الوسيط |CitationClass= تم تجاهله (مساعدة)

[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. الوسيط |CitationClass= تم تجاهله (مساعدة)

[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. الوسيط |CitationClass= تم تجاهله (مساعدة)