Página principal › Índice multilingüe del archivo › Código del prefijo

Código del prefijo

A código del prefijo es a código, típicamente a código variable-length, con la “característica de prefijo”: no palabra de código es a prefijo de cualquier otra palabra de código en el sistema. Un código con las palabras de código {0, 10, 11} tiene la característica de prefijo; un código que consiste en {0, 1, 10, 11} no, porque “1” es un prefijo de “10” y “11”.

Los códigos del prefijo también se conocen como códigos prefijo-libres, códigos de condición del prefijo, códigos coma-libres (aunque esto es incorrecto), y códigos instantáneos. Aunque Codificación de Huffman es apenas uno de muchos algoritmos para derivar los códigos del prefijo, códigos del prefijo también se refiere extensamente como “Huffman cifra”, aun cuando el código no fue producido por un algoritmo de Huffman.

Usando códigos del prefijo, un mensaje se puede transmitir como secuencia de las palabras de código concatenadas, sin cualesquiera out-of-band marcadores a marco las palabras en el mensaje. El recipiente puede descifrar el mensaje inequívoco, en varias ocasiones encontrando y quitando los prefijos que forman palabras de código válidas. Esto no es posible con los códigos de los cuales carezca la característica de prefijo, tal como nuestro ejemplo {0, 1, 10, 11}: un receptor que lee un “1” al principio de una palabra de código no sabría si ésa era la palabra de código completa “1”, o simplemente el prefijo de la palabra de código “10” o “11”.

El variable-length Códigos de Huffman, país que llama códigos, el país y las piezas del editor de ISBNs, y los códigos secundarios de la sincronización usados en UMTS W-CDMA el estándar sin hilos 3G es códigos del prefijo. Los códigos del prefijo son también una forma de codificación de la entropía utilizado adentro compresión de datos lossless.

Los códigos del prefijo no son códigos error-correcting. En práctica real, un mensaje se pudo primero comprimir con un código del prefijo, y en seguida codificar otra vez (con un código error-correcting) antes de la transmisión.

Este artículo se deriva en parte de Estándar federal 1037C, que utiliza el término código coma-libre.

Técnicas

Las técnicas para construir un código del prefijo pueden ser simples, o absolutamente complicadas.

Si cada palabra en el código tiene la misma longitud, el código se llama un código de longitud fija. Por ejemplo, ISO 8859-15 las letras son siempre 8 pedacitos largos. UTF-32/UCS-4 las letras son siempre 32 pedacitos largos. Paquetes de la atmósfera están siempre 424 pedacitos largos. Los prefijos no pueden existir en un código de longitud fija. Desafortunadamente, las codificaciones de longitud fija son ineficaces en situaciones donde están mucho más probables algunas palabras ser transmitidas que otras.

Algunos códigos marcan el final de una palabra de código con un símbolo especial de la “coma”, diferente de datos normales. ^[1] Esto es algo análogo al período en el final de una oración; marca donde una oración termina y otra comienza. Si cada palabra de código termina en una coma, y la coma no aparece a otra parte en una palabra de código, el código es prefijo-libre. Sin embargo, los sistemas de comunicación modernos envían todo como secuencias de “1” y “0” - la adición de un tercer símbolo sería costosa, y usarlo solamente en los finales de palabras sería ineficaz. Código Morse es un ejemplo diario de un código variable-length con una coma. Las pausas largas entre las letras, y las pausas más largas uniformes entre las palabras, gente de la ayuda reconocen donde los extremos de una letra (o palabra), y el siguiente comienza. Semejantemente, Codificación de Fibonacci utiliza “11” para marcar el final de cada palabra de código.

Codificación de Huffman es una técnica más sofisticada para construir códigos variable-length del prefijo. El algoritmo de la codificación de Huffman toma como entrada las frecuencias que las palabras de código deben tener, y construye un código del prefijo que reduzca al mínimo el promedio cargado de los largos de una palabra de código.

Desigualdad de Kraft caracteriza los sistemas de los largos de una palabra de código que son posibles en un código del prefijo.

El prefijo cifra funcionando hoy

Los ejemplos de los códigos del prefijo incluyen:

• país que llama códigos
• las piezas del país y del editor de ISBNs
• los códigos secundarios de la sincronización usados en UMTS W-CDMA estándar sin hilos 3G
• Códigos del VCR Plus+
• UTF-8 sistema para codificar Unicode caracteres

Técnicas

Las técnicas de uso general para construir códigos del prefijo incluyen Códigos de Huffman y el anterior Códigos de Shannon-Fano, y códigos universales por ejemplo:

• Codificación del delta de Elias
• Codificación gamma de Elias
• Codificación de Elias Omega
• Codificación de Fibonacci
• Codificación de Levenshtein
• Codificación singular
• Código del arroz de Golomb

Referencias

• P. Elias, sistemas universales del codeword y representaciones de los números enteros, transporte de IEEE. Informe. Teoría 21 (2) (1975) 194-203.
• D.A. Huffman, “Un método para la construcción de los códigos de la mínimo-redundancia“(Pdf), procedimientos del I.R.E., sept. 1952, pp. 1098-1102 (artículo original de Huffman)
• Perfil: David A. Huffman, Americano científico, Sept. 1991, pp. 54-58 (historia del fondo)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, y Clifford Stein. Introducción a los algoritmos, Segunda edición. Prensa y McGraw-Colina, 2001 del MIT. ISBN 0-262-03293-7. Sección 16.3, pp.385-392.

Acoplamientos externos

• Códigos, árboles y la característica de prefijo por Kona Macphee