Kod prefiksowy – Wikipedia, wolna encyklopedia
Ten artykuł od 2021-02 wymaga zweryfikowania podanych informacji. |
Kod prefiksowy lub przedrostkowy (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”.