Codificación de longitud variable

En teoría de la codificación , la codificación de longitud variable es un tipo de esquema de codificación de caracteres en el que se utilizan códigos de diferentes longitudes para codificar un conjunto de caracteres (un repertorio de símbolos) para su representación en una computadora . ^{[ 1 ]} El concepto equivalente en ciencias de la computación es cadena de bits .

Los códigos de longitud variable permiten comprimir y descomprimir fuentes sin errores ( compresión de datos sin pérdidas ) y leerlas símbolo por símbolo. Una fuente independiente e idénticamente distribuida puede comprimirse casi arbitrariamente cerca de su entropía . Esto contrasta con los métodos de codificación de longitud fija, en los que la compresión de datos solo es posible para grandes bloques de datos, y cualquier compresión que supere el logaritmo del número total de posibilidades conlleva una probabilidad de fallo finita (aunque quizás arbitrariamente pequeña).

Por estas razones, en ocasiones se utilizaban para comprimir texto en inglés en menos bytes en los juegos de aventuras para los primeros microordenadores . Sin embargo, los discos duros , el aumento de la memoria de los ordenadores y los algoritmos de compresión de propósito general han dejado obsoletos dichos métodos.

Las codificaciones multibyte suelen ser el resultado de la necesidad de aumentar el número de caracteres que se pueden codificar sin romper la compatibilidad con versiones anteriores de una restricción existente. Por ejemplo, con un byte (8 bits) por carácter, se pueden codificar 256 caracteres posibles; para codificar más de 256 caracteres, la opción obvia sería usar dos o más bytes por unidad de codificación. Dos bytes (16 bits) permitirían 65.536 caracteres posibles, pero tal cambio rompería la compatibilidad con los sistemas existentes y, por lo tanto, podría no ser factible en absoluto. ^{[ a ]}

A los símbolos de origen improbables se les pueden asignar palabras clave más largas, mientras que a los símbolos de origen probables se les pueden asignar palabras clave más cortas, lo que resulta en una longitud de palabra clave esperada baja . Algunos ejemplos de estrategias de codificación de longitud variable bien conocidas son la codificación de Huffman , la codificación de Lempel-Ziv , la codificación aritmética y la codificación de longitud variable adaptativa al contexto .

Estructura general

Un sistema de codificación multibyte minimiza las interrupciones en el software existente al mantener algunos caracteres como códigos de una sola unidad, mientras que otros requieren varias unidades. Esto crea tres tipos de unidades: singletons (que constan de una sola unidad), unidades iniciales (que aparecen primero en una secuencia de varias unidades) y unidades finales (que aparecen después en una secuencia de varias unidades). Los sistemas de entrada y visualización deben manejar estas estructuras, aunque la mayoría del software no lo hace.

Por ejemplo, la cadena de cuatro caracteres " I♥NY " se codifica en UTF-8 de la siguiente manera (mostrada como valores de bytes hexadecimales ): 49 E2 99 A5 4E 59. De las seis unidades en esa secuencia, 49 , 4E y 59 son singletons (para I , N e Y ), E2 es una unidad inicial y 99 y A5 son unidades finales. El símbolo del corazón está representado por la combinación de la unidad inicial y las dos unidades finales.

UTF-8 distingue claramente los caracteres individuales, los caracteres iniciales y los caracteres finales mediante rangos de valores que no se superponen. Por el contrario, las codificaciones más antiguas suelen reutilizar valores, lo que dificulta el análisis correcto del texto. Esto puede provocar falsos positivos en las búsquedas o hacer que un byte corrupto interrumpa secuencias largas. En codificaciones bien diseñadas como UTF-8, la búsqueda funciona de forma fiable y la corrupción afecta únicamente al carácter que contiene la unidad defectuosa.

Códigos y sus extensiones

