H(x) P(x) Log2 P(x) 2,89
bitga teng bo‗ladi.
Ushbu algoritm bo‗yicha hisoblash natijalari jadvalda keltirilgan. Kodlashtirilgan axborotdagi xar bir belgiga mos kelgan kodli kombinatsiyaning o‗rtacha uzunligi quyidagicha hisoblanadi:
no'rtacha ni P(x) 2,96
bitga teng.
2.1-jadvalda Shennon-Fano algoritmi bo‗yicha hisoblash natijalari
keltirilgan.
2.1-jadval Shennon- Fano algoritmi bo‗yicha hisoblash natijalari
|
Belgilar
|
Paydo
bo‗lish chastotasi
|
Yordamchi jadval
|
Kodi
| |
B
|
5
|
(1)
5 (1)
3 (1)
|
5 (1)
|
|
11
| |
D
|
5
|
5 (0)
3 (0)
|
5 (1)
|
101
| |
A
|
3
|
3 (0)
|
100
| |
E
|
3
|
3 (0)
2 (0)
2 (0)
2 (0)
2 (0)
|
3 (1)
|
3 (1)
|
011
| |
C
|
2
|
2 (1)
|
2 (0)
|
010
| |
F
|
2
|
2 (0)
2 (0)
2 (0)
|
2 (1)
|
|
001
| |
G
|
2
|
2 (0)
2 (0)
|
2 (1)
|
0001
| |
H
|
2
|
2 (0)
|
0000
|
Hozirgi kunda eng keng tarqalgan, amaliyotda ko‗p ishlatiladigan entropiyali kodlash usuliga asoslangan algoritmlardan biri bu – Devid Xaffman algoritmi hisoblanadi.
Devid Xaffman 1925 yil 9 avgustda AQShning Ogayo shtatida tug‗ilan. Devid Xaffman - axborot nazariyasi muhiti bo‗yicha ish olib borgan. U 1952 yil kam ortiqchalik bilan prefikslarni kodlash algoritmini yaratgan. 1999 yil axborot nazariyasiga qo‗shgan hissasi uchun Richard Xemming medalini olgan.
1999 yil 7 oktabrda AQShning
Kaliforniya shtatida vafot etgan. Devid Xaffman 1925 - 1999
Xaffman algoritmi asosida matnli axborotlar kodlashtiriladi. Ushbu algoritm yordamida axborotni kodlashtirish quyidagicha amalga oshiriladi:
axborotdagi barcha belgilar soni, ya‘ni N hisoblanadi;
jami N ta belgidan iborat bo‗lgan axborotdagi har bir belgining paydo bo‗lish chastotasi hisoblanadi;
har bir belgining paydo bo‗lish chastotasi kamayib borish tartibida jadvalga joylashtiriladi;
jadvaldagi oxirgi ikkita chastota yig‗indisi hisoblanib, bitta umumiy bo‗lgan yig‗indi chastotaga birlashtiriladi;
hisoblangan yangi yig‗indi chastotadan va hisoblashda qatnashmagan boshqa chastotalardan jadvalning yangi ustuni hosil qilinadi (bunda ham chastotalar kamayib borish tartibida joylashtiriladi);
shu tarzda to bitta umumiy N ga teng bo‗lgan yig‗indi hosil bo‗lguncha jarayon davom etaveradi;
jadval to‗ldirilgandan so‗ng, undagi hisoblashlarga muvofiq daraxt quriladi;
daraxtning tepa qismida N joylashgan bo‗ladi va uni teng ikkiga bo‗lish kerak, hosil bo‗lgan natijalarni yana teng ikkiga bo‗lish lozim;
shu tarzda axborotdagi har bir belgining paydo bo‗lish chastotasi topilguncha bo‗lish davom ettiriladi.
misol: Quyidagi ko‗rinishda axborot berilgan bo‗lsin: BBCBBBCDDEDAAADDFFGGHHEE.
Xaffman algoritmi bo‗yicha hisoblash natijalari 2.2-jadvalda keltirilgan.
2.2-jadval.
Xaffman algoritmi bo‗yicha hisoblash natijalari
| 