Estructura de datos comprimida

El término estructura de datos comprimida surge en los subcampos de algoritmos , estructuras de datos e informática teórica . Se refiere a una estructura de datos cuyas operaciones son aproximadamente tan rápidas como las de una estructura de datos convencional para el problema, pero cuyo tamaño puede ser sustancialmente menor. El tamaño de la estructura de datos comprimida suele depender en gran medida de la entropía de la información de los datos representados.

Ejemplos importantes de estructuras de datos comprimidas incluyen el array de sufijos comprimido ^{[ 1 ] [ 2 ]} y el índice FM ^{[ 3 ],} ambos capaces de representar un texto arbitrario de caracteres T para la búsqueda de patrones . Dado cualquier patrón de entrada P , admiten la operación de encontrar si P aparece en T y dónde . El tiempo de búsqueda es proporcional a la suma de la longitud del patrón P , una función de crecimiento muy lento de la longitud del texto T , y el número de coincidencias reportadas. El espacio que ocupan es aproximadamente igual al tamaño del texto T en forma comprimida por entropía, como la obtenida mediante Predicción por Coincidencia Parcial o gzip . Además, ambas estructuras de datos son autoindexables, ya que pueden reconstruir el texto T de forma aleatoria, y por lo tanto el texto subyacente T puede descartarse. En otras palabras, proporcionan simultáneamente una representación comprimida y de búsqueda rápida del texto T. Representan una mejora sustancial en el espacio con respecto al árbol de sufijos y el array de sufijos convencionales , que ocupan mucho más espacio que el tamaño de T. También permiten la búsqueda de patrones arbitrarios, a diferencia del índice invertido , que solo admite búsquedas basadas en palabras. Además, los índices invertidos no cuentan con la función de autoindexación.

Un concepto importante relacionado es el de estructura de datos concisa , que utiliza un espacio aproximadamente igual al mínimo teórico de la información, que representa el peor caso posible del espacio necesario para representar los datos. En cambio, el tamaño de una estructura de datos comprimida depende de los datos específicos que se representan. Cuando los datos son compresibles, como suele ocurrir en la práctica con el texto en lenguaje natural, la estructura de datos comprimida puede ocupar un espacio muy cercano al mínimo teórico de la información, y significativamente menor que la mayoría de los esquemas de compresión.