Código de longitud variable

---

En la teoría de la codificación, un código de longitud variable es un código que asigna símbolos fuente a un número variable de bits.

Los códigos de longitud variable pueden permitir que las fuentes se compriman y descompriman sin error ( compresión de datos sin pérdida ) y aún así se puedan leer símbolo por símbolo. Con la estrategia de codificación correcta, 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, para los cuales la compresión de datos solo es posible para grandes bloques de datos, y cualquier compresión más allá del logaritmo del número total de posibilidades tiene una probabilidad de falla finita (aunque quizás arbitrariamente pequeña).

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 .

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 de código correspondiente producida por el código original.

Usando términos de la teoría del lenguaje formal , la definición matemática precisa es la siguiente: Sean y sean dos conjuntos finitos, llamados alfabetos de origen y de destino , respectivamente. Un código es una función total ^{[1] que} asigna cada símbolo de a una secuencia de símbolos over , y la extensión de a un homomorfismo de into , que asigna naturalmente cada secuencia de símbolos de origen a una secuencia de símbolos de destino, se conoce como su extensión .${\ Displaystyle S}$${\ Displaystyle T}$ ${\ Displaystyle C: S \ a T ^ {*}}$${\ Displaystyle S}$${\ Displaystyle T}$${\ Displaystyle C}$${\ Displaystyle S ^ {*}}$${\ Displaystyle T ^ {*}}$

Los códigos de longitud variable se pueden anidar 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 se pueden decodificar de forma única y, a su vez, estos siempre no son singulares:

---