Saltar a contenido

Codificación Elias-Fano

Definición

La codificación Elias-Fano es una técnica avanzada de compresión de datos utilizada en la representación eficiente de conjuntos crecientes y sin repeticiones de números enteros no negativos. Propuesta por Peter Elias y Robert Fano en 1974, esta técnica surge como una opción relevante a la optimización de estructuras de datos que requieren almacenamiento compacto y operaciones de recuperación eficientes en aplicaciones como motores de búsqueda y sistemas de indexación. Dada la naturaleza de los elementos ya descritos, esta técnica encuentra gran valor en el campo de índices invertidos, los cuales juegan un rol fundamental en la eficiencia de los mencionados motores de búsqueda. La capacidad de recuperar información de forma eficiente también se considera de gran valor al permitir ahorrar espacio (casi a nivel sucinto) sin apenas sacrificar tiempo de consulta, aunque esto dependerá en gran medida de la implementación.

Descripción a alto nivel

En esencia, la codificación Elias-Fano se fundamenta en la división de cada entero en dos componentes: bits más significativos (high bits) y bits menos significativos (low bits). Los high bits, que representan la parte más destacada numéricamente, son codificados de manera compacta utilizando técnicas como la codificación unaria o gamma. Por otro lado, los low bits, la porción menos significativa, se almacenan sin comprimir. Esta estructura permite la rápida identificación de la posición relativa de un entero dentro del conjunto, posibilitando la recuperación eficiente de la información original.

Algoritmo de Elias-Fano

Construcción

Dada una secuencia creciente monótona de enteros sin repeticiones, \(S\), de largo \(n=|S|\):

  1. Tomamos el valor más grande en la secuencia y lo asignamos a \(u\), i.e. \(u=\max(S)\).
  2. Tomamos la representación en binario de cada uno de los \(x \in S\), utilizando \(\lceil \log(u) \rceil\) bits por cada uno.
  3. Separamos la forma binaria de cada \(x\) en 2 bit-vector, low y high, donde low almacena los primeros \(l=\log (\frac{u}{n})\) bits de derecha a izquierda, y high los restantes \(h = \log(u) - l\) bits.
  4. Guardamos las mitades alojadas en low tal como están, manteniendo la correspondencia de los bits con el orden de los números de los que provienen. En otras palabras, el bit-vector comienza con los l bits del entero más pequeño, luego con los del segundo más pequeño, y así hasta concatenar al final los \(l\) bits del entero más grande, \(u\).
  5. Las mitades en high por otro lado, se recodifican usando codificación unaria. Una manera sencilla de entender la construcción de high es que colocamos un 0 dentro de una secuencia por cada posible valor desde 0 hasta \(2^h\) (esto representa la cantidad de posibles representaciones binarias que podriamos encontrar en las mitades high). Luego, añadimos un 1 a cada 0 de la secuencia por cada ocurrencia del valor que representan (la figura más abajo muestra esta idea con mayor claridad). El bit-vector high será la concatenación de estos contadores de ocurrencias en formato unario.
  6. Finalmente, la codificación Elias-Fano es el par de bit-vector de ocurrencias (en unario) y low. Dependiendo de la implementación estos pueden concatenarse por prolijidad.

Access

La operación access(i) devuelve el i-ésimo elemento en la secuencia original. Para lograr esto se deben buscar las dos mitades del elemento \(x_i\) en los arreglos low y high. Encontrar la mitad en low es sencillo, saltamos a la posición \(l\times i\) y tomamos los \(l\) bits desde esa posición. Para la otra mitad computamos el valor \(select_1(i) -i\) sobre el bit-vector high. Esto es posible de hacer en tiempo constante dependiendo de la implementación de la operación \(select_1(i)\), la cual retorna la posición del \(i\)-ésimo bit en 1 en un bit-vector.

Análisis teórico

Veamos el espacio utilizado por esta codificación: El bit-vector low será proporcional a la cantidad de enteros de la secuencia original, a su vez, cada porción de los enteros almacenados en low tiene un largo de \(\lceil \log(\frac{u}{n})\rceil\), por lo que \(\textit{low} \in O(n \log(\frac{u}{n}))\). Para el caso de high tendremos tantos 1 como enteros en el arreglo original (\(n\)), ya que representan las ocurrencias de una cierta representacion binaria (de dichos enteros) en el vector. Además habrán tantos 0 como posibles cadenas binarias del tamaño de los elementos en high, esto es \(2^{\log(n)}=n\). De modo que \(\textit{high} \in O(n)\). Así, vemos que el costo de espacio de la codificación Elías-Fano es de \(n \log(\frac{u}{n}) + 2n\), lo cual está en \(O(n \log{\frac{u}{n}})\).

La teoría de la información nos dice que el minimo de bits necesario para representar un entero es de \(\lceil \log(x) \rceil\) bits, con \(x\) dicho entero. Si consideramos una secuencia monótona creciente de enteros de largo \(n\) a partir de un universo \(u\), el limite es de \(\lceil \log \binom{u+n}{n} \rceil\), por lo que se considera a esta codificación como quasi-sucinta al estar tan cerca del límite.

Ejemplo

Tomamos como ejemplo el arreglo de enteros [1,3,4,5,6,11,16,20]. Notemos que el largo es \(n=8\) y el número más grande es \(u=20\). Primero se pasa de su forma decimal al su forma binaria (marcado con fondo amarillo). Posteriormete tomamos las secciones de cada numero que van a high (en rojo) y las que van a low (en azul), según el largo establecido en la explicación del algoritmo.

Proceso de codificación del arreglo [1,3,4,5,8,11,16,20]

Se sigue trabajando únicamente con las que irán a high. Observamos todas las posibles cadenas binarias de largo 3 que podriamos obtener (buckets), y construimos un arreglo con las ocurrencias de cada uno.

Finalmente transformamos el arreglo de ocurrencia a unario, y este será nuestro bitvector high.

Si quisieramos recuperar un elemento del arreglo original podemos hacerlo con la función access de la siguiente manera:

  1. Mis bit-vector serán \(low=0111000100110000\) y \(high=1101101100101000\).
  2. Supongamos que queremos access(5), el quinto elemento de mi arreglo original, el procedimiento es como sigue (con todos los indexados partiendo desde 1):
  3. Calculamos sobre high: \(select_1(5) - 5 = 7 -5=2\), en binario \(2=010\).
  4. Accedemos directamente al \((5l)\)-ésimo elemento de \(low\) y tomamos la cadena de largo \(l\) hasta dicha posición. O dicho de otra forma, \(low[4l+1,5l+1]=low[9,11]=00\)
  5. Así el quinto elemento del arreglo será \(01000=8\).

Implementación en Golang

Por tema visual se muestra solo la construcción de esta implementación, para ver el código completo entrar aquí. 

package ef

import (
    "errors"
    "github.com/willf/bitset"
    "log"
    "math"
)

const (
    efInfo = `Universe: %d
Elements: %d
Lower_bits: %d
Higher_bits_length: %d
Mask: 0b%b
Lower_bits offset: %d
Bitvector length: %d
`
)

// EliasFano codec structure
type EliasFano struct {
    universe         uint64
    n                uint64
    lowerBits        uint64
    higherBitsLength uint64
    mask             uint64
    lowerBitsOffset  uint64
    bvLen            uint64
    b                *bitset.BitSet
    curValue         uint64
    position         uint64
    highBitsPos      uint64
}

// New creates a new empty EliasFano object
func New(universe uint64, n uint64) *EliasFano {
    var lowerBits uint64
    if lowerBits = 0; universe > n {
        lowerBits = msb(universe / n)
    }
    higherBitsLength := n + (universe >> lowerBits) + 2
    mask := (uint64(1) << lowerBits) - 1
    lowerBitsOffset := higherBitsLength
    bvLen := lowerBitsOffset + n*uint64(lowerBits)
    b := bitset.New(uint(bvLen))
    return &EliasFano{universe, n, lowerBits, higherBitsLength, mask, lowerBitsOffset, bvLen, b, 0, 0, 0}
}

// Compress a monotone increasing array of positive integers. It sets the position at the beginning.
func (ef *EliasFano) Compress(elems []uint64) {
    last := uint64(0)

    for i, elem := range elems {
        if i > 0 && elem < last {
            log.Fatal("Sequence is not sorted")
        }
        if elem > ef.universe {
            log.Fatalf("Element %d is greater than universe", elem)
        }
        high := (elem >> ef.lowerBits) + uint64(i) + 1
        low := elem & ef.mask
        ef.b.Set(uint(high))
        offset := ef.lowerBitsOffset + uint64(i)*ef.lowerBits
        setBits(ef.b, offset, low, ef.lowerBits)
        last = elem
        if i == 0 {
            ef.curValue = elem
            ef.highBitsPos = high
        }
    }
}

Otras implementaciones interesantes son las hechas en la librería Folly en C++, y la librería Sux4J en Java, por Sebastiano Vigna.

Referencias

[1] Vigna, S. (2013, February). Quasi-succinct indices. In Proceedings of the sixth ACM international conference on Web search and data mining (pp. 83-92).
[2] Mallia, A. (2018, January 6). Sorted integers compression with Elias-Fano encoding. Antonio Mallia. https://www.antoniomallia.it/sorted-integers-compression-with-elias-fano-encoding.html
[3] Ermanno, G. (2016, June 21) Elias-Fano encoding: Succint representation of monotone integer sequences with search operations. https://jermp.github.io/assets/pdf/slides/elias-fano-2.pdf