ต้นไม้ฮัฟฟ์แมนในโครงสร้างข้อมูล

คำจำกัดความ

การเข้ารหัส Huffman ให้รหัสแก่อักขระ โดยที่ความยาวของโค้ดจะขึ้นอยู่กับความถี่หรือน้ำหนักที่สัมพันธ์กันของอักขระที่เกี่ยวข้อง รหัส Huffman มีความยาวผันแปรได้ และไม่มีส่วนนำหน้า (หมายความว่าไม่มีรหัสใดเป็นคำนำหน้าของรหัสอื่นๆ) รหัสไบนารีที่ไม่มีคำนำหน้าใดๆ สามารถแสดงหรือแสดงเป็นภาพต้นไม้ไบนารีด้วยอักขระที่เข้ารหัสที่เก็บไว้ที่ใบไม้

Huffman tree หรือ Huffman coding tree กำหนดให้เป็นต้นไม้ไบนารีเต็มรูปแบบ โดยที่แต่ละใบของต้นไม้จะสอดคล้องกับตัวอักษรในตัวอักษรที่กำหนด

ต้นไม้ Huffman ถือเป็นไบนารีทรีที่เกี่ยวข้องกับน้ำหนักเส้นทางภายนอกขั้นต่ำ ซึ่งหมายความว่า ต้นไม้ที่เกี่ยวข้องกับผลรวมขั้นต่ำของความยาวเส้นทางที่ถ่วงน้ำหนักสำหรับชุดใบไม้ที่กำหนด เป้าหมายคือการสร้างต้นไม้ที่มีน้ำหนักเส้นทางภายนอกขั้นต่ำ

ตัวอย่างได้รับด้านล่าง-

ตารางความถี่ตัวอักษร

รหัส Huffman

ต้น Huffman (สำหรับตัวอย่างด้านบน) แสดงไว้ด้านล่าง -