รหัสฮัฟแมน และ รหัสแชนนอน-ฟาโน
จากวิกิพีเดีย สารานุกรมเสรี
รหัสฮัฟแมน(Huffman code) และ รหัสแชนนอน-ฟาโน(Shannon-Fano) ทั้งสองนี้เป็นการเข้ารหัส ประเภท เอนโทรปี เพื่อใช้ในการบีบอัดข้อมูลจากแหล่งกำเนิดข้อมูล
สารบัญ |
[แก้] รหัสไร้ส่วนนำ
โดยปกติแล้ว การเข้ารหัสนั้นจะเป็นการแปลง สัญญลักษณ์ที่ใช้ในการสร้างข้อมูลจากแหล่งกำเนิด ให้เป็นสายของสัญญลักษณ์ที่ใช้ในการสร้างรหัส ตัวอย่างเช่น ถ้าแหล่งกำเนิดข้อมูลเป็นข้อความหนังสือ สัญญลักษณ์ที่ใช้ในแหล่งกำเนิด ก็จะเป็นตัวอักษรต่างๆ เช่น ก,ข,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) มีค่าน้อยที่สุด และเข้าใกล้ค่าเอนโทรปี
ถ้าเราพิจารณาข้อมูลจากแหล่งกำเนิด อยู่ในรูปของการเอาสัญลักษณ์มาเรียงต่อกันในรูปแบบต่างๆ ทีไม่แน่นอน และจากสถิติสัญลักษณ์ต่างๆนั้นถูกใช้ด้วยความถี่ต่างๆกันไป ด้วยหลักเหตุผลง่ายๆ เราจะเห็นว่าถ้าเราใช้รหัสที่สั้น กับสัญลักษณ์ที่ใช้บ่อย โดยเฉลี่ยเราก็จะได้รหัสของข้อความที่สั้น
วิธีการเข้ารหัสฮัฟแมน และ การเข้ารหัสแชนนอน-ฟาโน เป็นอัลกอริทึม ที่ใช้สร้างแผนภูมิต้นไม้รหัสที่ดีที่สุด หรือใกล้เคียง
[แก้] รหัสแชนนอน-ฟาโน
อัลกอริทึมนี้ตั้งชื่อตาม คลาวด์ แชนนอน และ โรเบิร์ต ฟาโน โดยมีรายละเอียดดังต่อไปนี้
- เรียงสัญลักษณ์ ตามความถี่ (อาจเรียงจากที่ใช้บ่อยที่สุด ไปจนถึงใช้น้อยที่สุด)
- แบ่งสัญลักษณ์ออกเป็น 2 กลุ่มซ้าย และขวา โดยแบ่งให้ทั้งสองกลุ่มมีผลบวกของความถี่เท่ากันที่สุดเท่าที่จะเป็นไปได้ การแบ่งกลุ่มนี้จะเท่ากับแตกกิ่งของแผนภูมิต้นไม้ และสัญลักษณ์แต่ละกลุ่มจะอยู่ที่บัพของปลายกิ่งที่แตกออก
- แบ่งกลุ่ม และแตกกิ่งไปเรื่อยๆ จนแต่ละกิ่งปลายเหลือสัญลักษณ์เพียงสัญลักษณ์เดียว เราก็จะได้แผนภูมิต้นไม้รหัส
สังเกตว่า แผนภูมิต้นไม้นี้เริ่มต้นจากราก และ แตกกิ่งลงไปจนถึงบัพปลาย จึงเรียกเป็นการสร้างจาก บนลงล่าง(top down) ซึ่งจะสวนทางกับ รหัสฮัฟแมน ซึ่งสร้างจาก ล่างขึ้นบน(bottom up)
[แก้] ตัวอย่าง
สมมติเรามีข้อความซึ่งประกอบด้วยสัญลักษณ์(ตัวอักษร) เพียง 5 ตัวคือ A,B,C,D,E และปรากฏอยู่ในข้อความด้วยความถี่แสดงดังตาราง
| A | B | C | D | E |
| 15 | 7 | 6 | 6 | 5 |
ตัวอักษรในรูป a. เรียงตามความถี่มากไปน้อย ถัดมาในรูป b. เราแบ่งตัวอักษรออกเป็นสองกลุ่มให้มีความถี่รวมแต่ละกลุ่มใกล้เคียงกันมากที่สุด พิจารณากรณี
- แบ่ง {A}(15)และ {B,C,D,E}(7+6+6+5=24) จะต่างกัน 9
- แบ่ง {A,B}(15+7=22) และ {C,D,E}(6+6+5=17) ต่างกัน 5
จะเห็นว่ากรณี 2 นั้นแบ่งกึ่งกลางกว่า เช่นเดียวกัน {C,D,E} แบ่งเป็น {C} และ {D,E} ในรูป c. และสุดท้ายได้ต้นไม้แทนรหัสในรูป d.
ความยาวเฉลี่ยของรหัส:
เราจะเห็นว่ารหัสของ A,B,C นั้นยาว 3 บิต และ D,E นั้นยาว 4 บิต ความยาวรหัสเฉลี่ยคือ
บิต ต่อ สัญลักษณ์(อักษร)
[แก้] รหัสฮัฟแมน
ในปี ค.ศ. 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 บิต ความยาวรหัสเฉลี่ยคือ
บิต ต่อสัญลักษณ์
สังเกตว่า วิธีของฮัฟแมนนั้นให้รหัสที่มีความยาวโดยเฉลี่ยสั้นกว่า รหัสแชนนอน-ฟาโน
