Esto es principalmente un problema al diseñar los códigos binarios que se usan en transmisiones de un remitente a un receptor, o en un software de compresión de datos. En la programación regular, como lo señaló el Usuario, los valores que manipula suelen ser de longitud fija, y si no, anota la cadena binaria con un número (tamaño fijo) que representa su longitud. (La clase BitSet en Java hace esto, por ejemplo). Pero veamos los casos interesantes en los que este problema se enfrenta de frente.
El código Morse es un buen ejemplo: los puntos y guiones forman un código binario, pero un receptor necesita saber dónde termina una letra y comienza la siguiente, por lo que se insertan pequeñas pausas en la secuencia de código para identificar los límites de la letra. Esto significa que efectivamente, Morse es un código ternario (punto, guión, pausa) en lugar de un código binario. Entonces la pregunta es, ¿cómo hacemos esto con un alfabeto verdaderamente binario?
Los códigos con la propiedad de que, cuando las palabras de código se secuencian, el receptor puede determinar dónde termina una palabra de código y comienza la siguiente, se denomina “decodificable de forma exclusiva”. Ejemplo:
- ¿Cómo actualiza Facebook y clasifica las historias en el feed "Noticias principales"?
- Cómo encontrar los cambios mínimos necesarios para convertir una cuerda en un palíndromo
- ¿Cuáles son algunos algoritmos nuevos e interesantes en bioinformática / informática genómica?
- ¿Cómo se ordenan las matrices para que los valores altos y bajos se distribuyan en diagonal?
- ¿Debo aprender a diseñar estructuras de datos antes de aprender sobre algoritmos?
palabra fuente / palabra clave:
a / 0
b / 01
c / 011
Este código es decodificable de forma exclusiva, porque un cero indica el inicio de una nueva palabra de código. Los códigos decodificables únicos más convenientes son los “códigos de prefijo”: un código de prefijo es un código donde ninguna palabra de código es el prefijo de otra palabra de código. Una versión de prefijo del código anterior sería:
palabra fuente / palabra clave:
a / 0
b / 10
c / 110
La ventaja de los códigos de prefijo es que (1) se puede demostrar que son igualmente eficientes que cualquier otro código decodificable de forma exclusiva: para cualquier código decodificable de forma única, hay un código de prefijo con la misma longitud de palabra de código para cada palabra fuente. Y (2), el decodificador sabe inmediatamente cuándo termina una palabra de código; el decodificador no necesita mirar hacia adelante en la secuencia de código para poder decidir dónde están las divisiones.
Los códigos de prefijo se pueden organizar en un árbol binario:
[raíz]
El |
0 | 1
a —— + —— +
El |
0 | 1
b —– + —– +
El |
0 | 1
c —– + —– (sin asignar)
Tal árbol es súper útil: a medida que ingresa una secuencia de código, simplemente comienza en la raíz y deja que cada bit que recibas determine si tomas la rama izquierda o la rama derecha, hasta llegar a una hoja. Una vez que alcanza la hoja, ha decodificado un símbolo y reinicia desde la raíz.
Si está interesado en construir códigos de prefijo eficientes, debe buscar la codificación de Huffman: el código de Huffman es una construcción muy elegante de un código libre de prefijo que es óptimo para una fuente en términos del número esperado de bits que necesita.
