การเข้ารหัสแชนนอน–ฟาโน

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

รหัสแชนนอน-ฟาโน

 

ตัวอย่างรหัสแชนนอน-ฟาโน

ขั้นตอนวิธีนี้ตั้งชื่อตาม คลาวด์ แชนนอน และ โรเบิร์ต ฟาโน โดยมีรายละเอียดดังต่อไปนี้

1. เรียงสัญลักษณ์ ตามความถี่ (อาจเรียงจากที่ใช้บ่อยที่สุด ไปจนถึงใช้น้อยที่สุด)
2. แบ่งสัญลักษณ์ออกเป็น 2 กลุ่มซ้าย และขวา โดยแบ่งให้ทั้งสองกลุ่มมีผลบวกของความถี่เท่ากันที่สุดเท่าที่จะเป็นไปได้ การแบ่งกลุ่มนี้จะเท่ากับแตกกิ่งของแผนภูมิต้นไม้ และสัญลักษณ์แต่ละกลุ่มจะอยู่ที่บัพของปลายกิ่งที่แตกออก
3. แบ่งกลุ่ม และแตกกิ่งไปเรื่อยๆ จนแต่ละกิ่งปลายเหลือสัญลักษณ์เพียงสัญลักษณ์เดียว เราก็จะได้แผนภูมิต้นไม้รหัส

สังเกตว่า แผนภูมิต้นไม้นี้เริ่มต้นจากราก และ แตกกิ่งลงไปจนถึงบัพปลาย จึงเรียกเป็นการสร้างจาก บนลงล่าง(top down) ซึ่งจะสวนทางกับ รหัสฮัฟแมน ซึ่งสร้างจาก ล่างขึ้นบน(bottom up)

ตัวอย่าง

สมมติเรามีข้อความซึ่งประกอบด้วยสัญลักษณ์(ตัวอักษร) เพียง 5 ตัวคือ A,B,C,D,E และปรากฏอยู่ในข้อความด้วยความถี่แสดงดังตาราง

A	B	C	D	E
15	7	6	6	5

ตัวอักษรในรูป a. เรียงตามความถี่มากไปน้อย ถัดมาในรูป b. เราแบ่งตัวอักษรออกเป็นสองกลุ่มให้มีความถี่รวมแต่ละกลุ่มใกล้เคียงกันมากที่สุด พิจารณากรณี

1. แบ่ง {A}(15)และ {B,C,D,E}(7+6+6+5=24) จะต่างกัน 9
2. แบ่ง {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 บิต ความยาวรหัสเฉลี่ยคือ

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