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.

Yo'qotilgan siqishsiqilgan arxivni bo'shatgandan so'ng, avvalgisidan biroz farq qiladigan ma'lumotlar olinadi. Shubhasiz, siqilish darajasi qanchalik katta bo'lsa, yo'qotish hajmi va aksincha.

Albatta, bunday algoritmlar matnli hujjatlar, ma'lumotlar bazasi jadvallari va dasturlarida qo'llanilmaydi. Oddiy, formatlanmagan matnda siz ozgina buzilishlardan omon qolishingiz mumkin, ammo dasturda kamida bitta bitni buzish uni to'liq ishlamay qolishiga olib keladi.

Shu bilan birga, o'nlab marta siqishni olish uchun ma'lumotlarning bir necha foizini qurbon qilish mumkin bo'lgan ma'lumotlar mavjud, masalan, fotosuratlar, video va audio materiallar. Bunday ma'lumotlarning siqilishi va keyinchalik dekompressiyasi paytida yo'qolishi qo'shimcha "shovqin" paydo bo'lishi sifatida qabul qilinadi.

Axborot yo'qotishni siqish algoritmlari quyidagilar kabi algoritmlarni o'z ichiga oladi Jpeg(rasmlarni siqishda foydalaniladi) va MPEG(video va audioni siqishda foydalaniladi). Axborot yo'qotishlarni siqish algoritmlari faqat iste'molchilar uchun mo'ljallangan vazifalar uchun ishlatiladi.

Siqish paytida ruxsat etilgan yo'qotishning kattaligi odatda boshqarilishi mumkin, bu sizga "o'lcham / sifat" ning maqbul nisbatiga erishishga imkon beradi. Ekranda namoyish etilishi mo'ljallangan fotografiyalarda ma'lumotning 5% yo'qolishi odatda tanqidiy emas, ba'zi hollarda esa 20-25% yo'qolishi mumkin.

Usullari ma'lumotni yo'qotmasdan siqishniular matnli hujjatlar va dasturlar bilan ishlashda qo'llaniladi va ma'lumotlarning yo'qolishiga yo'l qo'ymaydi. Ular faqat uning ortiqcha bo'lishini yo'q qilishga asoslangan.

1-misol Ukraina tilida 32 ta harf, o'nta raqam va o'nlab o'nlab tinish belgilari va boshqa maxsus belgilar mavjud. Faqat katta harflar bilan yozilgan matn uchun (telegramdagi kabi) oltmish xil ma'no etarli bo'ladi. Biroq, har bir belgi odatda 8 bitdan iborat va 256 xil kodlarni ifoda etadigan baytda kodlangan. Bu zaxira uchun birinchi asosdir. "Telegraf" matni uchun har bir belgi uchun 6 bit etarli bo'ladi.

Shakl 1. Morse kodi

2-misol Xalqaro ASCII belgilar kodlashda har qanday belgi kodlash uchun bir xil miqdordagi bitlar ajratilgan (8). Biroq, eng keng tarqalgan belgilar kamroq belgilarni kodlash uchun mantiqiy ekanligi aniq. Shunday qilib, masalan, in morse kodiko'pincha topilgan "E" va "T" harflari bitta belgi bilan kodlangan (mos ravishda bu nuqta va tire). Va "Yu" (-) va "Ts" (- -) kabi noyob harflar to'rtta belgi bilan kodlangan. Samarasiz kodlash - bu ortiqcha to'lovning ikkinchi sababi.

