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 drzewa (dla kodów dwójkowych to 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]