El término estructura de datos comprimidos surge en los subcampos informáticos 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 comprimidos suele depender en gran medida de la entropía de los datos que se representan.
Ejemplos importantes de estructuras de datos comprimidos incluyen la matriz de sufijos comprimidos [1] [2] y el índice FM , [3] los cuales pueden representar un texto arbitrario de caracteres T para la coincidencia de patrones . Dado cualquier patrón de entrada P , apoyan la operación de encontrar si P aparece en T y dónde aparece . 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 informadas. El espacio que ocupan es aproximadamente igual al tamaño del texto Ten forma de entropía comprimida, como la obtenida por Predicción por coincidencia parcial o gzip . Además, ambas estructuras de datos se autoindexan, ya que pueden reconstruir el texto T de una manera de acceso aleatorio y, por lo tanto, el texto subyacente T puede descartarse. En otras palabras, que al mismo tiempo proporcionan una representación comprimida y rápida búsqueda del texto camiseta . Ellos representan una mejora sustancial sobre el espacio convencional de árbol de sufijos y arreglo de sufijos , que ocupan muchas veces más espacio que el tamaño de la camiseta . También admiten 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 tienen la función de autoindexación.
Una noción relacionada importante es la de una estructura de datos sucinta , que usa un espacio aproximadamente igual al mínimo teórico de la información, que es una noción del peor de los casos del espacio necesario para representar los datos. Por el contrario, el tamaño de una estructura de datos comprimidos depende de los datos particulares que se representan. Cuando los datos son comprimibles, como suele ser el caso en la práctica del texto en lenguaje natural, la estructura de datos comprimidos puede ocupar un espacio muy cercano al mínimo teórico de la información y significativamente menos espacio que la mayoría de los esquemas de compresión [se necesita un ejemplo ] [ se necesita una cita ] .
Referencias
- ^ R. Grossi y JS Vitter, Matrices de sufijos comprimidos y árboles de sufijos con aplicaciones a la indexación de texto y la coincidencia de cadenas], Actas del 32º Simposio de ACM sobre Teoría de la Computación , mayo de 2000, 397-406. Versión de revista en SIAM Journal on Computing , 35 (2), 2005, 378-407.
- ^ R. Grossi, A. Gupta y JS Vitter, índices de texto comprimido de entropía de alto orden, actas del 14º Simposio anual SIAM / ACM sobre algoritmos discretos , enero de 2003, 841-850.
- ^ P. Ferragina y G. Manzini, Estructuras de datos oportunistas con aplicaciones, Actas del 41º Simposio IEEE sobre fundamentos de la informática , noviembre de 2000, 390-398. Versión de la revista en Indexing Compressed Text, Journal of the ACM , 52 (4), 2005, 552-581.