Axborotni lug‘atli Lempel-Ziv arxivlash usullari


Axborotni iboralarga bo‘lish



Download 130,5 Kb.
bet3/4
Sana26.04.2022
Hajmi130,5 Kb.
#583001
1   2   3   4
Axborotni iboralarga bo‘lish

a

aa

b

ba

baa

baaa

bab

Raqamlarga ajratish

1

2

3

4

5

6

7

Natija

(0,a)

(1,a)

(0,b)

(3,a)

(4,a)

(5,a)

(4,b)

Axborotdagi har bir harf yoki iboralar (harflar birlashmasi) o‘zidan oldin qaytarilgan iboralar (harflar birlashmasi) va qo‘shuv mavjud bo‘lgan simvol bilan kodlanadi. Masalan oxirgi uchta belgi 4 (“b”) iborasi sifatida kodlashtiriladi.


Ko‘rsatkichning oldinga siljish uzoqligi cheklanmagan (ya’ni, oyna yo‘q), shuning uchun kodlash bajarilayotganida jumlalarning to‘planib borishi ko‘payadi. Ularning ixtiyoriy ravishda ko‘p miqdoriga yo‘l qo‘yilishi ko‘rsatkich o‘lchamini kattalashtirishni talab etadi. R jumla ajratilgan bo‘lsa, ko‘rsatkich [log R] bitlari sifatida taqdim etiladi. Amaliyotda lug‘at cheksiz ravishda o‘sib borishi mumkin emas. Foydalanish mumkin bo‘lgan xotira to‘lganidan so‘ng, u tozalanadi va yangi matn boshidan boshlangani singari kodlash davom etadi. LZ78 ning eng yaxshi amaliy hususiyati, kiritish yordamida raqamli qidiruv daraxtidan samarali qidiruv hisoblanadi. Har bir tugun tomonidan taqdim etiladigan jumla raqamini o‘z ichiga oladi. Chunki kiritiladigan jumla undan oldingilardan biriga faqat bitta simvolga uzunroq bo‘ladi, bunda ushbu operatsiyani amalga oshirish uchun kodlovchi daraxtdan bitta shox pastga tushishi kerak bo‘ladi. LZ78 ning muhim nazariy xususiyati joriy matnni statsionar ergodik manba bilan ishlab chiqarishdagi kiritishning ma’lum darajada oshishida siqish optimalroq bo‘lib hisoblanishidir. Bu shuni anglatadiki, LZ78 manba entropiyasi tomonidan belgilangan minimal o‘lchamga cheksiz uzunlikdagi satrni keltiradi. Faqat ayrim siqish usullari ushbu xususiyatga egadir. Agar u tomonidan amalga oshiriladigan istalgan ketma-ketlik uni o‘z uzunligining o‘sishiga nisbatan aniqroq xarakterlasa, manba ergodik hisoblanadi. Bu o‘ta zaif cheklash bo‘lganligi tufayli, LZ78 matnlarni siqish muammosining yechimi bo‘lib ko‘rinishi mumkin. Biroq, optimallik kiritish hajmi cheksizlikka intilishida hosil bo‘ladi, matnlarning ko‘pchiligi esa ancha qisqaroqdir. Bu jumlani butun kodning o‘lchamidan ancha kichik bo‘lgan aniq simvol o‘lchamiga asoslangan. Uning uzunligi 8 bit bo‘lganligi bois, 2^40 jumlani yaratishda u atigi chiqarishning 20 % ni egallaydi. Agar davomiylikdagi kiritish imkoni bo‘lganida ham xotirani siqish optimal bo‘lishidan ancha ilgariroq to‘ldiririladi. Real vazifa - LZ78 qanchalik tez ushbu chegaraga mos kelishini ko‘rishdir. Amaliyotda ko‘rganimizdek, muvofiqlik bu nisbatan sekinlikdir, LZ77 bilan qiyoslash usuli shundan iborat.
Hozirgi kunga kelib LZ oilasiga mansub bo‘lgan algoritmlar ichida eng samaraliroqlaridan biri bu LZSS algoritmi hisoblanadi. Ushbu algoritm 1982 yilda Storer va Szimanskilar tomonidan LZ77 algoritmini modifikatsiyalash natijasida paydo bo‘ldi. Ushbu algoritm vositasida axborotni kodlashtirilsa siqish koeffitsientining qiymati bir necha barobar katta. Ushbu algoritm asosida axborotni kodlashtirishga misol ko‘rib chiqamiz (2.6-jadval).
2.6-jadval
Hisoblash natijalari


Download 130,5 Kb.

Do'stlaringiz bilan baham:
1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish