Matnli ma'lumotlarni siqish algoritmining asosiy mohiyati nimadan iborat. Misollarda ma'lumotlarni siqish Matnli ma'lumotlarni siqish algoritmining asosiy mohiyati nimadan iborat

Download 61,99 Kb.
bet	2/2
Sana	17.05.2024
Hajmi	61,99 Kb.
	#240652

1 2

Bog'liq
dars

Mixail Svarichevskiy
Ma'lumotlarni siqish (siqish) ularni kamroq joy egallagan shaklga aylantirish deb ataladi. Ushbu shaklda ma'lumotlarni saqlash osonroq (saqlash moslamalari rezina emas, axir) va o'tkazish qobiliyati cheklangan kanallar orqali uzatish ancha yoqimli.
Barcha siqish algoritmlari ikki turga bo'linadi: yo'qotishli va yo'qotishsiz.
Yo'qotilgan siqish sizga ancha yuqori siqish nisbatiga erishish imkonini beradi (asl hajmning 1/30 qismigacha yoki undan kamroq).
Masalan, ochilmagan holda 30 gigabaytni egallagan videofilm 1 kompakt diskga yozilishi mumkin.
Biroq, yo'qotilgan siqish algoritmlari ma'lumotlarning o'zida ba'zi o'zgarishlarga olib keladi; shuning uchun bunday algoritmlar faqat kichik buzilishlar ahamiyatsiz bo'lgan ma'lumotlarga nisbatan qo'llanilishi mumkin: video, foto tasvirlar (JPEG algoritmlari), ovoz (MP3 algoritmi).
Yo'qotmasdan siqish, albatta, unchalik samarali emas (uning darajasi aniq ma'lumotlarga bog'liq), ammo o'rashdan keyin olingan ma'lumotlar asl nusxa bilan mutlaqo bir xil. Bu juda zarur, masalan, matnli ma'lumotlar, dastur kodi uchun. Ushbu maqola yo'qotishsiz siqilishga qaratilgan.
Ko'pgina yo'qotishsiz siqish algoritmlari ikki guruhga bo'linadi: birinchisi, u yoki bu shakldagi manba fayl qismlaridan matn tuzadi (lug'at usullari); ikkinchisi (statistik usullar) faylda turli belgilar yoki belgilar guruhlari turli ehtimolliklarga ega boʻlishidan foydalanadi (masalan, matnli fayllardagi “a” harfi “b” ga qaraganda tez-tez uchraydi).
Lug'at usullari
Lug'at usullari yuqori siqish / dekompressiya tezligi bilan tavsiflanadi, lekin biroz yomonroq siqish. So'z - bu belgilar ketma-ketligi. Umuman olganda, biz, albatta, belgilar haqida emas, balki baytlar haqida gapiramiz; lekin soddalik uchun misollar ASCII belgilaridan foydalanadi.
Lug'at bir qancha so'zlarni o'z ichiga oladi (odatda 2x; masalan, 4096).
Siqish lug'atdagi so'z raqami odatda so'zning o'zidan ancha qisqa bo'lishi tufayli erishiladi.
Lug'atni siqish algoritmlari ikki guruhga bo'linadi:
1) aniq lug'atdan foydalanish (algoritmlar LZ78, LZW, LZC, LZT, LZMV, LZJ, LZFG)
Masalan, lug'atga ko'ra
1. "Ko'pchilik"
2. "siqilish"
3. "siz"
4. "yo'qotish"
5. "algoritmlar"
"Eng yo'qotishsiz siqish algoritmlari" matni "15234" ga siqiladi.
2) raqam so'zi o'rniga - joriy holatga nisbatan pozitsiyani va takrorlanuvchi qismning uzunligini ko'rsatish (LZ77, LZR, LZSS, LZB, LZH algoritmlari)
Masalan, "ababbababbabwgbbbabw" matni
"05ababb5504abvg65" ga qisqaradi, bu erda:
"05ababb" - 0 pozitsiyasi keyingi 5 ta belgi siqilmaganligini bildiradi.
"55" - hozirgi holatdan 5 belgi orqaga o'rnatilgan joydan 5 ta harf.
"04abvg" - yana 4 ta belgi siqilmagan.
"65" – 5 ta joydan 6 ta belgi joriy joydan.
LZ algoritmlarining modifikatsiyalari faqat lug'atni ifodalash, so'zlarni qidirish va qo'shish usullari bilan farqlanadi. Ba'zilar tezroq siqib chiqadi, lekin yomonroq; boshqalar ko'proq xotira talab qiladi.
Keling, o'zgartirilgan LZ77 algoritmini batafsil ko'rib chiqaylik.
Arxiv quyidagi shakldagi yozuvlardan iborat bo'ladi:
(n, m) - m uzunlikdagi bir xil qator joriy pozitsiyadan boshlab n pozitsiyasidan boshlanishini bildiradi.
(0, m, "m belgi") - siqilib bo'lmaydigan yana m ta belgi kelishini bildiradi.
Siqish algoritmi quyidagicha bo'ladi: biz faylda eng uzun ketma-ketlik ketadigan joyni qidiramiz, bu joriy baytdan boshlanadigan ketma-ketlikka to'g'ri keladi. Agar uning uzunligi 3 dan ortiq bo'lsa, biz arxivga ketma-ketlikning boshlanishi va uzunligini yozamiz; aks holda biz 0 ni, ketma-ketlikning uzunligini va siqilmagan belgilarning o'zini yozamiz. Paketni ochish yanada osonroq: arxiv fayli tugaguncha biz 2 ta raqamni (n, m) o'qiymiz. Agar n = 0 bo'lsa, arxivdan m simvol darhol buferga joylashtiriladi (bizga bu belgilar hali ham kerak) va chiqish fayliga yoziladi. Agar n<>0 dan keyin n pozitsiyadagi buferdan m elementni buferga va chiqish fayliga ko'chiring.
Biroq, ikkita muammo bor:
1) Cheklangan bufer hajmi: agar biz 100 MB hajmdagi faylni siqishimiz kerak bo'lsa, biz uni hech qanday tarzda buferga joylashtirmaymiz. Shuning uchun, u to'lganida (aytaylik, 75%), undagi ma'lumotlarni boshiga o'tkazishingiz kerak bo'ladi (masalan, 25%; albatta, eng qadimgi belgilar yo'qoladi). Bu siqishni pasaytiradi, lekin algoritmni xotirani kamroq talab qiladi.
2) Siqish dasturining tezligi juda sekin. Haqiqatan ham, agar biz 10 KB faylni siqishimiz kerak bo'lsa, bu bizdan kamida 10 000 * 10 000 / 2 operatsiyani bajarishimizni talab qiladi (biz mos keladigan keyingi ketma-ketlikni 10 000 marta izlashimiz kerak va har bir bunday qidiruv o'rtacha 10 000/2 oladi. operatsiyalar). Qidiruv operatsiyasini tezlashtirish uchun chr (0), chr (2) ... chr (255) belgilaridan boshlanadigan ketma-ketliklarning joylashuv raqamlarini alohida massivda saqlashingiz mumkin. Keyin, qidiruvda biz faqat birinchi harfi kerakli ketma-ketlikning birinchi harfiga to'g'ri keladigan kombinatsiyalarni tekshirishimiz kerak.
Statistik usullar
Statistik usullar lug'at usullariga qaraganda ancha sekinroq, lekin kuchliroq siqilishga erishadi. Ularda har bir harf qandaydir kod bilan almashtiriladi. Kod - bu belgini noyob tarzda aniqlaydigan bir necha bit. Statistik usullar eng keng tarqalgan belgilarni qisqaroq kodlarga moslashtirish uchun turli usullardan foydalanadi. Harflarni paydo bo'lish chastotasiga qarab kodlashning ikkita asosiy algoritmi mavjud:
1) Huffman kodlari: barcha belgilar bitlarning butun soni bilan kodlangan; va shuning uchun dekodlash har doim bir ma'noli bo'ladi (masalan, agar "a" harfi "1001" bit ketma-ketligiga va "b" - "10010" ga to'g'ri kelsa, dekodlash noaniq bo'ladi). Afzallik - yuqori siqish tezligi. Kamchiliklari - suboptimal siqilish, adaptiv variantni amalga oshirishdagi qiyinchiliklar. So'nggi paytlardan beri haqiqiy kodlash algoritmining tezligi tobora kichikroq rol o'ynadi (statistik ma'lumotlarni to'plash algoritmlari sekinroq va sekinroq ishlaydi va hatto kodlovchining ish vaqtining 2 baravar oshishi ham tezlikka deyarli ta'sir qilmaydi), bu algoritm arifmetik kodlashdan sezilarli afzalliklarga ega emas. ...
2) Arifmetik kodlash: har bir belgi uchun segmentdagi bo'shliq aniqlanadi va ushbu segmentning kengligiga qarab, nisbatan, hatto kasrli bitlarning har xil soni ajratilishi mumkin (masalan: "a" qatori bo'lsin. 0 ga to'g'ri keladi va "ab" qatori - 1, keyin "aba" qatori 2 bitda kodlanadi, ya'ni har bir belgi uchun o'rtacha 2/3 bit). Bu usul statistik ma'lumotlardan aniqroq foydalanadi va har doim Huffman algoritmi kabi siqiladi, lekin sekinroq. Afzalliklar - maksimal nazariy erishilgan siqish nisbati, adaptiv versiyani oddiy amalga oshirish. Kamchiliklari - biroz past tezlik.
Arifmetik kodlash qanday ishlaydi:
Masalan, biz "a", "b" - va "c" - belgilariga bo'sh joy qo'ydik. Keyin, agar bizda 0,4 raqami bo'lsa, unda "b" harfi kodlangan deb aytishimiz mumkin (0,3).<=0.4<=0.6), а если 0.9 – то c(0.6<=0.9<=1). Итак, у нас получилось закодировать 1 букву в число. Как же закодировать 2 буквы? Очень просто: например, если первая буква – "b", то интервал равен . Разделим этот интервал на части, в отношении наших первоначальных отрезков. Тогда 2-м буквам "ba" будет соответствовать интервал , "bb" – и "bc" – . Для раскодирования нам достаточно знать любое число из этого интервала.
Keling, dekodlashga harakat qilaylik: 0,15 raqami berilsin. Bu raqam "a" harfi oralig'iga to'g'ri keladi, ya'ni birinchi kodlangan harf "a". Ikkinchi harfni bilish uchun siz raqamni emas, balki intervaldagi harfni ko'rsatishi uchun aylantirishingiz kerak. Buni amalga oshirish uchun raqamdan boshlang'ich intervalning pastki chegarasini (0) olib tashlang va uni intervalning kengligiga (0,3-0 = 0,3) bo'ling. Biz yangi raqamni olamiz (0,15-0) /0,3 = 0,5. Xuddi shu qadamlarni takrorlash orqali biz ikkinchi harfning "b" ekanligini bilib olamiz. Agar 3 yoki undan ortiq harflar kodlangan bo'lsa, bu jarayonni ko'p marta takrorlab, biz barcha harflarni topamiz.
Nima uchun raqamlarni ko'rsatish ma'lumotlarni siqish imkonini beradi:
Ko'proq ehtimoliy belgilar kengroq intervalga to'g'ri keladi va bunday harfni kodlashdan keyin interval unchalik kamaymaydi, shuning uchun bu oraliqdagi istalgan raqamni ifodalash uchun biroz ko'proq bit kerak bo'ladi.
Siqish algoritmi:
Har bir belgi uchun biz ma'lumotlardagi chastotaga (uchrashuv ehtimoli) mos ravishda tegishli intervalni belgilashimiz kerak: "a" belgisi 0,4 ehtimolga ega bo'lsin, "b" - 0,3 va "c" - shuningdek, 0,3; keyin belgi "a" bir interval mos bo'ladi, "b" -, "c" -. Ya'ni, biz mavjud bo'lgan bo'shliqni barcha kerakli harflar o'rtasida ularning uchrashish ehtimoliga qarab ajratamiz (ko'proq ehtimoliy belgi kattaroq bo'shliqqa to'g'ri keladi).
Siqish jarayonida bizda 2 ta chegara bor: yuqori va pastki, keling, ularni mos ravishda salom va lo deb ataymiz. Faraz qilaylik, biz bo'shliqni belgilagan belgini kodlashimiz kerak. Keyin belgi bo'shlig'i bizning bo'shliqqa "qo'shiladi" va mana kiritilgan bo'shliqning pastki chegarasiga, salom - yuqoriga teng bo'ladi. Natijada, kodlash davom etar ekan, lo va hi o'rtasidagi bo'shliq torayib boradi. Nihoyat, biz barcha ma'lumotlarni kodlab bo'lgach, natijada olingan intervaldan istalgan raqamni tanlaymiz va chop etamiz. Bu siqilgan ma'lumotlar bo'ladi.
Paketdan chiqarish:
Keling, belgilar uchun, shuningdek, siqish uchun bo'shliqlarni tuzamiz. Raqam-arxiv oraliqda tushadigan belgi ma'lumotlarning birinchi belgisidir. Biz belgi oralig'ini arxiv raqami bilan birga oraliqgacha "cho'zamiz" (ya'ni, biz yangi dekodlangan belgi oralig'ining pastki chegarasini ayirib, ushbu oraliqning kengligiga bo'lamiz), so'ngra operatsiyani takrorlang. hamma narsa dekodlangan.
Muammolar:
Agar hamma narsa juda oddiy bo'lsa ... Aslida, arxiv raqamini saqlash uchun sizga juda yuqori aniqlik kerak bo'ladi (o'nlab va yuz minglab belgilar), shuning uchun amalda siz oddiy ma'lumotlar turlaridan foydalanishingiz kerak. Bunga erishish uchun biz arxiv raqamining eng muhim bitlarini / raqamlarini ko'rib chiqamiz. Ular salom va ma'noga mos kelishi bilan biz ularni darhol arxivga yozib, "kesib" olamiz. Paketni ochishda, aksincha, biz intervalni bir necha marta kengaytirganimizni ko'rganimizda, biz arxiv faylidan bir nechta raqamlarni hisoblaymiz va ularni arxiv raqamimizning oxiriga qo'shamiz.
Ko'pincha arifmetik kodlashning modifikatsiyasi qo'llaniladi - range coder. Asosiy farq dastlabki interval -. Bu sizga ma'lumotlarni zudlik bilan bayt bo'yicha chiqarishga imkon beradi va ish tezligida aks etadi. Maqolaning oxirida ushbu alohida variantni amalga oshirish berilgan.
Belgilarning ehtimolliklarini aniqlash
Tezlik va siqish nisbatiga ta'sir qiluvchi asosiy jarayon - bu belgilarning ehtimolliklarini aniqlash. Eng oddiy holatda, biz belgining ehtimolini ko'rib chiqamiz - uning allaqachon kodlangan ma'lumotlar qismida paydo bo'lish soni, ma'lumotlardagi belgilarning umumiy soniga bo'linadi. Matnlar uchun bu taxminan 2x siqishni beradi. Uni oshirish uchun, masalan, "u" dan keyin "i" belgisi bilan uchrashish ehtimoli deyarli 0 ga, "c" dan keyin "o" ning taxminan 0,25 ga teng ekanligi kabi faktlarni hisobga olishingiz mumkin. Shuning uchun, har bir oldingi belgi uchun biz ehtimolliklarni alohida hisoblaymiz.
Siqilish uchun ma'lumotlar haqida biz qiladigan taxminlar (masalan, ehtimollikning oldingi belgilarga bog'liqligi) ehtimollik modeli deb ataladi. Ehtimollar oldingi belgilarga bog'liq bo'lmagan model 0-tartibli model deb ataladi. Agar ehtimolliklar oldingi belgining 1 tasiga bog'liq bo'lsa, bu 1-tartibning modeli, agar oxirgi 2-dan bo'lsa, ikkinchisi va hokazo. Yuqori tartibli modellarda belgilarning ehtimolliklarini samarali hisoblash uchun maxsus algoritmlar guruhi - PPM va uning modifikatsiyalari mavjud.
Modellar moslashtirilmaydigan, yarim moslashuvchi va moslashuvchan bo'lishi mumkin. Moslashuvchan bo'lmagan usullarda barcha belgilarning ehtimolliklari dasturga qattiq kodlangan. Kirish ma'lumotlariga ko'ra yarim adaptivda 2 ta o'tish amalga oshiriladi: 1-chi - ehtimolliklarni aniqlash uchun, 2-chi - siqishni o'zi uchun. Adaptiv - siqish jarayonida belgilarning ehtimoli o'zgaradi. Moslashuvchan modellar eng sekin, lekin ular moslashtirilmagan va yarim moslashuvchi modellarga qaraganda ma'lumotlarni kuchliroq siqib chiqaradi. Umuman olganda, barcha modellar orasida siqilgan ma'lumotlar haqida eng ko'p ma'lumotni ishlatadiganlar yaxshiroq siqiladi - oldingi belgilarga bog'liqlik, ba'zi faktlar, masalan: matnlarda katta harf odatda nuqtadan keyin keladi va hokazo. .
Mashhur arxivchilarda ishlatiladigan algoritmlar:
ZIP, ARJ, RAR - LZ + Huffman
HA - PPM + arifmetik kodlash
BOA - BWT + Arifmetik kodlash
UHARC - LZ + PPM + Arifmetik kodlash
(Bu yerda "+" belgining chap tomoniga yozilgan algoritm natijasi o'ng tomonga yozilgan algoritm tomonidan yanada siqilganligini bildiradi).
Ko'rib turganingizdek, 80-yillarning oxiri - 90-yillarning boshlarida ishlab chiqilgan ZIP, ARJ, RAR arxivchilari ancha eskirgan algoritmlardan foydalanadilar; shuning uchun ular zamonaviyroq sinovlardan pastroq.
0-tartibli adaptiv siqish/dekompressiya dasturiga misol:
Ma'lumotlar: compr - bu erda siqilgan ma'lumotlar saqlanadi
Ma'lumotlar - bu erda asl ma'lumotlar saqlanadi
Freq - belgilar chastotasi
Protsedura kompressor_oraligi; (siqish tartibi)
Var
cum_freq: kengaytirilgan;
Boshlash
(- Model va enkoderni ishga tushirish -)
q uchun: = 0 dan 255 gacha
chastota [q]: = 1; (Boshidagi barcha belgilar bir xil ehtimolga ega)
chastota: = chastota - 0,20000;
jami: = 256; (Barcha belgilar chastotalarining yig'indisi.)
(Chastada - 0 va maksimal qiymatlardan kichik ofset)
Kompyuter: = 0; (allaqachon kodlangan baytlar soni)
Lo: = 0; diapazon: = 256;
(- Kodlash -)
Q uchun: = 1 To Hajmi Do
Boshlash
(Kodlangan belgiga mos keladigan intervalni topish)
cum_freq: = 0,1; (Biz ehtimollikni to'plashni boshlaymiz)
w uchun: = 0 Ma'lumotlarga [q] - 1 Do
cum_freq: = cum_freq + chastota [w];
(Diapazonni o'zgartirish va shunga o'xshash)
diapazon: = diapazon / jami;
Lo: = Lo + diapazon * (cum_freq);
diapazon: = diapazon * chastota];
(Normallashtirish, ya'ni Lo va Hi uchun bir xil bo'lgan baytlarning chiqishi (Hi = Lo + Range))

Boshlash
Inc (kompyuter);

compr: = Trunc (Lo);
Lo: = Frac (Lo) * 256;
diapazon: = diapazon * 256;
Oxiri;
(Model yangilanishlari)
chastota]: = chastota] + 1;
(Kodlangan belgini 1 yuqori ehtimollik bilan belgilash)
jami: = jami + 1;
Oxiri;
(Siqish tugadi, qolganini ko'rsatadi)
Lo: = Lo + diapazon / 2;
Inc (kompyuter);
compr: = Trunc (Lo);
Lo: = Frac (Lo) * 256;
diapazon: = diapazon * 256;
Oxiri;
Protsedura dekompressiya_diapazoni; (Protsedurani ochish)
Var
harorat: kengaytirilgan;
ee: kengaytirilgan;
Boshlash
(Model va kodlovchini ishga tushirish)
q uchun: = 0 dan 255 gacha
chastota [q]: = 1;
chastota: = chastota - 0,20000; (Chastada - 0 va maksimal qiymatlardan kichik ofset)
jami: = 256;
Kompyuter: = 4; (Kompyuter - biz o'qiyotgan bayt soni)
kod: = 0;
Lo: = 0; diapazon: = 256;
(Biz kodning boshlang'ich, taxminiy qiymatini o'qiymiz.)
Q uchun: = 1 dan 4 gacha
Boshlash
kod: = kod * 256 + compr [q] / 65536/256;
Oxiri;
w: = 0; (W - to'g'ri ochilgan baytlar soni)
(Aslida ochilgan)
Haqiqat qilsa ham
Boshlash
(Keyingi belgining ehtimolini topish)
temp: = (kod- Lo) * umumiy / diapazon;
(Harorat tushadigan belgini qidiring)
yig'indisi: = 0,1; yig'indisi: = 0,1;
E uchun: = 0 dan 255 gacha
Boshlash
yig'indisi: = yig'indisi + chastota [e];
Agar sum> temp bo'lsa, Break;
yig'indi: = yig'indi;
Oxiri;
Inc (w);
(To'g'ri o'ralganligini tekshirish)
(Endi e - qadoqlanmagan bayt va uni faylga chiqarish mumkin)
Agar maʼlumotlar [w]<>e Keyin tanaffus; (Noto'g'ri ochilmagan bo'lsa - chiqish)
Agar w = Hajmi Keyin Boshlang Inc (w); Break End; (Agar hamma narsa ochilsa, biz ketamiz,)
(va model yangilanmagan :-))
(Lo & Hi Yangilanishlar (Uzun))
diapazon: = diapazon / jami;
Lo: = Lo + diapazon * (ssum);
diapazon: = diapazon * (chastotali [e]);
(Model yangilanishi (ehtimolini oshiring))
chastota [e]: = chastota [e] + 1;
jami: = jami + 1;
(Normallashtirish, raqamlarni yaxshilash)
Trunc (Lo) = Trunc (Lo + diapazon) Do
Boshlash
Inc (kompyuter);
temp: = compr;
kod: = (kod - trunc (kod)) * 256 + temp / 16777216;
Lo: = Frac (Lo) * 256;
diapazon: = diapazon * 256;
Oxiri;
Oxiri;
dekabr (w);
(DONE_DECOMPRESS)
Oxiri;

Ma'lumotlarni siqish usullari birinchi kompyuter paydo bo'lishidan ancha oldin boshlangan juda uzoq rivojlanish tarixiga ega. Ushbu maqola g'oyalarning asosiy nazariyalari, tushunchalari va ularning amalga oshirilishi haqida qisqacha ma'lumot berishga harakat qiladi, ammo mutlaq bo'lib ko'rinmaydi. Batafsil ma'lumotni, masalan, R.E.Krichevskiyda topish mumkin. , Ryabko B.Ya. , Vitten I.H. , Rissanen J., Huffman D.A., Gallager R.G. , Knuth D.E. , Vitter J.S. va boshq.
Axborotni siqish - bu juda uzoq tarixga ega bo'lgan muammo bo'lib, hisoblash texnologiyasining rivojlanish tarixidan ancha qadimiyroq bo'lib, u (tarix) odatda ma'lumotni kodlash va shifrlash muammosining rivojlanish tarixi bilan birga keladi. Barcha siqish algoritmlari axborotning kirish oqimida ishlaydi, uning minimal birligi bit, maksimal birligi esa bir necha bit, bayt yoki bir necha baytdir. Siqish jarayonining maqsadi, qoida tariqasida, ba'zi bir dastlabki ixcham bo'lmagan kirish oqimidan ma'lumot birliklarining yanada ixcham chiqish oqimini ularni qandaydir transformatsiya qilish orqali olishdir. Siqish jarayonlarining asosiy texnik tavsiflari va ularning ish natijalari:
Siqish nisbati (siqilish darajasi) yoki boshlang'ich va yakuniy oqimlarning hajmlarining nisbati (nisbati);
Siqish tezligi - kirish oqimidagi ma'lum miqdordagi ma'lumotni undan ekvivalent chiqish oqimi olinmaguncha siqish uchun sarflangan vaqt;
Siqish sifati chiqish oqimi qanchalik kuchli to'planganligini, unga bir xil yoki boshqa algoritm yordamida qayta siqishni qo'llash orqali ko'rsatadigan qiymatdir.
Axborotni siqish muammosiga turlicha yondashuvlar mavjud. Ba'zilari juda murakkab nazariy matematik asosga ega, boshqalari axborot oqimining xususiyatlariga asoslanadi va algoritmik jihatdan juda oddiy. Ma'lumotlarni siqish yoki siqishni amalga oshiradigan har qanday yondashuv va algoritm chiqish axborot oqimining hajmini uning qaytarilmas yoki qaytarilmas o'zgartirish orqali bitlarda kamaytirishga mo'ljallangan. Shuning uchun, birinchi navbatda, ma'lumotlarning tabiati yoki formati bilan bog'liq bo'lgan mezonga ko'ra, barcha siqish usullarini ikki toifaga bo'lish mumkin: qaytariladigan va qaytarilmaydigan siqish.
Qaytarib bo'lmaydigan siqilish deganda, ma'lum bir ma'lumot formatiga asoslangan chiqish oqimi ma'lum bir nuqtai nazardan, kirish oqimiga tashqi xususiyatlariga juda o'xshash, ammo undan farq qiladigan ob'ektni ifodalovchi kirish ma'lumotlar oqimining shunday o'zgarishi tushuniladi. hajmda. Kirish va chiqish oqimlari o'rtasidagi o'xshashlik darajasi ushbu axborot oqimi bilan ifodalangan ob'ektning ma'lum xususiyatlari (ya'ni, siqilgan va siqilmagan ma'lumotlar, ba'zi bir ma'lumotlar formatiga muvofiq) o'rtasidagi muvofiqlik darajasi bilan belgilanadi. Bunday yondashuvlar va algoritmlar, masalan, oqimdagi baytlarning takrorlanishi past bo'lgan bitmap grafik fayllari ma'lumotlarini siqish uchun ishlatiladi. Ushbu yondashuv grafik fayl formati tuzilmasining xususiyatidan va bir necha (aniqrog'i n) usullarda (odam ko'zi bilan idrok etish uchun) ekran sifatiga o'xshash grafik tasvirni taqdim etish qobiliyatidan foydalanadi. Shuning uchun bunday algoritmlarda siqilish darajasi yoki miqdoridan tashqari sifat tushunchasi paydo bo'ladi. siqish jarayonida asl tasvir o'zgaradi, keyin sifatni axborot formatiga asoslangan holda sub'ektiv baholanadigan asl va natijada olingan tasvir o'rtasidagi muvofiqlik darajasi sifatida tushunish mumkin. Grafik fayllar uchun bu yozishmalar vizual tarzda aniqlanadi, garchi tegishli aqlli algoritmlar va dasturlar ham mavjud. Qaytarib bo'lmaydigan siqishni kirish va chiqish oqimlarining ma'lumotlar strukturasining aniq mos kelishi kerak bo'lgan joylarda qo'llash mumkin emas. Ushbu yondashuv JPEG va JFIF algoritmlari hamda JPG va JIF fayl formatlari sifatida tanilgan video va foto ma'lumotlarini taqdim etish uchun mashhur formatlarda amalga oshiriladi.
Qaytariladigan siqilish har doim ma'lumot tarkibini o'zgartirmasdan, chiqadigan axborot oqimining hajmini pasayishiga olib keladi, ya'ni. - axborot tuzilmasini yo'qotmasdan. Bundan tashqari, chiqish oqimidan tiklash yoki dekompressiya algoritmidan foydalanib, siz kirishni olishingiz mumkin va tiklash jarayoni dekompressiya yoki dekompressiya deb ataladi va faqat dekompressiya jarayonidan so'ng ma'lumotlar ularning ichki formatiga muvofiq qayta ishlashga mos keladi.
Qaytariladigan algoritmlarda kodlashni jarayon sifatida statistik nuqtai nazardan ko'rish mumkin, bu nafaqat siqish algoritmlarini qurish, balki ularning samaradorligini baholash uchun ham foydalidir. Barcha qaytariladigan algoritmlar uchun kodlash narxi tushunchasi mavjud. Kodlash narxi kod so'zining bitdagi o'rtacha uzunligini anglatadi. Kodlashning ortiqchaligi xarajat va kodlash entropiyasi o'rtasidagi farqga teng va yaxshi siqish algoritmi har doim ortiqchalikni minimallashtirishi kerak (esda tutingki, axborotning entropiyasi uning buzilishining o'lchovi sifatida tushuniladi.). Shannonning axborotni kodlash bo'yicha asosiy teoremasida aytilishicha, "kodlash narxi har doim manbaning entropiyasidan kam emas, garchi u o'zboshimchalik bilan unga yaqin bo'lishi mumkin". Shuning uchun har qanday algoritm uchun har doim kirish oqimining entropiyasi bilan belgilanadigan siqilish nisbatining ma'lum chegarasi mavjud.
Keling, to'g'ridan-to'g'ri teskari algoritmlarning algoritmik xususiyatlariga murojaat qilaylik va kodlash tizimlari va axborotni siqish usullarini amalga oshirish bilan bog'liq ma'lumotlarni siqishning eng muhim nazariy yondashuvlarini ko'rib chiqaylik.
Ommaviy kodlash orqali siqish
Ma'lumotni teskari tarzda siqish uchun eng mashhur oddiy yondashuv va algoritm Run Length Encoding (RLE) hisoblanadi. Ushbu yondashuv usullarining mohiyati satrlarni yoki takrorlanuvchi baytlar qatorini yoki ularning ketma-ketligini bitta kodlash bayti va ularning takrorlanish soni hisoblagichi bilan almashtirishdan iborat. Barcha o'xshash usullar bilan bog'liq muammo faqatgina ochish algoritmi natijada bayt oqimidagi kodlangan qatorni boshqalardan - kodlanmagan bayt ketma-ketliklaridan ajratish usulini aniqlashda. Muammoni hal qilish odatda kodlangan satrlarning boshiga belgilar qo'yish orqali erishiladi. Bunday teglar, masalan, kodlangan ishga tushirishning birinchi baytidagi xarakterli bit qiymatlari, kodlangan ishga tushirishning birinchi baytining qiymatlari va boshqalar bo'lishi mumkin. Ushbu usullar, qoida tariqasida, rastr grafik tasvirlarni (BMP, PCX, TIF, GIF) siqish uchun juda samarali, chunki ikkinchisi baytlarning takroriy ketma-ketliklarining juda ko'p uzun qatorlarini o'z ichiga oladi. RLE usulining kamchiliklari - bu juda past siqish nisbati yoki oz sonli seriyali fayllarni kodlash va undan ham yomoni, ketma-ket takrorlanadigan baytlarning kichik soni.
RLE usulidan foydalanmasdan siqish
RLE usulidan foydalanmasdan ma'lumotlarni siqish jarayonini ikki bosqichga bo'lish mumkin: modellashtirish va aslida kodlash. Bu jarayonlar va ularni amalga oshirish algoritmlari ancha mustaqil va xilma-xildir.
Kodlash jarayoni va uning usullari
Kodlash odatda ma'lum bir alifboda belgilar oqimini (bizning holatlarimizda baytlar yoki nibbles) qayta ishlash deb tushuniladi va oqimdagi belgilarning paydo bo'lish chastotalari har xil. Kodlashning maqsadi bu oqimni minimal uzunlikdagi bit oqimiga aylantirishdir, bu esa kirish oqimining entropiyasini belgilar chastotalarini hisobga olgan holda kamaytirish orqali erishiladi. Oqim alifbosidagi belgilarni ifodalovchi kodning uzunligi kirish oqimidagi ma’lumotlar miqdoriga mutanosib bo‘lishi kerak va oqim belgilarining bitlardagi uzunligi 8 ga karrali yoki hatto o‘zgaruvchi ham bo‘lmasligi mumkin. Agar kirish oqimining alifbosidan belgilarning paydo bo'lish chastotalarining ehtimollik taqsimoti ma'lum bo'lsa, u holda optimal kodlash modeli tuzilishi mumkin. Biroq, juda ko'p turli xil fayl formatlari mavjudligi sababli, vazifa ancha murakkablashadi. ma'lumotlar belgilarining chastota taqsimoti oldindan ma'lum emas. Bunday holda, umuman olganda, ikkita yondashuv qo'llaniladi.
Birinchisi, kirish oqimini ko'rish va to'plangan statistik ma'lumotlar asosida kodlashni qurish (bu fayl orqali ikkita o'tishni talab qiladi - biri statistik ma'lumotlarni ko'rish va to'plash uchun, ikkinchisi kodlash uchun, bu esa bunday algoritmlarning ko'lamini biroz cheklaydi, chunki, shuning uchun , telekommunikatsiya tizimlarida qo'llaniladigan, ma'lumotlar miqdori ba'zan noma'lum bo'lgan va ularni qayta uzatish yoki tahlil qilish asossiz uzoq vaqt talab qilishi mumkin bo'lgan telekommunikatsiya tizimlarida qo'llaniladigan "parvozda" bir martalik kodlash imkoniyati bundan mustasno. Bunday holda, ishlatiladigan kodlashning statistik sxemasi chiqish oqimiga yoziladi. Ushbu usul statik Huffman kodlash deb nomlanadi.

Kirish.
Siqish kompyuterda fayllarni saqlash uchun zarur bo'lgan joy miqdorini kamaytiradi va
kanal majmui bo'yicha ma'lumotlarni uzatish uchun zarur bo'lgan vaqt miqdori
tarmoqli kengligi. Bu kodlashning bir shakli. Kodlashning boshqa maqsadlari
xatolarni qidirish va tuzatish, shuningdek shifrlash. Qidiruv jarayoni va
xatolarni tuzatish siqishni teskarisidir - bu ma'lumotlarning ortiqchaligini oshiradi,
ular inson o'qiy oladigan shaklda taqdim etilishi kerak bo'lmaganda. Olib tashlash orqali
matndan ortiqcha, siqish shifrlashga yordam beradi, bu esa qidiruvni murakkablashtiradi
kraker uchun mavjud bo'lgan statistik usuldan foydalangan holda shifr.
Qaytariladigan siqishni yoki shovqinsiz siqishni ko'rib chiqing, bu erda boshlang'ich
matn siqilgan holatdan aniq tiklanishi mumkin. Qaytarib bo'lmaydigan yoki
kabi analog signallarni raqamli yozib olish uchun nuqsonli siqish ishlatiladi
inson nutqi yoki rasmlari. Qaytariladigan siqish matnlar uchun ayniqsa muhimdir,
tabiiy va sun'iy tillarda yozilgan, chunki bu holda
xatolar odatda qabul qilinishi mumkin emas. Qo'llashning asosiy sohasi bo'lsa-da
Ko'rib chiqilgan usullar - bu bizning terminologiyamizda aks ettirilgan matnni siqish,
ammo, bu texnikada boshqa maqsadlarda ham bor, shu jumladan qaytariladigan
diskret ma'lumotlar ketma-ketligini kodlash.
Har bir siqilgan kompyuter resurslarini ajratish uchun juda ko'p yaxshi sabablar mavjud
vakillik, chunki tezroq ma'lumotlarni uzatish va bo'sh joyni qisqartirish
ularning saqlash muhim mablag'larni tejash va tez-tez yaxshilash imkonini beradi
kompyuter ko'rsatkichlari. Siqish, ehtimol, hamma tufayli diqqat markazida qoladi
kompyuterga saqlanadigan va uzatiladigan ma'lumotlar hajmini oshirish, bundan tashqari, u mumkin
ba'zi jismoniy cheklovlarni yengish uchun foydalaning, masalan:
masalan, telefon kanallarining nisbatan past o'tkazish qobiliyati.
MA'LUMOTLARNI SIQISH UCHUN KENGAYATGAN DARAXTLARNI QO'LLASH.
Siqish algoritmlari ma'lumotlarni saqlash va uzatish samaradorligini oshirishi mumkin
ularning ortiqcha miqdorini kamaytirish orqali. Siqish algoritmi qabul qilinadi
manba matnni kiritish va unga mos siqilgan matnni ishlab chiqarish,
ochiladigan algoritm sifatida u siqilgan matnga kirish va undan qabul qilish sifatida ega bo'lganda
u manbaning asl matnini chiqaradi. Ko'pgina siqish algoritmlari
manba matnni alifbo harflari qatori sifatida ko'rib chiqing
manba matn.
S satrning ko'rinishidagi ortiqchalik L (S) - H (S), bu erda L (S) uzunlikdir.
bitlarda ifodalash va H (S) - entropiya - axborot mazmunining o'lchovi, shuningdek
bitlarda ifodalanadi. Ma'lumotni yo'qotmasdan siqish mumkin bo'lgan algoritmlar
uning entropiyasidan kamroq bitli satr mavjud emas. Agar dan
manba matnini tasodifiy to'plamdan bir vaqtning o'zida bitta harfdan chiqarib oling,
A alifbosidan foydalanib, entropiya quyidagi formula bo'yicha topiladi:
H (S) = C (S) p (c) log ----,
Bu erda C (S) - satrdagi harflar soni, p (c) - statik ehtimollik
ba'zi C harfining paydo bo'lishi. Agar paydo bo'lish chastotasi p (c) ni baholash uchun ishlatilsa.
S satrdagi har bir c harfi, keyin H (C) satrning o'z-o'zidan entropiyasi deb ataladi. Bunda
dan olingan qatorning o'z-o'zidan entropiyasini ko'rsatish uchun H (S) maqolasidan foydalaniladi
statik manba.
Kengayuvchi daraxtlar odatda leksikografik tartiblash shakllarini tavsiflaydi
ikkilik qidiruv uchun daraxtlar, lekin ma'lumotlarni siqishda ishlatiladigan daraxtlar bo'lmasligi mumkin
doimiy tartibga ega. Buyurtmani yo'q qilish olib keladi
asosiy kengaytirish operatsiyalarini sezilarli darajada soddalashtirish. Natijada
algoritmlar juda tez va ixcham. Huffman kodlaridan foydalanganda,
kengaytirish natijasida mahalliy moslashtirilgan siqish algoritmi paydo bo'ladi
ajoyib darajada sodda va tez, garchi u optimal siqilishga erishmasa ham.
Arifmetik kodlarga qo'llanilganda, siqish natijasi yaqin bo'ladi
vaqtida optimal va taxminan optimal.
PREFIX KODLAR.
Keng o'rganilgan ma'lumotlarni siqish algoritmlarining aksariyati kodlarga asoslangan
Huffman. Huffman kodida manba matnning har bir harfi arxivda aks ettirilgan
o'zgaruvchan uzunlikdagi kod. Tez-tez uchraydigan harflar qisqa kodlar bilan ifodalanadi,
kamroq tez-tez - uzoq. Siqilgan matnda ishlatiladigan kodlar bo'ysunishi kerak
prefiksning xususiyatlari, ya'ni: siqilgan matnda ishlatiladigan kod bo'lishi mumkin emas
har qanday boshqa kodni oldindan belgilang.
Prefiks kodlarini har bir barg joylashgan daraxt orqali topish mumkin
manba alifbosining bir harfiga mos keladi. 1-rasmda kod daraxti ko'rsatilgan
4 harfli alifbo uchun prefiks. Harf uchun prefiks kodini o'qish mumkin
daraxtni ildizdan bu harfga kesib o'tish, bu erda 0 uning chap novdasini tanlashga to'g'ri keladi,
va 1 - o'ng. Huffman kod daraxti vazni tenglashtirilgan daraxt bo'lib, har birida
varaqning og'irligi asl matnda harfning paydo bo'lish chastotasiga teng bo'ladi va
ichki tugunlar o'z vazniga ega emas. Misoldagi daraxt optimal bo'ladi, agar
A, B, C va D harflarining chastotalari mos ravishda 0,125, 0,125, 0,25 va 0,5 bo'ladi.
Muntazam Huffman kodlari oldindan chastota ma'lumotlarini talab qiladi
asl matndagi harflar, bu ikki marta ko'rish zarurligiga olib keladi - bitta
harflar chastotalarining qiymatlarini olish uchun, boshqasi esa siqishni o'zi amalga oshiradi. V
Keyinchalik, ushbu chastotalarning qiymatlari siqilgan matnning o'zi bilan birlashtirilishi kerak
kelajakda uni joylashtirish imkoniyatini yarating. Adaptiv siqish amalga oshiriladi
bir qadamda, chunki asl matnning har bir harfi uchun ishlatiladigan kod asoslanadi
alifboning barcha boshqa harflarining chastotalarida. Samarali uchun asoslar
adaptiv Huffman kodini amalga oshirish Gallagher tomonidan ishlab chiqilgan, Knuth nashr etilgan
bunday algoritmning amaliy versiyasi va Vitter uni ishlab chiqdi.
Optimal moslashtirilgan Witter kodi har doim bir bit ichida joylashgan
optimal statik Huffman kodiga nisbatan manba harfi, odatda bu
H ning bir necha foizini tashkil qiladi. Bundan tashqari, statik Huffman kodlari har doim
H dan har bir manba harfiga bir bit ichida yotadi (ular bunga erishadilar
chegara faqat barcha harflar uchun p (C) = 2 bo'lganda. Siqish algoritmlari mavjud
bu cheklovlarni engib o'tishga qodir. Masalan, Ziv-Lempell algoritmi
belgilangan uzunlikdagi arxivdagi soʻzlarni manba matn satrlariga tayinlaydi
o'zgaruvchan uzunlik va arifmetik siqish kodlash uchun ishlatilishi mumkin
manba harflar hatto bitning bir qismidir.
Prefiks kodlariga kengaytmani qo'llash.
Kengaytiruvchi daraxtlar birinchi marta 1983 yilda va batafsilroq tasvirlangan.
1985 yilda ko'rib chiqilgan. Dastlab ular o'z-o'zini muvozanatlashning bir turi sifatida tushunilgan.
ikkilik qidiruv uchun daraxtlar va ular ruxsat berishlari ham ko'rsatilgan
Ustuvor navbatlarni eng tez amalga oshirish. Agar kengaytiruvchi daraxt tugunlari bo'lsa
mavjud bo'lsa, keyin uzaytiriladi. Bu mavjud tugunga aylanishini anglatadi
ildiz, uning chap tomonidagi barcha tugunlar yangi chap pastki daraxtni, o'ngdagi tugunlar -
yangi o'ng pastki daraxt. Kengayish daraxtni eskidan o'tish orqali erishiladi
maqsad tuguniga ildiz va bu holda mahalliy o'zgarishlar qilish, shuning uchun narx
kengayish bosib o'tilgan yo'lning uzunligiga proportsionaldir.
Tarjan va Slayton kengayadigan daraxtlar statik jihatdan optimal ekanligini ko'rsatdi.
Boshqacha qilib aytadigan bo'lsak, agar mavjud tugunlarning kodlari statikaga muvofiq olinsa
ehtimollikni taqsimlash, keyin kengayadigan daraxtga kirish tezligi va
statik muvozanatli, bu taqsimlash tomonidan optimallashtirilgan, bo'ladi
bir-biridan doimiy koeffitsient bilan farqlanadi, etarli darajada seziladi
uzoq kirishlar seriyasi. Chunki Huffman daraxti bunga misoldir
statik muvozanatli daraxt, so'ngra siqish kengaytmasi yordamida
ma'lumotlar, siqilgan matnning o'lchami ma'lum bir koeffitsient ichida bo'ladi
Huffman kodi yordamida olingan arxiv hajmi.
Dastlab tasvirlanganidek, kengaytma daraxtlarni saqlash uchun qo'llaniladi
barglar emas, balki ichki tugunlardagi ma'lumotlar. Prefiks kodli daraxtlar hamma narsani o'z ichiga oladi
Sizning ma'lumotlaringiz faqat barglarda. Biroq, kengaytma varianti mavjud
prefiks kod daraxti uchun qo'llaniladigan yarim kengaytma. U bilan, maqsad
tugun ildizga o'tkazilmaydi va uning vorislariga o'zgartirishlar kiritilmaydi;
Buning o'rniga, ildizdan maqsadgacha bo'lgan yo'l oddiygina yarmiga qisqartiriladi. Yarim kengayish darajasiga etadi
kabi doimiy koeffitsient doirasidagi bir xil nazariy chegaralar
kengaytma.
Sifatida ushlab leksikografik daraxtning zigzagli o'tish holatida
kengaytirish va yarim kengayish bo'ylab to'g'ridan-to'g'ri marshrutdan farqli o'laroq, murakkabroq
daraxtning chap yoki o'ng chetini maqsadli tugunga. Ushbu oddiy holat quyidagi rasmda ko'rsatilgan
Shakl 2. Yarim kengayishning ildizdan (tugun w) barggacha bo'lgan marshrutga ta'siri
A tugun bir-biridan keyingi har bir ichki juftlikni almashtirishdan iborat
boshqa tugunlar, buning natijasida ildizdan barg tuguniga boradigan yo'lning uzunligi qisqaradi
2 marta. Yarim kengayish jarayonida har bir juftning tugunlari ildizdan uzoqroqda,
yangi yo'lga (x va z tugunlari) va yaqinroqlari kiradi
bundan mustasno (tugunlar w va y).
Kod daraxtlarida yarim kengayish operatsiyasi orqali leksikografik tartibni saqlash
prefiks ixtiyoriy. Kod operatsiyalarida yagona muhim narsa
prefiks siqish protsedurasi tomonidan ishlatiladigan daraxtga to'liq mos keladi
joylashtirish protsedurasi tomonidan ishlatiladigan daraxt. Har qanday o'zgartirish kiritildi
ketma-ket harflar orasida, faqat agar bajariladi
ikkala protsedura ham bir xil tartibda bir xil o'zgarishlarni amalga oshiradi.
Leksikografik tartibni saqlash zarurati o'tkazishni sezilarli darajada osonlashtiradi
zigzag ishini yo'q qilish orqali yarim kengaytirish operatsiyalari. Bo'lishi mumkin
Tegishli maqolalar

"Select Case" filiali operatori

Ulanmagan teglar juftlangan teglardan qanday farq qiladi?

Kondensatorlar Kapasitansli kondansatör plitalari orasidagi potentsial farq
KATEGORIYALAR:

Dasturlar
Xavfsizlik
Windows 10
Temir
Windows 8
Bilan aloqada
Xatolar

Download 61,99 Kb.

1 2

Download 61,99 Kb.