C program Kompresia Dekompresia – C / C++ – Fórum – Programujte.com

Zdravim, 

vedel by mi niekto pomoct s programom ? Ja sa s ním už trápim hrozne dlho a neviem ho urobiť.

Naprogramuj nástroj na kompresiu a dekompresiu. Na kompresiu použite jeden alebo viac kompresných algoritmov: Huffmanovo kódovanie, LZ77, LZ78, Run Length kódovanie alebo iný.

Meno vstupného a výstupného súboru načítajte ako argument príkazového riadka. V zadaní by mali byť implementované tieto dve funkcie:

/**
* Skomprimuje súbor in a zapíše do súboru out.

* @arg in smerník na otvorený vstupný súbor (na čítanie)

* @arg out smerník na otvorený výstupný súbor (na zápis)
* @return počet bajtov skomprimovaného súboru
/**

int compress(FILE* in, FILE* out);

/**

* Dekomprimuje súbor in a zapíše do súboru out.
* @arg in smerník na otvorený vstupný súbor (na čítanie)

* @arg out smerník na otvorený výstupný súbor (na zápis)

* @return počet bajtov dekomprimovaného súboru

void decompress(FILE* in, FILE* out);

 

Nemůžeš dostat takový úkol a neumět napsat ani řádek. Takže s čím přesně potřebuješ poradit?

Zkus RLE, to je jen hodnota a počet opakování. To musíš zvládnout.

#1 Miroslav
LZ77 je na githubu

https://gist.github.com/fogus/5401265

je docela dlouhej ..

RLE je taky na githubu:

https://github.com/MichaelDipperstein/rle

Hufmanovo kodovani funguje takhle, treba. Nemusis tam zrovna delat generator stromu.

1. Zjistis pocet vyskytu znaku (slozitejsi algoritmy mapuji dvojice, trojice znaku nebo cela slova)
2. Kazdy znak nahradis binarnim kodem. Napr

00 - top 1
01 - top 2
1xxxxxxxx - vsechny ostatni, xxx jse puvodni kod

Nebo muj oblibeny je binarni koder, kde si vygenerujes binarni nahradu za dvojici bitu, pro celou sadu 256 znaku, ktere pak nahradis

00 - 1
01 - 01
10 - 001
11 - 000

Udelas vsechny kombinace pro 8 bitovy znak a ulozis si tabulky bitu,
takze dostanes pole, treba
ord(char) = 0 = 00000000 => 1111
ord(char) = 1 = 00000001 => 11101
ord(char) = 2 = 00000010 => 111001
...

3. Nezapomen zapsat take poradi cetnosti znaku, abys to mohl pak dekodovat.
---------------
RLE mas jeste jednodussi. Sledujes opakovani znaku
AABDAAAREEE -> A2-krat B1-krat D1-krat A3 R1 E3
AABDDDDAAAREEE (14 znaku) -> A2B1D4A3R1E3 (12 znaku)

----------------
LZ (ZIP) je slovnikovy algoritmus. Ten teda generuje slovnik podle vstupu.

Veme 2 znaky ze vstupu.
Kdyz je nenajde ve slovniku, tak je prida do slovniku. ZAPISE na vystup tyto 2 znaky.
Kdyz je najde ve slovniku, ulozi si index ze slovniku a prida dalsi znak ze vstupu.
Tuto novou trojici se opet pokusi najit ve slovniku.
Pokud nenajde. ZAPISE kod(indexu) + posledni znak ze vstupu, ktery pridaval.
Pokud najde, prepise kod indexu novym a dal pokracuje...

Mozna to zni slozite. Ale muzes udelat podobny, ne uplne ZIP.
Predstav si, ze vstupni data je plain-text Harry potter.
1. Tvuj program sesbira vsechna slova. Vytvori silovnik. Pocet slov v nem bude kolem 20.000 (v anglicke verzi, ceska verze bude mit i 40.000 slov).
2. Vsechny znaky, ktere nejsou slova zapises do tabulky ostatnich znaku (mezery, tecky, carky, uvozovky).
Kazde slovo nahradis bitem 0 + indexem ve slovniku slov (poradim).
Kazdy jiny znak nahradis bitem 1 + indexem ve slovniku znaku.
... Ono to krasne funguje, protoze prumerna delka slova je 6 znaku. Tvuj slovnik ma 20.000 znaku, na to ti staci 2 bajty (max 32.000). Takze nahrazujes pro slova 6 znaku za 2 (+1 bit, lze zanedbat pro vypocet). Pro ostatni znaky je to 1 bit + 5 bitu (rekneme 1 bajt, cili, zadny bonus). Celkovou kompresi lze tedy odhadnou tak, ze text je slovo+znak. znak je casto mezera. To se cele opakuje. Cili, mas 6+1 znaku na vstupu a 2+1 na vystupu, pomer 3/7 = 45%. LZ to umi lepe, na 35%. A s ruznymi vylepsenimi se da dostat na 25% i 15%. ale, to je text, ten se komprimuje krasne.

Jo, ten huff. kod muzes udelat velmi jednoduse. Proste urcis nejcastejsi znaky, treba top 16. Ty nahradis bit 0 + index (16 znaku, index ma 4 bity). Ostatni znaky ulozis jako bit 1 + puvodni kod. Velmi snadne, asi jako RLE.

Nebo, muzes udelat slovnik slov, pro e-book, jako jsem popisoval pro LZ. To je v podstate take huffman, kdyz si udelas seznam slov a seznam jinych znaku a kazde nahradis jinym binarnim kodem.