малко хюффман - по-просто от т'ва, здраве му кажи
те ти един прост стринг: 'аз обичам мач и боза'

ша са фаним да го кодираме ей с'а:
значи, к'во:

1. трябва да видим колко пъти дадена буквичка се среща в подадения стринг
а - 4, з - 2, ' ' (т'ва е спацията) - 4, о - 2, б - 2, и - 2, ч - 2, м - 2

2. ха сега де ги сортираме според т'ва кой колко пъти се среща (от най-малкио до най-големио)
з - 2
о - 2
б - 2
и - 2
ч - 2
м - 2
' ' - 4
а - 4

имаме 8 елемента - някои се срещат по 2, други по четити пъти! В някакъв друг стринг случаят може да е друг - например в 'на баба му ъ зъзъ' имаме, че н=1, а=3, б=2 и т.н.

3. Сега трябва да изпълним следващото, докато остане само един елемент. Демек, ако не си наясно с бинарните дървета, нищо нема да напраиш.
3.1 та значи хващаме първите 2 елемента 'з' и 'о' и ги събираме под един общ елемент (да го наречем '*1'), и се получава:

'*1' - 4 = 'з' - 2 ; 'о' - 2

'*1' има стойност 4, щото събираме 2 от 'з' и 2 от 'о'

3.2 та сега да пренаредим дръвцето и да го сортираме пак

б - 2
и - 2
ч - 2
м - 2
' ' - 4
а - 4
*1 - 4

3.3 най-отгоре остават 'б' и 'и' - ха да ги съберем и тех в една '*2'!

'*2' - 4 = 'б' - 2 ; 'и' - 2

и пак да пренаредим дърваро:

ч - 2
м - 2
' ' - 4
а - 4
*1 - 4
*2 - 4

ха! вече си имаме две '*'. Това, че и двете са наречени * няма значение, щото тези възли са фиктивни

3.4 ха сега да съберем отново двата най-горни елемента 'ч' и 'м':
'*3' - 4 = 'ч' - 2 ; 'м' - 2

и пак да сортираме:
' ' - 4
а - 4
*1 - 4
*2 - 4
*3 - 4

3.4 ами сега събираме 'а' и ' '
'*4' - 8= ' ' - 4 ; 'а' - 4

и пак сортираме

*1 - 4
*2 - 4
*3 - 4
*4 - 8

3.5 и сега пак събираме двата най-горни елемента *1 и *2

'*5' - 8= *1 - 4 ; *2 - 4

и пак сортираме

*3 - 4
*4 - 8
*5 - 8

и пак събираме двата най-горни *3 и *4:

'*6' - 12 = *3 - 4 = *4 - 8

и пак сортираме (баа-маа, взе да ми писва!!!)

*5 - 8
*6 - 12

и накрая за последно събираме тия що останаа

'*7' - 20 = *5 - 8 ; *6 - 12

ха сега да видим - остана само един елемент, които е върха на бинарно дърво
*7 - 20

а те го на и дървото

--------------------------------*7 - 20
-----------------/---------------------------------------------\
-----------*5 - 8------------------------------------------*6 - 12
---------/-----------\----------------------------------/-------------\
----*1 - 4-----------*2 - 4---------------------*3 - 4-----------*4 - 8
---/--------\-----------/--------\---------------/---------\-----------/-------\
'з' - 2----'о' - 2---'б' - 2----'и' - 2-------'ч' - 2-----'м' - 2----' ' - 4----'а' - 4

ма то много равно се получи... е нищо! Тъ значи *7 ти е корена, а надолу са клоните и листата - такова едно обърнато дръвце.
И как става кодирането шъ запиташ. Ами почваш да ходиш по дръвения от корена към буквата, която те интересува. Когато завиваш наляво пишеш '0', като завиваш надясно пишеш '1'
Та излиза, че кодирано:
а = 111
з = 000
' ' = 110
о = 001
б = 010
и = 011
ч = 100
м = 101
та какво стана: никой от кодовете не се повтаря.
Та за нашето 'аз обичам мач и боза' се получава
111000110001010011100111101110101111100110011010001000111
което имайки в предвид, че един байт=8 бита (ах дали е така?!)
се получава компресия!
некодирано - 20 байта
кодирано - 7 байта

компресия почти едно към три в случая.
Та както колегата по-горе каза, за да разкодираш требе да направиш точно обратното.
Ако на некой му се е дописало, може да напише как точно става тая работа, ама аз мисля, че е логично.
Ако имаш некви въпросчета-тъпросчета можеш да попиташ на

Съдържаниет е скрито
Влезте за да го видите