2.2 Xuffmann algoritmi.
Bu algoritm 1952-yilda D.A. Xuffmann tomonidan ishlab chiqilgan. Xuffmann algoritmidan foydalanib faylni siqib chiqarishda biz birinchi navbatda faylni to’liq o’qib chiqish va kengaytirilgan ASCII to’plamidagi har bir belgi necha marta sodir bo’lishini hisoblashimiz kerak. Agar biz barcha 256 belgilarni hisobga olsak, unda biz uchun matn va EXE fayllarini siqishda hech qanday farq bo’lmaydi. Har bir belgi paydo bo’lish chastotasini hisoblab chiqqandan so’ng, ASCII kodlash jadvaliga qarab ikkilik kodlari hosil qiladi.
Misol.
Bizda 100 bayt uzunlikdagi fayl mavjud va 6 xil belgilar mavjud. Biz fayldagi har bir belgini paydo bo’lishini hisoblab chiqdik.:
Belgi
|
A
|
B
|
C
|
D
|
E
|
F
|
Kirish soni
|
10
|
20
|
30
|
5
|
25
|
10
|
Endi biz ushbu raqamlarni olamiz va ularni har bir belgi uchun paydo bo’lish chastotasi deb ataymiz.
Belgi
|
C
|
E
|
B
|
F
|
A
|
D
|
Kirish soni
|
30
|
25
|
20
|
10
|
10
|
5
|
Biz oxirgi jadvaldan eng kam chastotali 2 belgini olamiz. Bizning holatlarimizda, bu D(5) va F yoki A(10) har qanday belgi, biz ulardan birini,A ni olishimiz mumkin.
Biz D va A “tugun”lardan yangi “tugun” hosil qilamiz, ularning paydo bo’lish chastotasi D va A chastotalarining yig’indisiga teng bo’ladi:
Belgi
|
C
|
A
|
D
|
F
|
B
|
E
|
Kirish soni
|
30
|
10
|
5
|
10
|
20
|
25
|
Kadrdagi raqam D va A harflarining chastotalari yig’indisidir. Endi biz yana eng kam uchraydigan chastotali ikkita belgini qidirmoqdamiz. D va A ni hisobga olmaganda paydo bo’lish chastotasiga ega yangi “ tugun”. Endi eng past chastota F va u yangi “tugun”da. Shunga qaramay, biz tugunlarni birlashtirish ishlarini bajaramiz. Keyingi ikkita belgilar uchun jadvalni yana ko’rib chiqamiz ( B va E). Biz butun “daraxt” hosil bo’lguncha ushbu rejimga o’tamiz, ya’ni hamma narsa bitta tugunga tushguncha. Endi bizning “daraxti”miz yaratildi, biz faylni kodlashimiz mumkin. Biz har doim “ildiz”dan boshlashimiz kerak (Root). Birinchi belgini (C daraxtning bargini) kodlash bilan biz daraxtning shoxlari bo'ylab barcha burilishlarni kuzatamiz va chap burilish qilsak, 0-bitni va shunga o'xshash o'ng burilish uchun 1-bitni eslaymiz. Shunday qilib, C uchun chapga 55 ga o'tamiz (va 0 ni eslaymiz), so'ngra yana belgini (0) chapga o'tkazamiz. C belgimiz uchun Huffman kodi 00 ga teng. Keyingi belgilar uchun (A) biz olamiz - chapga, o'ngga, chapga, chapga, bu 0100 ketma-ketlikni o'zgartiradi. Yuqoridagi so'zlarni barcha belgilar uchun to'ldirgandan so'ng, biz quyidagilarni olamiz:
C = 00 (2 bit)
A = 0100 (4 bit)
D = 0101 (4 bit)
F = 011 (3 bit)
B = 10 (2 bit)
E = 11 (2 bit)
Misol.
WENEEDMORESNOWFORBETTERSKIING
Xuffman algoritmidan foydalanib arxivlang.
|
