№1 laboratoriya ishi




Download 5,31 Mb.
bet2/4
Sana16.05.2024
Hajmi5,31 Mb.
#237499
1   2   3   4
Bog'liq
1 -2-3-LABORATORIYA ISHI (5)

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


Download 5,31 Mb.
1   2   3   4




Download 5,31 Mb.