การเข้ารหัสฮัฟฟ์แมน

การเข้ารหัสฮัฟฟ์แมน (อังกฤษ: Huffman coding) เป็นการเข้ารหัสประเภทเอนโทรปี เพื่อใช้ในการบีบอัดข้อมูลจากแหล่งกำเนิดข้อมูล

"รหัสไร้ส่วนนำ"

วิธีนี้ได้รับการพัฒนาขึ้นโดยเดวิด เอ. ฮัฟฟ์แมน และตีพิมพ์ในวารสารในชื่อว่า "A Method for the Construction of Minimum-Redundancy Codes" ปี 1952

รหัสไร้ส่วนนำ

โดยปกติแล้ว การเข้ารหัสนั้นจะเป็นการแปลงสัญลักษณ์ที่ใช้ในการสร้างข้อมูลจากแหล่งกำเนิดให้เป็นสายของสัญลักษณ์ที่ใช้ในการสร้างรหัส ตัวอย่างเช่น ถ้าแหล่งกำเนิดข้อมูลเป็นข้อความหนังสือ สัญลักษณ์ที่ใช้ในแหล่งกำเนิดก็จะเป็นตัวอักษรต่าง ๆ เช่น ก, ข, 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) ซึ่งสวนทางกับวิธีของแชนนอน-ฟาโน รหัสที่สร้างโดยวิธีของฮัฟแมนนั้นจะเป็นรหัสที่ดีที่สุดเสมอ ในขณะที่วิธีของแชนนอน-ฟาโนนั้นจะให้รหัสที่ดีที่สุดในบางกรณีเท่านั้น รายละเอียดวิธีการของฮัฟแมนมีดังต่อไปนี้

1. เริ่มจากสัญลักษณ์ ซึ่งเป็นบัพปลาย แล้วต่อกิ่งขึ้นไปหาราก โดยเริ่มจาก 2 บัพที่มีความถี่ต่ำที่สุด
2. เราจะเห็นว่าแต่ละองค์ประกอบที่ไม่ต่อกันนั้น ก็จะเป็นต้นไม้ต้นหนึ่ง ทั้งหมดจึงเรียกว่า "ป่า" ในแต่ละขั้น เราก็จะเลือกต่อกิ่งจากรากของต้นไม้ 2 ต้น ที่มีความถี่ต่ำที่สุด (ความถี่ของต้นไม้แต่ละต้นคือ ความถี่รวมของสัญลักษณ์ที่ต่อเป็นต้นไม้นั้น) เป็นต้นไม้ใหญ่ 1 ต้น
3. ทำซ้ำไปเรื่อย ๆ จนป่ารวมตัวกันเป็นต้นไม้รหัสเพียง 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 บิต ความยาวรหัสเฉลี่ยคือ

${\frac {1Bit*15+3Bit*(7+6+6+5)}{39}}\approx 2.23$ บิต ต่อสัญลักษณ์

สังเกตว่า วิธีของฮัฟแมนนั้นให้รหัสที่มีความยาวโดยเฉลี่ยสั้นกว่า รหัสแชนนอน-ฟาโน