En præfikskode i kodningsteori er en kode med et ord af variabel længde, der har følgende egenskab (opfyldelse af Fano-betingelsen ): hvis koden inkluderer ordet a , så for enhver ikke-tom streng b , gør ordet ab ikke findes i koden. Selvom præfikskoden består af ord af forskellig længde, kan disse ord skrives uden et skilletegn.
For eksempel er koden bestående af ordene 0, 10 og 11 præfiks, og meddelelsen 01001101110 kan opdeles i ord på en unik måde:
0 10 0 11 0 11 10Koden bestående af ordene 0, 10, 11 og 100 er ikke et præfiks, og den samme besked kan fortolkes på flere måder.
0 10 0 11 0 11 10 0 100 11 0 11 10De såkaldte "præfikser" kan opnås ved sekventielt at kassere det sidste tegn i kodekombinationen. For kodekombinationen 11101101 vil præfikserne f.eks. være 11101101, 1110110, 111011, 11101, 1110, 111, 11, 1.
Enten sådan her:
Vi skriver alle kombinationer af koder, uden indledende nuller: 0 //præfiks //en //10 <- kommentere (ekskluder) dem, der er begyndelsen på andre //elleve 100 //præfiks 101 //ukommenterede koder - præfikser for præfikskoden. 110 111 ... //lad det hele være tre-bit kombinationer.Den resulterende kodesekvens (0, 100, 101, 110, 111) svarer til præfikset Huffman-kodesekvens .
Hvis der ikke er mellemrum eller andre tegnsætningstegn mellem kodekombinationerne, så for entydig afkodning af kombinationen 111011101 kan ingen af kodekombinationerne repræsenteres af de anførte muligheder (præfikser). En kode kaldes præfiks, hvis ingen af dens kombinationer er præfiks for en anden kombination af samme kode. Den del af kodekombinationen, der fuldender præfikset til selve kombinationen, kaldes suffikset. Præfikskoder kan repræsenteres visuelt ved hjælp af kodetræer. Hvis ingen node i kodetræet er en node af den givne kode, så har den egenskaberne som et præfiks. Træknuder, der ikke forbinder sig med andre, kaldes bladknuder. De kombinationer, der matcher dem, er præfikskodekombinationer.
Enhver ordkode med fast længde er naturligvis en præfikskode. Lad os overveje nogle ikke-trivielle eksempler.
Morsekode er ikke præfiks. Ud over en prik og en bindestreg indeholder den også et skilletegn - en pause i længden af en bindestreg .