2 -laboratoriya

2 -Laboratoriya

Ma’lumotlarni siqish algoritmlari (Lempel – Ziv, LZSS algoritmlari) ni tadqiq qilish

Ishning maqsadi:

1. 
   Axborotni siqib beruvchi Lempel - Ziva algoritmlari bilan tanishib chikish;
   
2. 
   Axborotni yukotishsiz siqib beruvchi LZSS algoritmi yordamida axborotni hajmini kamaytirish bo‘yicha amaliy ko‘nikmalarga ega bo‘lish.
   

Nazariy ma’lumot:

Lempel – Ziva algoritmlarini iboralar bo‘yicha arxivlovchi algoritmlar deyiladi, chunka ushbu algoritmlarda axborotdagi iboralar yoki harflar birlashmasi o‘zidan olidinroq qaytarilgan xuddi shunday ibora yoki harflar birlashmasi bilan almashtirishga asoslangan. Iboralar bo‘yicha yo‘qotishsiz arxivlovchi algoritmlarni ayrim adabiyotlarda jadval asosida arxivlovchi algoritmlar ham deyiladi. Ushbu algoritmlarni asoschilari Yakoba Ziva (Jakob Ziv) va Abraxam Lempel (Abraham Lempel) hisoblanadi. Iboralar bo‘ycha arxivlovchi algoritmlar dastlabkisi 1977 yilda paydo bo‘ldi va ushbu algoritmnig nomi LZ77 deb nomlangan. Keyinchalik bir yildan so‘ng ushbu algoritmning modifikatsiyalangan varianti yaratildi va algoritm nomi LZ78 deb atala boshlandi. Keyinchalik ushbu LZ oilasiga mansub bo‘lgan ko‘plab yangi arxivlovchi algoritmlar paydo bo‘ldi. Ushbu oilaga mansub bo‘lgan eng sodda algoritmlardan biri hisoblanadigan LZ78 algoritmi yordamida axborotni kodlashtirish jarayonini ko‘rib chiqamiz. Masalan ushbu axborotni kodlashtirish talab qilsin "aaabbabaabaaabab". Ushbu axborotni jadval 2.1 ko‘rsatilganidek yettita ta mayda iboralarga (harflar birlashmasi) bulamiz. Axborotdagi har bir harf yoki iboralar (harflar birlashmasi) o‘zidan oldin qaytarilgan iboralar (harflar birlashmasi) va qo‘shuv mavjud bo‘lgan belgi bilan kodlanadi. Masalan, oxirgi uchta belgi 4 ("b") iborasi sifatida kodlshtiriladi. 2.1 - jadval LZ78 algoritmi yordamida "aaabbabaabaaabab" axborotni kodlashtirish natijalari keltirilgan.

2.1 - jadval

LZ78 algoritmi yordamida "aaabbabaabaaabab" axborotni kodlashtirish natijalari