Mavzu: ma’lumotlar hajmini siqish algoritmlari reja

Tabiiy tillarning ko'payishi
Axborot nazariyasi Xabarda aytilgan ma'lumotlar shunchalik kattaroq, uning entopiyali. Har qanday kodlash tizimi uchun uning maksimal ma'lumot idishni (HMAX) va haqiqiy entopiyani (H) hisoblash mumkin. Keyin N.R \u003d (hmax - h) / hmax Tabiiy tillarning ortiqcha bo'lishini o'lchash (biz gapiradigan odamlar) ajoyib natijalarni beradi: bu tillar taxminan 80% bo'lganligi aylanadi va bu ma'lumot tilidan foydalanadigan deyarli 80% ortiqcha, ya'ni , ortiqcha. Bu qiziquvchan va turli tillarning ortiqcha bo'lishi juda yaqin ekanligi qiziq. Bu raqam taxminan matnli fayllarni siqish nazariy chegarasini belgilaydi.
Yo'qotishlar bilan siqish
Kuchlanish kodlari, "yo'qolmasdan siqishni" tushunchasi va "yo'qotishlar bilan siqishni" tushuntirishlari haqida gapiradi. Shubhasiz, biz "Telefon raqami" haqida ma'lumot bilan shug'ullanayotganimizda, unda belgilarning yo'qolgan qismini yo'qotish orqali bunday yozuvlarning siqilishi hech qanday yaxshilikka olib kelmaydi. Shunga qaramay, siz ma'lumotlarning bir qismi yo'qolgan bir qator vaziyatlarni topshirishingiz mumkin, bu qolganlarning foydasi yo'qolishiga olib kelmaydi. Yo'qotishlar bilan siqish asosan grafika (JPEG), ovoz (MPEG), ya'ni fayllarning katta o'lchamlari tufayli, sektrorlik koeffitsienti juda muhimdir va tafsilotlar bilan qurbon qilinishi mumkin Ushbu ma'lumotni erkak tomonidan idrok etish uchun ahamiyatli emas. Ma'lumotni siqish uchun maxsus xususiyatlar video siqish bilan mavjud. Ba'zi hollarda, rasmning aksariyati o'zgarishsiz freymdan uzatiladi, bu sizga "rasmlar" ning yagona qismini tanlab olish asosida siqish algoritmlarini qurishga imkon beradi. Muayyan holatda, uning mavqeini o'zgartirmaydigan so'zlashuvchi kishining surati, faqat freymdan ramkadan eng tez o'zgaradigan joyda yangilanishi mumkin. Bir qator holatlarda, grafiklarning siqilishi, juda yuqori darajadagi siqishni ta'minlaydigan, deyarli insonlar uchun deyarli sezilarli darajada. Shunday qilib, quyida ko'rsatilgan uchta fotosuratdan avvalgi formatda (yo'qotmasdan) berilgan, ikkinchisi JPEG formatida minimal siqishni parametrlari va maksimal darajada saqlanadi. Shu bilan birga, ikkinchi rasm avvalgisidan deyarli ikkita kattalikning ikki buyurtmaini oladi. Biroq, yo'qotishlar bilan siqish usullari bir qator kamchiliklarga ega. Birinchisi shundaki, yo'qolishni siqish barcha holatlar uchun qo'llanilmaydi. grafik ma'lumot. Masalan, agar molning shakli yuzda siqish natijasida o'zgarsa (lekin yuz taniqli bo'lib qoladi), shundan so'ng, agar o'pkaning fotosurati bo'lsa, bu fotosurat juda maqbul bo'ladi Dimming shaklini tahlil qilish uchun tibbiy ko'rikdan o'tish bu juda boshqa narsa. Bundan tashqari, grafik ma'lumotlarni tahlil qilish uchun mashina usullari bo'lsa, kodlash natijalari (ko'zlarga ko'rinmas ko'z uchun ko'rinmas), mashina analizatori uchun "sezilarli" bo'lishi mumkin. Ikkinchi sabab - bu yo'qotish va dekompressiya xatolar to'planishiga olib keladi. Agar biz JPEG formatining qo'llanilishi haqida gapiradigan bo'lsak, shubhasiz, asl rang chuqurligini saqlashda katta siqish koeffitsienti muhim ahamiyatga ega. Bu ushbu formatni Internetdagi grafik ma'lumotlarni taqdim etishga olib kelgan, faylni ko'rsatish tezligi (uning o'lchamlari) katta ahamiyatga ega. JPEG formatining salbiy xususiyatlari tasvir sifatining yomonlashishidir, bu esa uni bosib chiqarishdan foydalanib bo'lmaydi, bu parametr aniqlanadi. Endi biz ma'lumotlarning siqilishi haqida suhbatga murojaat qilamiz va qaysi algoritmlar va dasturlarni ushbu operatsiyani amalga oshirishga imkon beradi.
Yo'qotmasdan siqish
Ichish yoki kodlash, yo'qotishsiz, har qanday ma'lumotlarni siqish uchun ishlatilishi mumkin, chunki u kodlash va dekodlashdan keyin aniq ma'lumotlarni tiklashni ta'minlaydi. Yo'qotishsiz siqilish bir guruh belgilardan bir guruhgacha ma'lumotlarni bir qator belgilardan bir guruhga aylantirishning oddiy printsipiga asoslanadi. Eng mashhur ikkita siqish algoritmi: bu Xuffman Coding (Xuffman) va LZW kodlash (Lemfite) kodini (Lemchel, Ziv, Welch ijodkorlarining bosh harflariga ko'ra), bu ma'lumotni siqishda asosiy yondashuvlarni anglatadi. Huffman Kodonmi 50-yillarning boshlarida paydo bo'ldi; Uning printsipi - ko'pincha duch kelgan belgilarni ifodalash uchun ishlatiladigan va shunga ko'ra, kamdan-kam uchraydigan belgilar sonini ko'paytirishda. LZW usuli, u qayta ishlangan chiziqlar asosida uzaytirilgan alifboni yaratish uchun kirish oqimini tahlil qilib belgilarni kodlaydi. Ikkala yondashuv ham kirish ma'lumotlarida ortiqcha ma'lumotlarning pasayishini ta'minlaydi.
Xuffman kodlash
Xuffman Koding - bu ma'lumotlarga asoslangan, ular fonda joylashgan, ba'zi belgilar boshqalarga qaraganda tez-tez ishlatiladigan ba'zi belgilar tez-tez qo'llaniladi. Yuqorida aytib o'tilganidek, rus tilida ba'zi harflar ko'proq, ehtimol ko'proq boshqalarga qaraganda ko'proq bo'lishi mumkin, ammo ASCII kodlarida biz belgilarni ifodalash uchun bir xil bitlardan foydalanamiz. Agar biz tez-tez uchraydigan belgilar uchun kichikroq bitlardan foydalansak va kamdan-kam uchraydigan bo'lsak, biz xabarning ortiqcha bo'lishini kamaytira olamiz deb taxmin qilish mantiqan. Goffeman kodlash matnda paydo bo'lish ehtimoli bilan belgilar kodi uzunligining uzunligiga asoslanadi.
Dinamik kodlash
Agar belgilar kiritish ma'lumotlari noma'lum bo'lsa, dinamik kodlash qo'llaniladi, unda ba'zi belgilarning paydo bo'lishi ehtimoli ma'lumotni o'qish ma'lumotlari paytida "chivinda" ko'rsatilgan.
Lzv siqishni
Yaqinda LZW algoritmi nisbatan (1984 yilda) patentlangan va sperilga tegishli. LZW algoritmi an'anaviy belgilarning qatorlarini ifodalash uchun qo'shimcha belgilardan foydalanishga imkon beradigan alifboni kengaytirish g'oyasiga asoslanadi. Masalan, 8-bitli ASCII kodlari 9-bit o'rniga, qo'shimcha 256 belgidan iborat bo'ladi. Kompressor ishi qatorlardan iborat stolning qurilishiga va ularga tegishli kodlarni qurishga keladi. Siqish algoritmi quyidagilarga tushadi: Dastur keyingi belgini o'qiydi va uni satrga qo'shadi. Agar satr allaqachon stolda bo'lsa, o'qishda davom etsa, bu satr satr stoliga qo'shiladi. Ko'proq takroriy chiziqlar bo'ladi, ma'lumotlar kuchayadi. Telefon bilan misolga qaytish, siz juda soddalashtirilgan o'xshashliklarni sarflab, 2010 34 44 yozishni qisqartirish, biz yangi qatorlarni 333 va 444 va qo'shimcha belgilar bilan ifoda etishimiz mumkinligini aytamiz , Yozuv uzunligini kamaytirishimiz mumkin.
Qaysi tanlangan arxivli?
Ehtimol, o'quvchi tarkibchi yaxshiroq ekanligini bilishdan manfaatdor bo'ladi. Bu savolga javob bir ma'nodan uzoqdir. Agar siz "raqobatdosh" stolga qarasangiz (siz Internetdagi va CD-ROMga tegishli joylarda ham tegishli saytda), "musobaqalarda" da tegishli dasturlar sonidan oshib ketishini ko'rishingiz mumkin. yuz. Ushbu mazali arxivni qanday tanlash kerak? Ko'p foydalanuvchilar uchun ushbu savol dasturni tarqatish masalasi emas. Aksariyat arxiyotchilar yakka tartibda tarqatiladi va ba'zi dasturlar ro'yxatdan o'tmagan versiyalar uchun funktsiyalar sonini cheklaydi. Bepul dastur sifatida tarqatiladigan dasturlar mavjud. Agar so'raladigan mulohazalar tashvishlanmasa, avvalgidek, birinchi navbatda, bir qator ishchilarni hal qilish uchun optimallashtiriladigan bir qator arxivlar mavjudligini tushunish kerak. Shu munosabat bilan turli xil ixtisoslashtirilgan testlar, masalan, faqat matnli fayllar yoki faqat grafik mavjud. Shunday qilib, xususan, to'lqinli zip, birinchi navbatda wat fayllarini siqishni biladi va Eri Multimediya arxiviacs tiff fayllaridan yaxshiroqdir. Shuning uchun, agar siz biron bir o'ziga xos fayllarni siqishga qiziqsangiz, siz dastlab maxsus yaratilgan dasturni topishingiz mumkin. Kaper, Exper yoki DLL bajariladigan modullarini siqish uchun xizmat qiladigan arxiv (ekstrackers deb ataladigan) tur mavjud. Fayl ishga tushirilganda qadoqlangan holda, u "Chivinada" xotirada o'z-o'zini ochib beradi va keyin odatdagidek ishlaydi Ushbu toifadagi eng yaxshisidan biri Assaft va Petite dasturlari deb atash mumkin. Ko'proq batafsil ma'lumot Ushbu sinf dasturlari, shuningdek tegishli reytinglar bilan tanishish mumkin. Agar sizga arxiv ishchisi kerak bo'lsa, "barcha holatlar uchun" gapirish ", so'ngra ma'lum bir dasturning turli xil fayllarni qayta ishlaydigan" raqobatlash "dasturiga aniqroq topshirish mumkinligini tushuning. Siz CD-ROM-da ushbu sinovda ishtirok etadigan chekchilar ro'yxatini ko'rishingiz mumkin. Yuqorida aytib o'tilganidek, shifrlash uchun ma'lumotlarni oldindan tayyorlashning muhim vazifalaridan biri bu ularning daromadlarini kamaytirish va amaliy tilning statistik shakllarini muvofiqlashtirishdir. Raqamni qisman qisqartirish bilan bog'liq.