Prefixový kód

Z Wikipedie, otevřené encyklopedie

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.

[editovat] Příklady

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.