Estructura de datos sucinta

Estructura de datos que sea eficiente tanto para almacenar en memoria como para realizar consultas.

En informática , una estructura de datos sucinta es una estructura de datos que utiliza una cantidad de espacio que está "cerca" del límite inferior teórico 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 planares . A diferencia de los algoritmos generales de compresión de datos sin pérdida , las estructuras de datos sucintas conservan la capacidad de usarlos en el lugar, sin descomprimirlos primero. Una noción relacionada es la de una estructura de datos comprimida , en la medida en que el tamaño de los datos almacenados o codificados depende de manera similar del contenido específico de los datos en sí.

Supongamos que es el número óptimo de bits en teoría de la información necesario para almacenar algunos datos. Una representación de estos datos se denomina: ${\displaystyle Z}$

• implícito si ocupatrozos de espacio, ${\displaystyle Z+O(1)}$
• sucinto si ocupa fragmentos de espacio, y ${\displaystyle Z+o(Z)}$
• compacto si ocupa trozos de espacio. ${\displaystyle O(Z)}$

Por ejemplo, una estructura de datos que utiliza bits de almacenamiento es compacta, bits es concisa, bits también es concisa y bits es implícita. ${\displaystyle 2Z}$ ${\displaystyle Z+{\sqrt {Z}}}$ ${\displaystyle Z+\lg Z}$ ${\displaystyle Z+3}$

Por lo general, las estructuras implícitas se reducen a almacenar información mediante alguna permutación de los datos de entrada; el ejemplo más conocido de esto es el montón .

Diccionarios indexables sucintos

Los diccionarios indexables sucintos, también llamados diccionarios de rango/selección , forman la base de una serie de técnicas de representación sucinta, incluidos árboles binarios , árboles -arios y multiconjuntos , ^[2] así como árboles de sufijos y matrices . ^[3] El problema básico es almacenar un subconjunto de un universo , generalmente representado como una matriz de bits donde s/f Un diccionario indexable admite los métodos habituales en los diccionarios (consultas e inserciones/eliminaciones en el caso dinámico), así como las siguientes operaciones: ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle U=[0\dots n)=\{0,1,\dots ,n-1\}}$ ${\displaystyle B[0\dots n)}$ ${\displaystyle B[i]=1}$ ${\displaystyle i\in S.}$

• ${\displaystyle \mathbf {rank} _{q}(x)=|\{k\in [0\dots x]:B[k]=q\}|}$
• ${\displaystyle \mathbf {select} _{q}(x)=\min\{k\in [0\dots n):\mathbf {rank} _{q}(k)=x\}}$

para . ${\displaystyle q\in \{0,1\}}$

En otras palabras, devuelve el número de elementos igual a hasta la posición mientras que devuelve la posición de la -ésima ocurrencia de . ${\displaystyle \mathbf {rank} _{q}(x)}$ ${\displaystyle q}$ ${\displaystyle x}$ ${\displaystyle \mathbf {select} _{q}(x)}$ ${\displaystyle x}$ ${\displaystyle q}$

Existe una representación simple ^[4] que utiliza bits de espacio de almacenamiento (la matriz de bits original y una estructura auxiliar) y admite el rango y la 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 un tamaño limitado. La matriz de bits se divide en bloques grandes de tamaño bits y bloques pequeños de tamaño bits. Para cada bloque grande, el rango de su primer bit se almacena en una tabla separada ; cada una de esas 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 bloques pequeños que contiene. La diferencia aquí es que solo necesita bits para cada entrada, ya que solo se necesitan almacenar las diferencias con el rango del primer bit en el bloque grande que lo contiene. Por lo tanto, esta tabla toma un total de bits. Luego se puede usar una tabla de búsqueda que almacena la respuesta a cada posible consulta de rango en una cadena de bits de longitud para ; esto requiere bits de espacio de almacenamiento. De esta forma, como cada una de estas tablas auxiliares ocupa espacio, esta estructura de datos admite consultas de rango en tiempo y bits de espacio. ${\displaystyle n+o(n)}$ ${\displaystyle o(n)}$ ${\displaystyle B}$ ${\displaystyle l=\lg ^{2}n}$ ${\displaystyle s=\lg n/2}$ ${\displaystyle R_{l}[0\dots n/l)}$ ${\displaystyle \lg n}$ ${\displaystyle (n/l)\lg n=n/\lg n}$ ${\displaystyle R_{s}[0\dots l/s)}$ ${\displaystyle l/s=2\lg n}$ ${\displaystyle \lg l=\lg \lg ^{2}n=2\lg \lg n}$ ${\displaystyle (n/s)\lg l=4n\lg \lg n/\lg n}$ ${\displaystyle R_{p}}$ ${\displaystyle s}$ ${\displaystyle i\in [0,s)}$ ${\displaystyle 2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)}$ ${\displaystyle o(n)}$ ${\displaystyle O(1)}$ ${\displaystyle n+o(n)}$

