Huffman’s Code

สมมุติว่าเราต้องการบีบอัดไฟล์ข้อมูล (compression) เช่นพวก zip ไฟล์ ปกติแล้วเราจะเปลี่ยนตัวอักษรที่อยู่ในไฟล์ให้กลายเป็นบิตข้อมูล (bit) ที่มีขนาดเล็กกว่าบิตข้อมูลธรรมดา เช่น ปกติเลข 5 อาจจะเป็นตัวเลข 0000 0101 ถ้าเก็บแบบ 8 บิต แต่ถ้าเราบีบอัดแล้วอาจจะใช้ที่เก็บจริงๆแค่ 3 บิตคือ 101 เท่านั้น

เช่นถ้าในไฟล์เรามีข้อมูลตัวอักษร a, e, i, s, t, space bar, new line (สำหรับ space bar ก็คือช่องไฟ และ new line คือ ขึ้นบรรทัดใหม่ พวกนี้เป็นตัวอักษรล่องหน มองไม่เห็น แต่กินพื้นที่ไฟล์ด้วยเช่นกัน)

เราต้องการบีบอัดไฟล์นี้ให้มีขนาดเล็กเราอาจจะเปลี่ยนตัวอักษรเหล่านี้ให้กลายเป็นรหัสขนาด 3 บิต ดังตารางต่อไปนี้

จากตารางข้างต้น สมมุติว่าในไฟล์มีข้อมูลดังนี้

aaeeiiissttt 

a  ti

เราสามารถแปลงให้กลายเป็นรหัสตามที่กำหนดไว้ได้ดังนี้

000 000 001 001 010 010 010 011 011 100 100 100 110 000 101 101 100 010

เมื่อนับจำนวนบิตดูจะพบว่ามีขนาดทั้งหมด เท่ากับ 18 x 3 = 54 บิต

สมมุติว่าถ้าในไฟล์มีตัว a อยู่ 10 ตัว ตัว e อยู่ 15 ตัว ตัว i อยู่ 12 ตัว ตัว s อยู่ 3 ตัว ตัว t อยู่ 4 ตัว ตัว space อยู่ 13 ตัว และ new line อยู่ 1 ตัว เราสามารถคำนวณ จำนวนบิตทั้งหมดหลังจากบีบอัดไฟล์ แล้วได้ดังนี้

วิธีการของ Haffman ต้องการลดจำนวนบิตที่ใช้ในการเข้ารหัสให้เหลือน้อยที่สุดเท่าที่จะเป็นไปได้ โดยทำดังนี้

o    นำตัวอักษรทั้งหมดมาเรียงเป็นโหนดใบ (Leaf Node) พร้อมกับใส่จำนวนครั้งที่พบ (Frequency) กำกับไว้ด้วย

o    ให้เลือกเอาตัวที่พบน้อยครั้งที่สุด มารวมเข้าด้วยกันก่อน วิธีรวมทำโดยสร้างโหนดแม่ขึ้นมาผูกโหนดลูกทั้ง 2 ตัวเข้าด้วยกัน

o    ที่โหนดแม่ที่ใช้ผูกโหนดลูกเข้าด้วยกันให้มีค่า Frequency เป็นผลรวมของโหนดลูกรวมกัน

o    ทำไปเรื่อยๆ จนกระทั่งครบทุกตัวอักษรจะได้ต้นไม้ Huffman

o    การเข้ารหัสจะท่อง (Traverse) เข้าไปในต้นไม้ เริ่มจาก Root

o    ถ้าเดินไปทางซ้าย จะให้รหัสเป็น 0

o    ถ้าเดินไปทางขวา จะให้รหัสเป็น 1

จากตัวอย่างข้างต้น เรานำตัวอักษรทั้งหมดออกมาเรียงจาก Frequence มากสุดไปหาน้อยสุดได้ดังนี้

เมื่อจัดเรียงแล้วจะสังเกตว่า s กับ nl มีค่า Frequency น้อยที่สุดให้รวม s กับ nl เข้าด้วยกันก่อน โดยสร้างโหนดแม่มารับโหนดทั้งสองตัวนี้ ดังนี้

ทุกรอบของการสร้างต้นไม้ จะต้องหาโหนด 2 โหนดที่มีค่าน้อยที่สุดมารวมเข้าด้วยกัน

การต่อโหนดใหม่เข้าไปในต้นไม้เดิม จะยึดหลักว่าให้ต่อต้นเดิมเข้าไปที่แขนซ้าย และ ต่อโหนดใหม่เข้าไปที่ด้านขวา เสมอ

ดังนั้นให้ดูในต้นไม้ปัจจุบัน พบว่าโหนดที่มีค่าน้อยที่สุดคือ t = 4 และ T1 = 4 ของต้นใหม่ ดังนั้นเมื่อบวกเข้าด้วยกันจะได้ต้นไม้ใหม่มีขนาดเท่ากับ 8 เราให้ต้นใหม่นี้ชื่อว่า T2 ดังนี้

รอบต่อมา หาตัวที่น้อยที่สุด 2 ตัว ในที่นี้คือ a = 10 และ T2 = 8 เมื่อรวม 2 ตัวนี้เข้าด้วยกันเราจะได้ T3 ที่มีค่าเป็น 18 ดังนี้

รอบต่อมา หาตัวที่น้อยที่สุด 2 ตัว เราจะได้ i = 12 และ sp = 13 ดังนั้น เราจะรวม sp กับ i เข้าด้วยกันได้เป็น T4 มีค่าเป็น 25 ดังนี้

ปัจจุบันจะเหลืออยู่แค่ 3 โหนดเท่านั้นคือ e, T4 และ T3 สังเกตว่าโหนดที่น้อยที่สุด 2 ตัวคือ e = 15 และ T3 = 18 ดังนั้นเราจะรวม e กับ T3 เข้าด้วยกันเป็น T5 มีค่าเป็น 33 ดังนี้

สุดท้ายเรารวมโหนด T4 กับ T5 เข้าด้วยกันเป็น T6 ที่มีค่าเป็น 58 ดังนี้

ต่อจากนั้นเราสามารถเข้ารหัสได้ โดยเดินเข้าไปในต้นไม้ โดยให้เดินไปแขนซ้ายเข้ารหัสเป็น 0 และเดินไปทางแขนขวาให้รหัสเป็น 1 ตัวอย่างเช่น ถ้าเราจะเดินไปที่ตัว a เราจะไปตามทาง T5, T3, a และได้รหัสเป็น 001 ดังนี้

ดังนั้นด้วยวิธีการนี้เราสามารถสร้างรหัสของตัวอักษรทุกตัวได้ตามตารางดังนี้

และเมื่อคำนวณผลรวมจำนวนบิตที่ใช้แล้วจะได้จำนวนบิตดังนี้

จะเห็นว่าวิธีการเข้ารหัสแบบ Huffman ได้จำนวนบิตออกมาเป็น 146 ซึ่งเป็นผลลัพธ์ที่ Optimum ที่สุด และน้อยกว่าวิธีเดิมที่ได้จำนวนบิตออกมามากถึง 174

หลักการเลือกตัวที่น้อยที่สุดมาในแต่ละรอบ เราสามารถประยุกต์ใช้ Heap และแต่ละรอบเลือก deleteMin และนำผลรวมใหม่ insert เข้าไปใน Heap ได้ ซึ่งจะได้ประสิทธิภาพออกมาเป็น O(N log N)