Наука за компресиране на данни за всички
Това е термин, който е лесно разбираем, но чието действие е трудно обяснимо. Точно тези понятия обичам да обяснявам в този блог.
В компютърните науки компресирането на данни може да бъде формулирано по следния начин: „Трансформиране на поредица от битове в друга поредица от по-малки битове с помощта на алгоритъм, като същевременно се запазва информацията, т.е.
Компресия без загуби
Най-лесният за разбиране алгоритъм за компресиране без загуби е RLE кодиране (Run Length Encoding), което се състои от преброяване на повторенията на символ (или бит).
Пример за RLE кодиране: думата "ouuuuuaauuuuuu" се интерпретира като последователност от "o", 5 "u", 2 "a" и 6 "u", т.е.: "o5u2a6u". Следователно сме компресирали 14 знака в 7 знака (50% степен на компресия). Очевидно е, че този тип кодиране е от значение само ако се повтарят големи низове от символи. Това важи за кодирането на факсове за кодиране на последователността на точки
черно и бяло на лист (CCITT кодиране).
Други техники за компресиране без загуби са компресия на ентропията . Тези алгоритми се основават на статистическо проучване на информацията, която трябва да се компресира, така че да кодират повтарящите се символи в много малко битове. Най-известните ентропийни алгоритми са алгоритъмът на Хъфман и алгоритъма
LZ77.
Алгоритъм на Хъфман
Най-добрият начин да разберете този алгоритъм е да дадете пример. Нека си поставим за цел да компресираме изречението „УЧЕНИТЕ СА ИНТЕЛИГЕНТНИ“.
В класическото представяне на ASCII са необходими 7 бита на буква (2 ^ 7 = 128 символа общо): това изречение от 35 знака ще заема място в паметта от 35 * 7 = 245 бита.
Сега, използвайки кодирането на Huffman, ще проучим броя на появите на всяка буква в текста, която трябва да бъде компресирана, за да разпределим по-малък брой битове към най-използваните букви:
- C, F, Q, U, O, G: 1 поява
- L, ПРОСТРАНСТВО: 3 повторения
- T, N: 4 повторения
- E, S, I: 5 повторения
След това изграждаме дърво, където всеки лист представлява буква, придружена от теглото му (броя на повторенията). След това вземаме 2-те най-ниски тегла, за да ги групираме заедно и получаваме възел с тегло, равно на сумата от 2-те листа и така нататък, докато се получи единичен възел в края.
С нашия пример:
- а) Прегрупираме буквите с тегло "1" и ги добавяме, за да направим възли с тегло "2" (жълто)
- б) Добавяме 2-те букви с тегло "3" към 2 възела с тегло "2", за да направим възли с тегло "5" (зелено)
- в) Добавяме 2-те букви с тежест "4" към възли с тегло "2" и "5", за да направим възли с тегло "6" и "9" (пурпурно).
- г) Добавяме 3-те букви с тежест "5" към възли с тегло "5", "6" и "9", за да направим възли с тегло "10", "11" и "14" (оранжево).
- д) Завършваме дървото, докато получим общ възел с тегло "35" (червен).
- е) Остава да присвоите поредица от битове на всяка буква. За целта избираме да добавим бит "0" за левите клонове и бит "1" за десните клони и след това получаваме следното дърво: