Stránka 1 z 1
Huffmanovo kódování
Napsal: pát 15. lis 2013, 14:27
od 1Pupik1989
Zdravím všechny.
Může mi někdo polopaticky vysvětlit jak zakódovat strom?
Mám konkrétně na mysli
tuto stránku.
Jak přišel na "1101000"? To jako že zapisuji při každém průchodu vlevo 1 a pokud najdu potomka, tak 0?
Už se s tím patlám snad týden. Je mi jasné, že to bude prkotina, ale čím víc nad tím přemýšlím, tím to je horší.
Přiřazování kódu ke znakům mám hotové, to jsem ještě pochopil.
Děkuji za každou radu.
Re: Huffmanovo kódování
Napsal: ned 17. lis 2013, 17:17
od nou
tiez nechapem ako k tomu prisiel. ale nasiel som iny sposob ako ulozit ten strom.
ak mas list tak zapis 1-bit+8 bitov toho znaku. ak je to uzol tak zapis 0 a potom zapis laveho potomka a nasledne praveho. v tebou linkovanom priklade by ten strom bol zapisany takto.
01A001B01D1K1R
prva nula hovori ze koren je uzol. lavy potomok je list s A. ideme dalej. lavy potomok korena je uzol a ze lavy potomok toho uzla je zase uzol. potomok tohto druheho uzla je list s B.
Re: Huffmanovo kódování
Napsal: ned 17. lis 2013, 19:03
od 1Pupik1989
Něco takového jsem našel na
stackoverflow. To se vlastně dá zapisovat při přiřazování znaků z kořene.
Mě spíš zajímalo jak to dokázal stáhnout na 7 bitů.
//edit: Když tak koukám na ten jeho strom, tak mi to asi začíná docházet. Ona má vždy list vlevo a vrchol vpravo. O úroveň níž je to zase naopak. Takže mu nejspíš stačí uložit jen krok o úroveň níž vlevo. Je to tedy jen teorie, ale odpovídá to.
//edit2: Ten výstup jak píšeš vlastně mám.
Kód: Vybrat vše
function recursive(node,bin,level){
if(node.left == null){ //pokud nemá potomky, pak je to list
o[node.name] = bin;
tree += '1'+node.name; //zapíšu 1 + znak
return;
}
tree += '0'; //není list, zapíšu 0
recursive(node.left,bin+'0',level+1);
recursive(node.right,bin+'1',level+1);
};