Kompresní program – Java – Fórum – Programujte.com

Potreboval bych poradit s nejakym navrhem jak to naimplementovat? 

Vim že H. kodovani vyuziva prefixoveho opt. kodovani.na wikip. jsem nasel toto:

Minimální prefixový kód: Minimálním prefixovým kódem potom rozumíme takový kód, který obsahuje minimální možný počet znaků pro kódování. Délka kódu pro jednotlivé znaky se určuje z pravděpodobnosti jejich výskytu v kódovaném textu.

Jak urcim pravd. jejich vyskytu?

1. Ulozim si do souboru 1 21 22 231 232 coz je prefixovy kod.Symbol kod. abecedy neobsahuje predponu napr. pridanim 225 by uz to nebyl prefixovy kod, pokud jsme to pochopil spravne,nebo budu ukladat jakykoli znaky a z nich vytvorim pref. kod?Jeslti ano mohl by mi nekdo poradit jak na to?

#1 jack

2. Jak mysli jeden znak povazujte jako 1byte v souboru?

Moc dekuju predem za odpovedi 

pokud me pamet nesali, tak huffmanovo kodovani znamena projet si cely soubor, spocitat ktere znaky jsou nejcetnejsi... uplne nejcastejsi znak ma pak hodnotu binarne dejme tomu 0b1 druhej nejcastejsi se vejde na 2b (zacinajici 0) ... (a samozrejme nejmene casty pak muze obsadit i daleko delsi pocet bitu nez 8b.. )

#2 jack

Ahoj,

myslí se to tak, že budeš číst ze souboru po jednom bytu.

Budeš mít tabulku tak velikou, jako je abeceda vstupního souboru(textu).

Tzn na 1bytu může být 2^8 možností = tabulka bude mít max 256 řádků(kdybys věděl že v textu bude čeština, můžeš si spočítat počet písmen a číslic české abecedy). Z počátku inicializovaná na nuly

Např.: přečteš byte, ten bude mít hodnotu (0x30) a v tabulce na indexu 0x30 inkrementuješ hodnotu.

Potom co pročteš celej soubor projedeš tvou tabulku, zjistíš nejčastější výskyt a koduješ písmena

Následně bych soubor projel ještě jednou s tím že bych už vytvořil i nějakej výstupní a postupně každý písmeno vzal, kouknul jakej má kód a zapsal ho do výstupu.

Složitost polynomiální, možná někdo vymyslí i něco rychlejšího :)

+ jak píše KIIV, ten 1byte nemá s max délkou výsledného kodu nic společného

#4 TheOndrap
Uz sem si pro takovy text: AAAABBBBBBBCCCCCCCCCCCCDDDDDDDDDEEEEEEEEEE ,ktery prectu ze souboru napsal tabulku:

D 00
E 01
A 100
B 101
C 11

Vytvorim retezec "000110010111"

Smazu predchozi text ze souboru a ulozim do nej komprimovany text + tabulku.

Muze to tak probuhat?

Jakym zpusobem to potom dekomprimuji...??

To máš zakódovaný nějak krátký, ne?

#6 TheOndrap

Zde to kodovani maji velikostne stejny: http://www.google.cz/url?sa=t&rct=j&q=huffmanovo_k%C3%B3dov%C3%A1n%C3%AD.doc&source=web&cd=7&ved=0CFYQFjAG&url=http%3A%2F%2Feamos.pf.jcu.cz%2Famos%2Fkat_inf%2Fexterni%2Fkat_inf_97511%2Ffiles%2Ftema_komprese_a_uchovani_dat%2Fhuffmanovo_kodovani.doc&ei=80zLUIDtCIfntQa81ICgAw&usg=AFQjCNEdrmvwJ_xAkvP3mfAHa49VkqqlTw

1. http://www.stringology.org/…ndex_cs.html
2. předpoklad je že víš jak funguje huffmanův kod a máš všechno správně (což vypadá OK), ověř podle linku

Potom prostě načteš 1byte ze vstupu, koukneš do tabulky a přidáš do výstupu. Sám vidíš že původní tvůj vstup byl asi 40bytů a ten zakodováný je asi 20bytů

Dekodování?

Načetl bych celý zakodovaný text a četl ho po bitech. Vzal první bit a kouknul, jestli pro něj existuje kód, když ne tak bych vzal 2 bity a takhle musíš ke kódu adekvátní písmeno