Алгоритми за компресиране: описание, основни техники, характеристики

Компресията е специален случай на кодиране, чиято основна характеристика е, че полученият код е по-малък от оригинала. Процесът се основава на намиране на повторения в поредица от информация и след това запазване само на едно до броя на повторенията. Така например, ако една последователност се появи във файл като "AAAAAA", заемаща 6 байта, тя ще бъде записана като "6A", която заема само 2 байта, в алгоритъма за компресия RLE.

История на произхода на процеса

Морзовата азбука, изобретена през 1838 г., е първият известен случай на компресиране на данни. По-късно, когато мейнфрейм компютрите започват да набират популярност през 1949 г., Клод Шанън и Робърт Фано изобретяват процес на кодиране, наречен на името на авторите - Шанън-Фано. При това криптиране на символите в набора от данни се присвояват кодове съгласно теорията на вероятностите.

Едва през 70-те години на миналия век, с появата на интернет и онлайн съхранението, се прилагат пълноценни алгоритми за компресиране. Кодовете на Хъфман се генерират динамично въз основа на входната информация. Ключовата разлика между кодирането на Шанън-Фано и кодирането на Хъфман е, че при първото вероятностното дърво е построено отдолу нагоре, което създава неоптимален резултат, докато при второто то е построено отгоре надолу.

През 1977 г. Абрахам Лемпел и Якоб Зив публикуват своя иновативен метод LZ77, който използва по-модернизиран речник. През 1978 г. същият екип от автори публикува LZ78 - усъвършенстван алгоритъм за компресиране. която използва нов речник, който анализира входните данни и генерира статичен речник, а не динамичен речник от версията 77.

Форми на изпълнение на компресия

Компресията се извършва от програма, която използва формула или алгоритъм, определящ, как да намалите размер на данните. Например, за да представите низ от битове с по-малък низ от 0 и 1, като използвате речник за преобразуване или формула.

Компресията може да бъде проста. Така например, като изтриване на всички ненужни символи, вмъкване на един повтарящ се код за обозначаване на ред с повторения и замяна на по-малък низ от битове. Алгоритъмът за компресиране на файлове може да свие текстов файл с до 50% или значително повече.

За да се прехвърли, процесът се извършва в блок за прехвърляне, включващ заглавни данни. Когато информацията се изпраща или получава по интернет, архивираните поотделно или заедно с други големи файлове могат да се прехвърлят в ZIP, GZIP или други "намален" формат.

Предимство на алгоритмите за компресия:

1. Значително намаляване на пространството за съхранение. При съотношение на компресия 2:1 файл с размер 20 мегабайта (MB) заема 10 MB място. В резултат на това мрежовите администратори изразходват по-малко средства и време за съхраняване на бази данни.
2. Оптимизира производителността на архивирането.
3. Важен метод за намаляване на данните.
4. Почти всеки файл може да бъде компресиран, но е важно да се избере правилната технология за дадения тип файл. В противен случай файловете могат да бъдат "намален", но не променя общия размер.

Използват се два вида методи за компресиране - алгоритми за компресиране без загуби и със загуби. Първата позволява възстановяването на файла в първоначалното му състояние, без да се губи нито един бит информация в некомпресиран файл. Вторият - е типичен Подход към изпълними файлове, текст и електронни таблици, при които загубата на думи или цифри ще промени информацията.

Компресията със загуба на данни премахва трайно битовете данни, които са излишни, маловажни или незабележими. Тя е полезна при графики, аудио, видео и изображения, при които премахването на някои части има малък или никакъв забележим ефект върху представянето на съдържанието.

Алгоритъм за компресия на Хъфман

Този процес, който може да се използва за "намаляване на" или криптиране.

Тя се основава на присвояване на кодове с различна дължина на битовете за всеки повтарящ се символ, като колкото повече са тези повторения, толкова по-голямо е съотношението на компресия. За да се възстанови оригиналният файл, е необходимо да се знае зададеният код и неговата дължина в битове. По същия начин използвайте програмата за криптиране на файловете.

Създаване на алгоритми за компресиране на данни:

