Основно съдържание
Компютрите и интернет
Курс: Компютрите и интернет > Раздел 1
Урок 7: Компресия на данниКомпресия на битове без загуби
Компютрите представят всички данни двоично, така че всички видове файлове, текстови, изображения, видео и т.н. в крайна сметка са последователности от битове. Независимо дали битовете представляват документ или GIF, компютрите могат да използват техника за компресиране на битове, наречена Кодиране на Хъфман.
Алгоритъм за кодиране на Хъфман
Нека видим как работи с прост текстов пример. Този примерен език използва само 4 различни символа, но въпреки това е изключително важен за нас – това е езикът, използван за представяне на ДНК и се състои от последователности от 4 символа – A, C, G и T.
Например 4,6-те милиона символа, които представят ДНК поредицата на Ешерихиа коли, започват така:
agcttttcattct
Тъй като трябва да представим 4 символа, обикновено компютър би представил всеки символ с помощта на 2 бита, например:
символ | двоичен код |
---|---|
a | 00 |
c | 01 |
g | 10 |
t | 11 |
Тринадесетте символа по-горе биха били написани с помощта на 26 бита, както следва (забележи, че не са ни нужни интервали между кодовете за всеки бит).
100 111 111 111 000 000 000 000
Но можем да се справим и по-добре. В краткия примерен текст по-горе буквата "t" е по-често срещана от другите букви ("t" се среща 7 пъти, "c" – 3 пъти, "a" – два пъти и "g" – само веднъж). Ако дадем по-кратък код на "t", тогава ще използваме по-малко място в 54% от времето (7 от 13 символа). Например бихме могли да използваме следните кодове:
символ | двоичен код |
---|---|
a | 010 |
c | 00 |
g | 011 |
t | 1 |
Тогава нашите 13 символа биха се кодирали така:
100 110 011 110 000 000 000
Това са само 22 бита – с 4 по-малко от оригиналното ни кодиране. Това може да не изглежда като много, но представи си ако използваме подобна оптимизация върху всички 4,6 милиона символа на ДНК!
Декодиране на Хъфман
Сигурно си блъскаш главата над новите двоични кодове, които използваме, с всички различни дължини. Възможно ли е да ги декодираме надеждно? Да, с подходящия набор кодове.
В това е красотата на кодирането на Хъфман – алгоритъмът ни дава начин да стигнем до набор от двоични кодве за дадена поредица, който да ни подсигури, че данните могат да се възстановят недвусмислено и надеждно.
Приложения на кодирането на Хъфман
Много файлови формати използват някакъв вариант на кодирането на Хъфман, за да намалят размера на файлове си. Факс машините използват Кодиране на Хъфман след като са приложили Кодиране по дължина (RLE) върху черно-белите последователности. PNG изображенията компресират с помощта на LZ77 – алторитъм, подобен на текстовата компресия, която научихме, комбиниран с Кодиране на Хъфман върху резултата от нея.
🙋🏽🙋🏻♀️🙋🏿♂️Имаш ли въпроси по темата? Ще се радваме да ти отговорим, просто задай въпросите си по-долу!
Искаш ли да се присъединиш към разговора?
Все още няма публикации.