Para responder a una consulta en tiempo constante, un algoritmo de tiempo constante calcula: ${\displaystyle \mathbf {rank} _{1}(x)}$

• ${\displaystyle \mathbf {rank} _{1}(x)=R_{l}[\lfloor x/l\rfloor ]+R_{s}[\lfloor x/s\rfloor ]+R_{p}[x\lfloor x/s\rfloor ,x{\text{ mod }}s]}$

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 la cantidad de bits establecidos en los bloques pequeños. Esto suele ser beneficioso, ya que las estructuras de datos sucintas encuentran su uso en conjuntos de datos grandes, en cuyo caso los errores 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 se vuelven mayores. ^[5] Las consultas de selección se pueden respaldar fácilmente haciendo una búsqueda binaria en la misma estructura auxiliar utilizada para rank ; sin embargo, esto lleva tiempo en el peor de los casos. Se puede usar una estructura más complicada que use bits de almacenamiento adicional para respaldar la selección en tiempo constante. ^[6] En la práctica, muchas de estas soluciones tienen constantes ocultas en la notación que dominan antes de que se haga evidente cualquier ventaja asintótica; las implementaciones que usan operaciones de palabras amplias y bloques alineados con palabras a menudo funcionan mejor en la práctica. ^[7] ${\displaystyle R_{p}}$ ${\displaystyle O(\lg n)}$ ${\displaystyle 3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)}$ ${\displaystyle O(\cdot )}$

Soluciones comprimidas por entropía

El enfoque espacial se puede mejorar al notar que hay distintos subconjuntos de (o cadenas binarias de longitud con exactamente 1), y por lo tanto es un límite inferior teórico de la información sobre la cantidad de bits necesarios para almacenar . Hay un diccionario sucinto (estático) que alcanza este límite, es decir, usando espacio. ^[8] Esta estructura se puede extender para admitir consultas de rango y selección y ocupa espacio. ^{[2] Sin embargo, las consultas} de rango correctas en esta estructura están limitadas a los elementos contenidos en el conjunto, de manera análoga a cómo funcionan las funciones hash perfectas mínimas. Este límite se puede reducir a un compromiso de espacio/tiempo al reducir el espacio de almacenamiento del diccionario a con consultas que toman tiempo. ^[9] ${\displaystyle n+o(n)}$ ${\displaystyle \textstyle {\binom {n}{m}}}$ ${\displaystyle m}$ ${\displaystyle [n)}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle \textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil }$ ${\displaystyle B}$ ${\displaystyle {\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))}$ ${\displaystyle {\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)}$ ${\displaystyle {\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})}$ ${\displaystyle O(t)}$

También es posible construir un diccionario indexable que admita rangos (pero no selección) que utilice menos de bits. Este tipo de diccionario se denomina función hash perfecta mínima monótona y se puede implementar utilizando tan solo bits. ^{[10] [11]} ${\displaystyle \textstyle {\mathcal {B}}(m,n)}$ ${\displaystyle O(m\log \log \log n)}$

Tablas hash concisas

Una tabla hash sucinta, también conocida como diccionario desordenado sucinto, es una estructura de datos que almacena claves de un universo utilizando bits espaciales y, al mismo tiempo, admite consultas de membresía en un tiempo esperado constante. Si una tabla hash sucinta también admite inserciones y eliminaciones en un tiempo esperado constante, se la denomina dinámica y, de lo contrario, se la denomina estática. ${\displaystyle m}$ ${\displaystyle \{0,1,\dots ,n-1\}}$ ${\displaystyle (1+o(1)){\mathcal {B}}(m,n)}$

La primera tabla hash sucinta dinámica se debió a Raman y Rao en 2003. ^[12] En el caso donde , su solución utiliza bits de espacio. Posteriormente, se demostró que este límite de espacio podría mejorarse a bits para cualquier número constante de logaritmos ^[13] y un poco después de eso, este límite también era óptimo. ^{[14] [15]} La última solución admite todas las operaciones en tiempo constante en el peor de los casos con alta probabilidad. ${\displaystyle n={\text{poly}}(m)}$ ${\displaystyle {\mathcal {B}}(m,n)+O(m\log \log m)}$ ${\displaystyle {\mathcal {B}}(m,n)+O(m\log \log \log \cdots \log m)}$

