Компресия на битове без загуби

Компютрите представят всички данни двоично, така че всички видове файлове, текстови, изображения, видео и т.н. в крайна сметка са последователности от битове. Независимо дали битовете представляват документ или GIF, компютрите могат да използват техника за компресиране на битове, наречена Кодиране на Хъфман.

Нека видим как работи с прост текстов пример. Този примерен език използва само 4 различни символа, но въпреки това е изключително важен за нас – това е езикът, използван за представяне на ДНК и се състои от последователности от 4 символа – A, C, G и T.

Например 4,6-те милиона символа, които представят ДНК поредицата на Ешерихиа коли, започват така:

Тъй като трябва да представим 4 символа, обикновено компютър би представил всеки символ с помощта на 2 бита, например:

Тринадесетте символа по-горе биха били написани с помощта на 26 бита, както следва (забележи, че не са ни нужни интервали между кодовете за всеки бит).

Но можем да се справим и по-добре. В краткия примерен текст по-горе буквата "t" е по-често срещана от другите букви ("t" се среща 7 пъти, "c" – 3 пъти, "a" – два пъти и "g" – само веднъж). Ако дадем по-кратък код на "t", тогава ще използваме по-малко място в 54% от времето (7 от 13 символа). Например бихме могли да използваме следните кодове:

Тогава нашите 13 символа биха се кодирали така:

Това са само 22 бита – с 4 по-малко от оригиналното ни кодиране. Това може да не изглежда като много, но представи си ако използваме подобна оптимизация върху всички 4,6 милиона символа на ДНК!

Сигурно си блъскаш главата над новите двоични кодове, които използваме, с всички различни дължини. Възможно ли е да ги декодираме надеждно? Да, с подходящия набор кодове.

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

Много файлови формати използват някакъв вариант на кодирането на Хъфман, за да намалят размера на файлове си. Факс машините използват Кодиране на Хъфман след като са приложили Кодиране по дължина (RLE) върху черно-белите последователности. PNG изображенията компресират с помощта на LZ77 – алторитъм, подобен на текстовата компресия, която научихме, комбиниран с Кодиране на Хъфман върху резултата от нея.

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Имаш ли въпроси по темата? Ще се радваме да ти отговорим, просто задай въпросите си по-долу!