อัลกอริธึมอย่างง่าย
- มีการเตรียมต้นไม้ฮัฟฟ์แมนเริ่มต้นจำนวน n ต้น ซึ่งแต่ละต้นจะเป็นโหนดใบเดียว จัดต้นไม้ n ต้นไว้ในคิวลำดับความสำคัญที่จัดตามน้ำหนัก (ความถี่)
- ลบหรือลบต้นไม้สองต้นแรก (ต้นที่มีน้ำหนักน้อยที่สุด) รวมต้นไม้ทั้งสองนี้เข้าด้วยกันเพื่อสร้างต้นไม้ใหม่ที่มีรากเชื่อมโยงกับต้นไม้ทั้งสองต้นในฐานะลูก และมีน้ำหนักคือผลรวมของน้ำหนักของต้นไม้ลูกทั้งสอง
- เก็บทรีใหม่นี้ไว้ในคิวลำดับความสำคัญ
- ทำซ้ำขั้นตอนที่ 2-3 จนกว่าจะถึงและเว้นแต่ต้นไม้ Huffman บางส่วนทั้งหมดจะถูกรวมเป็นต้นเดียว
เป็นอัลกอริธึมที่โลภ:ในการทำซ้ำแต่ละครั้ง อัลกอริธึมจะสร้างการตัดสินใจที่ "โลภ" เพื่อรวมทรีย่อยทั้งสองเข้าด้วยกันโดยมีน้ำหนักน้อยที่สุด เป็นไปได้ไหมที่อัลกอริทึมจะให้ผลลัพธ์ที่ต้องการ?
- บทแทรก:ให้ x และ y เป็นอักขระที่มีความถี่ต่ำที่สุดสองตัว มีแผนผังโค้ดที่เหมาะสมที่สุดที่ x และ y เป็นพี่น้องกันซึ่งมีความลึกต่ำสุดเท่ากับโหนดปลายสุดอื่นๆ ในแผนผัง
- ทฤษฎีบท:รหัส Huffman ถือเป็นรหัสไบนารี่ที่ไม่มีส่วนนำหน้า (อัลกอริทึมที่โลภสร้างแผนภูมิ Huffman โดยมีน้ำหนักพาธภายนอกต่ำสุดสำหรับชุดตัวอักษรที่กำหนด)
