ircodecs es un repositorio que permite la compresión de listas de enteros. Es compatible con las versiones 2 y 3 de Python, siendo útil para prototipos o pruebas, o para quien ya posea conocimientos en este lenguaje y desee incursionar en el área de compresión contextualizada en el ámbito de la Recuperación de Información (Information Retrieval).
Este repositorio surgió a partir de la realización de un trabajo titulado Esquema Multicompresión para Índices Invertidos de Motores de Búsqueda (https://github.com/gustingonzalez/irmulticompression) en el contexto de la materia Recuperación de Información, de la carrera Licenciatura en Sistemas de Información, dictada en la Universidad Nacional de Luján.
Los distintos módulos aquí implementados permiten la codificación y decodificación de listas de enteros con una serie de métodos estado del arte, en concreto: Unario, Gamma, Variable Byte, Empaquetado Binario, Elias Fano (ver notas en el siguiente subapartado), Simple16 y PFor (NewPFD/OptPFD). También contiene un módulo que permite realizar Delta Gaps (gapsencoder.py) y otro que permite tratar secuencias de bytes como arrays de bits de bytes (bitbytearray). A su vez, estas implementaciones se basan en la bibliografía expuesta en la sección de Referencias y en desarrollos ya conocidos para lograr cierto grado de eficiencia (teniendo en cuenta las limitaciones que un lenguaje interpretado supone). Por ejemplo, los desarrollos de Simple16 y PFor, están fuertemente basados en la implementación kamikaze expuesta en el repositorio de @lemire (basada, a su vez, en el repositorio de @javasoze) mientras que, tanto la decodificación de Unario, como de Elias Fano, se fundamentan en la implementación de @catenamatteo.
Con el fin de mejorar el ratio de compresión de Elias Fano (nativo), la versión aquí implementada tiene una premisa similar a la variación Multinivel presentada en el paper Partitioned Elias Fano Indexes de Ottaviano y Venturini. Sin embargo, dado que esta versión Multinivel descomprime cada partición (chunk) de lista teniendo en cuenta el máximo número de la partición, es incompatible con la propuesta del esquema múltiple de compresión en la que originalmente se gestó este repositorio. En efecto, para suplir lo mencionado, dada una secuencia de chunks
pertenecientes a una lista, para cada
se definen
como el menor elemento del
chunk, y
con
, una secuencia creciente que se comprime utilizando Elias Fano. Si se analiza el algoritmo utilizado para computar
, el establecer
como su primer número permite que su codificación no pierda un posible alineamiento en caso de haber definido un tamaño de chunk múltiplo de 8. En adición, el valor de
será siempre lo más cercano posible a
, lo cual tiene sentido si se tiene en cuenta que el ratio de compresión de Elias Fano depende únicamente del mayor elemento de la lista. Finalmente, se define
, que se comprime utilizando Variable Byte: a esta codificación se concatena
. Por otra parte, VByte también se utiliza en caso de que la lista a comprimir sea de tamaño 1 ya que, para definir
, se requieren como mínimo 2 elementos. En el caso de que
,
se define como
y
como
, de otro modo el valor de
resultaría negativo. Para salvar ineficiencias en la compresión, cuando la secuencia
es densa, esta se comprime utilizando vectores de bits siempre que
con
. Para rearmar la lista original, luego de la descompresión de
y de
, simplemente se redefine
y se adiciona este valor a cada
. La ventaja de la variante propuesta, es que cada partición de lista es independiente de las demás.
Si bien esta librería es compatible con las versiones 2 y 3 de Python, la primera brinda mejores resultados en términos de eficiencia. Esto se debe a la forma en que se implementa el tipo entero en cada versión del lenguaje. En concreto, mientras que la versión 2 diferencia entre un tipo entero de 64 bits y un long (de tamaño arbitrario), la versión 3 presupone toda variable numérica como long (arbitraria): en efecto las operaciones a nivel bit sobre este último tipo de variables, son más costosas que sobre las primeras. Referencias a este hecho, se pueden encontrar en https://docs.python.org/2/c-api/long.html y https://docs.python.org/3/c-api/long.html.
El siguiente cuadro expone una comparativa de los tiempos de decodificación, especificados en enteros por segundo, en relación a cada versión del lenguaje:
| Códec | Py2 (2.7.9) | Py3 (3.4.2) | Δ% |
|---|---|---|---|
| PFD (NewPFD) | 1367019,0 | 1167724,5 | -14,6% |
| Bit Packing | 1019746,3 | 867998,7 | -14,9% |
| EF Local | 617343,7 | 561147,9 | -9,1% |
| Gamma | 354815,1 | 318848,3 | -10,1% |
| Vbyte | 3050411,3 | 2436618,0 | -20,1% |
| Simple16 | 3044125,2 | 2328077,2 | -23,5% |
| Unario | 658449,6 | 612273,8 | -7,0% |
Para las mediciones se ha utilizado el script decodingspeedtest.py, cuya metodología consiste en comprimir, con cada códec, una secuencia de gaps derivada de una lista creciente de 1 millón de enteros, para finalmente obtener el tiempo de cada decodificación. Tener en cuenta que, dado que Elias Fano comprime la lista original utilizando dgaps internamente, para equiparar, el tiempo de decodificación delta se añade a los resultados de los restantes métodos. Esta operación se lleva a cabo 5 veces, aunque también se realiza una inicial (a modo de warm-up), que no se toma en cuenta para el promedio final. Además, por cada repetición, la distancia entre números se duplica. Es decir, en la primera (pertinente a la medición), se prueba la secuencia S=[1, 2, 3], en la segunda S=[1, 3, 5], en la tercera S=[1, 5, 9] y así sucesivamente. El entorno de pruebas utilizado ha sido un Intel® Xeon® X5650 @ 2.67Ghz de 24 núcleos con 32 GB de memoria RAM.
Suponiendo que se requiere codificar una lista de 128 números...
from irencoder import pforencoder
numbers = list(range(1, 129))
encoded = pforencoder.encode(numbers)
decoded = pforencoder.decode(encoded, 128)Tener en cuenta que el resultado de la codificación es una secuencia enteros.
from irencoder import simple16encoder
numbers = list(range(1, 129))
encoded = simple16encoder.encode(numbers)
decoded = simple16encoder.decode(encoded, 128)Tener en cuenta que el resultado de la codificación es una secuencia enteros.
from irencoder import bitpackingencoder
numbers = list(range(1, 129))
encoded, padding = bitpackingencoder.encode(numbers)
decoded = bitpackingencoder.decode(encoded, 128)Tener en cuenta que el resultado de la codificación es una secuencia bytes.
from irencoder import eliasfanoencoder
numbers = list(range(1, 129))
encoded, padding = eliasfanoencoder.encode(numbers)
decoded = eliasfanoencoder.decode(encoded, 128)Tener en cuenta que el resultado de la codificación es una secuencia bytes.
Nota preliminar: aunque la implementación ha sido diseñada para comprimir un único número por vez, la codificación de una lista tan sólo requiere la importación de la clase BitByteArray del módulo bitbytearray. Esta funcionalidad no ha sido desarrollada debido a que, en la propuesta del esquema de compresión múltiple en la que se gestó esta librería, esta tarea se lleva a cabo en una capa superior. De todas formas, sería útil su implementación. Tener en cuenta que, alternativamente, se podría utilizar la función write_binary_in_barray(array, offset, number, bits) de bitutils.py: aun así, la clase BitByteArray abstrae la complejidad inherente a las escrituras de secuencias de bits como, por ejemplo, el control de offset (puntero de bit relativo al array de bytes). Por su parte, el uso de write_binary_in_barray(array, offset, number, bits), se recomienda en los casos en los que se utilicen cantidades fijas de bits o en los que se requiera mayor eficiencia en la codificación: por ejemplo, el módulo bitpackingencoder.py utiliza esta función de forma interna tanto para el proceso de codificación, como para el de decodificación.
from irencoder import unaryencoder
from irencoder.bitbytearray import BitByteArray
numbers = list(range(1, 129))
optimized = True # Unario optimizado
# Encode
encoded = BitByteArray()
for number in numbers:
e, padding = unaryencoder.encode(number)
encoded.extend(e, padding)
# Decode
decoded = unaryencoder.decode(encoded, 128, optimized)También es posible especificar el inicio de la lectura, desde un bit arbitrario. Por ejemplo, en la siguiente sentencia, se leen los 127 números restantes desde el offset 1:
decoded = unaryencoder.decode(encoded, 127, True, offset=1)Tener en cuenta que no es estrictamente necesario que la función decode reciba un BitByteArray: bien pudiera recibir un array de bytes (bytearray) o de enteros.
Nota preliminar: para este códec aplican las mismas observaciones señaladas para Unario.
from irencoder import gammaencoder
from irencoder.bitbytearray import BitByteArray
numbers = list(range(1, 129))
# Encode
encoded = BitByteArray()
for number in numbers:
e, padding = gammaencoder.encode(number)
encoded.extend(e, padding)
# Decode
decoded = gammaencoder.decode(encoded, 128)Tener en cuenta que el resultado de la codificación es una secuencia bytes.
Nota preliminar: para la decodificación con este método no se requiere el parámetro de la cantidad de números a descomprimir, puesto que se lee la totalidad de los bytes pasados por parámetro. Quizás, a modo de aunar criterios, sería útil la futura implementación de lo descrito.
from irencoder import vbencoder
numbers = list(range(1, 129))
# Encode
encoded = bytearray()
for n in numbers:
encoded.extend(vbencoder.encode(n))
# Decode
decoded = vbencoder.decode(encoded)También es posible realizar la lectura de un único número desde un bit especifico. Por ejemplo, en la siguiente sentencia, el valor de number, leído desde el bit 8, es 2 y el nuevo offset, 16:
number, offset = vbencoder.decode_number(encoded, 8)Nota: como Variable Byte realiza la lectura en grupos de octetos, si el offset no es múltiplo de 8, esta se inicia desde el byte relativo.
En caso de requerir utilizar algún módulo en concreto y de que querer evitar la descarga completa del repositorio, hay que tener en las dependencias internas de cada uno:
- bitpackingencoder.py: vbencoder.py, bitutils.py.
- eliasfanoencoder.py: bitutils.py, gapsencoder.py, unaryencoder.py, vbencoder.py, /bitbytearray.
- gammaencoder.py: bitutils.py, unaryencoder.py, bitbytearray.
- gapsencoder.py: sin dependencias.
- pforencoder.py: simple16encoder.py, bitutils.py.
- simple16encoder.py: sin dependencias.
- vbencoder.py: sin dependencias.
Este repositorio está basado en diversas lecturas:
- C. D. Manning, P. Raghavan, H. Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008.
- M. Catena, C. MacDonald, and I. Ounis. On inverted index compression for search engine efficiency. Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 8416 LNCS, pp. 359–371, 2014.
- J. Zhang, X. Long, y T. Suel. Performance of Compressed Inverted List Caching in Search Engine. Proceedings of the 17th international conference on World Wide Web, WWW '08, pp. 387–396, 2008.
- D. Lemire, L. Boytsov. Decoding billions of integers per second through vectorization. Software: Practice & Experience, Vol. 45 (1), pp. 1-29, 2015.
- M. Zukowski, S. Heman, N. Nes y P. Boncz. Super-Scalar RAM-CPU Cache Compression. 22nd International Conference on Data Engineering (ICDE'06), pp. 59-59, 2006.
- G. Ottaviano, R. Venturini. Partitioned Elias-Fano Indexes. Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval, SIGIR ‘14, pp. 273-282, 2014.
También se han utilizado (y se recomiendan) las siguientes implementaciones como referencia:
- DocId set compression and set operation library - https://github.com/javasoze/kamikaze
- JavaFastPFOR: A java integer compression library - https://github.com/lemire/JavaFastPFOR
- Elias Fano: A simpl(istic) Java implementation of the Elias-Fano compression schema - https://github.com/catenamatteo/eliasfano
- Partitioned Elias-Fano Indexes - https://github.com/ot/partitioned_elias_fano
- Data Structures for Inverted Indexes (ds2i) - https://github.com/ot/ds2i
- Terrier IR Platform - http://terrier.org
Python v2 o Python v3
Agustín González