การเข้ารหัสแชนนอน–ฟาโน
รหัสแชนนอน-ฟาโน (Shannon-Fano code) เป็นการเข้ารหัส ประเภท เอนโทรปี เพื่อใช้ในการบีบอัดข้อมูลจากแหล่งกำเนิดข้อมูล
รหัสแชนนอน-ฟาโน
[แก้]
ขั้นตอนวิธีนี้ตั้งชื่อตาม คลาวด์ แชนนอน และ โรเบิร์ต ฟาโน โดยมีรายละเอียดดังต่อไปนี้
- เรียงสัญลักษณ์ ตามความถี่ (อาจเรียงจากที่ใช้บ่อยที่สุด ไปจนถึงใช้น้อยที่สุด)
- แบ่งสัญลักษณ์ออกเป็น 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 นั้นยาว 2 บิต และ D,E นั้นยาว 3 บิต ความยาวรหัสเฉลี่ยคือ
บิต ต่อ สัญลักษณ์(อักษร)
