Belgilar
|
Paydo bo‘lish chastotasi
|
Yordamchi jadval
|
Kodi
|
B
|
5
|
1
|
1
|
|
11
|
D
|
5
|
0
|
1
|
101
|
A
|
3
|
0
|
100
|
E
|
3
|
0
|
1
|
1
|
011
|
C
|
2
|
0
|
010
|
F
|
2
|
0
|
1
|
|
001
|
G
|
2
|
0
|
1
|
0001
|
H
|
2
|
0
|
0000
|
Kodli kombinatsiyaning o‘rtacha uzunligini hisoblaymiz:
bitga teng.
Xaffman algoritmi
Hozirgi kunda eng keng tarqalgan, amaliyotda ko‘p ishlatiladigan entropiyali kodlash usuliga asoslangan yo‘qotishsiz siqish algoritmlaridan biri bu –Xaffman algoritmi hisoblanadi. Xaffman algoritmi asosida matnli axborotlar siqiladi.
1. Axborotdagi barcha belgilar soni, ya’ni N ni hisoblanadi
2. Jami N ta belgidan iborat bo‘lgan axborotdagi Har bir belgining paydo bo‘lish chastotasi hisoblanadi.
3. Har bir belgining paydo bo‘lish chastotasini kamayib borish tartibida jadvalga joylashtiriladi
4. Jadvaldagi oxirgi ikkita chastota yig‘indisi hisoblanib, bitta umumiy bo‘lgan yig‘indi chastotaga birlashtiriladi.
5. Hisoblangan yangi yig‘indi chastotadan va hisoblashda qatnashmagan boshqa chastotalardan jadvalning yangi ustuni hosil qilinadi (bunda ham chastotalar kamayib borish tartibida joylashtiriladi)
6. Shu tarzda to bitta umumiy N ga teng bo‘lgan yig‘indi hosil bo‘lguncha jarayon davom etaveradi
7. Jadval to‘ldirilgandan so‘ng, jadvaldagi hisoblashlarga muvofiq daraxt quriladi (1.2-rasm).
8. Daraxtning tepa qismida N joylashgan bo‘ladi va uni teng ikkiga bo‘lish kerak, hosil bo‘lgan natijalarni yana teng ikkiga bo‘lish kerak. Shu tarzda axborotdagi har bir belgini paydo bo‘lish chastotasi topilguncha bo‘lishni davom ettirish kerak.
2-misol: Quyidagi ko‘rinishda axborot berilgan bo‘lsin: BBCBBBCDDEDAAADDFFGGHHEE.
Ushbu algoritm bo‘yicha hisoblash natijalari 1.2-jadvalda keltirilgan.
1.2-jadval
Xaffmen algoritmi bo‘yicha hisoblash natijalari
Belgilar
|
Paydo bo‘lish chastotasi
|
Yordamchi jadval
|
B
|
5
|
5
|
5
|
6
|
8
|
10
|
14
|
24
|
D
|
5
|
5
|
5
|
5
|
6
|
8
|
10
|
|
A
|
3
|
4
|
4
|
5
|
5
|
6
|
|
|
E
|
3
|
3
|
4
|
4
|
5
|
|
|
|
C
|
2
|
3
|
3
|
4
|
|
|
|
|
F
|
2
|
2
|
3
|
|
|
|
|
|
G
|
2
|
2
|
|
|
|
|
|
|
H
|
2
|
|
|
|
|
|
|
|
1.2-rasm. Xaffman algoritmining daraxtsimon ko‘rinishi
1.3-jadval
Xaffman algoritmida har bir belgini paydo bo‘lish chastotasi
Belgilar
|
B
|
D
|
A
|
E
|
C
|
F
|
G
|
H
|
Kodi
|
01
|
00
|
100
|
101
|
1101
|
1100
|
1111
|
1110
|
|
