Saltar a contenido

Elias Delta

La codificación Elias-delta es una codificación universal para números enteros positivos desarrollada por Peter Elias en 1975. La codificacción Elias-delta ofrece un compromiso entre codificación unaria y binaria.

Intuición

Una manera de intuitiva de llegar a la codificación Elias-delta es a través de la analogía de la relación entre la búsqueda binaria y la codificación binaria. Es conocido que al hacer búsqueda binaria sobre un arreglo ordenado, el índice del número buscado en el arreglo corresponde a la codificación binaria de las decisiones tomadas al ejecutar la búsqueda binaria, siendo "ir a la derecha" un 1 e "ir a la izquierda" un 0. El acercamiento mencionado anteriormente es útil para un arreglo de tamaño conocido ¿qué pasa cuando queremos aplicar esta misma idea y tenemos un arreglo de tamaño indeterminado? Acá es donde entra la codificación Elias-delta. La codificación Elias-delta se relaciona con la búsqueda galopante, en vez de hacer consultas sobre el tamaño del arreglo, se puede pensar como una serie de consultas asociada a la búsqueda galopante, es decir, ¿es el número mayor que 1? ¿Es mayor que 2? ¿Es mayor que 4? ¿Es mayor que 8? y así sucesivamente. De esta manera la codificación Elias-delta tiene en cuenta la magnitud del número a codificar.

Procedimiento para codificar

Para codificar un número primero se debe definir lo siguiente, sea \(X\) el número a codificar:

  • Sea \(N = \lfloor\log_2 X\rfloor\) el índice de la potencia de 2 más grande que no puede representar \(X\).

  • Sea \(L = \lfloor\log_2 N+1\rfloor\) el índice de la potencia de 2 más grande que no puede representar \(N+1\)

  • Escribir:

  • La codifiación unaria de \(L\), es decir escribir \(L\) ceros.
  • La representación binaria de \(N+1\) de largo \(L+1\) bits.
  • Los últimos \(N\) bits de \(X\).

Procedimiento para decodificar

  1. Leer y contar ceros hasta encontrar el primer 1. Llamar a la cantidad de ceros \(L\).
  2. Considerar el primer 1 leído el primer dígito de un entero, con valor \(2^L\), leer los siguientes \(L\) dígitos del entero. Llamar a este número \(N+1\), y restarle uno para obtener \(N\).
  3. Poner un uno en la primera parte de la salida final, representando el valor \(2^N\).
  4. Leer y poner en la salida los siguientes \(N\) Dígitos.

Ejemplo

Codificación

Sea \(x = 7\) el número a codificar.

  • \(N = \lfloor\log_2 7 \rfloor \rightarrow N = 2\)
  • \(L = \lfloor\log_2 2+1\rfloor \rightarrow L = 1\)

Teniendo \(N\) y \(L\), basta con escribir \(L\) ceros, seguido de la representación binaria de \(N+1\) de \(L+1\) bits de largo, para finalmente añadir últimos \(N\) bits de la representación binaria de \(x = 7\). Finalmente el número codificado es: \(0~11~11\)

Decodificación

Luego, para decodificar 01111 seguimos los siguientes pasos:

  1. Leemos un cero en \(01\).

  2. Leemos un bit más: \(011\)

  3. Decodificar \(N+1\): \(011=3\).

  4. Obtener \(N\): \(N=3-1=2\). Obtener los \(N\) últimos bits, o sea \(11\).

  5. Finalmente el número codificado es: \(2^2+3=7\)

Complejidad espacial

Para representar un número \(x\), Elias-delta usa \(\lfloor\log_2 x\rfloor + 2\lfloor\log_2(\lfloor\log_2 x\rfloor+1\rfloor +1\) bits

Comparativa

La codificación Elias-delta ofrece una gran ventaja ante la codificación unaria. Sólo es peor para valores en el rango \([2..15]\).

Usos

Gracias a que la codificación Elias-delta proporciona una codificación razonablemente corta para valores pequeños y de orden logarítmico para grandes valores, ha sido utilizada con un éxito considerable en la compresión de índices para sistemas de bases de datos de textos.

Calculadora de codificación Elias delta

En el siguiente enlace se encuentra una calculadora online de la codificación Elias-delta:

https://nitrolanco.github.io/Elias-Delta-basic-encoder/

Referencias

[1] https://en.wikipedia.org/wiki/Elias_delta_coding

[2] Compression and Coding Algorithms (The Springer International Series in Engineering and Computer Science)