Cuando el número (generalmente un número grande) se representa en un conjunto alfabético finito, y no puede ser representado por un solo miembro del conjunto, se utiliza la indexación recursiva .
La indexación recursiva en sí misma es un método para escribir las diferencias sucesivas del número después de extraer el valor máximo del conjunto alfabético del número y continuar de forma recursiva hasta que la diferencia cae en el rango del conjunto.
La indexación recursiva con un alfabeto de 2 letras se denomina código unario .
Codificación
Para codificar un número N , siga reduciendo el elemento máximo de este conjunto ( S max ) de N y la salida S max para cada diferencia de este tipo, deteniéndose cuando el número se encuentre en el rango medio cerrado medio abierto [0 - S max ).
Ejemplo:
Sea S = [0 1 2 3 4… 10], un conjunto de 11 elementos, y tenemos que indexar recursivamente el valor N = 49.
De acuerdo con este método, debemos seguir quitando 10 de 49 y continuar hasta que alcancemos un número en el rango de 0 a 10.
Entonces los valores son 10 ( N = 49 - 10 = 39), 10 ( N = 39 - 10 = 29), 10 ( N = 29 - 10 = 19), 10 ( N = 19 - 10 = 9), 9. Por tanto, la secuencia indexada recursivamente para N = 49 con el conjunto S , es 10, 10, 10, 10, 9.
Descodificación
Mantenga la adición de todos los elementos del índice, deteniéndose cuando el valor del índice es de entre (inclusive de extremos) los elementos menos y penúltimo del conjunto S .
Ejemplo:
Continuando con el ejemplo anterior, tenemos 10 + 10 + 10 + 10 + 9 = 49.
Usos
Esta técnica se usa más comúnmente en sistemas de codificación de longitud de ejecución para codificar ejecuciones más largas de lo que permiten los tamaños del alfabeto.
Referencias
- Khalid Sayood, Introducción a la compresión de datos 3ª ed, Morgan Kaufmann .