Shannon-fanovo kodovani – Python – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 

Kris
~ Anonymní uživatel
12 příspěvků
10. 5. 2018   #1
-
0
-

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?

Nahlásit jako SPAM
IP: 213.155.254.–
gna
~ Anonymní uživatel
1891 příspěvků
11. 5. 2018   #2
-
0
-

Bez kódu tu chybu nenajdeme.

Nahlásit jako SPAM
IP: 213.211.51.–
Kris
~ Anonymní uživatel
12 příspěvků
11. 5. 2018   #3
-
0
-

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

Nahlásit jako SPAM
IP: 213.155.254.–
gna
~ Anonymní uživatel
1891 příspěvků
11. 5. 2018   #4
-
0
-

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

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

Nahlásit jako SPAM
IP: 213.211.51.–
Kris
~ Anonymní uživatel
12 příspěvků
11. 5. 2018   #5
-
0
-

#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

Nahlásit jako SPAM
IP: 213.155.254.–
gna
~ Anonymní uživatel
1891 příspěvků
Nahlásit jako SPAM
IP: 213.211.51.–
Kris
~ Anonymní uživatel
12 příspěvků
11. 5. 2018   #7
-
0
-

#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

Nahlásit jako SPAM
IP: 213.155.254.–
gna
~ Anonymní uživatel
1891 příspěvků
11. 5. 2018   #8
-
0
-

Tak ukaž i ten soubor.

Nahlásit jako SPAM
IP: 213.211.51.–
gna
~ Anonymní uživatel
1891 příspěvků
11. 5. 2018   #9
-
0
-

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.

Nahlásit jako SPAM
IP: 213.211.51.–
Kris
~ Anonymní uživatel
12 příspěvků
11. 5. 2018   #10
-
0
-
Nahlásit jako SPAM
IP: 213.155.254.–
Kris
~ Anonymní uživatel
12 příspěvků
11. 5. 2018   #11
-
0
-

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ý

Nahlásit jako SPAM
IP: 213.155.254.–
gna
~ Anonymní uživatel
1891 příspěvků
11. 5. 2018   #12
-
0
-

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.

Nahlásit jako SPAM
IP: 213.211.51.–
Kris
~ Anonymní uživatel
12 příspěvků
11. 5. 2018   #13
-
0
-

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?

Nahlásit jako SPAM
IP: 213.155.254.–
gna
~ Anonymní uživatel
1891 příspěvků
11. 5. 2018   #14
-
0
-

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.)

Nahlásit jako SPAM
IP: 213.211.51.–
Kris
~ Anonymní uživatel
12 příspěvků
11. 5. 2018   #15
-
0
-

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

Nahlásit jako SPAM
IP: 213.155.254.–
gna
~ Anonymní uživatel
1891 příspěvků
11. 5. 2018   #16
-
0
-

Ano, přesně tak.

Nahlásit jako SPAM
IP: 213.211.51.–
Kris
~ Anonymní uživatel
12 příspěvků
11. 5. 2018   #17
-
0
-

#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ší?

Nahlásit jako SPAM
IP: 213.155.254.–
gna
~ Anonymní uživatel
1891 příspěvků
12. 5. 2018   #18
-
0
-

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ší.

Nahlásit jako SPAM
IP: 213.211.51.–
peter
~ Anonymní uživatel
4014 příspěvků
14. 5. 2018   #19
-
0
-

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.

Nahlásit jako SPAM
IP: 2001:718:2601:258:e502:9b...–
peter
~ Anonymní uživatel
4014 příspěvků
14. 5. 2018   #20
-
0
-

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

Nahlásit jako SPAM
IP: 2001:718:2601:258:e502:9b...–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 3 hosté

Podobná vlákna

Kódování — založil wise

Kódování — založil viky

Kódování — založil wise

Kódování — založil Alf

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý