Código de prefijo

Un código de prefijo es un tipo de sistema de codificación que se distingue por poseer la propiedad de prefijo , la cual exige que no exista ninguna palabra de código completa en el sistema que sea un prefijo (segmento inicial) de ninguna otra palabra de código en el sistema. Esto es trivialmente cierto para códigos de longitud fija, por lo que solo es un punto a considerar para códigos de longitud variable .

Por ejemplo, un código con código${\displaystyle \{{\texttt {a}},{\texttt {bb}}\}}$tiene la propiedad de prefijo; un código que consta de${\displaystyle \{{\texttt {a}},{\texttt {b}},{\texttt {ab}},{\texttt {aa}}\}}$No, porque a es un prefijo de ab y también de aa . Un código de prefijo es un código decodificable de forma única : dada una secuencia completa y precisa, un receptor puede identificar cada palabra sin necesidad de un marcador especial entre ellas. Sin embargo, existen códigos decodificables de forma única que no son códigos de prefijo; por ejemplo, el inverso de un código de prefijo también es decodificable de forma única (es un código de sufijo), pero no necesariamente es un código de prefijo.

Los códigos de prefijo también se conocen como códigos libres de prefijo , códigos de condición de prefijo y códigos instantáneos . Aunque la codificación de Huffman es solo uno de los muchos algoritmos para derivar códigos de prefijo, estos también se denominan comúnmente "códigos de Huffman", incluso cuando el código no fue producido por un algoritmo de Huffman. El término código libre de coma a veces también se aplica como sinónimo de códigos libres de prefijo ^{[ 1 ] [ 2 ]} , pero en la mayoría de los libros y artículos matemáticos (por ejemplo, ^{[ 3 ] [ 4 ]} ) un código libre de coma se usa para referirse a un código autosincronizado , una subclase de códigos de prefijo.

Mediante códigos de prefijo, un mensaje puede transmitirse como una secuencia de palabras clave concatenadas, sin marcadores fuera de banda ni marcadores especiales entre palabras para delimitar el mensaje. El destinatario puede decodificar el mensaje sin ambigüedad, buscando y eliminando repetidamente secuencias que formen palabras clave válidas. Esto no suele ser posible con códigos que carecen de la propiedad de prefijo, por ejemplo${\displaystyle \{{\texttt {0}},{\texttt {1}},{\texttt {10}},{\texttt {11}}\}}$: un receptor que lea un 1 al comienzo de una palabra clave no sabría si se trata de la palabra clave completa 1 , o simplemente del prefijo de la palabra clave 10 u 11 ; por lo tanto, la cadena 10 podría interpretarse como una sola palabra clave o como la concatenación de las palabras 1 y luego 0 .

Los códigos Huffman de longitud variable , los códigos de país telefónicos , las partes de país y editor de los ISBN , los códigos de sincronización secundaria utilizados en el estándar inalámbrico UMTS W-CDMA 3G y los conjuntos de instrucciones (lenguaje máquina) de la mayoría de las microarquitecturas informáticas son códigos de prefijo.

Los códigos de prefijo no son códigos de corrección de errores . En la práctica, un mensaje puede comprimirse primero con un código de prefijo y luego volver a codificarse con codificación de canal (incluida la corrección de errores) antes de su transmisión.

Para cada código decodificable de forma única, existe un código de prefijo que tiene la misma longitud de palabra clave. ^{[ 5 ]} La desigualdad de Kraft caracteriza los conjuntos de longitudes de palabra clave que son posibles en un código decodificable de forma única. ^{[ 6 ]}

Si cada palabra del código tiene la misma longitud, el código se denomina código de longitud fija o código de bloque (aunque el término código de bloque también se utiliza para códigos correctores de errores de tamaño fijo en la codificación de canales ). Por ejemplo, las letras ISO 8859-15 siempre tienen 8 bits de longitud. Las letras UTF-32/UCS-4 siempre tienen 32 bits de longitud. Las celdas ATM siempre tienen 424 bits (53 bytes) de longitud. Un código de longitud fija de longitud fija${\displaystyle k}$Los bits pueden codificar hasta${\displaystyle 2^{k}}$símbolos fuente.

Un código de longitud fija es necesariamente un código de prefijo. Es posible convertir cualquier código en uno de longitud fija añadiendo símbolos fijos a los prefijos más cortos para que coincidan con la longitud de los prefijos más largos. Alternativamente, estos códigos de relleno pueden emplearse para introducir redundancia que permita la autocorrección o la sincronización. Sin embargo, las codificaciones de longitud fija resultan ineficientes en situaciones donde algunas palabras tienen mucha más probabilidad de transmitirse que otras.

La codificación binaria truncada es una generalización directa de los códigos de longitud fija para tratar casos en los que el número de símbolos n no es una potencia de dos. A los símbolos fuente se les asignan palabras clave de longitud${\displaystyle k}$y${\displaystyle k+1}$, dónde${\displaystyle k}$se elige de modo que${\displaystyle 2^{k}<n\leq 2^{k+1}}$.

La codificación Huffman es una técnica más sofisticada para construir códigos de prefijo de longitud variable. El algoritmo de codificación Huffman toma como entrada las frecuencias que deben tener las palabras clave y construye un código de prefijo que minimiza el promedio ponderado de las longitudes de dichas palabras. (Esto está estrechamente relacionado con la minimización de la entropía). Se trata de una forma de compresión de datos sin pérdidas basada en la codificación de entropía .

Algunos códigos marcan el final de una palabra clave con un símbolo especial de "coma" (también llamado valor Centinela ), distinto de los datos normales. ^{[ 7 ]} Esto es algo análogo a los espacios entre palabras en una oración; marcan dónde termina una palabra y comienza otra. Si cada palabra clave termina en una coma, y ​​la coma no aparece en ningún otro lugar de la palabra clave, el código está automáticamente libre de prefijos. Sin embargo, reservar un símbolo completo solo para usarlo como coma puede ser ineficiente, especialmente para idiomas con un número reducido de símbolos. El código Morse es un ejemplo cotidiano de un código de longitud variable con una coma. Las largas pausas entre letras, y las pausas aún más largas entre palabras, ayudan a las personas a reconocer dónde termina una letra (o palabra) y comienza la siguiente. De manera similar, la codificación de Fibonacci usa un 11 para marcar el final de cada palabra clave.

Los códigos autosincronizables son códigos de prefijo que permiten la sincronización de tramas .

Un código de sufijo es un conjunto de palabras que no son sufijos de ninguna otra; equivalentemente, un conjunto de palabras que son el inverso de un código de prefijo. Al igual que con un código de prefijo, la representación de una cadena como concatenación de dichas palabras es única. Un código bifijo es un conjunto de palabras que es a la vez un código de prefijo y un código de sufijo. ^{[ 8 ]} Un código de prefijo óptimo es un código de prefijo con una longitud media mínima. Es decir, supongamos un alfabeto de n símbolos con probabilidades${\displaystyle p(A_{i})}$para un código de prefijo C. Si C' es otro código de prefijo y${\displaystyle \lambda '_{i}}$son las longitudes de las palabras clave de C' , entonces${\displaystyle \sum _{i=1}^{n}{\lambda _{i}p(A_{i})}\leq \sum _{i=1}^{n}{\lambda '_{i}p(A_{i})}\!}$. ^{[ 9 ]}

Algunos ejemplos de códigos de prefijo son:

• códigos Huffman de longitud variable
• códigos telefónicos de países
• Codificación de Chen-Ho
• el país y la editorial, partes del ISBN
• Los códigos de sincronización secundarios utilizados en el estándar inalámbrico UMTS W-CDMA 3G
• Códigos VCR Plus+
• Formato de transformación Unicode , en particular el sistema UTF-8 para codificar caracteres Unicode , que es a la vez un código sin prefijos y un código autosincronizado ^{[ 10 ].}
• prefijos de código de operación utilizados en los conjuntos de instrucciones de la computadora
• cantidad de longitud variable

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Códigos y autómatas . Enciclopedia de Matemáticas y sus Aplicaciones. Vol.  129. Cambridge: Cambridge University Press . ISBN 978-0-521-88831-8. Zbl 1187.94001 . 
• Elias, Peter (1975). "Conjuntos de palabras clave universales y representaciones de los enteros". IEEE Trans. Inf. Theory . 21 (2): 194– 203. doi : 10.1109/tit.1975.1055349 . ISSN 0018-9448 . Zbl 0298.94011 .  
• DA Huffman, "Un método para la construcción de códigos de redundancia mínima", Actas del IRE, septiembre de 1952, págs.  1098-1102 (artículo original de Huffman).
• Perfil: David A. Huffman , Scientific American , septiembre de 1991, págs.  54-58 (Artículo de contexto)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7Sección 16.3, págs.  385–392.
•  Este artículo incorpora material de dominio público de la Norma Federal 1037C . Administración de Servicios Generales . Archivado del original el 22 de enero de 2022.

• Códigos, árboles y la propiedad de prefijo por Kona Macphee