Shannon-fanovo kodovani – Python – Fórum – Programujte.com

Ahoj, chtěla bych se zeptat, zda by mi někdo dokázal pomoci, mám program, který bere na vstupu při kompresi soubor a zakoduje ho do binárního souboru a naopak při dekompresi binární soubor převede do původního. Mám akorát problém, že při využití Shannon fanova kodování pokud rozdělím pole na dvě poloviny podle součtu četností, aby byly přibližně stejné, tak při dekodování (konkrétné u jpg souboru, co jsem zkoušla) mi to háže chybu a nevím si rady, pokud pole rozdělím na dvě poloviny, tak to funguje v pohodě.

Mohl by mi s tím někdo pomoci prosím?

Bez kódu tu chybu nenajdeme.

#2 gna
 Tady je uložený kód: https://uloz.to/!XKMMzAJ6I1XZ/shannon-py

Když opravím to chaotické odsazování, tak mi to funguje.

A máš to zbytečně šíleně složité.

#2 gna
A šlo by to nějak zjednodušit případně tady dát tu funkční verzi protože si vážně nevím rady :/ prosím

https://pastebin.com/9yvuUaZq

#6 gna
Při tom dekódování mi to pořád háže chybu (u souboru jpg konkrétně, zakoduje normálně a zpět to vyhodí tohle):

Traceback (most recent call last):

File "shannon.py", line 143, in <module>

for b in range(numBytes):

MemoryError

Tak ukaž i ten soubor.

Dej si tam výpis té hodnoty numBytes. Chybu tam nevidím (a nechápu co tam všude kutíš s tím +-1), ale možná to načetlo nějaké hausnumero.

A místo range tam dej xrange.

Připojen obrázek.

Ten výpis je podle mě v pohodě právě, ten jsem vypisovala....

Plus s xrange to něco začalo dělat ale zase to něco vyhodilo a neúplný soubor byl o hodně větší jak původní a musí být stejně velký

Mně to ukazuje numBytes 1640623802. Jsou tam kódy delší než 8 bitů, takže se jejich délka nevejde do těch očekávaných 3 bitů a všechno se to posune.

A co s tím můžu udělat? Nebo spíš nerozumím tomu, proč když tto pole rozdělím fakt na poloviny tak to normálně funguje a když jej rozdělím takto tak ne?

Protože když to dělíš podle četnosti, tak se ti to svažuje doprava, častější hodnoty vlevo mají kratší kódy a ty méně časté zase delší. To je přece to o co jde. 

     *
    / \
   /   \
  *     *
 / \   / \
00 01 10 11


  *
 / \
0   *
   / \
  10  *
     / \
   110 111

Můžeš prostě tu délku kódů ukládat na víc bitů. (Teda mimo to, že je vůbec není potřeba ukládat.)

#14 gna
Takže tam, kde mám 3 jako pro 3bity hodím větší číslo? Třeba 6 nebo jak?

Ano, přesně tak.

#16 gna
Super, funguje to děkuji moc a ještě bych se chtěla zeptat. Je normální, že velikost toho zakodovaného souboru je větší než velikost původního? Jsou tam i věci pro to dekodování, ale dalo by se s tím něco udělat, aby ten soubor byl menší?

Je to vidět na tom stromě. Těch hodnot s kratkým kódem musí být výrazně víc než těch s dlouhým, aby výsledná velikost byla menší.

U JPG je normální, že jednoduchým překódováním se nezmenší.

Aha. Ty nechapes zaklady toho kodovani.

Mas text, treba
DAAABBAC

cetnosti | puvodni binarni kod
A = 4 | 00
B = 2 | 01
C = 1 | 10
D = 1 | 11

huffmanuv kod podle cetnosti
A = 4 | 0
B = 2 | 10
C = 1 | 110
D = 1 | 111

Cili DAAABBAC
pred 11 00 00 00 01 01 00 10 = 16 bitu
po 111 0 0 0 10 10 0 110 = 14 bitu

Stejny huff kod pro jiny soubor, string DCBA
pred 11 10 01 00 = 8 bitu
po 111 110 10 0 = 9 bitu

Cili ano, huff. kodovani muze vytvorit vetsi vystup. Min-max se da spocitat ze stromu.
S-F je jen metoda lepsiho rozdeleni kodu huff. stromu. Ale porad muze nastat situace, kdy je vystup vetsi.

Musis mit spravny soubor. Jako je treba komprimovany obrazek, zip, rar, a pod. Zkus si ten obrazek prevest na nekomprimovany bmp. Huff by mohlo dat odhadem 60%. Lze upravit na 45%, rozdil sousednich barev a prevod na barevny model.
Zip, rar ten jpeg dokaze komprimovat na 85-95%. Takze samotne huffmanovo kodovani by nemelo byt lepsi.
Jpeg kodovani take pouziva huffmana na vystupu. Ale pouziva obvykle preddefinovanou tabulku.

Pri vytvareni stromu, prideleni pravdepodobnosti delce binarnimu kodu provadis jakesi zaokrouhlovani. Urcite skupine opakovani priradis treba 9 a vice bitu. A pokud je pocet vsech takovych znaku vetsi nez 50% (odhadem, to cislo je da vypocitat pro kazdy strom, soubor) , tak muze nastat situace, ze vysledek bude vetsi.

AABBCCD - puvodni pocet bitu 7*2 = 14 bitu
0 - 10 - 110 - 111 - 3 znaky ze 7 (43%) maji vetsi bin. kod nez puvodni 2 bity
2 + 4 + 6 + 3 = 15 bitu