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

รหัสแชนนอน-ฟาโน (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 บิต ความยาวรหัสเฉลี่ยคือ

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

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