| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Sk@łR
Forumaš(ica)
Pridružen/a: 11. 02. 2004. (19:55:24)
Postovi: (12)16
|
 Postano: 14:16 sri, 25. 2. 2004 Naslov: Huffman |
    |
|
|
Dakle, mi imamo neku abecedu od n znakova, kodiramo je s bitovima pomocu stabla, ali gledamo koliko se puta u poruci pojavljuje neki znak i tako najucestalije kodiramo najjednostavnije itd.
Sada ja nekome posaljem npr. :
100110101100111001101 (bezveze sam napiso), i on treba skuziti o cemu se radi? Dakle, kako on to dekodira?
Moze li se to malo pojasniti?
Dakle, mi imamo neku abecedu od n znakova, kodiramo je s bitovima pomocu stabla, ali gledamo koliko se puta u poruci pojavljuje neki znak i tako najucestalije kodiramo najjednostavnije itd.
Sada ja nekome posaljem npr. :
100110101100111001101 (bezveze sam napiso), i on treba skuziti o cemu se radi? Dakle, kako on to dekodira?
Moze li se to malo pojasniti?
|
|
| [Vrh] |
|
Pero Peric
Gost
|
| Postano: 14:48 sri, 25. 2. 2004 Naslov: |
|
|
|
Ako ne znas abecedu, nikako. Ako ti je najfrekventnije A, onda je ideja da se a zapise najkracim zapisom, slijedeci znak po frekvenciji nesto duzim itd. Na taj nacin dobijes ustedu ako imas frekvencijski debalans :-) Uglavnom, ideja je da ne postoji mogucnost dvostruke interpretacije. Ako si A ukodirao nulom i iskoristio 1 bit za njega, svi ostali kodovi moraju pocinjati jedinicom (jer ako bi pocinjali nulom nisi siguran jel to a ili neki duzi znak). Dakle recimo onda je 10 B, 110 C a 111 D. Binarna stabla ti sluze kod dekodiranja, usporedis s korijenom i vidis, ako je nula ides lijevo gdje ti cuci a i stvar rijesena jer A nema djece. Ako je jedinica ides na nize dijete, opet usporedjujes i ides lijevo ili desno. Ako je nula, dosao si u B, b nema djece, dekodirao si...
Lose objasnjavam, citaj na netu :-)
Ako ne znas abecedu, nikako. Ako ti je najfrekventnije A, onda je ideja da se a zapise najkracim zapisom, slijedeci znak po frekvenciji nesto duzim itd. Na taj nacin dobijes ustedu ako imas frekvencijski debalans  Uglavnom, ideja je da ne postoji mogucnost dvostruke interpretacije. Ako si A ukodirao nulom i iskoristio 1 bit za njega, svi ostali kodovi moraju pocinjati jedinicom (jer ako bi pocinjali nulom nisi siguran jel to a ili neki duzi znak). Dakle recimo onda je 10 B, 110 C a 111 D. Binarna stabla ti sluze kod dekodiranja, usporedis s korijenom i vidis, ako je nula ides lijevo gdje ti cuci a i stvar rijesena jer A nema djece. Ako je jedinica ides na nize dijete, opet usporedjujes i ides lijevo ili desno. Ako je nula, dosao si u B, b nema djece, dekodirao si...
Lose objasnjavam, citaj na netu
|
|
| [Vrh] |
|
veky
Forumaš(ica)
Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Lokacija: negdje daleko...
|
| Postano: 14:50 sri, 25. 2. 2004 Naslov: Re: Huffman |
|
|
|
[quote="Sk@łR"]Dakle, mi imamo neku abecedu od n znakova, kodiramo je s bitovima pomocu stabla, ali gledamo koliko se puta u poruci pojavljuje neki znak i tako najucestalije kodiramo najjednostavnije itd.
Sada ja nekome posaljem npr. :
100110101100111001101 (bezveze sam napiso), i on treba skuziti o cemu se radi? Dakle, kako on to dekodira?
Moze li se to malo pojasniti?[/quote]
Moraš mu ili poslati tablicu (stablo) kodiranja, ili zapravo samo listu frekvencijâ pojedinih slovâ (iz toga može jednoznačno rekonstruirati stablo kodiranja, uz dogovor da 0 odgovara stringu koji je leksikografski prije, a 1 onom koji je poslije). Treća varijanta je da jednostavno zna jezik kojim je poruka pisana - za većinu svjetskih jezikâ postoje standardne tablice frekvencijâ, koje se onda mogu upotrijebiti i na jednom i na drugom kraju za izgradnju stabla. Npr. za engleski:
http://www.central.edu/homepages/LintonT/classes/spring01/cryptography/letterfreq.html .
HTH,
| Sk@łR (napisa): | Dakle, mi imamo neku abecedu od n znakova, kodiramo je s bitovima pomocu stabla, ali gledamo koliko se puta u poruci pojavljuje neki znak i tako najucestalije kodiramo najjednostavnije itd.
Sada ja nekome posaljem npr. :
100110101100111001101 (bezveze sam napiso), i on treba skuziti o cemu se radi? Dakle, kako on to dekodira?
Moze li se to malo pojasniti? |
Moraš mu ili poslati tablicu (stablo) kodiranja, ili zapravo samo listu frekvencijâ pojedinih slovâ (iz toga može jednoznačno rekonstruirati stablo kodiranja, uz dogovor da 0 odgovara stringu koji je leksikografski prije, a 1 onom koji je poslije). Treća varijanta je da jednostavno zna jezik kojim je poruka pisana - za većinu svjetskih jezikâ postoje standardne tablice frekvencijâ, koje se onda mogu upotrijebiti i na jednom i na drugom kraju za izgradnju stabla. Npr. za engleski:
http://www.central.edu/homepages/LintonT/classes/spring01/cryptography/letterfreq.html .
HTH,
|
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
|
| [Vrh] |
|
|
