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

จากวิกิพีเดีย สารานุกรมเสรี

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

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