การเข้ารหัสฮัฟฟ์แมน
รหัสฮัฟแมน (อังกฤษ: Huffman code) เป็นการเข้ารหัสประเภทเอนโทรปี เพื่อใช้ในการบีบอัดข้อมูลจากแหล่งกำเนิดข้อมูล
รหัสไร้ส่วนนำ
โดยปกติแล้ว การเข้ารหัสนั้นจะเป็นการแปลงสัญลักษณ์ที่ใช้ในการสร้างข้อมูลจากแหล่งกำเนิดให้เป็นสายของสัญลักษณ์ที่ใช้ในการสร้างรหัส ตัวอย่างเช่น ถ้าแหล่งกำเนิดข้อมูลเป็นข้อความหนังสือ สัญลักษณ์ที่ใช้ในแหล่งกำเนิดก็จะเป็นตัวอักษรต่าง ๆ เช่น ก, ข, A, B, C สระ และอื่น ๆ ที่ใช้ประกอบกันเป็นตัวแทนข้อมูล ในกรณีของคอมพิวเตอร์ โดยทั่วไปแล้วสัญลักษณ์ ที่ใช้ในการเข้ารหัสก็จะเป็นบิต คือ 0 และ 1
แต่ละสัญลักษณ์นี้จะแทนด้วยสายบิตที่แตกต่างกัน สามารถถอดรหัสกลับได้โดยไม่สับสนแล้ว ยังจะต้องมีคุณสมบัติเป็นรหัสไร้ส่วนนำ (prefix code, prefix-free code หรือ comma-free code)
ลองพิจารณตัวอย่าง ถ้าเราเข้ารหัสอักษร A, B และ C โดย "10" เป็นรหัสแทน A, "01" เป็นรหัสแทน B, และ "0" เป็นรหัสแทน C จะเห็นว่ารหัสของ A, B, C นั้นแตกต่างกัน แต่หากเราต้องการเข้ารหัสข้อความ "ABC" ด้วยรหัสข้างต้นจะได้ "10010" ในลักษณะเดียวกันถ้ารหัสของข้อความ "ACA" จะเป็น "10010" ซึ่งรหัสทั้งสองนั้นเหมือนกันทำให้การถอดรหัสนั้นสับสน
การแก้ปัญหาข้างตันนี้อาจทำได้โดยการใช้สัญลักษณ์เฉพาะในการแยกรหัสของสัญลักษณ์ออกจากกัน หรือทำได้โดยการใช้รหัสไร้ส่วนนำ (prefix-free code) หรือเรียกในอีกชื่อว่า instantaneous code ซึ่งหมายถึงสามารถถอดรหัสได้ทันทีโดยไม่ต้องรอดูรหัสที่จะตามมา รหัสไร้ส่วนนำนี้คือรหัสที่ไม่มีรหัสใดเป็นส่วนนำของรหัสอื่น ในตัวอย่างข้างต้นรหัสของ C ("0") เป็นส่วนนำของรหัส B ("01")
วิธีการสร้างรหัสไร้ส่วนนำ
เราสามารถสร้างรหัสไร้ส่วนนำได้โดยการใช้แผนภูมิต้นไม้สองทาง (binary tree) โดยมีสัญลักษณ์ที่ต้องการเข้ารหัสอยู่ที่บัพปลายสุดของกิ่ง (leaf node) เท่านั้น
รหัสของแต่ละสัญลักษณ์จะหาได้โดยการระบุค่า "0" และ "1" ให้แก่กิ่งทั้งสองที่แตกออกจากแต่ละบัพ ตัวอย่างหนึ่งที่เป็นไปได้คือ ถ้าเราให้กิ่งด้านซ้ายที่แตกออกจากทุกบัพมีค่า "0" และ กิ่งขวามีค่า "1" เราจะได้รหัส
(1) 0 1 (2) (3) 0 1 0 1 A B (4) E "00" "01" 0 1 "11" C D "100" "101"
| A | B | C | D | E |
| 00 | 01 | 100 | 101 | 11 |
เราอาจจะระบุค่า "0", "1" ให้กับกิ่งซ้ายและขวาในลักษณะที่แตกต่างออกไป ซึ่งจะได้รหัสที่แตกต่างไปเช่น
| A | B | C | D | E |
| 10 | 11 | 000 | 001 | 01 |
| 11 | 10 | 010 | 011 | 00 |
| 11 | 10 | 001 | 000 | 01 |
การเข้ารหัสข้อความก็เพียงนำรหัสของสัญลักษณ์หรืออักษรมาเรียงต่อกัน เข่น ถ้าเราใช้รหัสในตารางแรกเพื่อเข้ารหัสข้อความ "ACDC" เราก็จะได้สายบิต "00100101100"
การถอดรหัสจากสายบิตก็เพียงไล่ตามต้นไม้โดยเริ่มจากรากของต้นไม้ แล้วเลือกเดินไปกิ่งซ้ายหรือขวาตามแต่ละบิตที่อ่านเข้ามาจากบิตแรกไปเรื่อย ๆ จนถึงบัพปลายก็จะได้สัญลักษณ์ของรหัสที่ถอดออก แล้วก็ไปเริ่มจากรากใหม่เพื่อถอดรหัสถัดไป จากตัวอย่างด้านบน เริ่มจากรากบัพ 1 บิตแรกคือ "0" ก็เดินตามกิ่งด้านซ้ายไปยังบัพ 2 บิตที่ 2 เป็น "0" ก็เดินตามกิ่งซ้ายไปถึงบัพปลาย ซึ่งถอดรหัสออกเป็น A แล้วก็ไปเริ่มจากราก บิตถัดมาคือ "1" ก็เดินตามกิ่งขวาไปยังบัพ 3 เช่นนี้ไปเรื่อย ๆ จนสุดสายบิต
การออกแบบ
การออกแบบแผนภูมิต้นไม้นี้เพื่อให้ได้รหัสที่มีความยาวโดยเฉลี่ยสั้นที่สุด หมายถึง ค่าความยาวคาดหมายของรหัสต่อหนึ่งสัญลักษณ์ (expected length) มีค่าน้อยที่สุด และเข้าใกล้ค่าเอนโทรปี
ถ้าเราพิจารณาข้อมูลจากแหล่งกำเนิด อยู่ในรูปของการเอาสัญลักษณ์มาเรียงต่อกันในรูปแบบต่าง ๆ ทีไม่แน่นอน และจากสถิติสัญลักษณ์ต่าง ๆ นั้นถูกใช้ด้วยความถี่ต่าง ๆ กันไป ด้วยหลักเหตุผลง่าย ๆ เราจะเห็นว่าถ้าเราใช้รหัสที่สั้นกับสัญลักษณ์ที่ใช้บ่อย โดยเฉลี่ยเราก็จะได้รหัสของข้อความที่สั้น
วิธีการเข้ารหัสฮัฟแมนและการเข้ารหัสแชนนอน-ฟาโนเป็นขั้นตอนวิธีที่ใช้สร้างแผนภูมิต้นไม้รหัสที่ดีที่สุด หรือใกล้เคียง
รหัสฮัฟแมน
ในปี ค.ศ. 1951 เดวิด ฮัฟแมน และเพื่อนร่วมชั้นเรียนที่วิชาทฤษฎีข้อมูลที่ MIT โดยศาสตราจารย์โรเบิร์ต เอ็ม ฟาโน ให้นักเรียนในชั้นเลือกทำรายงานส่ง หรือสอบปลายภาค หัวข้อรายงานคือให้หารหัสไบนารีที่มีประสิทธิภาพที่สุด ในขณะที่ฮัฟแมนเกือบจะล้มเลิกทำรายงานไปเตรียมตัวอ่านหนังสือสอบนั้น เขามีความคิดที่จะใช้แผนภูมิต้นไม้สองทางแบบเรียงความถี่ (frequency-sorted binary tree) ขึ้นมาได้ และเขาก็ได้พิสูจน์ถึงประสิทธิภาพของรหัสที่เขาคิดขึ้นมา
วิธีการของฮัฟแมนนั้น สร้างต้นไม้โดยเริ่มจากบัพปลายของต้นไม้ไปหาราก จึงเป็นวิธีการสร้างจากล่างขึ้นบน (bottom up) ซึ่งสวนทางกับวิธีของแชนนอน-ฟาโน รหัสที่สร้างโดยวิธีของฮัฟแมนนั้นจะเป็นรหัสที่ดีที่สุดเสมอ ในขณะที่วิธีของแชนนอน-ฟาโนนั้นจะให้รหัสที่ดีที่สุดในบางกรณีเท่านั้น รายละเอียดวิธีการของฮัฟแมนมีดังต่อไปนี้
- เริ่มจากสัญลักษณ์ ซึ่งเป็นบัพปลาย แล้วต่อกิ่งขึ้นไปหาราก โดยเริ่มจาก 2 บัพที่มีความถี่ต่ำที่สุด
- เราจะเห็นว่าแต่ละองค์ประกอบที่ไม่ต่อกันนั้น ก็จะเป็นต้นไม้ต้นหนึ่ง ทั้งหมดจึงเรียกว่า "ป่า" ในแต่ละขั้น เราก็จะเลือกต่อกิ่งจากรากของต้นไม้ 2 ต้น ที่มีความถี่ต่ำที่สุด (ความถี่ของต้นไม้แต่ละต้นคือ ความถี่รวมของสัญลักษณ์ที่ต่อเป็นต้นไม้นั้น) เป็นต้นไม้ใหญ่ 1 ต้น
- ทำซ้ำไปเรื่อย ๆ จนป่ารวมตัวกันเป็นต้นไม้รหัสเพียง 1 ต้น
ตัวอย่าง
ใช้ตัวอย่างเดียวกับ รหัสแชนนอน-ฟาโน ด้านบน
เริ่มจากขั้นแรก เราจะเลือกต่อกิ่ง D, E ซึ่งเป็น 2 บัพที่มีความถี่น้อยที่สุด ในรูป b. ในขั้นตอนนี้เรามีป่าของต้นไม้ {A}(15), {B}(7), {C}(6), {D,E}(11) ซึ่งต้นไม้ {D,E} นั้นมีความถี่ = 5+6 = 11 ดังนั้นเราจะต้องเลือกต่อกิ่ง {B}(7) และ {C}(6) ซึ่งเป็นต้นไม้ 2 ต้นที่มีความถี่น้อยที่สุด ดังรูป c. เช่นเดียวกัน ต้นไม้ {B,C}(13) และต้นไม้ {D,E}(11) มีน้ำหนักน้อยกว่า {A}(15) ในขั้นนี้จึงเลือกต่อกิ่งต้นไม้ {B,C} และ {D,E} ดังในรูป d. และสุดท้ายเมื่อตอกิ่งทุกส่วนเป็นต้นไม้รหัสดังในรูป e.
- ความยาวเฉลี่ยของรหัส
เราจะเห็นว่ารหัสของ A นั้นยาว 1 บิต และ B, C, D, E นั้นยาว 3 บิต ความยาวรหัสเฉลี่ยคือ
บิต ต่อสัญลักษณ์
สังเกตว่า วิธีของฮัฟแมนนั้นให้รหัสที่มีความยาวโดยเฉลี่ยสั้นกว่า รหัสแชนนอน-ฟาโน
