Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

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


ไดอะแกรมของความสูงจำกัดหรือความลึกจำกัด Huffman tree ได้รับด้านล่าง

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

การจำกัดความลึกของต้นไม้เป็นปัญหาที่ไม่สำคัญซึ่งการใช้งาน Huffman ในโลกแห่งความเป็นจริงส่วนใหญ่ต้องรับมือ

โครงสร้าง Huffman ไม่จำกัดความสูงหรือความลึก หากเป็นเช่นนั้น ก็เป็นไปไม่ได้ที่มันจะ "เหมาะสมที่สุด" จริงอยู่ที่ความลึกที่ใหญ่ที่สุดของต้นไม้ Huffman นั้นล้อมรอบด้วยอนุกรม Fibonacci แต่นั่นก็เหลือที่เพียงพอสำหรับความลึกที่มากกว่าที่ต้องการ

เหตุผลในการจำกัดความลึกของต้นไม้ Huffman คืออะไร? ตัวถอดรหัส Fast Huffman ใช้ตารางการค้นหา เป็นไปได้ที่จะใช้ตารางหลายระดับเพื่อลดต้นทุนหน่วยความจำ แต่ตัวถอดรหัสที่รวดเร็วมาก เช่น Huff0 ใช้สำหรับตารางเดียว ทั้งเพื่อความเรียบง่ายและความเร็ว ในกรณีนี้ ขนาดตารางจะถือเป็นผลคูณโดยตรงของความลึกของต้นไม้ (tablesize =1 <

เพื่อประโยชน์ของการจัดการความเร็วและหน่วยความจำ ต้องเลือกขีดจำกัด:ตารางถอดรหัสคือ 8 KB ซึ่งเหมาะกับแคช L1 ของ Intel เป็นอย่างดี และทำให้มีพื้นที่บางส่วนเพื่อรวมเข้ากับตารางอื่นๆ หากจำเป็น เนื่องจากตารางถอดรหัสล่าสุดใช้ 2 ไบต์ต่อเซลล์ จึงแปลเป็นเซลล์ 4K ดังนั้นจึงมีความลึกของต้นไม้สูงสุด 12 บิต

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

การสร้างต้นไม้ที่มีความลึกจำกัดจึงเป็นปัญหาในทางปฏิบัติที่ต้องแก้ไข

ต้นไม้ฮัฟฟ์แมนจำกัดความลึกได้รับการศึกษามาตั้งแต่ปี 1960 จึงมีวรรณกรรมมากมาย