รหัสฮัฟแมน (Huffman code)

รหัสฮัฟแมน

ตัวอย่างรหัสฮัฟแมน

ในปี ค.ศ. 1951 นั้น เดวิด ฮัฟแมน และ เพื่อนร่วมชั้นเรียนที่วิชาทฤษฎีข้อมูลที่ MIT โดยโปรเฟสเซอร์ โรเบิร์ต เอ็ม ฟาโน ผู้สอน ให้นักเรียนในชั้นเลือกทำรายงานส่ง หรือสอบปลายภาค หัวข้อรายงานคือให้หารหัสไบนารี ที่มีประสิทธิภาพที่สุด ในขณะที่ฮัฟแมนเกือบจะล้มเลิกทำรายงาน ไปเตรียมตัวอ่านหนังสือสอบนั้น เขามีความคิดที่จะใช้ แผนภูมิต้นไม้สองทางแบบเรียงความถี่(frequency-sorted binary tree) ขึ้นมาได้ และเขาก็ได้พิสูจน์ถึงประสิทธิภาพของรหัสที่เขาคิดขึ้นมา

วิธีการของฮัฟแมนนั้น สร้างต้นไม้โดยเริ่มจากบัพปลายของต้นไม้ ไปหาราก จึงเป็นวิธีการสร้างจาก ล่างขึ้นบน(bottom up) ซึ่งสวนทางกับวิธีของ แชนนอน-ฟาโน รหัสที่สร้างโดยวิธีของฮัฟแมนนั้นจะเป็นรหัสที่ดีที่สุดเสมอ ในขณะที่วิธีของแชนนอน-ฟาโนนั้นจะให้รหัสที่ดีที่สุดในบางกรณีเท่านั้น รายละเอียดวิธีการของฮัฟแมนมีดังต่อไปนี้

1. เริ่มจากสัญลักษณ์ ซึ่งเป็นบัพปลาย แล้วต่อกิ่งขึ้นไปหาราก โดยเริ่มจาก 2 บัพที่มีความถี่ต่ำที่สุด
2. เราจะเห็นว่าแต่ละองค์ประกอบที่ไม่ต่อกันนั้น ก็จะเป็นต้นไม้ต้นหนึ่ง ทั้งหมดจึงเรียกว่า ป่า ในแต่ละขั้น เราก็จะเลือกต่อกิ่งจากรากของต้นไม้ 2 ต้น ที่มีความถี่ต่ำที่สุด(ความถี่ของต้นไม้แต่ละต้นคือ ความถี่รวมของสัญลักษณ์ที่ต่อเป็นต้นไม้นั้น)เป็นต้นไม้ใหญ่ 1 ต้น
3. ทำซ้ำไปเรื่อยๆ จนป่ารวมตัวกันเป็น ต้นไม้รหัสเพียง 1 ต้น

ตัวอย่าง

ใช้ตัวอย่างเดียวกับ รหัสแชนนอน-ฟาโน ด้านบน

เริ่มจาก ขั้นแรกเราจะเลือกต่อกิ่ง D,E ซึ่งเป็น 2 บัพที่มีความถี่น้อยที่สุด ในรูป b. ในขั้นตอนนี้เรามีป่าของต้นไม้ {A}(15),{B}(7),{C}(6),{D,E}(11) ซึ่งต้นไม้ {D,E} นั้นมีความถี่ =5+6=11 ดังนั้นเราจะต้องเลือกต่อกิ่ง {B}(7) และ {C}(6) ซึ่งเป็นต้นไม้ 2 ต้นที่มีความถี่น้อยที่สุด ดังรูป c. เช่นเดียวกัน ต้นไม้ {B,C}(13) และ ต้นไม้{D,E}(11) มีน้ำหนักน้อยกว่า {A}(15) ในขั้นนี้จึงเลือกต่อกิ่งต้นไม้ {B,C} และ {D,E} ดังในรูป d. และสุดท้ายเมื่อต่อกิ่งทุกส่วนเป็นต้นไม้รหัสดังในรูป e.

ความยาวเฉลี่ยของรหัส:

เราจะเห็นว่ารหัสของ A นั้นยาว 1 บิต และ B,C,D,E นั้นยาว 3 บิต ความยาวรหัสเฉลี่ยคือ

บิต ต่อสัญลักษณ์

สังเกตว่า วิธีของฮัฟแมนนั้นให้รหัสที่มีความยาวโดยเฉลี่ยสั้นกว่า รหัสแชนนอน-ฟาโน

Cradit http://th.wikipedia.org/wiki