En informática , una estructura de datos sucinta es una estructura de datos que utiliza una cantidad de espacio "cercana" al límite inferior de la teoría de la información , pero (a diferencia de otras representaciones comprimidas) aún permite operaciones de consulta eficientes. El concepto fue introducido originalmente por Jacobson [1] para codificar vectores de bits , árboles (sin etiquetar) y gráficos planos . A diferencia de los algoritmos generales de compresión de datos sin pérdida , las estructuras de datos sucintas conservan la capacidad de usarlas in situ, sin descomprimirlas primero. Una noción relacionada es la de una estructura de datos comprimidos., en el que el tamaño de la estructura de datos depende de los datos particulares que se representan.
Suponer que es el número óptimo teórico de información de bits necesarios para almacenar algunos datos. Una representación de estos datos se llama:
- implícito si se necesita pedazos de espacio,
- sucinto si se necesita pedazos de espacio, y
- compacto si se necesita pedazos de espacio.
Por ejemplo, una estructura de datos que usa bits de almacenamiento es compacto, bits es sucinto, bits también es sucinto, y bits está implícito.
Por tanto, las estructuras implícitas suelen reducirse a almacenar información utilizando alguna permutación de los datos de entrada; el ejemplo más conocido de esto es el montón .
Diccionarios sucintos
Los diccionarios indexables sucintos, también llamados diccionarios de clasificación / selección , forman la base de una serie de técnicas de representación sucinta, incluidos árboles binarios ,árboles ary y conjuntos múltiples , [2] , así como sufijo árboles y matrices . [3] El problema básico es almacenar un subconjunto de un universo , generalmente representado como una matriz de bits dónde si Un diccionario indexable admite los métodos habituales de los diccionarios (consultas e inserciones / eliminaciones en el caso dinámico), así como las siguientes operaciones:
por .
En otras palabras, devuelve el número de elementos igual a hasta la posición tiempo devuelve la posición del -ésima aparición de .
Hay una representación simple [4] que usa bits de espacio de almacenamiento (la matriz de bits original y un estructura auxiliar) y admite rango y selección en tiempo constante. Utiliza una idea similar a la de las consultas de rango mínimo ; hay un número constante de recursiones antes de detenerse en un subproblema de tamaño limitado. La matriz de bitsestá dividido en grandes bloques de tamañobits y pequeños bloques de tamañobits. Para cada bloque grande, el rango de su primer bit se almacena en una tabla separada; cada una de estas entradas toma bits para un total de bits de almacenamiento. Dentro de un bloque grande, otro directorio almacena el rango de cada uno de los pequeños bloques que contiene. La diferencia aquí es que solo necesitabits para cada entrada, ya que solo es necesario almacenar las diferencias con respecto al rango del primer bit en el bloque grande que lo contiene. Por lo tanto, esta tabla toma un total debits. Una tabla de búsqueda luego se puede usar que almacena la respuesta a cada consulta de rango posible en una cadena de bits de longitud por ; esto requierebits de espacio de almacenamiento. Así, dado que cada una de estas tablas auxiliares toma espacio, esta estructura de datos admite consultas de clasificación en tiempo y pedazos de espacio.
Para responder a una consulta de en tiempo constante, un algoritmo de tiempo constante calcula:
En la práctica, la tabla de búsqueda se puede reemplazar por operaciones bit a bit y tablas más pequeñas que se pueden usar para encontrar el número de bits establecidos en los bloques pequeños. Esto a menudo es beneficioso, ya que las estructuras de datos sucintas encuentran su uso en grandes conjuntos de datos, en cuyo caso las fallas de caché se vuelven mucho más frecuentes y las posibilidades de que la tabla de búsqueda sea expulsada de cachés de CPU más cercanos aumentan. [5] Las consultas seleccionadas se pueden respaldar fácilmente haciendo una búsqueda binaria en la misma estructura auxiliar utilizada para la clasificación ; sin embargo, esto requieretiempo en el peor de los casos. Una estructura más complicada usandoSe pueden utilizar bits de almacenamiento adicional para admitir la selección en tiempo constante. [6] En la práctica, muchas de estas soluciones tienen constantes ocultas en elnotación que domina antes de que se haga evidente cualquier ventaja asintótica; las implementaciones que utilizan operaciones de palabra amplia y bloques alineados con palabras suelen funcionar mejor en la práctica. [7]
Diccionarios comprimidos en entropía
La El enfoque espacial se puede mejorar notando que hay distinto -subconjuntos de (o cadenas binarias de longitud exactamente con 1's), y por lo tanto es un límite inferior teórico de la información sobre el número de bits necesarios para almacenar . Hay un diccionario sucinto (estático) que alcanza este límite, es decir, utilizandoespacio. [8] Esta estructura se puede ampliar para admitir consultas de clasificación y selección yespacio. [2] Sin embargo, las consultas de rango correcto en esta estructura se limitan a los elementos contenidos en el conjunto, de forma análoga a cómo funcionan las funciones mínimas de hash perfecto. Este límite se puede reducir a una compensación de espacio / tiempo reduciendo el espacio de almacenamiento del diccionario a con consultas tomando hora. [9]
Ejemplos de
Una cadena terminada en nulo ( cadena C ) ocupa un espacio Z + 1 y, por lo tanto, está implícita. Una cadena con una longitud arbitraria ( cadena Pascal ) ocupa un espacio Z + log ( Z ) y, por lo tanto, es sucinta. Si hay una longitud máxima, que es el caso en la práctica, dado que 2 32 = 4 GiB de datos es una cadena muy larga, y 2 64 = 16 EiB de datos es más grande que cualquier cadena en la práctica, entonces una cadena con una longitud también está implícito, tomando el espacio Z + k , donde k es el número de datos para representar la longitud máxima (por ejemplo, 64 bits).
Cuando es necesario codificar una secuencia de elementos de longitud variable (como cadenas), existen varias posibilidades. Un enfoque directo es almacenar una longitud y un elemento en cada registro; estos se pueden colocar uno tras otro. Esto permite seguir eficientemente, pero no encontrar el k- ésimo elemento. Una alternativa es colocar los elementos en orden con un delimitador (por ejemplo, una cadena terminada en nulo ). Esto usa un delimitador en lugar de una longitud y es sustancialmente más lento, ya que se debe escanear toda la secuencia en busca de delimitadores. Ambos son eficientes en espacio. Un enfoque alternativo es la separación fuera de banda: los elementos pueden simplemente colocarse uno tras otro, sin delimitadores. Los límites de los elementos se pueden almacenar como una secuencia de longitud, o mejor, compensaciones en esta secuencia. Alternativamente, se codifica una cadena binaria separada que consta de unos en las posiciones donde comienza un elemento y ceros en cualquier otro lugar. Dada esta cadena, elLa función puede determinar rápidamente dónde comienza cada elemento, dado su índice. [10] Esto es compacto pero no sucinto, ya que ocupa un espacio de 2 Z , que es O ( Z ).
Otro ejemplo es la representación de un árbol binario : un árbol binario arbitrario en los nodos se pueden representar en bits mientras admite una variedad de operaciones en cualquier nodo, lo que incluye encontrar su padre, su hijo izquierdo y derecho, y devolver el tamaño de su subárbol, cada uno en tiempo constante. El número de árboles binarios diferentes en los nodos es . Para grande, esto es sobre ; por lo que necesitamos al menos sobrebits para codificarlo. Por lo tanto, un árbol binario sucinto ocuparía solo bits por nodo.
Ver también
Referencias
- ^ Jacobson, G. J (1988). Estructuras sucintas de datos estáticos (tesis doctoral). Pittsburgh, PA: Universidad Carnegie Mellon.
- ^ a b Raman, R .; V. Raman; S. S Rao (2002). "Diccionarios indexables sucintos con aplicaciones para la codificación de árboles k-ary y multisets" . Actas del decimotercer simposio anual ACM-SIAM sobre algoritmos discretos . págs. 233–242 . arXiv : 0705.0552 . CiteSeerX 10.1.1.246.3123 . doi : 10.1145 / 1290672.1290680 . ISBN 0-89871-513-X.
- ^ Sadakane, K .; R. Grossi (2006). "Exprimir estructuras de datos sucintas en límites de entropía" (PDF) . Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmo discreto . págs. 1230-1239. ISBN 0-89871-605-5. Archivado desde el original (PDF) el 29 de septiembre de 2011.
- ^ Jacobson, G. (1 de noviembre de 1989). Árboles y gráficos estáticos que ahorran espacio (PDF) . 30º Simposio del IEEE sobre fundamentos de la informática. doi : 10.1109 / SFCS.1989.63533 . Archivado desde el original (PDF) el 12 de marzo de 2016.
- ^ González, R .; S. Grabowski; V. Mäkinen; G. Navarro (2005). "Implementación práctica de consultas de clasificación y selección" (PDF) . Poster Proceedings Volume del 4º Taller sobre Algoritmos Eficientes y Experimentales (WEA) . págs. 27–38.
- ^ Clark, David (1996). Árboles de palmaditas compactos (PDF) (tesis doctoral). Universidad de Waterloo.
- ^ Vigna, S. (2008). Implementación de palabra amplia de consultas de clasificación / selección (PDF) . Algoritmos experimentales . Apuntes de conferencias en Ciencias de la Computación. 5038 . págs. 154-168. CiteSeerX 10.1.1.649.8950 . doi : 10.1007 / 978-3-540-68552-4_12 . ISBN 978-3-540-68548-7.
- ^ Brodnik, A .; J. I Munro (1999). "Membresía en tiempo constante y espacio casi mínimo" (PDF) . SIAM J. Comput . 28 (5): 1627-1640. CiteSeerX 10.1.1.530.9223 . doi : 10.1137 / S0097539795294165 .
- ^ Pătraşcu, M. (2008). "Succínter" (PDF) . Fundamentos de la informática, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on . págs. 305–313.
- ^ Belazzougui, Djamal. "Hash, desplazar y comprimir" (PDF) .