สิ่งที่ผมรู้ หากคุณอ่าน คุณจะรู้ตามผมไปด้วย

Huffman Coding

เป็นส่วนหนึ่งของ Data Compression แบบที่เรียกว่า Lossless Compression ที่เมื่อผู้รับปลายทาง รับข้อมูล สามารถ Decode กลับมาเป็นข้อมูลได้ครบถ้วน ถือว่าเป็นแม่แบบของ Data Compression เนื่องจากเป็นหลักในการศึกษาทฤษฏีอื่น ๆ ต่อไป

ตัวอย่างการเข้ารหัส Huffman Code

ผู้ส่ง ต้องการส่งข้อมูลดังนี้ {a , b , c , d } โดยที่มีโอกาศเกิดคำนั้นในเอกสาร {0.5 ; 0.3 ; 0.1 ; 0.1 } หากคิดง่าย โดยการแทนตัวอักษรดังนี้

• a = 00
• b = 01
• c = 10
• d = 11

หากต้องการส่งข้อมูล abcd ไปยังผู้รับ หากแทนตัวอักษรด้วยจำนวน 2 Bit จะได้ข้อมูล 00011011 ไปยังปลายทาง สังเกตุว่า เราใช้ ถึง 2 Bit ในการแทนตัวอักษรทั้งหมด ซึ่งไม่จำเป็นต้องใช้ Bit จำนวนมากขนาดนั้น

หากเราใช้ Huffman Code ให้การแทนนั้น เราจะสามารถแทน

• a = 1
• b = 01
• c = 001
• d = 000

สามารถคำนวณค่าเฉลี่ยการใช้ Bit แทนตัวอักษรได้ดังนี้
(0.5)*1+(0.3)*2+(0.1)*3+(0.1)*3 = 1.7 Bit เท่านั้น

ยิ่งหากมีเอกสารมากขึ้นยิ่งสามารถลดจำนวน Bit ได้มากขึ้น

ขอบพระคุณที่สนใจอ่าน

อ่านเพิ่มเติม : http://en.wikipedia.org/wiki/Huffman_coding