Un código de prefijo en la teoría de la codificación es un código con una palabra de longitud variable que tiene la siguiente propiedad (cumplimiento de la condición de Fano ): si el código incluye la palabra a , entonces para cualquier cadena b no vacía , la palabra ab no existen en el código. Aunque el código de prefijo consta de palabras de diferentes longitudes, estas palabras se pueden escribir sin un carácter de separación.
Por ejemplo, el código que consta de las palabras 0, 10 y 11 es un prefijo, y el mensaje 01001101110 se puede dividir en palabras de una manera única:
0 10 0 11 0 11 10El código que consta de las palabras 0, 10, 11 y 100 no es un prefijo y el mismo mensaje puede interpretarse de varias formas.
0 10 0 11 0 11 10 0 100 11 0 11 10Los llamados "prefijos" se pueden obtener descartando secuencialmente el último carácter de la combinación de códigos. Por ejemplo, para la combinación de códigos 11101101, los prefijos serán 11101101, 1110110, 111011, 11101, 1110, 111, 11, 1.
O así:
Escribimos todas las combinaciones de códigos, sin ceros a la izquierda: 0 //prefijo //una //10 <- comentar (excluir) las que son principio de otras //once 100 //prefijo 101 //códigos sin comentar - prefijos del código de prefijo. 110 111 ... //que sean todas combinaciones de tres bits.La secuencia de código resultante (0, 100, 101, 110, 111) es equivalente a la secuencia de código de prefijo Huffman .
Si no hay espacios u otros signos de puntuación entre las combinaciones de códigos, entonces, para la decodificación inequívoca de la combinación 111011101, ninguna de las combinaciones de códigos puede representarse mediante las opciones enumeradas (prefijos). Un código se llama prefijo si ninguna de sus combinaciones es prefijo de otra combinación del mismo código. La parte de la combinación de códigos que completa el prefijo de la combinación misma se llama sufijo. Los códigos de prefijo se pueden representar visualmente mediante árboles de códigos. Si ningún nodo del árbol de código es un nodo del código dado, entonces tiene las propiedades de un prefijo. Los nodos de árbol que no se conectan con otros se denominan nodos de hoja. Las combinaciones que los emparejan son combinaciones de códigos de prefijos.
Cualquier código de palabra de longitud fija es obviamente un código de prefijo. Consideremos algunos ejemplos no triviales.
El código Morse no es un prefijo. Además de un punto y un guión, también incluye un carácter separador: una pausa de la longitud de un guión .