Википедија

Компресија података

У обради сигнала, компресија података, кодирање извора,[1] или редукција битне стопе обухвата кодирање информација користећи мањи број битова него у оригиналној репрезентацији.[2] Компресија може да буде било са губицима или без губитака. Компресија без губитка редукује битове путем идентификације и елиминације статистичке излишности. Информације се не губе при том виду копресије. Компресија са губицима редукује битове уклањањем непотребних или мање важних информација.[3]

Процес редуковања величине датотеке са подацима се обично назива компресијом података. У контексту преноса података, тој процес се назива кодирањем извора; кодирање се типично врши на извору података пре њиховог складиштења или преноса.[4] Кодирање извора не треба мешати са кодирањем канала ради детекције и корекције грешака, или кодирањем линије средства за мапирање података на сигнал.

Компресија је корисна јер се њом редукују ресурси неопходни за складиштење и пренос података. Рачунарски ресурси се конзумирају при процесу компресије и исто тако при супротном процесу (декомпресији). Компресија података је зависна од компромиса просторно–временске комплексности. На пример, компресиона схема за видео може да захтева скуп хардвер да би се видео доволно брзо декомпресовао тако да се може гледати као да је већ био декомпримовао. Опција да се видео у потпуности декомпресује пре гледања може да пуде неподесна или да захтева знатан додатни простор. Дизајн схема за компресију података обухвата компромисе међу мноштвом различитих фактора, укључујући степен компресије, количину унешене дисторзије (при кориштењу компресије са губитком), и рачунарске ресурсе неопходне за компримовање и декомпримовање података.[5][6]

Компресија без губитка уреди

Алгоритми компресије без губитка обично искоришћавају статистичку редунданцију за приказивање податка без губитака информација, тако да је процес реверзибилан. Компресија без губитака је могућа зато што већина података из реалног света показује статистичку излишност. На пример, једна слика може имати подручја боје која се не мењају током неколико пиксела; уместо кодирања „црвени пиксел, црвени пиксел, ...” подаци могу да буду кодирани као „279 црвених пиксела”. Ово је базни пример кодирања дужине трајања; постоје многе схеме за смањење величине датотеке уклањањем редунданције.

Лемпел–Зивови (ЛЗ) компресиони методи су међу најпопуларнијим алгоритмима за складиштење без губитака.[7] DEFLATE је варијација ЛЗ приступа оптимизована за декомпресију говора и побољшање компресионог односа, али компресија може да буде спора. Током средине 1980-их, након рада Терија Велча, Лемпел-Зив-Велчов (ЛЗW) алгоритам брзо је постао преферентни метод за већину компресионих система опште намене. ЛЗW се користи у ГИФ имиџима, програмима као што је ПКЗИП, и хардверским уређајима као што су модеми.[8] ЛЗ методи користе компресиони модел који је базиран на табелама, при чему се табеларним уносима замењују понављајући низови података. За већину ЛЗ метода, ова табела се динамички генерише из ранијих података на улазу. Сама табела је обично кодирана помоћу Хафманових кодова. Граматички засновини кодови попут ових могу да могу да компресују високо репетитивне податке са екстремном ефикасношћу, на пример, колекција биологишких података о истој или блиско сродним врстама, огромна колекција докумената са вишеструким верзијама, интернетско архивирање, етц. Основни задатак на граматици заснованих кодова је конструисање безконтекстне граматике изведене из појединачних низова. Други практични граматички компресиони алгоритми су Секвитур и Re-Pair.

Најснажнији модерни компресори без губитака користе пробабилистичке моделе, као што је предвиђање парцијалног подударања. Бароус-Вилерова трансформација се исто тако може сматрати индиректном формом статистичког моделовања.[9] У даљем побољшању директне употребе пробабилистичког моделовања, статистичке процене се могу повезати са алгоритмом званим аритметичко кодирање. Аритметичко кодирање је модерна техника кодирања која користи математичке прорачуне машине коначног стања за произвођење низа кодираних битова из серије симбола инпутних података. Овим приступом се може остварити супериорна компресија у односу на друге технике, као што је добро познати Хафманов алгоритам. При аритметичком кодирању се користе унутрашња меморијска стања да би се избегла потреба за мапирањем један-на-један индивидуалних улазних симбола на дистинктне репрезентације које користе целобројни број битова. До чишћења унутрашње меморије долази само након што се искодира целокупни низ симбола података. Аритметичко кодирање је веома подесно за задатке прилагодљиве компресије података где статистика варира и зависи од контекста, јер се оно лако може повезати са адаптивним моделом дистрибуције вероватноће улазних података. Један рани пример употребе аритметичког кодирања је био у опционом (мада не широко кориштеном) својству ЈПЕГ стандарда кодирања слка.[10] Од тог времена је оно било примењено на разне друге дезајне, укључујући Х.263, Х.264/МПЕГ-4 АВЦ и ХЕВЦ за видео кодирање.[11]

Компресија са губицима уреди

