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

Същност
Компресирането на данни е едно от основните проявления на теорията на информацията. Тя е клон на математиката, водеща началото си от работата на Клод Шенън в Bell Labs през втората половина на 40-те години, където той разглежда различни въпроси, свързани с информацията като метод на възникване, съхраняване и предаване. Копресирането на данните е част от Теорията на информацията, тъй като се занимава с излишеството на информация в дадено съобщение. Излишната информация в едно съобщение ни принуждава да използваме повече битове за неговото кодиране. Ако можа да се премахне излишеството, ще се намали размерът на съобщението. Теорията на информацията използва термина ентропия като мярка колко информация е закодирана в дадено съобщение. Колкото е по-висока ентропията на дадео съобщение, толкова по-голямо е информационното му съдържание. Ентропията на дадео съобщение се дефинира като отрицателен логаритъм при основа две. Ентропията на цялото съобщение е сумата от ентропиите на всички символи в съобщението.

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

Те компресират един едни и същи файлове, които се разделят на три големи групи:
1. Текст – бележки, ръкописи, програмен код и друга текстова информация.
2. Двоични данни – таблици, изпълними файлове, бази данни.
3. Графична информация.

Алгоритмите се групират по три показателя:
1. Времето, необходимо за компресиране на даден файл.
2. Нивото на компресия на целия пакет от файлове – текстове, двоични и графични.
3. Ниво на загуба на качество при компресиране на данните.

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

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

Методи за кодиране на информация
1. Кодиране дължината на серията (run-length encoding)
Това е метод за намаляване размера на повтарящи се поредици от знаци. Обикновено RLE използва два байта за представянето на един знак – брой повторения и самия знак. RLE може да се използва върху произволни данни, но техният тип влияе върху коефициента на компресията. Обикновено RLE не води до високи нива на компресия, но е бърз за изпълнение и алгоритъмът му се имплементира много лесно.

Пример:
АААААААААААААААААААА →след кодиране→20А, което отнема само два байта. Коефициентът на компресия е много голям.
ABCD→ след кодиране→1A1B1C1D→размерът вместо да намалява се увеличава.
Ако компресираните данни не съдържат достатъчно дълги поредици от повтаряеми знаци, коефициентът на компресия може да падне до 1.

2. Относително кодиране (relative encoding)
При него се записват разликите между два блока от информация, а не самите блокове. Може да се прилига ефективно при приложения с последователно регистриране на данни.

3. Честотно кодиране (frequency dependent encoding)
Ако някой символ се среща по-често, той трябва да има съкратен код. Например буквите, които се използват по-често имат определен код. Развитие този метод получава прз 40-те години на миналия век във връзка с надеждността на релетата. Системата от кодове се нарича Кодове на Хъфман. Основната идея е, че най-чесо срещаните символи в поредицата се записват с най-малък брой битожа. . Хъфмановите кодове имат свойството уникалност, което означава, че могат еднозначно да бъдат декодирани независимо от различната си дължина. Декодирането става чрез декодиращо двоично дърво, което се построява в посока от корена към листата.
Използването на този метод води до създаването на нова азбука, която използва този метод. Кодирането е обратимо.

4. Метод на Lempel Ziv encoding
Той е свързан с кодиране с адаптивен речник, всъщност е подход, който се реализира чрез използването на много други методи. Основан е на изследванията на Лемпел и Зив и намира развитие чрез два сходни алгоритъма за речниково кодиране - LZ77 и LZ78. Първият е с плъзгащ прозорец, при който речникът се състои от множеството от фрази с фиксиран размер, открити в "прозорец" към вече прочетения текст. LZ78 подхожда по съвсем различен начин към съставянето на речника. Вместо да използва фрази с фиксирана дължина, към вече прочетения текст, LZ78 увеличава дължината на фразата при всяко следващо нейно срещане в обработвания текст или пакет от данни.

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