|
Ma'lumotlarni siqish manba xabarini bitta kod tizimidan boshqasiga aylantirish jarayonini anglatadi, natijada kamayadi xabar hajmi. Ma'lumotni siqish uchun mo'ljallangan algoritmlarni ikki katta guruhga bo'lish mumkin: yo'qolgan (qaytarib bo'lmaydigan siqishni) va yo'qotishlar bilan siqishni amalga oshirish va siqishni amalga oshirish (qaytarib bo'lmaydigan siqilishlar). Qayta tiklanadigan siqish Bu dekodlashdan keyin aniq tiklanishni anglatadi va har qanday ma'lumotlarni siqish uchun qo'llanilishi mumkin. Bu har doim ma'lumotlarning informatsiyasini o'zgartirmasdan, ya'ni ma'lumot tuzilishini yo'qotmasdan har doim ma'lumot olish hajmining pasayishiga olib keladi. Bundan tashqari, siz tikuv oqimidan, tiklash yoki detompressiya algoritsiyasidan foydalanib, siz kirish yoki ochish jarayoniga va faqat qovurilgan jarayon deb ataladi. Yo'qotishsiz siqilish matnlar uchun ishlatiladi, bajariladigan fayllar, yuqori sifatli ovoz va grafika. Qaytarib bo'lmaydigan siqish Odatda inkressiyaning yo'qolishisiz kazizadan yuqori daraja, ammo manbadan dekodlangan ma'lumotlarni ba'zi og'ishlarga imkon beradi. Amalda, dekompressiyadan keyin dastlabki ma'lumotlarni aniq tiklash talabiga rioya qilish talab qilinmasa, keng qamrovli amaliy vazifalar mavjud. Bu, xususan, multimedia ma'lumotlarini siqishni anglatadi: tovush, fotosurat yoki video rasmlar. Masalan, JPEG va MPEG Multimedia ma'lumot formatlari keng qo'llaniladi, bu esa qaytarib bo'lmaydigan siqishni ishlatadi. Qaytarilishning qaytarilmas siqish odatda kriptografik shifrlash bilan birgalikda ishlatilmaydi, chunki kriptotsymate tizimining asl nusxasi asl nusxadan olingan ma'lumotlarni identifikatsiyadan o'tkazadi. Biroq, multimedia texnologiyalaridan foydalanganda, raqamli shaklda keltirilgan ma'lumotlar ko'pincha ovqatlantirishdan oldin qaytarib bo'lmaydigan siqilishga duchor bo'ladi kriptografik tizim Shifrlash uchun. Ma'lumotni iste'molchiga va shifrlash uchun uzatilgandan so'ng, multimedia fayllari siqilgan shaklda (ya'ni tiklanmagan) ishlatiladi. Qayta tiklanadigan ma'lumotlar siqishnining eng keng tarqalgan usullarini ko'rib chiqing. Axborotni siqish uchun eng taniqli oddiy yondashuv va algoritm qaytariladi - bu ketma-ketlik seriyasining kodlashidir (tezda kodlash - rl). Ushbu yondashuv usullarining mohiyati bir-birining zanjirlarini yoki seriyasini birlashtirilgan baytga va takrorlashlar soniga almashtirishdan iborat. Shunga o'xshash barcha usullar muammosi faqat boshqa, kodlanmagan bayt ketma-ketliklaridan olingan baytlar kodlangan seriyasida ajratilishi mumkin bo'lgan usulni aniqlashda. Muammoning echimi odatda kodlangan zanjirlarning boshida yorliqlarni kengaytirish bilan ta'minlanadi. Bunday yorliqlar kodlangan seriyalarning birinchi papasida, kodlangan seriyalarning birinchi baytining qiymatlari aniqlangan. 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. Yagona kodlash ma'lumotlari bilan, tashqi ko'rinishi ehtimolidan qat'i nazar, xabarga bir xil xabarga ajratiladi. Shu bilan birga, uzatiladigan xabarlarning umumiy uzunligi qisqa kod so'zlar bilan tez-tez uchraydigan bo'lsa, tez-tez uchraydigan xabarlar paydo bo'lsa, kamayadi deb taxmin qilish mantiqan. Bu haqda yuzaga keladigan muammolardan foydalanish zarurati bilan bog'liq o'zgaruvchan kod so'zi bo'lgan kodlar. Bunday kodlarni qurish uchun ko'plab yondashuvlar mavjud. Amaliyotning ba'zi bir qismida keng tarqalgan usullar, ularning asosiy vakillari - bu Ziva oilasi va esdalik algoritmlarini o'z ichiga olgan asosiy vakillar. Ularning asosiy g'oyasi shundaki, kiritish oqimining ("iboralar") parchalari matnda paydo bo'lgan joyga ko'rsatgich bilan almashtiriladi. Adabiyotda bunday algoritmlar algoritmlar sifatida ko'rsatilgan LZ siqish. Shunga o'xshash usul tezda matnning tuzumiga moslashadi va qisqa funktsional so'zlarni kodlashi mumkin, chunki ular juda tez-tez ko'rinadi. Yangi so'zlar va iboralar, ilgari duch kelgan so'zlarning bir qismidan ham shakllanishi mumkin. Siqilgan matnni dekodlash to'g'ridan-to'g'ri amalga oshiriladi, - bu ko'rsatgichning ta'kidlashicha, belgilangan lug'atdan boshlab ko'rsatgichni oddiy almashtirish mavjud. Amalda, LZ usuli yaxshi siqilishga erishmoqda, uning muhim xususiyati juda muhimdir tez ish dekoder. Ma'lumotni siqish uchun yana bir yondashuv kodi Huffman, uning tarkibidagi kodeker va dekoder juda oddiy apparatni amalga oshiradigan. Algoritm g'oyasi quyidagilardan iborat: Belgilar xabarnomaga uchragan ehtimolliklarni bilish, siz butun sondan iborat o'zgaruvchan uzunlik kodlarini qurish tartibini tavsiflashingiz mumkin. Belgilar ko'proq qisqartirilgan kodlarga ega bo'lish ehtimoli kamroq, ko'pincha belgilar tez-tez uchraydi. Shu sababli, kod so'zining o'rtacha uzunligi va ko'proq siqishni samaradorligi pasayishi kuzatilmoqda. Huffman kodlari noyob prefiksga ega (Kodchi so'zning boshlanishi), bu ularning o'zgaruvchan uzunligiga qaramay, ularni bir-biriga aylantirishga imkon beradi. Klassik Xaffman Kodeksi sintezi tartibi prorijiy axborot ma'lumotlari xabar manbasining statistik xususiyatlari to'g'risida ma'lumot beradi. Boshqacha qilib aytganda, ishlab chiqaruvchi ushbu xabarlar shakllantirilgan ushbu yoki boshqa belgilar ehtimolligini bilishlari kerak. Oddiy misolda Xuffman kodining sintezini ko'rib chiqing. p (s 1) \u003d 0,2, p (s (s 2) \u003d p i (s 3) \u003d 0,55, p (s 4) \u003d 0,1. Belgilarni tashqi ko'rinish shaklida kamaytirish va tasavvur qilish ehtimolini kamaytirish va tasavvur qilish uchun tartiblang (14.3-rasm, a). Kod sintez protsedurasi uchta asosiy bosqichdan iborat. Stolning birinchi stigsiyasi ro'y beradi: Ramziylarning eng kichik ehtimolligi bilan mos keladigan ikki qator umumiy ehtimollik bilan almashtiriladi, shundan keyin jadval yana takrorlandi. Talabalar jadvalda umumiy ehtimollik bilan faqat bitta chiziq bo'lguncha davom etmoqda. teng birlik. Ikkinchi bosqichda, kodvudiya katlangan stol yordamida qurilgan (14.4-rasm). Daraxt, stolning so'nggi ustunidan boshlab qurilgan. Daraxtning ildizi oxirgi ustunda joylashgan birlik hosil bo'ladi. Ushbu misolda ushbu birlik 0,55 va 0,45 ehtimollikdan hosil bo'lgan, ehtimol, ildiz bilan bog'liq bo'lgan daraxtning ikkita tugunining shaklida tasvirlangan. Ulardan birinchisi s belgilariga to'g'ri keladi va shu sababli ushbu tugunning keyingi qismida bu sodir bo'lmaydi. Ikkinchi tugunning 0,45 bilan belgilangan ikkinchi tugunning uchinchi darajali tugunga, ehtimoliy, ehtimollik bilan 0,25 va 0,2 ga bog'liq. 0,2 ehtimolligi 1 belgisiga mos kelishi va 0,25 ehtimolligi, o'z navbatida, S Belfonning 2 va 0,1 ko'rinishi ehtimolligidan hosil bo'ladi. Shaxsiy kodni bog'laydigan qovurg'alar, raqamlar 0 va 1 raqamlar (masalan, chap qovurg'alar - 0 - 1). Uchinchisida, yakuniy bosqichda stol quriladi, bunda manba belgilari va Xuffmon kodining kodlari. Ushbu kod so'zlari daraxtning ildizidan mos keladigan ramzga to'g'ri keladigan qovurg'alar bilan belgilangan rasmlar natijasida hosil bo'ladi. Ko'rib chiqilayotgan misol uchun Huffman Kodeksi jadvalda ko'rsatilgan ko'rinishni to'g'ri qabul qiladi (14.4, b). Biroq, klassik Xuffman algoritmda bitta ahamiyatsiz narsalarga ega. Siqilgan xabar tarkibini tiklash uchun dekoder kodlovchidan zavqlangan chastota stolini bilishi kerak. Shuning uchun, siqilgan xabarning uzunligi chastota stolining uzunligi bilan ko'payadi, uni ma'lumotlardan oldin yuborilishi kerak, uni xabarni siqish uchun hech qanday kuch sarflamasligi mumkin. Boshqa variant statik kodlash Xuffman Bu to'plangan statistika asosida kiritilgan oqim va qurilish kodini ko'rishdir. Bu faylda ikkita faylni talab qiladi - biri statistik ma'lumotlarni ko'rish va to'plash, ikkinchisi kodlash uchun. Xuffmanning statik kodlashida, kiritish ramzlari (turli xil uzunlikdagi bitlar zanjirlari) Bits zanjirining sirtqi va o'zgaruvchan uzunligi - ularning kodlari. Har bir belgi kodining uzunligi qarama-qarshi belgisi bilan olingan chastotaning tozaluvchan ikkilik logarifm tomonidan olinadi. Va turli xil belgilarning umumiy to'plamining umumiy ramzlari - bu oqim alifbosi. Boshqa usul - moslashuvchan yoki dinamik kodlash Xuffman. Uning umumiy printsip Kodlash sxemasini kiritish oqimining o'zgarishi xususiyatiga qarab kodlash sxemasini o'zgartirish. Bunday yondashuv bitta pass algoritmga ega va ular aniq ishlatiladigan kodlash haqida ma'lumotni saqlashni talab qilmaydi. Adaptiv kodlash statik bilan taqqoslaganda ko'proq siqish koeffitsientini berishi mumkin, chunki kirish oqimining chastotalaridagi o'zgarishlar to'liq hisobga olinadi. Adaptiv Xuffman kodlashdan foydalanganda, algoritmning asorati asosiy alifbosining o'tin va kodlarini o'zgartirish zaruratini o'zgartirish zaruratini o'zgartirish zarur. Xuffman usullari yuqori tezlikda va o'rtacha darajada beradi yaxshi sifat siqishni. Biroq, Huffmanni kodlash minimal bir martalik e'tiborga ega, agar har bir belgi belgining aniq zanjiri bilan alohida zanjiri bilan kodlanadi - (0, 1). Asosiy noqulaylik bu usul Ba'zi salbiy darajada belgilar ehtimolidan 2 tagacha bo'lgan tog 'ehtimolligidan siqilish darajasining qaramligi, ya'ni har bir belgi butun son bilan kodlanganligi sababli. Butunlay boshqa echim taklif qiladi arifmetik kodlash. Ushbu usul kirish oqimini bitta suzuvchi nuqtaga almashtirish g'oyasiga asoslanadi. Arifmetik kodlash - bu kiritilgan belgilarning chastotali tarqalishi ma'lum bo'lgan taqdirda, kiritilgan alifbosining belgilari yo'q.
Do'stlaringiz bilan baham: |
