Prefixkod

En prefixkod i kodningsteori  är en kod med ett ord av variabel längd som har följande egenskap (uppfyllelse av Fano-villkoret ): om koden innehåller ordet a , så för en icke-tom sträng b , gör inte ordet ab finns i koden. Även om prefixkoden består av ord av olika längd kan dessa ord skrivas utan skiljetecken.

Till exempel är koden som består av orden 0, 10 och 11 prefix, och meddelandet 01001101110 kan delas upp i ord på ett unikt sätt:

0 10 0 11 0 11 10

Koden som består av orden 0, 10, 11 och 100 är inte ett prefix, och samma meddelande kan tolkas på flera sätt.

0 10 0 11 0 11 10 0 100 11 0 11 10

Definition

De så kallade "prefixen" kan erhållas genom att sekventiellt kassera det sista tecknet i kodordet. Till exempel, för kodkombinationen 11101101, kommer prefixen att vara 11101101, 1110110, 111011, 11101, 1110, 111, 11, 1.

Antingen så här:

Vi skriver alla kombinationer av koder, utan inledande nollor: 0 //prefix //ett //10 <- kommentera (uteslut) de som är början på andra //elva 100 //prefix 101 //okommenterade koder - prefix för prefixkoden. 110 111 ... //låt det vara alla tre-bitars kombinationer.

Den resulterande kodsekvensen (0, 100, 101, 110, 111) motsvarar prefixet Huffman-kodsekvens .

Om det inte finns några mellanslag eller andra skiljetecken mellan kodkombinationerna, då för entydig avkodning av kombinationen 111011101 kan ingen av kodkombinationerna representeras av de listade alternativen (prefix). En kod kallas prefix om ingen av dess kombinationer är ett prefix för en annan kombination av samma kod. Den del av kodkombinationen som kompletterar prefixet till själva kombinationen kallas suffixet. Prefixkoder kan representeras visuellt med hjälp av kodträd. Om ingen nod i kodträdet är en nod av den givna koden, har den egenskaperna hos ett prefix. Trädnoder som inte ansluter till andra kallas lövnoder. Kombinationerna som matchar dem är prefixkodkombinationer.

Exempel

Varje ordkod med fast längd är uppenbarligen en prefixkod. Låt oss överväga några icke-triviala exempel.

• Telefonnummer i fasta nät.
• UTF-8 .
• Huffman-kod som används för datakomprimering .
• Syntax för Pascal och andra språk med LL(1) -syntax (förutsatt att ett lexem är en symbol och en operator är ett ord ). Därför, för att bestämma typen av en operatör, behöver Pascal-kompilatorn inte returnera de lästa tecknen till strömmen eller lagra dem i stacken .

Morsekod är inte prefix. Förutom en punkt och ett bindestreck innehåller det också ett avgränsningstecken - en paus av längden på ett bindestreck .

Se även

• Kraft-McMillan ojämlikhet