Ma'lumotni siqish usullari

Saidjalolov M

Ma'lumotni siqish usullari birinchi kompyuter paydo bo'lishidan ancha oldin boshlangan rivojlanishning uzoq tarixiga ega. Ushbu maqolada asosiy nazariyalar, g'oyalar tushunchalari va ularni hayotga tatbiq etish haqida qisqacha ma'lumot berishga harakat qilinadi, ammo bu mutlaqo to'liqlikni talab qilmaydi. Batafsil ma'lumotni, masalan, Krichevskiy R.E.dan topish mumkin. Ryabko B.Ya. , Witten I.H. , Rissanen J., Huffman D.A., Gallager R.G. , Knut D.E. , Vitter J.S. va boshq.
Axborotni siqish - bu kompyuter texnologiyalarining rivojlanish tarixidan ancha uzoq tarixga ega bo'lgan muammodir, odatda (tarix) axborotni kodlash va shifrlash muammolari rivojlanish tarixi bilan birga keladi. Barcha siqish algoritmlari kirishning oqimi bilan ishlaydi, ularning minimal birligi bir oz, maksimal esa bir necha bit, bayt yoki bir necha bayt. Siqish jarayonining maqsadi, qoida tariqasida, ba'zi bir transformatsiyalar yordamida ba'zi boshlang'ich kompakt bo'lmagan kirish oqimlaridan ma'lumot birliklarining yanada ixcham chiqish oqimini olishdir. Siqish jarayonlarining asosiy texnik xususiyatlari va ularning ishlash natijalari quyidagilardan iborat.
Siqish darajasi (siqish darajasi) yoki manba va natijada paydo bo'ladigan oqimlarning hajmiga nisbati;
Siqish tezligi - undan oqimning ekvivalent chiqish oqimini olish uchun kirish oqimining ma'lum miqdorini siqish uchun sarflangan vaqt;
Siqish sifati - bir xil yoki boshqa algoritmdan foydalanib, unga qayta siqishni qo'llash orqali chiqish oqimi qancha miqdorda to'ldirilishini ko'rsatadigan qiymat.
Axborotni siqish muammosiga turli xil yondashuvlar mavjud. Ba'zilarida juda murakkab nazariy matematik baza mavjud, boshqalari axborot oqimining xususiyatlariga asoslangan va algoritmik darajada etarlicha sodda. Ma'lumotni siqishni yoki siqishni amalga oshiradigan har qanday usul va algoritm, qaytariladigan yoki qaytarib bo'lmaydigan o'zgartirilishi orqali bitlarda axborot chiqishi oqimini kamaytirishga mo'ljallangan. Shuning uchun, birinchi navbatda, ma'lumotlarning tabiati yoki formati bilan bog'liq mezon bo'yicha barcha siqishni usullarini ikki toifaga bo'lish mumkin: qaytariladigan va qaytarib bo'lmaydigan siqish.
Qaytarib bo'lmaydigan siqish deganda kirish ma'lumotlari oqimining o'zgarishi tushuniladi, unda ma'lum bir ma'lumot formatiga asoslangan chiqish oqimi, ba'zi nuqtai nazardan, tashqi xarakteristikalarda kirish oqimiga mutlaqo o'xshash bo'lgan, ammo hajmidan farq qiladigan ob'ektni anglatadi. Kirish va chiqish oqimlarining o'xshashligi darajasi ushbu ma'lumot oqimi bilan ifodalangan ob'ektning ba'zi xususiyatlarining (ya'ni, ma'lum bir ma'lumot formatiga muvofiq siqilgan va siqilmagan ma'lumotlar) muvofiqligi darajasi bilan belgilanadi. Bunday yondashuvlar va algoritmlar, masalan, oqimdagi baytlarning past darajadagi takrorlanish darajasi past bo'lgan grafik fayllarning ma'lumotlarini siqish uchun ishlatiladi. Ushbu yondashuv grafik faylning tuzilish formatining xususiyatidan va displey sifatida (inson ko'zi bilan ko'rish uchun) bir xil (yoki aniqroq n) usulda grafik rasmni taqdim etish qobiliyatidan foydalanadi. Shuning uchun, siqilish darajasi yoki kattaligiga qo'shimcha ravishda, bunday algoritmlarda sifat tushunchasi paydo bo'ladi, chunki siqish jarayonida asl rasm o'zgaradi, keyin sifatni ma'lumot formatiga qarab, sub'ektiv ravishda baholangan asl va natijada olingan rasmning muvofiqlik darajasi deb tushunish mumkin. Grafik fayllar uchun bunday yozishmalar vizual ravishda aniqlanadi, ammo mos keladigan aqlli algoritmlar va dasturlar mavjud. Qaytish mumkin bo'lgan siqishni, kirish va chiqish oqimlarining axborot tuzilishining aniq muvofiqligi zarur bo'lgan joylarda qo'llash mumkin emas. Ushbu yondashuv JPEG va JFIF algoritmlari va JPG va JIF fayl formatlari deb nomlanuvchi video va foto ma'lumotlarini taqdim etishning mashhur formatlarida amalga oshiriladi.
Qayta tiklanadigan siqish har doim axborot tarkibini o'zgartirmasdan, ya'ni chiqarilayotgan axborot oqimi hajmining pasayishiga olib keladi, ya'ni. - axborot tuzilishini yo'qotmasdan. Bundan tashqari, chiqish oqimidan qutqarish yoki dekompressiya algoritmidan foydalangan holda siz kirishni olishingiz mumkin va tiklash jarayoni dekompressiya yoki dekompressiya deb ataladi va dekompressiya jarayonidan so'ng ma'lumotlar ularning ichki formatiga muvofiq qayta ishlashga mos keladi.
Qayta tiklanadigan algoritmlarda jarayon sifatida kodlashni statistik nuqtai nazardan ko'rib chiqish mumkin, bu nafaqat siqishni algoritmlarini tuzishda, balki ularning samaradorligini baholashda ham foydalidir. Qaytariladigan barcha algoritmlar uchun kodlash qiymati tushunchasi mavjud. Kodlash narxiga bitdagi kod so'zining o'rtacha uzunligi kiradi. Kodlashning qisqarishi xarajat va kodlash entropiyasi o'rtasidagi farqga teng va yaxshi siqish algoritmi har doim ortiqcha ishlarni kamaytirishi kerak (esda tutingki, ma'lumotlarning entropiyasi uning buzilishini o'lchaydi.) Shannonning ma'lumotni kodlash bo'yicha asosiy teoremasi "kodlash har doim manba atrof-muhitidan kam emas, garchi unga o'zboshimchalik bilan yaqinlashishi mumkin". Shuning uchun har qanday algoritm uchun har doim kirish oqimining entropiyasi tomonidan aniqlanadigan siqilish darajasida har qanday cheklov mavjud.
Endi biz to'g'ridan-to'g'ri qaytariladigan algoritmlarning algoritmik xususiyatlariga murojaat qilamiz va kodlash tizimlari va axborotni siqish usullarini amalga oshirish bilan bog'liq ma'lumotlarni siqishning eng muhim nazariy yondashuvlarini ko'rib chiqamiz.

