ترميز هوفمان

مثال على شجرة الترميز لهوفمان مطبقة على النص التالي:
"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 .العقدة يمكن أن تكون عقدة ورقة(أي آخر عقدة) أو عقدة داخلية

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

مراجع[عدل]

^ 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. مؤرشف من الأصل في 2016-03-01. اطلع عليه بتاريخ 2016-02-09.
^ 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.
^ 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) في 2018-12-28.

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

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

[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. مؤرشف من الأصل في 2016-03-01. اطلع عليه بتاريخ 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. مؤرشف من الأصل (PDF) في 2018-12-28.

[1]

[2]

[3]