Над 9 милиарда гигабайта информация всеки ден се прехвърлят в

Над 9 милиарда гигабайта информация всеки ден се трансферират в интернет, което постанова непрекъснато търсене на нови способи за компресиране на данните. Най-ефективните решения употребяват подходи, при които се реализира по-голяма компактност посредством „ загуба “ на информация в процеса на компресиране. Гугъл да вземем за пример неотдавна вкара версия на компресия със загуби, при която изпращащият компютър отхвърля някои от детайлите на изображението, а изкуственият разсъдък на приемащата страна ги реконструира. Дори 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 компресията не участва в този по-нов материал и ще бъде прегледана в друга публикация.