Компресиране на данни

Компресирането на данни е процес, при който информацията от един файл се преобразува така, че да се използват по-малко битове, тоест размерът на файла да е по-малък.

Архивирането (вид компресиране без загуба на данни) е процес, при който даден файл се добавя в компресирана папка. Въпреки че се нарича „папка“, това всъщност не е директория, а отделен файл във формат ZIP, RAR, GZ, BZIP, 7z, XZ или друг. Трябва да се има предвид, че архивиране се нарича и процесът, при който се създават резервни копия (например Архив на БНТ).

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

Същност

В компютърните науки компресирането представлява кодиране на информацията, използвайки по-малко битове от оригиналния файл.^[1] Компресирането може да бъде със или без загуба. Компресирането без загуба намалява броя на битовете, като идентифицира и елиминира статистически излишните. Няма загуба на информация. При компресирането със загуба се идентифицира ненужната информация и се премахва. По този начин се намалява броят на битовете. Процесът на намаляване на размера на файла често се нарича компресиране на данни, но всъщност формалното му име е „кодиране на сорс кода“ (на английски: source coding).

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

Една от ползите е, че така се води до намаляване на заетото пространство, и съответно на компютъра може да се запише далеч повече информация, отколкото, ако ненужните файлове не са архивирани;
Препоръчително е файловете да се архивират, защото обикновено повечето от архивираните файлове остават незасегнати от компютърни вируси. Това е добър вариант за запазването им;
Обикновено пощите и програмите за комуникация (като Скайп) имат ограничение върху обема на файла. Затова архивирането може да разреши преноса на един филм например, който иначе няма как да бъде изпратен.

Видове компресиране на данни

Със загуба

Компресирането на данни със загуба е обратното на компресирането на данни без загуба. В тези схеми загубите на информацията са приемливи. Изпускането на несъществен детайл от източника на данни може да запази място в хранилището. Схемите на компресирането на данни със загуба са изпълнени с изследване за това, как хората възприемат данните, които са под въпрос. Например човешкото око е по-чувствително към проницателни видоизменения на яркостта, отколкото към видоизменения на цвета. Компресирането на JPEG изображение работи в частност от закръглянето на несъществени битове от информация. Има съответстваща замяна между загубата на информация и размера на намалението. Редица популярни формати за компресиране използват тези разлики във възприятието, включвайки онези, използвани в музикални файлове, изображения и видео.

Компресирането на изображения със загуба на данни може да бъде използвано от цифровите камери за увеличаване на капацитета на съхранение с минимално понижение на качеството на снимката. По същия начин DVD устройствата използват MPEG-2 видео кодеци със загуба на данни за видео компресиране.

При аудио компресирането със загуба на данни методите за психоакустика са използвани за премахването на такива компоненти на сигнал, които не могат да се чуват (или са по-слабо чуваеми). Компресирането на човешката реч е често изпълнявано с дори по-специализирани техники. Кодирането на речта или на гласа е понякога разграничавано като отделна дисциплина от аудио компресирането. Различни аудио и речеви стандарти за компресиране са описани като аудио кодеци. Компресирането на гласа е използвано от интернет телефонията, например аудио компресирането е използвано за пренасяне на аудио информацията от CD на твърд диск и е декодирано от аудио плейъри.

Без загуба

Алгоритмите за компресиране без загуба обикновено използват методи за премахване на статистическото повторение, за да представят данните в по-сбит вариант, без да се губи информация.^[2] Компресирането без загуба е възможно, тъй като в повечето данни от реалния живот има статистическо излишество. Например в едно изображение може да има области, в които цветът не се променя върху няколко пиксела. Вместо да кодираме „червен пиксел, червен пиксел, ...“, информацията може да се представи като „279 червени пиксела“. Това е базов пример за това, как работи run-length encoding, има много схеми, по които може да се намали размер на файл, като се елиминира излишеството в информацията.

LZ (Lempel-Ziv) компресията е сред най-популярните алгоритми за компресия без загуба. DEFLATE е вариация на LZ с оптимизирана скорост на декомпресия и добър коефициент на компресия, но самото компресиране може да бъде бавно. DEFLATE се използва в PKZIP, Gzip и PNG форматите за компресия. LZW (Lempel-Ziv-Welch) се използва в GIF изображенията. Струва си да обележим и LZR (Lempel-Ziv-Renau) алгоритъма, който служи за база при ZIP компресията. LZ методите използват таблично базиран модел за компресия, записите в таблицата представляват повторяеми низове от данни. При повечето LZ методи таблицата се генерира динамично от предходно постъпилите входни данни. Самата таблица много често използва Huffman енкодинг (напр. SHRI, LZX). LZХ е кодираща схема (базирана на LZ), която се използва в CAB формата на Microsoft.

Най-добрите модерни методи за компресия без загуба използват вероятностни модели, такива като прогнозирането по частично съвпадение.