Axborotni siqishni amalga oshiradigan dasturlar o'zlarining kodlashlarini (turli xil fayllar uchun har xil) kiritishlari va siqilgan faylga ma'lum bir jadval (lug'at) belgilashlari mumkin, bunda paketdan chiqarish dasturi ushbu faylda qanday belgilar va ularning guruhlari kodlanganligini bilib oladi. Axborotni transkodlashga asoslangan algoritmlar deyiladi xuffman algoritmlari.

Ikki nusxadagi bo'laklarning mavjudligi ortiqcha sonning uchinchi sababi hisoblanadi. Bu matnlarda kam uchraydi, lekin jadval va grafikalarda kodlarning takrorlanishi odatiy holdir. Masalan, agar 0 soni ketma-ket yigirma marta takrorlangan bo'lsa, unda yigirma nol baytni qo'yish mantiqiy emas. Buning o'rniga, ular bitta nol va 20 koeffitsientini qo'yadilar. Takrorlanishlarni aniqlashga asoslangan bunday algoritmlar usul deb ataladi seriyali uzunlikdagi kodlash(RLE,Kod uzunligini kodlash) Bir xil baytlarning katta takroriy ketma-ketligi ayniqsa grafik rasmlar bilan ajralib turadi. Usul "pikselga bayt" formatidagi grafik tasvirlar uchun juda samarali (masalan, formatlar) Pcxyoki BMP).

Qattiq disklarda zaxira nusxalarini yaratishda, fayllarni siqish paytida ish joyida daromad olishning yana bir imkoniyati mavjud, bu ma'lumotlarning ko'payishi bilan emas, balki kompyuterning fayl tizimini tashkil qilish bilan bog'liq. Uning mohiyati shundan iboratki, katta yoki kichik har qanday fayl faqat diskdagi butun sonlarni egallashi mumkin. FAT16 fayl tizimida qattiq diskda 65536 dan ortiq klaster bo'lishi mumkin (2 16). Bu shuni anglatadiki, hajmi 1 dan 2 GB gacha bo'lgan drayvlar uchun klaster hajmi 32 Kbni tashkil qiladi.

Katta guruhli fayllarni bitta faylga siqish paytida, fayl tizimining mantiqsiz tashkil etilishi natijasida yo'qotishlarning kamayishi tufayli bitta faylga kamida 16 Kbayt tejash kerak.

FAT32 uchun daromad kichikroq, ammo bu holda klasterning minimal hajmi 4 KB ni tashkil qiladi, shuning uchun ko'p miqdordagi kichik fayllar bilan ishlayotgan bo'lsangiz, unda saqlash kerak bo'lgan narsa ham mavjud.

Ko'p turli xil siqish usullari mavjud bo'lsa-da, ba'zilari mavjud tamoyillari va qoidalaribu barcha siqish usullariga xosdir. Ular ma'lum bo'lishi va to'g'ri ishlatilishi kerak.

1. Har qanday siqishni chegarasi bor,ya’ni ilgari siqilgan faylni zichlashtirish hech qanday foyda keltirmaydi va eng yomon holatda natijada olingan fayl hajmining yo'qolishiga olib kelishi mumkin.

Kecha, gigabayt o'lchamdagi disk shunchalik ko'p bo'ldiki, uni qanday to'ldirishni ham bilmayman, va har kim hamma o'zlariga shunday o'ylardi: agar men bir gigabayt xotiraga ega bo'lsam, "ochko'zlik" qilishni bas qilaman va ma'lumotlarimni nima bilan siqaman. arxivchilar. Ammo, dunyo, shunchalik tartibga solinganki, "muqaddas joy bo'sh bo'lmaydi" va bizda qo'shimcha gigabayt mavjud bo'lganda - uni to'g'ri to'ldiradigan narsa bor. Va dasturlarning o'zlari, siz bilganingizdek, tobora ko'payib bormoqda. Demak, terabayt va ekzabaytlar bilan bir xil bo'ladi.

Shuning uchun, disk xotirasi qancha o'smasin, ular ma'lumot yig'ishni to'xtatmayotganga o'xshaydi. Aksincha, "kompyuterdagi joy" tobora ko'payib borar ekan, yangi arxivchilar soni ko'paymoqda, ularni ishlab chiquvchilar nafaqat interfeys qulayligida raqobatlashmaydilar, balki avvalambor, ma'lumotni yanada zichroq va zichroq to'plamoqchi bo'lmoqdalar.

Biroq, bu jarayon cheksiz emasligi aniq. Ushbu chegara qaerda joylashgan bo'lsa, bugungi kunda qanday arxivchilar mavjud, ular qanday parametrlarda bir-biri bilan raqobatlashadi va yangi arxivni qaerdan topish mumkin - bu maqolada keltirilgan muammolarning to'liq ro'yxati emas. Nazariy masalalarni hal qilish bilan bir qatorda, hal qilinayotgan vazifalarning xususiyatlariga qarab, muayyan dasturning samaradorligini tekshirish va ulardan eng maqbulini tanlash uchun biz diskdan yuklab olinadigan arxivchilarni tanladik.