La primera tabla hash sucinta estática se debió a Pagh en 1999. ^{[16] [17]} En el caso en que , su solución utiliza bits de espacio y admite consultas de tiempo constante en el peor de los casos . Este límite se mejoró posteriormente a bits, ^[18] y luego a bits. ^[19] Mientras que las dos primeras soluciones ^{[17] [18]} admiten consultas de tiempo constante en el peor de los casos, la última admite consultas de tiempo esperado constante. ^[19] La solución final también requiere acceso a una tabla de búsqueda de tamaño , pero esta tabla de búsqueda es independiente del conjunto de elementos que se almacenan. ^[19] ${\displaystyle n={\text{poly}}(m)}$ ${\displaystyle {\mathcal {B}}(m,n)+O(m(\log \log m)^{2}/\log m)}$ ${\displaystyle {\mathcal {B}}(m,n)+m/{\text{poly}}\log m}$ ${\displaystyle {\mathcal {B}}(m,n)+{\text{poly}}\log m}$ ${\displaystyle n^{\epsilon }}$

Otros ejemplos

Una cadena con una longitud arbitraria ( cadena de Pascal ) ocupa el espacio Z + log( Z ) y, por lo tanto, es concisa. Si hay una longitud máxima (que es el caso en la práctica, ya 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 es implícita, ocupando el espacio Z + k , donde k es el número de datos para representar la longitud máxima (por ejemplo, 64 bits).

Cuando se necesita 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 pueden colocarse uno después del otro. Esto permite encontrar el elemento k de manera eficiente, pero no así el k -ésimo elemento. Una alternativa es colocar los elementos en orden con un delimitador (por ejemplo, una cadena terminada en nulo ). Esto utiliza 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 métodos son eficientes en términos de espacio. Un enfoque alternativo es la separación fuera de banda: los elementos pueden colocarse simplemente uno después del otro, sin delimitadores. Los límites de los elementos pueden almacenarse como una secuencia de longitud o, mejor aún, como desplazamientos dentro de esta secuencia. Alternativamente, se codifica una cadena binaria separada que consta de 1 en las posiciones donde comienza un elemento y 0 en todos los demás lugares. Dada esta cadena, la función puede determinar rápidamente dónde comienza cada elemento, dado su índice. ^[20] Esto es compacto pero no conciso, ya que ocupa 2 Z espacio, que es O( Z ). ${\displaystyle select}$

Otro ejemplo es la representación de un árbol binario : un árbol binario arbitrario en nodos se puede representar en bits y, al mismo tiempo, admitir una variedad de operaciones en cualquier nodo, que incluyen 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 , esto es aproximadamente ; por lo tanto, necesitamos al menos aproximadamente bits para codificarlo. Por lo tanto, un árbol binario sucinto ocuparía solo bits por nodo. ${\displaystyle n}$ ${\displaystyle 2n+o(n)}$ ${\displaystyle n}$ ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle /(n+1)}$ ${\displaystyle n}$ ${\displaystyle 4^{n}}$ ${\displaystyle \log _{2}(4^{n})=2n}$ ${\displaystyle 2}$

Véase también

• Función hash mínima perfecta
• Argumentos breves y no interactivos sobre el conocimiento

Referencias

