Метод Шеннона-Фано
В цьому методі для кожного символа формується бітовий код, довжина якого залежить від частоти появи символа. Чим менша частота, тим довший код. Визначення частоти (ймовірності) символа буває статичне (на основі таблиці даних) або динамічне (коли відомості про ймовірність появи символів визначаються на основі обробки потоку даних).
Кодування здійснюється таким чином (рис. 1):
Всі символи записуються в таблицю по зменшенню їх частоти. Потім вони поділяються на дві групи так, щоб суми частот для отриманих груп були максимально близькі. Для першої групи перший біт коду встановлюється рівним 1, а для другої – 0. Потім групи знову поділяємо на дві і визначаємо наступні розряди коду. Процес продовжується поки в групі не залишиться тільки один символ.
Номер Символ Частота Код
1 a 10 11
2 b 8 10
-----------------------------‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑----------------------------
3 c 6 011
4 d 5 010
5 e 4 001
6 f 3 000
Рис. 1.
Можливий варіант програмної реалізації методу базується на формуванні і обробці такої таблиці
| Nгр | Np | Nk | S | Код |
Ця таблиця забезпечує зручний запис алгоритму поділу на підгрупи і формування кодів. Перша група (Nгр=1) складається з двох підгруп: перша - починається з першого символа (Np=1) і закінчується другим (Nк=2), друга – починається з третього символа (Nр=3) і закінчується шостим (Nк=6). Сума частот першої підгрупи S=18, другої S=18. Друга група (Nгр=2) формується в результаті поділу першої підгрупи з першої групи і складається теж з двох підгруп: перша – починається з першого символа (Nр=1) і ним закінчується (Nк=1), друга – починається другим символом (Nр=2) і ним закінчується (Nк=2). Третя група описує процес поділу другої підгрупи з першої групи. Процуес продовжується до тих пір поки кожна підгрупа не буде складатися тільки з одного символа (Nр=Nк). Відповідний новий біт коду кожної групи визначається таким чином: для першої підгрупи він встановлюється рівним одиниці, а для другої підгрупи – нулю.
Нижче приведений можливий варіант демонстраційної програми і результати її роботи
implicit integer*2(j),character*1(z)
dimension jmp(12),jmk(12),jms(12),jml(12),zmk(12,5),zm(6),jmc(6)
data zm/'a','b','c','d','e','f'/,jmc/10,8,6,5,4,3/
js=0
do 100 j=1,12
100 jml(j)=0
do 1 j=1,6
1 js=js+jmc(j)
jp=1
jk=6
ju=0
jz=1
12 jdr=32000
jmp(jz)=jp
jmk(jz+1)=jk
js1=0
jv=jp
jvr=jv
9 js1=js1+jmc(jv)
js2=js-js1
jd=js2-js1
if(abs(jd).ge.jdr) go to 11
jdr=jd
jms(jz)=js1
jms(jz+1)=js2
jvr=jv
if(jd.le.0) go to 11
jv=jv+1
go to 9
11 jmk(jz)=jvr
jmp(jz+1)=jvr+1
if(ju.eq.0) go to 50
jml(jz)=jml(ju)
jml(jz+1)=jml(ju)
do 20 j=1,jml(ju)
zmk(jz,j)=zmk(ju,j)
20 zmk(jz+1,j)=zmk(ju,j)
50 jml(jz)=jml(jz)+1
zmk(jz,jml(jz))='1'
jml(jz+1)=jml(jz+1)+1
zmk(jz+1,jml(jz+1))='0'
jz=jz+2
15 ju=ju+1
if(ju.ge.jz) go to 17
jp=jmp(ju)
jk=jmk(ju)
js=jms(ju)
if(jp.eq.jk) go to 15
if(jp+1.lt.jk) go to 12
jmp(jz)=jp
jms(jz)=jmc(jp)
jmk(jz+1)=jk
jms(jz+1)=jmc(jk)
jvr=jp
go to 11
17 do 30 j=1,10
30 write(6,31) jmp(j),jmk(j),jms(j),jml(j),(zmk(j,jj),jj=1,5)
31 format(' ',4i4,1x,5a1)
stop
end
1 2 18 1 1
3 6 18 1 0
1 1 10 2 11
2 2 8 2 10
3 4 11 2 01
5 6 7 2 00
3 3 6 3 011
4 4 5 3 010
5 5 4 3 001
6 6 3 3 000
Кодування Шеннона-Фано неоднозначне. В залежності від варіанту поділу на групи (при однаковій різниці частот між ними) можуть бути отримані різні коди для символів (рис. 2).
Символ Частота Код Символ Частота Код
с 22 11 с 22 11
e 20 101 e 20 10
h 16 100 --------------------------------------------
----------------------------------------------- h 16 011
i 16 011 і 16 010
a 10 010 a 10 001
k 10 001 k 10 0001
m 4 0001 m 4 00001
b 2 0000 b 2 00000
Рис. 2.