Компресията на данни без загуби движи интернет. Ето как работи тази тези технология

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

В същото време се обръща много малко внимание на компресията без загуби. Защо? Отговорът е прост – техниките за компресиране без загуби вече са изключително ефективни. С тях работи буквално всичко – от формата PNG до програмата PKZip. И всичко това е благодарение на един студент, който искал да пропусне един изпит.

Преди 70 години в Масачузетския технологичен институт (MIT) професор Робърт Фано предлага на студентите си избор: да напишат редовен финален писмен изпит или да подобрят водещия алгоритъм за компресиране на данни. Не е известно дали Фано е казал или не е казал на своите студенти, че именно той е авторът на този алгоритъм и дотогава в продължение на много години е търсил подобрение на неговата работа. Единственото, което ни е известно, е самият факт на това предложение.

Нека си представим едно съобщение, съставено от букви, цифри и препинателни знаци. Очевидният начин за кодиране на подобно съобщение би бил просто да се присвои уникално двоично число на всеки символ. Така например компютърът би могъл да представи символа А като 01000001, а възклицателния знак – като 00100001. Такива кодирания са много лесни за анализиране – всеки 8 бита съответстват на един символ. Но те имат един основен недостатък – те са отвратително неефективни, тъй като един и същ брой битове се използват както за редките, така и за често срещаните символи. За мнозина по-ефективният подход е по-скоро като Морзовата азбука, където често срещаното Е се представя с една точка, а рядко срещаното Q – с поредица от тирета – тире – точка – тире.

Въпреки всичко Морзовата азбука също е доста неефективна. Да, кодирането на някои символи е по-кратко, на други – по-дълго. Но поради факта, че дължината на един символ може да варира, съобщенията могат да бъдат разбрани само ако между символите има малки периоди на мълчание. Всъщност без тези паузи получателят няма да може да направи разлика между – .-. .. – . – „trite“ от – .-. ..- . – „true“.

Фано е успял да реши тази част от проблема. Той е осъзнал, че може да се използват кодове на символи с различна дължина, без да се използват „интервали“ между тях, стига да не се използват едни и същи битове както за пълния символ, така и за началото на друг. Така например, ако символът S се среща много често в дадено съобщение, той може да бъде кодиран като 01, като в този случай нито един друг символен код не трябва да започва с 01. Например кодовете 010, 011 или 0110 не биха били разрешени. В този пример полученото съобщение може да бъде прочетено еднозначно отляво надясно. Чрез присвояване на S на кода 01, на L на 1, на M на 001 и на A на 000 съобщението 0100100011 може да бъде недвусмислено декодирано като думата „small“, въпреки че L е представен с един бит, S с два, а всяка от останалите букви с три.

За да дефинира конкретните кодове, Фано решава да изгради двоични дървета, така че всеки символ да е лист от това дърво. Кодът на символа се определя като път от върха до основата. Ако клонът отива наляво, към кода се добавя 0; ако отива надясно, се добавя 1. Структурата на дървото дава възможност за лесно избягване на „припокриването“ – тъй като всички символи се намират във възлите – листа, т.е. в краищата на разклоненията, като нито един код не може да започне с битове, които съставляват целия друг код.

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

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

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

Сега нека си представим съобщение, в което методът на Фано се проваля. В съобщението „Schoolroom“ буквата О се среща 4 пъти, а S, C, H, L, R и M се срещат по веднъж. Подходът на Фано започва с присвояване на О и някоя друга буква към лявото разклонение, като 5 използвания на букви от това разклонение ще съответстват на 5 използвания на букви от дясното разклонение. Полученото съобщение е с дължина 27 бита.

Точно обратното, Хъфман започва с най-рядко срещащите се символи – например R и M – и ги групира заедно, като по-нататък третира получената двойка като един символ.

След това актуализираният списък с елементи предлага 4 възможности за избор: О, което се среща 4 пъти, двойката RM, чиято честота е 2, и единичните букви S, H, C и L. Хъфман отново избира двата най-малко често срещани елемента, а именно H и L.

Списъкът отново се обновява: O все още има тегло 4, RM и HL имат по 2, а единичните S и C остават. Хъфман продължава да актуализира дървото и списъка, като на всяка стъпка отново групира заедно двата най-редки елемента.

В резултат на това „schoolroom“ е във вид на 11101111110000110110000101, което е с един бит по-малко от подхода на Фано.

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

И всичко това е благодарение на решението на Хъфман да не се яви на изпита.

Забележка от оригиналната статия: В предишната версия на статията се предполагаше, че стандартът за компресия на изображения JPEG е без загуби. Макар че алгоритъмът на Хъфман без загуби е част от процеса на JPEG компресията, като цяло стандартът е със загуби. Ето защо JPEG компресията не присъства в този по-нов материал и ще бъде разгледана в друга статия.