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

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

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

 บิต ต่อสัญลักษณ์

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

 อ้างอิง 

หมวดหมู่:ขั้นตอนวิธีการบีบอัดข้อมูลแบบไม่สูญเสีย
หมวดหมู่:ต้นไม้แบบทวิภาค