Prefixový kód

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Prefixový kód je takový kód, který má tu vlastnost, že žádný symbol jeho kódové abecedy není předponou (prefixem, začátkem) jiného (delšího) symbolu abecedy.

Pokud je nějaký kód prefixový, je možné řetězce symbolů tohoto kódu jednoznačně dekódovat, aniž by mezi jednotlivými symboly musely být oddělovače.

Mezi prefixové kódy patří např. Huffmanovy kódy, prefixový kód tvoří také mezinárodní směrová čísla.

Minimální prefixový kód: Minimálním prefixovým kódem potom rozumíme takový kód, který obsahuje minimální možný počet znaků pro kódování. Délka kódu pro jednotlivé znaky se určuje z pravděpodobnosti jejich výskytu v kódovaném textu.

Příklady[editovat | editovat zdroj]

Kód s následující kódovou abecedou je prefixový kód: { 1, 21, 22, 231, 232, 24, 35, 535, 7 }
Kód s následující kódovou abecedou není prefixový kód: { 1, 21, 22, 221, 222, 24, 35, 355, 7 }

U prvního kódu není žádný symbol předponou jiného delšího symbolu. U druhého kódu se však symbol 22 objevuje jako předpona symbolů 221 a 222 a symbol 35 je předponou symbolu 355, takže se nejedná o prefixový kód.

Z řetězce symbolů prvního kódu, např. 2312224535121, lze jednoznačně určit, že posloupnost původních symbolů byla 231, 22, 24, 535, 1, 21. U řetězce symbolů druhého kódu, např. 2472217, však toto jednoznačně určit nelze, původní posloupnost mohla být jak 24, 7, 22, 1, 7, tak i 24, 7, 221, 7.