1. Изчислете колко пъти се повтаря всеки символ във файла за "намаляване на".
2. Създаване на свързан списък с информация за символите и честотите.
3. Сортирайте списъка от най-ниската към най-високата стойност в зависимост от честотата.
4. Преобразуване на всеки елемент от списъка в дърво.
5. Сливане на дървета в едно, като първите две дървета образуват ново дърво.
6. Добавяне на честотите на всеки клон към нов запис в дървото.
7. Поставете новата на правилното място в списъка според сумата на получените честоти.
8. Присвояване на нов двоичен код на всеки символ. Ако се вземе нулев клон, към кода се добавя нула, а ако се вземе първи клон, се добавя единица.
9. Файлът се прекодира в съответствие с новите кодове.
10. Например характеристиките на алгоритмите за компресиране на кратък текст:"ata la jaca a la estaca"
11. Пребройте колко пъти се появява всеки символ и съставете свързан списък:` (5), а (9), в (2), д (1), й (1), л (2), с (1), т (2)
12. Подредете по честота от най-ниската към най-високата: д (1), й (1), с (1), в (2), л (2), т (2), "" (5), а (9)

Както можете да видите, създаден е кореновият възел на дървото, зададени са следните кодове.

Остава само да съберем битовете в групи по осем, т.е. байтове:

Общата сума е осем байта, а оригиналният текст е 23.

Демонстрация на библиотека LZ77

Разгледайте алгоритъма LZ77 за пример за текст"howtogeek". Ако го повторите три пъти, то ще се промени на.

След това, когато иска да прочете текста обратно, той ще замени всеки случай (h) с "howtogeek", връщайки се към първоначалната фраза. Това показва, че алгоритъмът за компресиране на данни е без загуби, тъй като въведените данни са същите като получените.

Това е идеален пример, при който по-голямата част от текста е компресирана с няколко символа. Например думата "това" ще бъде компресирана, дори ако се появява в думи като "този", "техните" и "това". С повтарящи се думи можете да постигнете огромни коефициенти на компресия. Например текст с думата "howtogeek", повторен 100 пъти, е с размер три килобайта, а компресирането му ще отнеме само 158 байта, т.е. с 95% "намаление".

Това, разбира се, е доста краен пример, но той ясно демонстрира свойствата на алгоритмите за компресиране. В общата практика тя е 30-40% при текстовия формат ZIP. Алгоритъмът LZ77 се прилага за всички двоични данни, а не само за текст, въпреки че последният е по-лесен за компресиране заради повтарящите се думи.

Дискретно косинусово преобразуване на изображения

Компресията на видео и аудио работи по много различен начин. За разлика от текста, при който се използват алгоритми за компресия без загуби и не се губят данни, изображенията се "намаление" със загубите и колкото по-висок е %, толкова по-големи са загубите. Това води до онези ужасно изглеждащи JPEG файлове, които хората изтеглят, разменят и правят многократни снимки на екрана.

Повечето картини, снимки и други неща съхраняват списък от числа, всяко от които представлява един пиксел. JPEG ги записва, като използва алгоритъм за компресиране на изображения, наречен дискретно косинусово преобразуване. Това е съвкупност от синусоидални вълни, които се събират с различна интензивност.

Този метод използва 64 различни уравнения, а след това кодиране на Huffman за още по-голямо намаляване на размера на файла. Този алгоритъм за компресиране на изображения дава безумно висока степен на компресия и намалява размера на изображението от няколко мегабайта до няколко килобайта в зависимост от необходимото качество. Повечето снимки са компресирани, за да се спести време за изтегляне, особено за потребители на мобилни устройства с лошо предаване на данни.

Видеото работи малко по-различно от изображенията. Обикновено алгоритмите за компресиране на графики използват т.нар. "компресиране между кадрите", което изчислява промените между всеки кадър и ги съхранява. Така например, ако има такъв относително неподвижна снимка, която отнема няколко секунди във видео, тя ще "намален" в едно. Компресията между кадрите позволява цифрова телевизия и уеб видео. Без него видеоклиповете биха тежали стотици гигабайти, което е повече от средния размер на твърдия диск през 2005 г.

Компресирането на аудио работи по същия начин като компресирането на текст и изображения. Когато JPEG премахва детайли от изображението, които не са видими за човешкото око, компресията на звука прави същото за звуците. MP3 използва битрейт, вариращ от 48 и 96 kbps (долната граница) през 128 и 240 kbps (доста добър) до 320 kbps (висококачествен звук), като разликата може да се чуе само с изключително добри слушалки. Съществуват кодеци за аудио без загуби, като основният е FLAC и използва кодиране LZ77 за аудио без загуби.

Формати "намаляване на" текст

Обхватът на библиотеките за текст се състои главно от алгоритъм за компресиране на данни без загуби, освен в екстремни случаи за данни с плаваща запетая. Повечето компресорни кодеци включват "намаление" LZ77, Huffman и аритметични кодеци. Те се прилагат след други инструменти, за да се изстискат още няколко процентни пункта компресия.

Стойностите на сериите се кодират като символ, последван от дължината на серия. Можете да правилно възстановяване оригинална нишка. Ако дължината на пробега<= 2 символа, има смисъл просто да ги оставите непроменени, като например в края на потока с "bb".

В някои редки случаи се получават допълнителни икономии чрез прилагане на преобразуване с алгоритми за компресиране със загуба на данни към части от съдържанието, преди да се приложи методът без загуба на данни. Тъй като при тези преобразувания файловете не могат да бъдат възстановени в първоначалното им състояние, тези "процеси" Запазено за текстови документи. които не са засегнати от загуба на информация, например съкращаване на числата с плаваща запетая само до два значещи десетични знака.

Днес повечето системи за компресиране на текст работят чрез комбиниране на различни преобразувания на данни, за да се постигне възможно най-добрият резултат. Смисълът на всеки етап от системата е да извърши преобразуването, за да може следващият етап да продължи да компресира ефективно. Обобщавайки тези стъпки, получавате малък файл, който може да бъде възстановен до състояние без загуби. Съществуват буквално стотици формати и системи за компресиране, всяка от които има предимства и недостатъци за различни видове данни.

Схеми на HTTP: DEFLATE и GZIP

Днес в интернет се използват два широко разпространени алгоритъма за компресиране на HTTP текст: DEFLATE и GZIP.

DEFLATE - обикновено обединяване на данни, използване на LZ77, кодиране на Хъфман. GZIP - файлът използва вътрешно DEFLATE, заедно с някои интересни заключвания, евристики за филтриране, заглавие и контролна сума. Като цяло допълнителното заключване и евристиката при използване на GZIP дават по-добри коефициенти на компресия, отколкото само при DEFLATE.

Протоколи за данни от следващо поколение - SPDY и HTTP2.0, поддържат компресия на заглавието GZIP, така че повечето уеб сървъри ще я използват и в бъдеще.

Повечето разработчици просто качват некомпресирано съдържание и разчитат на уеб сървъра за "намаляване на" данни в движение. Това дава отлични резултати и лесен за използване алгоритъм за компресиране на изображения. Много сървъри по подразбиране използват GZIP на ниво 6, а най-високото ниво е 9. Това е умишлено създадено, за да позволи на сървърите да компресират данните по-бързо за сметка на по-голям изходен файл.

формати BZIP2 и LZMA, които създават по-компактни форми от GZIP, но се декомпресират по-бързо.

LZMA може да се счита за далечен роднина на GZIP. И двете започват с популярен речник LZ, последвана от система за статистическо кодиране. Подобрената способност на LZMA да компресира файлове с малък размер обаче се крие в неговите "усъвършенствани алгоритми за съпоставяне и прозорци LZ.

Предварителна обработка на документи

За компресиране на качеството се извършва двуетапен процес:

• стъпка на минимизиране;
• стъпка без загуби.

Минификацията е свързана с намаляване на размера на данните, така че да могат да се използват без обработка, като се изтриват много ненужни данни във файла, без да се променя синтаксисът. Затова е безопасно да се премахнат повечето от интервалите в Jscript, като се намали размерът, без да се променя синтаксисът. Минификацията се извършва по време на процеса на изграждане. Като ръчна стъпка или като част от автоматизирана верига за изграждане.

Съществуват много програми, които изпълняват основни алгоритми за компресиране, сред които

1. Winzip е формат за съхранение без загуби, който се използва широко за документи, изображения или приложения. Това е сравнително проста програма, която компресира всеки от файловете поотделно, като по този начин дава възможност да се възстанови всеки от тях, без да се налага да се четат останалите. като по този начин се подобрява ефективността на процеса.
2. 7zip - Безплатен мениджър за много мощен и прост алгоритъм за компресиране на данни. Благодарение на файловия формат 7z, който подобрява стандарта ZIP с 50%. Подкрепя другите най-често срещаните формати като RAR, ZIP, CAB, GZIP и ARJ, така че няма проблем да се използва с всеки компресиран файл и се интегрира с контекстното меню в Windows.
3. GZIP е един от най-известните компресори, предназначени за Linux. Предвид успеха му в тази платформа, той е завършен за Windows. Едно от основните предимства на gzip е, че използва алгоритъма DEFLATE (комбинация от кодиране LZ77 и Huffman).
4. WinRAR - компресорна програма и многофункционален декомпресор на данни. Това е незаменим инструмент за пестене на дисково пространство и време за трансфер при изпращане и получаване на файлове по интернет или при архивиране. Използва се за компресиране на всички видове документи или програми, така че да заемат по-малко място на диска и да могат да се съхраняват или прехвърлят по-бързо по мрежата. Това е първият компресор с 64-битово управление на файловете, което ви позволява да обработвате големи обеми от данни, ограничени единствено от операционна система.

Минификатори на CSS

Съществуват много минификатори на CSS. Някои от наличните опции включват:

• онлайн CSS Minifier;
• freeformatter.com/css-minifier;
• cleancss.com/css-minify;
• cnvyr.io;
• минификатор.org;
• css-minifier.com.

Основната разлика между тези инструменти зависи от това колко дълбоки са процесите на минификация. Опростена оптимизация филтрира текста, за да премахне ненужните интервали и масиви. Усъвършенстваната оптимизация включва замяна на "AntiqueWhite" с " # FAEBD7 ", тъй като шестнайсетичната форма във файла е по-кратка, и налагане на използването на символа GZIP с малки букви.

По-агресивните начини на CSS спестяват място, но могат да нарушават изискванията CSS. Затова повечето от тях не могат да бъдат автоматизирани и разработчиците правят избор между размера и степента на риска.

Всъщност има нова тенденция за създаване на други версии от CSS езици, които да помагат на автора на кода по-ефективно, като допълнителна полза, позволяваща на компилатора да произвежда по-малко CSS код.

Плюсове и минуси на компресията

Основните предимства на компресията са намаляването на хардуера за съхранение, времето за прехвърляне на данни и ширината на честотната лента.

Такъв файл изисква по-малко памет, а използването на метода води до намаляване на разходите за дисково или полупроводниково съхранение. Предаването отнема по-малко време, когато пропускателната способност на мрежата е малка.

Основният недостатък на компресирането е въздействието върху производителността, което се дължи на използването на ресурси на процесора и паметта за процеса и впоследствие за декомпресиране.

Много доставчици са проектирали системи, за да се опитат да сведат до минимум въздействието на изчисленията, изискващи компресия. Ако се изпълни преди данните да бъдат записани на диска, системата може да разтовари процеса, за да спести системни ресурси. Например IBM използва отделна карта за хардуерно ускорение, за да се справи с компресията в някои корпоративни системи за съхранение.

Ако данните се компресират след записването им на диска или след обработката им, компресирането се извършва във фонов режим, за да се намали въздействието върху производителността на машината. Въпреки че компресирането след обработката намалява времето за реакция за всеки вход и изход (I/O), то все пак консумира памет и цикли на процесора и влияе върху броя на операциите, които системата за съхранение обработва. Освен това, тъй като първоначално данните трябва да бъдат записани на диск или флаш устройство в некомпресиран вид, икономията на физическа памет не е толкова голяма, колкото при вградените "намаляване ".

Бъдещето никога не е сигурно, но въз основа на настоящите тенденции можем да направим някои прогнози за това какво може да се случи с технологията за компресиране на данни. Алгоритмите за смесване на контекста, като PAQ и неговите варианти, започнаха да набират популярност и са склонни да постигат най-високи съотношения "намаляване на". Въпреки че обикновено са бавни.

С експоненциалното нарастване на скоростта на хардуера по закона на Мур процесите на смесване на контекста вероятно ще процъфтяват. Тъй като разходите за скорост се преодоляват от бързия хардуер поради високата степен на компресия. Алгоритъмът, който PAQ се опитва да подобри, се нарича "Предвиждане на частични пътища за картографиране". Или PPM.

И накрая, верижният алгоритъм на Лемпел-Зив-Марков (LZMA) постоянно демонстрира отличен компромис между скорост и висока степен на компресия и в бъдеще вероятно ще създаде още варианти. Тя ще бъде водеща, защото вече е възприета в много конкурентни формати за компресиране, като например програмата 7-Zip.

Друга потенциална разработка е използването на компресия с изброяване на поднизове (CSE), която е обещаваща технология и все още няма много софтуерни реализации.