1. Jacobson, G. J (1988). Estructuras de datos estáticas sucintas (tesis doctoral). Pittsburgh, PA: Carnegie Mellon University.
2. Raman, R.; V. Raman; S. S Rao (2002). "Diccionarios indexables sucintos con aplicaciones para codificar árboles k-arios y multiconjuntos". 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.
3. Sadakane, K.; R. Grossi (2006). "Cómo reducir la entropía a la mínima expresión las estructuras de datos sucintas" (PDF) . Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmos discretos . pp. 1230–1239. ISBN 0-89871-605-5. Archivado desde el original (PDF) el 29 de septiembre de 2011.
4. Jacobson, G. (1 de noviembre de 1989). Árboles y gráficos estáticos que ahorran espacio (PDF) . 30.º Simposio IEEE sobre fundamentos de la informática. doi :10.1109/SFCS.1989.63533. Archivado desde el original (PDF) el 12 de marzo de 2016.
5. González, R.; S. Grabowski; V. Mäkinen; G. Navarro (2005). "Implementación práctica de consultas de rango y selección" (PDF) . Actas del 4º Taller sobre Algoritmos Eficientes y Experimentales (WEA) . págs. 27–38.
6. Clark, David (1996). Árboles compactos (PDF) (tesis doctoral). Universidad de Waterloo.
7. Vigna, S. (2008). "Implementación de consultas de selección/clasificación en palabras amplias" (PDF) . Algoritmos experimentales . Apuntes de clase en informática. Vol. 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. Número de identificación del sujeto  13963489.
8. Brodnik, A.; J. I Munro (1999). "Pertenencia 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. 
9. Pătraşcu, M. (2008). "Succincter" (PDF) . Fundamentos de la informática, 2008. FOCS'08. IEEE 49.º Simposio anual del IEEE sobre . págs. 305–313.
10. Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano (4 de enero de 2009). "Hash mínimo perfecto monótono: búsqueda en una tabla ordenada con accesos O(1)". Actas del vigésimo simposio anual ACM-SIAM sobre algoritmos discretos . Filadelfia, PA: Society for Industrial and Applied Mathematics: 785–794. doi : 10.1137/1.9781611973068.86 . ISBN: 978-0-2009-04-0000000000 . 978-0-89871-680-1.
11. Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (enero de 2023), "Límites estrictos para el hash perfecto mínimo monótono", Actas del Simposio anual ACM-SIAM de 2023 sobre algoritmos discretos (SODA) , Filadelfia, PA: Society for Industrial and Applied Mathematics, págs. 456–476, arXiv : 2207.10556 , doi : 10.1137/1.9781611977554.ch20, ISBN 978-1-61197-755-4, consultado el 28 de abril de 2023
12. Raman, Rajeev; Rao, Satti Srinivasa (2003), "Diccionarios y árboles dinámicos sucintos", Automata, Languages ​​and Programming , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 357–368, doi :10.1007/3-540-45061-0_30, ISBN 978-3-540-40493-4, consultado el 28 de abril de 2023
13. Bender, Michael A.; Farach-Colton, Martín; Kuszmaul, John; Kuszmaul, William; Liu, Mingmou (9 de junio de 2022). "Sobre el equilibrio óptimo entre tiempo y espacio para las tablas hash". Actas del 54.º Simposio anual ACM SIGACT sobre teoría de la computación . Nueva York, NY, EE. UU.: ACM. págs. 1284–1297. arXiv : 2111.00602 . doi :10.1145/3519935.3519969. hdl :1721.1/146419. ISBN . 9781450392648.S2CID240354692  .​
14. Li, Tianxiao; Liang, Jingxun; Yu, Huacheng; Zhou, Renfei (2023). "Límites inferiores ajustados de la sonda celular para diccionarios dinámicos y sucintos". arXiv : 2306.02253 [cs.DS].
15. Nadis, Steve (8 de febrero de 2024). "Los científicos encuentran el equilibrio óptimo entre el almacenamiento de datos y el tiempo". Revista Quanta .
16. Pagh, Rasmus (28 de enero de 1998). "Baja redundancia en diccionarios con tiempo de búsqueda en el peor de los casos O(1)". Serie de informes BRICS . 5 (28). doi : 10.7146/brics.v5i28.19434 . ISSN  1601-5355.
17. Pagh, Rasmus (enero de 2001). "Baja redundancia en diccionarios estáticos con tiempo de consulta constante". Revista SIAM de informática . 31 (2): 353–363. doi :10.1137/s0097539700369909. ISSN  0097-5397.
18. Patrascu, Mihai (octubre de 2008). "Succincter". 49.° Simposio anual IEEE sobre fundamentos de la informática de 2008. IEEE. págs. 305–313. doi :10.1109/focs.2008.83. ISBN 978-0-7695-3436-7. Número de identificación del sujeto  257721481.
19. Yu, Huacheng (22 de junio de 2020). "Diccionario sucinto estático de Las Vegas casi óptimo". Actas del 52.º Simposio anual ACM SIGACT sobre teoría de la computación . Nueva York, NY, EE. UU.: ACM. págs. 1389–1401. arXiv : 1911.01348 . doi :10.1145/3357713.3384274. ISBN 9781450369794. Número de identificación del sujeto  207780523.
20. Belazzougui, Djamal. "Hash, desplazar y comprimir" (PDF) .