У касним 1980-им, дигиталне слике су постале уобичајене, и стандарди за компресију слика без губитака су се појавили. У раним 1990-им, методе компресије са губицима су ушле у широку употребу.[8] У тим схемама, известан губитак информације је прихватљив, јер одбацивање небитних детаља може да уштеди складишни простор. Постоји кореспондирајући компромис између очувања информација и смањења величине података. Шеме компресије података са губитком су дизајниране истраживањем начина на који људи спознају дате податке. На пример, људско око је сензитивније за суптилне варијације у осветљењу, него за варијације боје. Компресија ЈПЕГ имиџа се делимично остварује заокруживањем небитних битова информација.[12] Бројни популарни компресиони формати искориштавају ове перцептивне разлике, укључујући психоакустику за звук, и психовизуалне ефекте за имиџе и видео.

Компресија са губицима се може користити у дигиталним камерама, за повећање капацитета складиштења уз минималну деградацију квалитета слике. Слично томе, ДВД технологија користи МПЕГ-2 видео кодирајући формат са губицима за видео компресију.

У аудио компресији са губицима, методи психоакустике се користе за уклањање нечујних (или мање чујних) компоненти аудио сигнала. Компресија људског говора се често изводи још више специјализованим техникама; кодирање говора, или кодирање гласа, понекад се издваја као засебна дисциплина од аудио компресије. Различити стандарди аудио и говорне компресије су присутни у форматима аудио кодирања. Компресија гласа се користи у интернетској телефонији, док се аудио компресија користи за CD складиштење, и аудио плејери декодирају те записе.[9]

Теорија уреди

Теоретску залеђину компресије пружа теорија информације (која је блиско сродна са алгоритамско информационом теоријом) за компресију без губитака и теоријом стопне дисторзије за компресију са губицима. Ове области изучавања је есенцијално створио Клод Шенон, који је објавио фундаменталне публикације у овом пољу током касних 1940-их и раних 1950-их. Теорија кодирања је исто тако сродна област. Идеја компресије података је дубоко повезана са статистичким закључивањем.[13]

Машинско учење уреди

Такође погледајте: Машинско учење

Постоји блиска веза између машинског учења и компресије: систем који предвиђа постериорне вероватноће секвенце полазећи од њене целокупне историје може се користити за оптималну компресију података (користећи аритметичко кодирање на излазној дистрибуцији) док се оптимални компресор може користити за предвиђање (проналажењем симбола који се најбоље компримују, с обзиром на претходну историју). Ова је еквивалентност кориштена као оправдање за употребу компресије података као мерила за „генералну интелигенцију”.[14][15][16]

