Hej igen.
Tak for dit indlæg.
Jeg har lavet et binært træ for bogstaverne A-Z + mellemrum, se det her:
http://d00d.dk/Huffman.jpg. Jeg har også sat en state-machine op som du
foreslår, men det jeg har svært ved at forstå er hvordan man kan
bevise(eller argumentere for), at ingen kode er prefix til en anden kode.
Nogen der kan hjælpe?
--
Hilsen Anders.
"Jesper Louis Andersen" <jlouis@miracle.mongers.org> wrote in message
news:3v8qd2-con.ln1@miracle.mongers.org...
> Anders <gregersenNOSPAM@adslhome.dk> wrote:
>
> > Jeg har netop skrevet et program der kan komprimere filer ved hj?lp af
> > algoritmen "Huffman-kodning". Det smarte ved denne kode-type, udover at
den
> > komprimerer godt, er at den er prefix-l?s, hvilket betyder at man ikke
> > beh?ver fort?lle dekomprimeringsalgoritmen hvor mange bits der skal
l?ses,
> > det kan den selv finde ud af. Mit problem er dog at jeg ikke kan forst?
> > hvorfor den er prefix l?s, s? er der ikke et af jer kloge hoveder der
kan
> > give mig et logisk argument eller bevis p? dette?
>
> Hvert bogstav i din kode er et blad i et binaert trae. Er koden
> for 'g' eksempeltvist 110, saa findes bladet ved fra roden af
> det binaere trae at gaa ad 1 grenen, 1 grenen og 0 grenen.
> Hvis hver gren i traaet annoteres med 1 hhv. 0. e er
> maaske 0, sa:
>
> r
> 0/ \1
> (e) \
> 0/\1
> x \
> \
> 0/ \1
> / y
> (g)
>
> Hvor x og y er nogle andre undertraaer.
>
> Hvis du nu saetter en state-machine op til at starte i roden af
> dette trae og saa foelge de enkelte bits vej til et blad, saa ved
> du at naar du naar et blad (hvilket der kun er 1 maade at goere paa),
> saa er det det tegn du skal skrive og resette din state-machine til
> roden igen.
>
> Bare saet dig ned og tegn det. Saa bliver du pludselig glad ;)
>
> --
> jlouis