Kod prefiksowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Kod prefiksowy lub przedrostkowy, także bezprefiksowy (ang. prefix code) – kod, w którym żadne ze słów kodowych nie jest przedrostkiem innego słowa; taki kod jest jednoznacznie dekodowalny. Dodatkowo każdy kod prefiksowy można reprezentować w formie drzew (dla kodów dwójkowych drzewo binarne).

Dzięki tej cesze kody są jednoznacznie identyfikowane, nie ma potrzeby wstawiania dodatkowych informacji np. o tym, gdzie kończy się słowo kodowe (jest to jednoznaczne) albo jaką ma długość (długość każdego słowa kodowego jest znana z góry). Stosując kody prefiksowe, można uzyskać maksymalny stopień upakowania danych w różnych metodach kompresji.

Dla przykładu weźmy kod niebędący prefiksowym: literze 'a' odpowiada bit 0, literze 'b' odpowiada bit 1, zaś literze 'c' dwa bity 01 – kod litery 'a' jest prefiksem kodu litery 'c'. Przy takim przyporządkowaniu nie można jednoznacznie stwierdzić, co oznacza np. komunikat 0110 – może to być zarówno 'cba', jak i 'abba'.

Zmieniając kod na prefiksowy: 'a' – 0, 'b' – 10, 'c' – 11, ten sam komunikat ma jednoznaczną interpretację, tj. 'aca'.

Zobacz też[edytuj | edytuj kod]