La extensión de un código es el mapeo de secuencias fuente de longitud finita a cadenas de bits de longitud finita, que se obtiene concatenando para cada símbolo de la secuencia fuente la palabra clave correspondiente producida por el código original. Utilizando términos de la teoría de lenguajes formales , la definición matemática precisa es la siguiente: Sea $S$ y $T$ Sean dos conjuntos finitos, denominados alfabetos fuente y alfabetos destino , respectivamente. Un código $C:S\to T^{*}$ es una función total ^{[ 2 ]} que asigna cada símbolo de $S$ a una secuencia de símbolos sobre $T$ y la extensión de $C$ a un homomorfismo de $S^{*}$ en $T^{*}$ , que asigna de forma natural cada secuencia de símbolos de origen a una secuencia de símbolos de destino, se denomina su extensión .

Los códigos de longitud variable pueden anidarse estrictamente en orden de generalidad decreciente como códigos no singulares, códigos decodificables de forma única y códigos de prefijo. Los códigos de prefijo siempre son decodificables de forma única, y estos a su vez siempre son no singulares:

Códigos no singulares

Un código es no singular si cada símbolo fuente se asigna a una cadena de bits no vacía diferente; es decir, la asignación de símbolos fuente a cadenas de bits es inyectiva .

Por ejemplo, el mapeo $M_{1}=\{\,{\texttt {a}}\mapsto {\texttt {0}},{\texttt {b}}\mapsto {\texttt {0}},{\texttt {c}}\mapsto {\texttt {1}}\,\}$ no es no singular porque tanto a como b se asignan a la misma cadena de bits 0 ; cualquier extensión de esta asignación generará una codificación con pérdidas (no sin pérdidas). Dicha codificación singular aún puede ser útil cuando se acepta cierta pérdida de información (por ejemplo, cuando dicho código se utiliza en la compresión de audio o video, donde una codificación con pérdidas se vuelve equivalente a la cuantización de la fuente ).

Sin embargo, el mapeo $M_{2}=\{\,{\texttt {a}}\mapsto {\texttt {1}},{\texttt {b}}\mapsto {\texttt {011}},{\texttt {c}}\mapsto {\texttt {01110}},{\texttt {d}}\mapsto {\texttt {1110}},{\texttt {e}}\mapsto {\texttt {10011}},{\texttt {f}}\mapsto {\texttt {0}}\}$ es no singular; su extensión generará una codificación sin pérdidas, útil para la transmisión general de datos (aunque esta característica no siempre es necesaria). No es preciso que el código no singular sea más compacto que el original (y en muchas aplicaciones, un código más extenso resulta útil, por ejemplo, para detectar o recuperar errores de codificación o transmisión, o en aplicaciones de seguridad para proteger el original de manipulaciones indetectables).

Códigos decodificables de forma única

Un código es decodificable de forma única si su extensión es § no singular . Si un código dado es decodificable de forma única se puede determinar con el algoritmo de Sardinas-Patterson .

El mapeo $M_{3}=\{\,{\texttt {a}}\mapsto {\texttt {0}},{\texttt {b}}\mapsto {\texttt {01}},{\texttt {c}}\mapsto {\texttt {011}}\,\}$ es decodificable de forma única (esto se puede demostrar mirando el conjunto de seguimiento después de cada cadena de bits objetivo en el mapa, porque cada cadena de bits termina tan pronto como vemos un ${\texttt {0}}$ bit que no puede seguir ningún código existente para crear un código válido más largo en el mapa, sino que inicia un nuevo código de forma inequívoca).

Consideremos nuevamente el código. $M_{2}$ de la sección anterior. ^{[ 2 ]} Este código no es decodificable de forma única, ya que la cadena 011101110011 puede interpretarse como la secuencia de palabras clave 01110 – 1110 – 011 , pero también como la secuencia de palabras clave 011 – 1 – 011 – 10011. Dos posibles decodificaciones de esta cadena codificada son dadas por cdb y babe . Sin embargo, dicho código es útil cuando el conjunto de todos los posibles símbolos fuente es completamente conocido y finito, o cuando hay restricciones (como una sintaxis formal) que determinan si los elementos fuente de esta extensión son aceptables. Dichas restricciones permiten la decodificación del mensaje original al verificar cuáles de los posibles símbolos fuente mapeados al mismo símbolo son válidos bajo esas restricciones.

