4-ma’ruza. Yo‘qotishli va yo‘qotishsiz siqish usullari

Yo‘qotishsiz siqish usulida siqish algoritmi bilan kodlashtirilgan ma’lumot (raqamli holatga keltirilgan video, audio, grafik hujjatli ma’lumotlar ) oxirgi bit aniqligida dekodlashtiriladi.
Bu usulda har bir turdagi raqamli axborot uchun optimal yo‘qotishsiz siqish algoritmi qo‘llaniladi.
Usul juda ko‘p ilovalarni siqishda va fayl arxivatorlarida ishlatiladi. Hamda yo‘qotishli siqish algoritmlarida asosiy komponent sifatida ham qo‘llaniladi. Usul siqilgan ma’lumot originali bilan bir xil bo‘lishi muhim blgan hollarda qo‘llaniladi, masalan bajariladigan fayl va uning kodlashtirilgan ko‘rinishi.
Umumiy ko‘rinishda yo‘qotishsiz siqish usuli quyidagicha izohlanadi:
Berilgan birlamchi ma’lumotda iboralar ishlatilishining qonuniyati aniqlanadi va unga asosan birlamchi ketma-ketlikni to‘liq tavsiflaydigan ikkinchi ketma - ketlik generasiya qilinadi. Masalan, “0” iboralari ko‘p va “1” iboralari kam ikkilik ketma-ketlikni kodlashtirishda quyidagi almashtirishlarni qo‘llash mumkin:
00 → 0
01 → 10
10 → 110
11 → 111
Bunda 16 bitli ushbu ko‘rinishdagi axborot 00 01 00 00 11 10 00 00
13 bitli axborotga almashtiriladi 0 10 0 0 111 110 0 0
Bunday o‘zgartirish quyidagi xususiyatga ega: siqilgan qatorni probelsiz yozib chiqilgan taqdirda ham unga probellar qo‘yib, birlamchi ma’lumotni tiklash mumkin bo‘ladi. Bunday usulda yaratilgan kod prefiksli kod deb yuritiladi.
Bunday kodlashtirishga Xaffman kodini misol qilib keltirish mumkin.
Ko‘pchilik yo‘qotishsiz siqish algoritmlari ikki bosqichda ishlaydi:

• 
  birinchi bosqichda birlamchi ma’lumotning statistik modeli generasiya qilinadi, ko‘p uchraydigan elementlari va ularning ehtimollari aniqlanadi;
  
• 
  ikkinchi bosqichda statistik modelning “bit”dagi (ya’ni, ikkilik sistemadagi) ko‘rinishi yaratiladi.
  

Tekst ma’lumotlari uchun statistik model algoritmi quyidagilardan tarkib topadi:
1. Barrouz-Uiler usuli bo‘yicha statistik model yaratish, ya’ni bloklarga ajratish yo‘li bilan sortirovkalash - siqish jarayonlarining samarasini oshiradi. Bunda ishlatiladigan algoritmlar quyidagicha nomlanadi :
LZ77 va LZ78 (DEFLATE),
LZW
2. Bitlar ketma-ketligini generasiya qilish orqali kodlashtirish algoritmlari sifatida Xaffman va arifmetik kodlashtirish usullari qo‘llaniladi.