Референце уреди

  1. ^ Wаде, Грахам (1994). Сигнал цодинг анд процессинг (2 изд.). Цамбридге Университy Пресс. стр. 34. ИСБН 978-0-521-42336-6. Приступљено 22. 12. 2011. „Тхе броад објецтиве оф соурце цодинг ис то еxплоит ор ремове 'инеффициент' редунданцy ин тхе ПЦМ соурце анд тхеребy ацхиеве а редуцтион ин тхе овералл соурце рате Р.” 
  2. ^ Махди, О.А.; Мохаммед, M. А.; Мохамед, А. Ј. (новембар 2012). „Имплементинг а Новел Аппроацх ан Цонверт Аудио Цомпрессион то Теxт Цодинг виа Хyбрид Тецхниqуе” (ПДФ). Интернатионал Јоурнал оф Цомпутер Сциенце Иссуес. 9 (6, Но. 3): 53—59. Приступљено 6. 3. 2013. 
  3. ^ Пујар, Ј.Х.; Кадласкар, L. M. (мај 2010). „А Неw Лосслесс Метход оф Имаге Цомпрессион анд Децомпрессион Усинг Хуффман Цодинг Тецхниqуес” (ПДФ). Јоурнал оф Тхеоретицал анд Апплиед Информатион Тецхнологy. 15 (1): 18—23. Архивирано из оригинала (ПДФ) 28. 12. 2018. г. Приступљено 11. 03. 2019. 
  4. ^ Саломон, Давид (2008). А Цонцисе Интродуцтион то Дата Цомпрессион. Берлин: Спрингер. ИСБН 9781848000728. 
  5. ^ Миттал, Ј.; Веттер (2015), „А Сурвеy Оф Арцхитецтурал Аппроацхес фор Дата Цомпрессион ин Цацхе анд Маин Меморy Сyстемс”, ИЕЕЕ Трансацтионс он Параллел анд Дистрибутед Сyстемс, ИЕЕЕ 
  6. ^ Танк, M.К. (2011). Имплементатион оф Лимпел-Зив алгоритхм фор лосслесс цомпрессион усинг ВХДЛ. Тхинкqуест 2010: Процеедингс оф тхе Фирст Интернатионал Цонференце он Цонтоурс оф Цомпутинг Тецхнологy. Берлин: Спрингер. стр. 275—283. 
  7. ^ Навqи, Сауд; Наqви, Р.; Риаз, Р. А.; Сиддиqуи, Ф. (април 2011). „Оптимизед РТЛ десигн анд имплементатион оф ЛЗW алгоритхм фор хигх бандwидтх апплицатионс” (ПДФ). Елецтрицал Ревиеw. 2011 (4): 279—285. 
  8. ^ а б Wолфрам, Степхен (2002). А Неw Кинд оф Сциенце. Wолфрам Медиа, Инц. стр. 1069. ИСБН 978-1-57955-008-0. 
  9. ^ а б Махмуд, Салауддин (март 2012). „Ан Импровед Дата Цомпрессион Метход фор Генерал Дата” (ПДФ). Интернатионал Јоурнал оф Сциентифиц & Енгинееринг Ресеарцх. 3 (3): 2. Архивирано из оригинала (ПДФ) 28. 12. 2018. г. Приступљено 6. 3. 2013. 
  10. ^ Лане, Том. „ЈПЕГ Имаге Цомпрессион ФАQ, Парт 1”. Интернет ФАQ Арцхивес. Индепендент ЈПЕГ Гроуп. Приступљено 6. 3. 2013. 
  11. ^ Г. Ј. Сулливан; Ј.-Р. Охм; W.-Ј. Хан; Т. Wиеганд (децембар 2012). „Овервиеw оф тхе Хигх Еффициенцy Видео Цодинг (ХЕВЦ) Стандард” (ПДФ). ИЕЕЕ Трансацтионс он Цирцуитс анд Сyстемс фор Видео Тецхнологy. ИЕЕЕ. 22 (12). Приступљено 12. 8. 2017. 
  12. ^ Арцангел, Цорy. „Он Цомпрессион” (ПДФ). Приступљено 6. 3. 2013. 
  13. ^ Марак, Ласзло. „Он имаге цомпрессион” (ПДФ). Университy оф Марне ла Валлее. Архивирано из оригинала (ПДФ) 28. 5. 2015. г. Приступљено 6. 3. 2013. 
  14. ^ Махонеy, Матт. „Ратионале фор а Ларге Теxт Цомпрессион Бенцхмарк”. Флорида Институте оф Тецхнологy. Приступљено 5. 3. 2013. 
  15. ^ Кахири; Бен-Гал I.; Хаусер, С. (2009). „Меасуринг тхе Еффициенцy оф тхе Интрадаy Фореx Маркет wитх а Универсал Дата Цомпрессион Алгоритхм” (ПДФ). 33 (2). Цомпутатионал Ецономицс: 131—154.  |фирст1= захтева |ласт1= у Аутхорс лист (помоћ)
  16. ^ I. Бен-Гал (2008). „Он тхе Усе оф Дата Цомпрессион Меасурес то Аналyзе Робуст Десигнс” (ПДФ). 54 (3). ИЕЕЕ Трансацтионс он Релиабилитy: 381—388. Архивирано из оригинала (ПДФ) 26. 09. 2020. г. Приступљено 11. 03. 2019. 

Литература уреди

  • Танк, M.К. (2011). Имплементатион оф Лимпел-Зив алгоритхм фор лосслесс цомпрессион усинг ВХДЛ. Тхинкqуест 2010: Процеедингс оф тхе Фирст Интернатионал Цонференце он Цонтоурс оф Цомпутинг Тецхнологy. Берлин: Спрингер. стр. 275—283. 
  • Саломон, Давид (2008). А Цонцисе Интродуцтион то Дата Цомпрессион. Берлин: Спрингер. ИСБН 9781848000728. 
  • Wаде, Грахам (1994). Сигнал цодинг анд процессинг (2 изд.). Цамбридге Университy Пресс. стр. 34. ИСБН 978-0-521-42336-6. Приступљено 22. 12. 2011. „Тхе броад објецтиве оф соурце цодинг ис то еxплоит ор ремове 'инеффициент' редунданцy ин тхе ПЦМ соурце анд тхеребy ацхиеве а редуцтион ин тхе овералл соурце рате Р.” 
  • Реза, Фазлоллах M. (1994) [1961]. Ан Интродуцтион то Информатион Тхеорy. Неw Yорк: Довер [МцГраw-Хилл]. ИСБН 978-0-486-68210-5. 
  • Сцхнеиер, Бруце (1996). Апплиед Црyптограпхy: Протоцолс, Алгоритхмс, анд Соурце Цоде ин C. Неw Yорк: Јохн Wилеy & Сонс, Инц. ИСБН 978-0-471-12845-8. 
  • Ауффартх, Б; Лопез-Санцхез, M.; Церqуидес, Ј. (2010). „Цомпарисон оф Редунданцy анд Релеванце Меасурес фор Феатуре Селецтион ин Тиссуе Цлассифицатион оф ЦТ имагес”. Адванцес ин Дата Мининг. Апплицатионс анд Тхеоретицал Аспецтс. Спрингер. стр. 248—262. ЦитеСеерX 10.1.1.170.1528  . 

Спољашње везе уреди

 
Компресија података на Викимедијиној остави.
Преузето из „https://sr.wikipedia.org/w/index.php?title=Kompresija_podataka&oldid=27699520”