Seriyali kodlarni siqish

Qayta tiklanadigan usulda ma'lumotlarni siqish uchun eng taniqli oddiy yondashuv va algoritm ketma-ketlikni kodlashdir (Run Length Encoding - RLE). Ushbu yondashuv usullarining mohiyati zanjirlarni yoki takrorlanuvchi baytlar seriyasini yoki ularning ketma-ketligini bitta kodlash bayti va takroriy sonlarning hisoblagichiga almashtirishdir. Shunga o'xshash barcha usullar bilan muammo shundan iboratki, dekompressiya algoritmi kodlangan seriyani boshqa bayt oqimlaridan ajratib olish usulini - kodlanmagan baytlar ketma-ketligini aniqlashdir. Muammoni hal qilishga odatda kodlangan zanjirlarning boshida yorliqlarni o'rnatish orqali erishiladi. Bunday yorliqlar, masalan, kodlangan seriyaning birinchi baytidagi bitlarning xarakterli qiymatlari, kodlangan seriyaning birinchi baytining qiymatlari va boshqalar bo'lishi mumkin. Ushbu usullar odatda rastrli grafik tasvirlarni (BMP, PCX, TIF, GIF) siqish uchun juda samarali, chunki ikkinchisida baytlarning takrorlanadigan ketma-ketliklari juda ko'p. RLE usulining kamchiliklari nisbatan kam siqilish nisbati yoki kam sonli seriyalar bilan fayllarni kodlash qiymati va undan ham yomoni, ketma-ket kam sonli takroriy baytlar mavjudligi.

RLE siqish

RLE usulidan foydalanmasdan ma'lumotlarni siqish jarayonini ikki bosqichga bo'lish mumkin: modellashtirish (modellashtirish) va aslida kodlash. Ushbu jarayonlar va ularni amalga oshirish algoritmlari ancha mustaqil va xilma-xil.

Kodlash jarayoni va uning usullari

Kodlash deganda odatda alfavitda belgilar oqimini (baytlar yoki nibbles) qayta ishlash tushuniladi va oqimdagi belgilar paydo bo'lish chastotalari turlicha. Kodlashning maqsadi - bu oqimni simvol chastotalarini hisobga olgan holda kirish oqimining entropiyasini kamaytirish orqali erishiladigan minimal uzunlikdagi oqimga aylantirish. Oqim alfavitidagi belgilarni ifodalovchi kodning uzunligi kirish oqimi ma'lumotiga mutanosib bo'lishi kerak va bitdagi oqim belgilarining uzunligi 8 dan ko'p bo'lmasligi yoki hatto o'zgarmas bo'lishi mumkin. Agar kirish oqimining alfavitidan belgilar paydo bo'lish chastotalarining ehtimollik taqsimoti ma'lum bo'lsa, unda biz optimal kodlash modelini tuzishimiz mumkin. Ammo juda ko'p sonli turli xil fayl formatlari mavjudligi sababli, vazifa ancha murakkablashadi, chunki Ma'lumot belgilarining chastota taqsimoti oldindan ma'lum emas. Bunday holda, umuman olganda, ikkita yondashuv qo'llaniladi.
Birinchisi, kirish oqimini ko'rish va to'plangan statistika asosida kodlashni yaratish (bu holda fayldan ikkita o'tish kerak - biri statistik ma'lumotni ko'rish va to'plash uchun, ikkinchisi kodlash uchun, bunday algoritmlarni qo'llash doirasini biroz cheklaydi, chunki shunday qilib, , telekommunikatsiya tizimlarida ishlatiladigan "parvozda" bir martalik kodlash imkoniyatini yo'q qiladi, bu erda ma'lumotlar miqdori ba'zan noma'lum va ularni qayta yuborish yoki tahlil qilish asossiz uzoq vaqt talab qilishi mumkin). Bunday holda, ishlatilgan kodlashning statistik sxemasi chiqish oqimiga yoziladi. Ushbu usul Huffman statik kodlash nomi bilan tanilgan.
Axborotni siqish algoritmlarini ishlab chiqish amaliy matematikaning bir sohasiga tegishli. Ular tabiiy zaxirani yo'q qilish tamoyiliga asoslanadi.
Axborotni siqish usullari an'anaviy ravishda ikkita ajratish sinfiga bo'linadi: yo'qolgan siqishva ma'lumotni yo'qotmasdan siqishni.