Класовете от граматично-базирани кодове набират популярност, защото те могат да компресират изключително добре многократно повтарящи се текстове, например колекция от биологични данни за едни и същи или родствени видове, документ с огромен набор от версии, интернет архиви и т.н. Основна задача на граматичното кодиране е изграждането на контекстно независима граматика, произтичаща от единствен низ. Sequitur и Re-Pair са практични граматични алгоритми за компресия, за които има достъпни публични кодове.

Като резултат от усъвършенстването на тези техники, статистическите прогнозирания могат да бъдат комбинирани в алгоритъм, наречен аритметично кодиране. Аритметичното кодиране, измислено от Jorma Rissanen и превърнато в практичен метод от Witten, Neal и Cleavy, постига по-добра компресия от добре известния алгоритъм на Huffman и се справя на изключително ниво при задачи за адаптивна компресия на данни, където прогнозиранията са контекстнозависими. Аритметичното кодиране се използва в bi-level стандарта за компресията на изображения JBIG и при стандарта за компресия на документи DjVu. Системата за вход на текст Dasher използва инвертиран аритметичен кодер.

Алгоритми за компресиране

Кодиране по дължина

Кодирането по дължина (на английски: Run – length encoding) е форма на компресиране на информация, използвана при последователности от данни, където едни и същи елементи се повтарят многократно. След края на кодировката информация е запазена в единична клетка, съдържаща вида данни и броя на неговото срещане. Кодирането по дължина е най-оптимално при файлове, където се срещат много повторения на данни, например простите графични изображения или икони.

Нека имаме картина с бял фон и черен текст. Тя е съставена от много последователности от бели пиксели в празното пространство и много черни пиксели, там където е текстът. Хипотетично нека вземем, че следната последователност представлява един ред от картинката (B представлява черните пиксели, а W – белите):

   WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB

Ако използваме алгоритъма за кодиране по дължина, ще получим:

   12WB12W3B24WB

който се интерпретира по следния начин: 12 бели, 1 черно, 3 бели, 3 черни и т.н.

Алгоритъмът представя оригиналния запис от 53 символа в запис с 13. Разбира се, истинският формат, използван за запаметяване на картинки, е бинарен код вместо ASCII символи, но принципът остава същият. Всеки файл може да бъде компресиран с помощта на този метод.

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

Речниково кодиране

Речниковото кодиране представлява всеки от редицата алгоритми за компресиране на данни без загуба, който оперира чрез търсене на съвпадения между текста, който да бъде компресиран и набора от низове, съдържащи се в структурата от данни (наричан „речник“), поддържан от енкодер. Когато енкодерът намери такова съвпадение, той заменя отношение към позицията на низа в структурата от данни.

Някои речникови кодирания използват „статичен речник“, при който пълният набор от низове е определен преди да започне кодирането и не се променя в процеса на кодиране. Този подход е най-често използван, когато съобщението или наборът от съобщения, които трябва да бъдат енкодирани, е голям и устойчив. Например многото софтуерни пакети, които съхраняват съдържанието на библията в ограничено пространство на PDA устройство главно изграждат статичен речник от показател от думи в текст и след това използват този речник, за да компресират стиховете.

По-често използвани са методите, при които речникът започва при някое предопределено състояние, но съдържанието се променя в продължение на процеса на енкодиране, основано на данните, които вече са били енкодирани. Двата алгоритъма LZ77 и LZ78 работят на този принцип. При LZ77 структура от данни, наричана „плъзгащ прозорец“ (на английски: sliding windows), се използва за задържане на последните N байтове от преработени данни. Този прозорец служи като речник, ефективно запазвайки всеки подниз, който се е появил при последните N байтове като входове на речник. Вместо да се използва единичен индекс за идентифициране на входовете на речника се използват две стойности – дължината, показваща дължината на съвпадащия текст и отстоянието (също наричано разстояние), показващо, че съвпадението е намерено в плъзгащия прозорец, започвайки байтове на отстояние преди настоящия текст.

Кодиране с частично съвпадение

Кодирането с частично съвпадение (на английски: Prediction by Partial Matching)е статистически техника за компресиране на информация, базирана на контекстно моделиране и предсказание. Кодирането с частично съвпадение (известен като PPM) използва набор от предхождащи символи в некомпресирания символен поток, за да предскаже какъв е следващия символ в потока.

Броят на предхождащите символи n определя реда на PPM модела, който се означава като PPM(n). Неограничените варианти, където контекста няма определена дължина, също съществуват и се означават като PPM*. Ако не може да бъде създадено предсказание базирано на всичките n на брой символи в контекста, алгоритъма опитва да създаде такова, използвайки n-1 символа. Процеса се повтаря докато се намери съвпадение или не останат символи в контекста. В този момент се фиксира предсказание.

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

Прилагането на PPM компресирането варира спрямо различни детайли. Избраният символ в повечето случаи се запазва с помощта на аритметично кодирано, въпреки че е възможно да бъде използвана и кодировката на Хъфман. Основният модел на PPM алгоритъма може да бъде развит да предсказва множество символи.

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

