Mavzu: ma’lumotlar hajmini siqish algoritmlari reja

1.2 Kodlash jarayoni va uning usullari

Serial kodlashidan foydalangan holda siqishni Axborotni siqish uchun eng taniqli oddiy yondashuv va algoritm qaytariladi - bu ketma-ketlik seriyasining kodlashidir (tezda kodlash - rl). Ushbu yondashuv usullarining mohiyati - bu zanjirlar yoki bir qator axlat baytini yoki ularning ketma-ketligini bitta kodi baytiga va takrorlashlar sonini almashtirishda tashkil etadi. Barcha shunga o'xshash usullar muammosi faqat hosil bo'lgan bayt oqimida ajratilishi mumkin bo'lgan usulni aniqlashda, natijada yoki noto'g'ri tuzatilmagan baytlar ketma-ketligi bo'yicha kodlangan seriyalar. Muammoning echimi odatda kodlangan zanjirlarning boshida teglarni postlashi bilan erishiladi. Bunday teglar, masalan kodlangan seriyalarning birinchi baytasining birinchi baytining birinchi baytining va boshqalarning qiymatlari bo'lishi mumkin. Ushbu usullar odatda raster grafik tasvirlarini siqish (BMP, PCX, TIF, GIF, GIF) uchun juda samarali, chunki Ikkinchisida uzoq vaqt davomida takrorlanadigan baytlar ketma-ketliklari juda ko'p. Qovurilgan usulning noqulayligi - bu juda past siqish koeffitsienti yoki kam sonli seriyalar, hatto undan ham yomoni, hatto undan ham yomoni - bir qator takroriy vetriya bilan. Tarmoq usulini qo'llamasdan siqishni Rl usulidan foydalanishsiz ma'lumotlarni siqish jarayoni ikki bosqichga bo'linishi mumkin: modellashtirish (modellashtirish) va aslida, kodlash (kodlash). Ushbu jarayonlar va ularning amalga oshiradigan algoritmlar juda mustaqil va rang-barang.
Kodlash paytida odatda ba'zi alifboda belgilar oqimini qayta ishlashni tushunadi (bizning holatlarimiz yoki yarim tanamizda) va oqimdagi belgilar chastotasi boshqacha. Kodlashning maqsadi ushbu oqimni minimal uzunlikdagi ozgina oqimga aylantirishdir, bu esa belgilar chastotasini hisobga olgan holda kirish oqimining entrope-endopiyasining pasayishiga olib keladi. Oqim alifbosidagi belgilarni ifodalovchi kodning uzunligi kirish oqimlari ma'lumotlari hajmiga mutanosib bo'lishi kerak va bitlardagi oqim belgilarining uzunligi 8 ga va hatto o'zgaruvchan bo'lmasligi mumkin. Agar kirish oqimining alifbosidagi belgilar chastotalarini ehtimollik bilan taqsimlash ma'lum bo'lsa, unda maqbul kodlash modeli qurilishi mumkin. Biroq, turli xil fayl formatlari mavjudligini hisobga olgan holda, vazifa sezilarli darajada murakkab. Ma'lumotlar belgilarining ma'lumotlar chastotasi tarqalishi oldindan noma'lum. Bunday holda, ichkarida umumiyIkkala yondashuv qo'llaniladi. Birinchisi, to'plangan statistika asosida kiritish oqimini va qurilish kodini ko'rish (bu faylda ikkita faylni talab qiladi - bu statistik ma'lumotlarni, ikkinchi kodni ko'rib chiqing, ikkinchi kododikani ko'rib chiqing, bu esa bunday algoritmlarni qo'llash hajmini cheklaydi , shuning uchun telekommunikatsiya tizimlarida ishlatiladigan "chivinda" kodlash imkoniyati, qaerda va ularda ma'lumotlarning miqdori ma'lum emas va ulardan voz kechish yoki tahlil qilinishi mumkin emas. Bunday holda, ishlatilgan kodlashni statistik sxemasi chiqish oqimida qayd etiladi. Axborotni siqish algoritmlarining rivojlanishi amaliy matematika sohalaridan biriga tegishli. Ular tabiiy tejashni bartaraf etish tamoyiliga asoslanadi. Axborotni siqish usullari an'anaviy ravishda ikki tsikl bo'lmagan sinfga bo'linadi: ma'lumot yo'qolishi bilan siqishva ma'lumotni yo'qotmasdan siqish. Takroriy bo'laklarning mavjudligi ortiqchachilik uchun uchinchi asosdir. Matnlarda bu kamdan-kam, ammo jadvallarda va grafikada kodlarni takrorlash umumiy hodisadir. Masalan, agar 0 raqami ketma-ket yigirma marta takrorlansa, bu yigirmata nol baytni qo'yish uchun ma'nosi yo'q. Buning o'rniga, ular bitta nolni va koeffitsientni ushlab turishadi. Aniqlangan takrorlashlarga asoslangan bunday algoritmlar deyiladi seriya uzunligi kodlash(Rl,Ishlashning oxirgi kodlashi). Xuddi shu baytlarning katta protezlantiruvchi ketma-ketligi ayniqsa turli xil grafikli rasmlardir. Usul "pikselda bayt" formatidagi "bayt" formatidagi grafik tasvirlar uchun juda samarali (masalan, formatlar) Pcxyoki BMP.). Yaratishda zaxira nusxalari Qattiq disklarda ish joyida daromadni siqish paytida, masalan, ma'lumotlarning ko'payishi bilan bog'liq bo'lmagan, ammo kompyuter fayl tizimi qanday tashkil etilganligi bilan. Uning mohiyati shundaki, katta yoki kichik bo'lgan har qanday fayl faqat diskdagi butun klasterni egallay oladi. Ichida fayl tizimi FAT16 65536 klaster (2 16) dan oshmasligi kerak. Bu shuni anglatadiki, 1 dan 2 gb hajmli disklar uchun klaster hajmi 32 Kb. Katta guruh muhrlangan bo'lsa, tejash faqat har bir faylda faqat 16 Kbaytni faqat fayl tizimining irodasi tashkilotidan mahrum qiladi. FAT32 uchun yutuqlar kamroq bo'ladi, ammo bu holda minimal klaster hajmi 4 KB, shuning uchun agar ko'p miqdordagi kichik fayllar bilan shug'ullansa, saqlab qolish uchun ham mavjud. Siqishning turli xil usullari mavjudligiga qaramay, ba'zilari bor printsiplar va qoidalarbarcha siqish usullari uchun keng tarqalgan. Ular bilishlari va to'g'ri foydalanishlari kerak. Har bir siqishni cheklovga egaular. Ilgari siqilgan faylning muhri g'alaba bermaydi va eng yomon holatda natija faylining hajmida yo'qotishlarga olib kelishi mumkin. Kechagi bir gigabaytning disk hajmi shunchalik tuyuldi, shunda hamma o'zini o'zi o'yladi va menda gigabayt xotiram bor edi, men "ochko'zlik" ni to'xtataman va o'zimning ma'lumotlarimni siqib chiqaraman - Arxivlar. Ammo, aftidan, dunyo shunday yo'lladiki, "muqaddas joy bo'sh emas" va bizda qo'shimcha gigabayt bor ekan, uni to'ldirish kerak. Ha, va siz o'zingizniki dasturlari, tobora ko'payib bormoqda. Shunday qilib, ehtimol, terabayt va imtihonlar bilan bir xil bo'ladi. Shuning uchun, disk xotirasi qancha bo'lishidan qat'i nazar, qadoqlash ma'lumotlari endi to'xtamaydi. Aksincha, "kompyuter joylari" kabi, yangi arxivlar ko'paymoqda, ularning soni ko'paymoqda, ularning ishlab chiquvchilari nafaqat interfeyslararo raqobatlashmoqda va birinchi navbatda ma'lumotni eng ko'p to'plashga intilmoqda zich va zich. Biroq, bu jarayon cheksiz emasligi aniq. Bu cheklovlar bugungi kunda kiradigan joylarda, ular bir-birlari bilan qanday parametrlar bilan tanishishlari, bu erda yangi arxivni topish mumkin - bu ushbu maqolada ko'rsatilgan savollarning to'liq ro'yxati emas. Nazariy masalalarni ko'rib chiqishdan tashqari, biz dasturning samaradorligi yoki boshqasini tanlash uchun uni yuklab olish va ulardan optimal tanlash uchun bizdan yuklab olinadigan va ularning maqbulligini tanlash uchun. Professional bo'lmaganlar uchun juda kichik nazariya .Buni eski hazil bilan bu juda jiddiy mavzuni boshlashga ijozat bering. Ikki nafaqaxo'r gaplashish: Menga telefoningiz raqamini ayta olasizmi? - deydi bittasi. Bilasizmi, "ikkinchisini tan oling", afsuski, men buni eslay olmayman. Afsuski, birinchi maydalash, - yaxshi, menga kamida taxminan ...Darhaqiqat, javob bema'nilik bilan ajablanarli. Etti raqamli raqamlar to'plamida, qolgan ma'lumotlar mutlaqo foydasiz bo'lganligi uchun bitta belgi bilan xato qilish kifoya. Biroq, xuddi shu telefon rus tilining so'zlari bilan yozilganini tasavvur qiling va aytaylik, matn uzatilganda, harflarning bir qismi yo'qolganda - shunga o'xshash holatda nima bo'ladi? Aniqlik uchun aniq misolni ko'rib chiqing: Shunga ko'ra, "Chetra Sarch Chate" yozuvi, unda hech kim yo'q, lekin o'tkazib yuborilgan belgilar hali ham oson o'qiladi. Buning sababi bizning tilimiz bir nechta bir nechta bir nechta bir nechta bir nechta bir nechta bir nechta reklamani oshiradi, yozish hajmini oshiradi va boshqa tomondan, u transferning ishonchliligini yaxshilaydi. Bu raqamli telefon yozuvidagi har bir keyingi ramzning paydo bo'lishi ehtimoli bir xil, bu rus tili so'zlari bilan yozilgan matnda emas, balki matnda emas. Shubhasiz, masalan, rus tilida ishonchli belgi, masalan, "a" harfi ko'proq ko'rinadi. Bundan tashqari, harflarning ba'zi bir kombinatsiyasi boshqalarga qaraganda ko'proq, masalan, ketma-ket ikkita qattiq belgi printsipda imkonsiz va hokazo. Ma'lumotni bilish, matndagi har qanday harfning paydo bo'lishi ehtimoli va uni maksimal darajada taqqoslash, kodlash usuli tejamkor (bizning holatda, rus tili) kabi o'rnatilishi mumkin. Yana bir aniq eslatma, masalan, telefon bilan javob qaytarish orqali amalga oshirilishi mumkin.