Código prefijo
Un código prefijo es un código, generalmente un código de longitud variable, con la "propiedad de prefijo": ninguna palabra de código es prefijo de cualquier otra palabra de código del conjunto. Un código con las palabras de código {0, 10, 11} tiene la propiedad de prefijo; un código {0, 1, 10, 11} no la tiene, porque "1" es prefijo de tanto "10" como "11".
A los códigos prefijo también se les conoce como códigos sin prefijo y códigos instantáneos. Aunque la codificación Huffman es sólo uno de los muchos algoritmos para obtener códigos prefijo, a los códigos prefijo también se les llama códigos Huffman, incluso cuando el código no se generó con un algoritmo Huffman.
Usando códigos prefijo, un mensaje puede transmitirse como una secuencia de palabras de código concatenadas, sin ninguna señal fuera de banda para distinguir las palabras del mensaje. El receptor puede descodificar el mensaje sin ambigüedad, encontrando y quitando repetidamente los prefijos que forman una palabra de código válida. Esto no es posible con códigos que no tienen la propiedad de prefijo, como en el ejemplo de {0, 1, 10, 11}: un receptor que leyera un "1" al principio de una palabra de código no sabría si este es la palabra de código completa "1" o si es simplemente el prefijo de la palabra de código "10" o "11".
Los códigos Huffman de longitud variable, los prefijos telefónicos internacionales, las partes del país y la editorial del ISBN y los códigos de sincronización secundaria usados en el estándar inalámbrico 3G UMTS W-CDMA son códigos prefijo. Los códigos prefijo también son una forma de codificación de entropía usados en compresión de datos sin pérdidas.
Los códigos prefijo no son códigos correctores de error. En la práctica, un mensaje puede estar comprimido primero con un código prefijo, y después codificarse de nuevo (con un código de corrección de errores) antes de la transmisión.
Técnicas
Las técnicas para construir un código prefijo pueden ser simples, o bastante complicadas.
Si cada palabra en el código tiene la misma longitud, el código se llama código de longitud fija. Por ejemplo, las letras del ISO 8859-15 son siempre de 8 bits de longitud. Las letras del UTF-32/UCS-4 son siempre de 32 bits de longitud. Los paquetes ATM son siempre de 424 bits de longitud. Los prefijos no pueden existir en un código de longitud fija. Desafortunadamente, la codificación de longitud fija es ineficiente en situaciones donde algunas palabras son mucho más probables de ser transmitidas que otras.
Algunos códigos de longitud variable señalan el final de una palabra de código con un símbolo especial. Este es de alguna manera análogo al punto del final de una frase; marca donde acaba una frase y comienza la siguiente. Si cada palabra de código acaba en un símbolo especial, y el símbolo especial no aparece en la palabra de código, es un código sin prefijo. Sin embargo, los sistemas de comunicación modernos envían todo como secuencias de "0" y "1" – añadir un tercer símbolo sería caro, y usarlo sólo al final de las palabras sería ineficiente. El código Morse es un ejemplo cotidiano de un código de longitud variable con un símbolo especial. Las pausas largas entre letras, y las pausas aún más largas entre palabras, ayudan a la gente a reconocer donde una letra (o palabra) acaba, y donde comienza la siguiente.
La codificación Huffman es una técnica más sofisticada para construir códigos prefijo de longitud variable. El algoritmo de codificación Huffman toma como entrada las frecuencias que las palabras de código derían tener, y construye un código prefijo que minimiza la media ponderada de la longitud de las palabras de código.
La desigualdad de Kraft caracteriza los conjuntos de longitudes de palabras de código que son posibles en un código prefijo.
Códigos prefijo en uso hoy en día
El sistema UTF-8 para codificar caracteres Unicode usando entre uno y cuatro bytes por carácter puede verse como una forma de codificación prefijo, como también los códigos VCR Plus+ y el sistema de códigos telefónicos de los países para la telefonía internacional.
Entre las técnicas comúnmente usadas para construir códigos prefijo se encuentran la codificación Shannon-Fano, la codificación Huffman, y los códigos universales con la codificación delta de Elias, la codificación gamma de Elias, la codificación omega de Elias, la codificación Fibonacci, y la codificación Levenshtein.
Referencias
- P. Elias, Universal codeword sets and representations of integers, IEEE Trans. Inform. Theory 21 (2) (1975) 194-203.
- D.A. Huffman, "A method for the construction of minimum-redundancy codes" (PDF), Proceedings of the I.R.E., Sept. 1952, pp. 1098-1102 (artículo original de Huffman)
- , Scientific American, Sept. 1991, pp. 54-58 (Historia de los antecedentes)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 16.3, pp.385–392.
Enlaces externos
- Codes, trees and the prefix property (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). por Kona Macphee (en inglés)