Кодиране чрез смесване на контекста

Компресирането чрез смесване на контекста е тип алгоритъм за компресиране на данни, при който предвижданията за следващ символ от два или повече статистически модела са комбинирани, за да извикват предвиждане, което често е по-точно, отколкото всяко от индивидуалните предвиждания. Например един прост метод (не е необходимо най-добрият) е да се осреднят вероятностите, приложени към всеки модел. Случайната гора е друг метод, който извежда предвиждането, което е способът на предвижданията изведени от индивидуални модели. Комбинирането на модели е активна зона за изследване на машинното изучаване.

Сериите за компресиране на данни PAQ използват компресирането чрез смесване на контекста, за да назначават предвиждания към индивидуални битове от вкарването на данни.

Ентропологично кодиране

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

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

Според теоремата на Шанън за източник на кодиране оптималната дължина на код за символ е –log_bP, където b е сумата от символи използвани за направата на извеждането на кодовете, а P е вероятността на вкарването на съмвол.

Две от най-честите техники на ентропологично кодиране са кодировката на Хъфман и аритметичното кодиране. Ако приблизителните ентропологични характеристики на потока от данни са предванително известни (особено за сигналното компресиране), прост статичен код би могъл да е от полза. Тези статични кодове включват универсални кодове (гама-кодът на Елиас или кодът на Фибоначи) и кодовете на Голомб (унарния код или кодът на Райс).

Кодировка на Хъфман

В компютърните науки и информационната теория кодировката на Хъфман представлява алгоритъм за ентропологично кодиране, използван за компресиране на данни без загуба. Терминът се отнася за използването на таблица с код, притежаващ променлива дължина, използвана за кодиране на сорс символ (например писмен знак във файл), където тази таблица е произлязла по особен начин, базиран на оценената вероятност на проявление на всяка възможна стойност на сорс символа. Кодировката е създадена от Дейвид Хъфман, докато е бил докторант по философия в Масачузетския технологичен институт, и е публикувана през 1952 под заглавие „Метод за конструкция на кодове с минимална претрупаност“.

Аритметично кодиране

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

Кодиране чрез сортиране на блокове

Кодирането чрез сортиране на отделни блокове (на английски: Block – sorting compression) е алгоритъм за компресиране на данни, който не променя нито една от стойностите на входните символи. Трансформацията се състои в пренареждане реда на символите. Ако оригиналния низ е имало няколко подчасти, които се повтарят често, тогава трансформирания от алгоритъма низ ще има няколко места, където единични символи ще бъдат повторени няколко пъти на един ред. Това е полезно за компресирането, защото се оказва, че е лесно да бъде компресиран низ, който се състои от много последователности на едни и същи символи.

Файлови формати

RAR

RAR е архивен файлов формат, който поддържа компресиране на данни, възстановяване на грешки и раздробяване на файлове. Разработен е от руския софтуерен инженер Евгени Рошал. Името RAR идва от Roshal ARchive и се поддържа от win.rar GmbH.

Файловото разширение използвано от RAR e .rar за обем данни и .rev за файлови набори за възстановяване. Предходните версии на RAR разделят големите файлови архиви на няколко по-малки. Добавят се числа в разширенията на малките части, за да могат те да са правилно подредени. Първият от малките файлове е с разширение .rar, вторият – .r00, после r.01, r.02 и т.н. Минималния размер на RAR файл е 20 байта, а максималния – 9 223 372 036 854 775 807 байта, което е 8 екзабайта минус 1 байт.

RAR файлове се създават с WinRAR, RAR, или всеки друг софтуер, който е под лиценз на Александър Рошал, по-възрастния брат на Евгени Рошал, а могат да бъдат разархивирани с много на брой програми. RARLAB предоставят сорс код за безплатна програма за разархивирнане, макар че самия код е под платен лиценз. Тази програма може да разархивирва .rar файлове, но не може да създава такива.

ZIP

Основна статия: ZIP

ZIP е популярен формат за компресиране на данни и архивиране на файлове. Файл в този формат обикновено има разширение .zip и съхранява в компресиран или некомпресиран вид един или няколко файла, които могат да се извлечат от него, посредством разопаковане със специална помощна програма. ZIP е разработен от Филип Кац за употреба в програмата PKZIP. Впоследствие се появяват много други инструменти, работещи с този формат.

7z

7z е комппресиран архивен файлов формат, който поддържа няколко различни алгоритъма за компресиране на данни, криптиране и препроцесиране. 7z форматът първоначално се появява при програмата за архивиране 7-Zip. Тази програма е публично достъпна под лиценза GNU Lesser General Public License.

Официалната спецификация на 7z файловия формат се разпределя при сорс кода на 7-Zip. Спецификацията може да бъде намерена в простия .doc текстови формат на поддиректорията, намираща се в дистрибуцията на сорс код.