Códigos de prefijo

Un código es un código de prefijo si ninguna cadena de bits de destino en la asignación es un prefijo de la cadena de bits de destino de un símbolo fuente diferente en la misma asignación. Esto significa que los símbolos se pueden decodificar instantáneamente después de recibir su palabra clave completa. Otros nombres comunes para este concepto son código sin prefijo , código instantáneo o código libre de contexto . Un caso especial de códigos de prefijo son los códigos de bloque , LEB128 y los códigos de cantidad de longitud variable (VLQ).

Por ejemplo, el mapeo $M_{3}$ El código anterior no es un código de prefijo porque, tras leer la cadena de bits 0, desconocemos si codifica un símbolo fuente "a " o si es el prefijo de las codificaciones de los símbolos "b" o "c" . A continuación se muestra un ejemplo de código de prefijo.

Ejemplo de codificación y decodificación:

aabacdab → 00100110111010 → | 0 | 0 | 10 | 0 | 110 | 111 | 0 | 10 | → aabacdab

Para este ejemplo, si las probabilidades de $({\texttt {a}},{\texttt {b}},{\texttt {c}},{\texttt {d}})$ eran $\textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)$ El número esperado de bits utilizados para representar un símbolo fuente utilizando el código anterior sería:

1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}

.

Dado que la entropía de esta fuente es de 1,75 bits por símbolo, este código comprime la fuente lo máximo posible para que pueda recuperarse sin errores .

Véase también

Código Golomb
Recuento de Kruskal
Arquitectura del conjunto de instrucciones § Longitud de la instrucción en informática
caracteres anchos wchar_t
Conjunto de caracteres multibyte de Lotus (LMBCS)
Conjunto de caracteres de triple byte (TBCS)
Conjunto de caracteres de doble byte (DBCS)
Conjunto de caracteres de un solo byte (SBCS)

Notas

↑ Como ejemplo real de esto, UTF-16 , que representa los caracteres más comunes exactamente de la manera que se acaba de describir (y utiliza pares de unidades de código de 16 bits para los caracteres menos comunes), nunca ganó popularidad como codificación de texto destinada al intercambio debido a su incompatibilidad con la omnipresente codificación ASCII de 7/8 bits, y su función prevista la asumió UTF-8 , que sí conserva la compatibilidad con ASCII.

Referencias

↑ Crispin, M. (2005-04-01). UTF-9 y UTF-18 Formatos de transformación eficientes de Unicode . IETF . doi : 10.17487/rfc4042 .
1 2 Este código se basa en un ejemplo que se encuentra en Berstel et al. (2009), Ejemplo 2.3.1, pág. 63.

Lecturas adicionales

Salomon, David (septiembre de 2007). Códigos de longitud variable para compresión de datos (1.ª ed.). Springer Verlag . ISBN 978-1-84628-958-3.(xii+191 páginas) Fe de erratas 1 Fe de erratas 2
Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Códigos y autómatas . Enciclopedia de Matemáticas y sus Aplicaciones. Vol. 129. Cambridge, Reino Unido: Cambridge University Press . ISBN 978-0-521-88831-8. Zbl 1187.94001 . Borrador disponible en línea

[2] Como ejemplo real de esto, UTF-16 , que representa los caracteres más comunes exactamente de la manera que se acaba de describir (y utiliza pares de unidades de código de 16 bits para los caracteres menos comunes), nunca ganó popularidad como codificación de texto destinada al intercambio debido a su incompatibilidad con la omnipresente codificación ASCII de 7/8 bits, y su función prevista la asumió UTF-8 , que sí conserva la compatibilidad con ASCII.

[1] Crispin, M. (2005-04-01). UTF-9 y UTF-18 Formatos de transformación eficientes de Unicode . IETF . doi : 10.17487/rfc4042 .

[:0-3] 1 2 Este código se basa en un ejemplo que se encuentra en Berstel et al. (2009), Ejemplo 2.3.1, pág. 63.

[ 1 ]

[ a ]