Estructura de datos sucinta

Estructura de datos que es eficiente tanto para almacenar en memoria como para consultar.

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 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érdidas , las estructuras de datos concisas conservan la capacidad de utilizarlas in situ, sin descomprimirlas primero. Una noción relacionada es la de estructura de datos comprimidos , 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 mismos.

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

• implícito si tomabits de espacio, ${\displaystyle Z+O(1)}$
• conciso si requiere un poco de espacio, y ${\displaystyle Z+o(Z)}$
• compacto si ocupa un poco de espacio. ${\displaystyle O(Z)}$

Por ejemplo, una estructura de datos que utiliza bits de almacenamiento es compacta, los bits son concisos, los bits también son concisos y los bits están implícitos. ${\displaystyle 2Z}$ ${\displaystyle Z+{\sqrt {Z}}}$ ${\displaystyle Z+\lg Z}$ ${\displaystyle Z+3}$

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 indexables 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 sucintas, incluidos árboles binarios , árboles -arios y conjuntos múltiples , ^[2] así como árboles y matrices de sufijos . ^[3] El problema básico es almacenar un subconjunto de un universo , generalmente representado como una matriz de bits donde iff. Un diccionario indexable admite los métodos habituales en 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 aparición de . ${\displaystyle \mathbf {rank} _{q}(x)}$ ${\displaystyle q}$ ${\displaystyle x}$ ${\displaystyle \mathbf {select} _{q}(x)}$ ${\displaystyle x}$ ${\displaystyle q}$

Hay una representación simple ^[4] que utiliza bits de espacio de almacenamiento (la matriz de bits original y una estructura auxiliar) y admite clasificación 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 bits se divide en bloques grandes de tamaño de bits y pequeños bloques de tamaño de bits. 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 bloques pequeños que contiene. La diferencia aquí es que solo necesita bits 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 tanto, esta tabla ocupa un total de bits. Luego se puede utilizar una tabla de búsqueda que almacene la respuesta a cada consulta de clasificación posible en una cadena de bits de longitud para ; esto requiere poco espacio de almacenamiento. Por lo tanto, dado que cada una de estas tablas auxiliares ocupa espacio, esta estructura de datos admite consultas de clasificación 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 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 el número de bits establecidos en los bloques pequeños. Esto suele ser beneficioso, ya que las estructuras de datos concisas encuentran su uso en grandes conjuntos de datos, en cuyo caso los errores de caché se vuelven mucho más frecuentes y aumentan las posibilidades de que la tabla de búsqueda sea expulsada de los cachés de CPU más cercanos. ^[5] Las consultas de selección se pueden admitir fácilmente realizando una búsqueda binaria en la misma estructura auxiliar utilizada para la clasificación ; sin embargo, esto lleva tiempo en el peor de los casos. Se puede utilizar una estructura más complicada que utiliza 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 la notación que dominan antes de que cualquier ventaja asintótica se haga evidente; Las implementaciones que utilizan operaciones de palabras anchas 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 observando que hay distintos subconjuntos de (o cadenas binarias de longitud con exactamente unos) y, por lo tanto, existe un límite inferior teórico de la información para el número de bits necesarios para almacenar . Existe un diccionario sucinto (estático) que alcanza este límite, es decir, utilizando el espacio. ^[8] Esta estructura se puede ampliar para admitir consultas de clasificación y selección y ocupa espacio. ^{[2] Sin embargo, las consultas} de clasificación correcta en esta estructura se limitan a los elementos contenidos en el conjunto, de forma análoga a cómo funcionan las funciones hash perfectas mínimas. Este límite se puede reducir a una compensación de espacio/tiempo reduciendo el espacio de almacenamiento del diccionario para que las consultas tomen 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 clasificación (pero no selección) que utilice menos de bits. Un diccionario de este tipo 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 sucintas

Una tabla hash sucinta, también conocida como diccionario desordenado sucinto, es una estructura de datos que almacena claves de un universo utilizando bits de espacio 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, entonces se la denomina dinámica y, en caso 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 dinámica y sucinta se debió a Raman y Rao en 2003. ^[12] En el caso de , su solución utiliza bits de espacio. Posteriormente, se demostró que este límite espacial podía mejorarse a bits para cualquier número constante de logaritmos ^[13] y poco después este límite también era óptimo. ^{[14] [15]} La última solución admite todas las operaciones en el peor de los casos en tiempo constante 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 estática y sucinta se debió a Pagh en 1999. ^{[16] [17]} En el caso de , 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 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 ³² = 4 GiB de datos es una cadena muy larga, y 2 ⁶⁴ = 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; luego, estos se pueden colocar uno tras otro. Esto permite ser eficiente a continuación, 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 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 ahorran espacio. Un enfoque alternativo es la separación fuera de banda: los elementos pueden simplemente colocarse uno tras otro, sin delimitadores. Luego, los límites de los elementos se pueden almacenar como una secuencia de longitud, o mejor, compensaciones en esta secuencia. Alternativamente, se codifica junto con él una cadena binaria separada que consta de 1 en las posiciones donde comienza un elemento y 0 en el resto. 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 requiere 2 espacios Z , 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 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 . En el caso de las grandes , se trata de ; por lo tanto, necesitamos al menos unos bits para codificarlo. Por lo tanto, un árbol binario sucinto ocuparía sólo 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}$

Ver también

• Función hash mínima perfecta
• Argumentos de conocimiento sucintos y no interactivos

Referencias

1. Jacobson, GJ (1988). Estructuras de datos estáticas sucintas (tesis doctoral). Pittsburgh, PA: Universidad Carnegie Mellon.
2. Raman, R.; V. Raman; SS Rao (2002). "Diccionarios indexables sucintos con aplicaciones para codificar conjuntos múltiples y árboles k-arios". 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). "Comprimir estructuras de datos concisas dentro de 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.
4. 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.
5. González, R.; S. Grabowski; V. Mäkinen; G. Navarro (2005). "Implementación práctica de consultas de clasificación y selección" (PDF) . Volumen de actas del póster del cuarto taller sobre algoritmos experimentales y eficientes (WEA) . págs. 27–38.
6. Clark, David (1996). Árboles de palmaditas compactos (PDF) (tesis doctoral). Universidad de Waterloo.
7. Vigna, S. (2008). "Implementación general de consultas de clasificación/selección" (PDF) . Algoritmos experimentales . Apuntes de conferencias sobre 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. S2CID  13963489.
8. Brodnik, A.; J. I Munro (1999). «Membresía en tiempo constante y espacio casi mínimo» (PDF) . SIAM J. Computación . 28 (5): 1627-1640. CiteSeerX 10.1.1.530.9223 . doi :10.1137/S0097539795294165. 
9. Pătraşcu, M. (2008). "Resumen" (PDF) . Fundamentos de la Informática, 2008. FOCS'08. IEEE 49º Simposio Anual de IEEE sobre . págs. 305–313.
10. Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano (4 de enero de 2009). "Hash perfecto mínimo 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: Sociedad de Matemáticas Industriales y Aplicadas: 785–794. doi : 10.1137/1.9781611973068.86 . ISBN 978-0-89871-680-1.
11. Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (enero de 2023), "Tight Bounds for Monotone Minimal Perfect Hashing", Actas del Simposio anual ACM-SIAM de 2023 sobre algoritmos discretos (SODA) , Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas, págs. , arXiv : 2207.10556 , doi :10.1137/1.9781611977554.ch20, ISBN 978-1-61197-755-4, recuperado el 28 de abril de 2023
12. Raman, Rajeev; Rao, Satti Srinivasa (2003), "Árboles y diccionarios dinámicos sucintos", Autómatas, lenguajes y programación , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 357–368, doi :10.1007/3-540-45061-0_30, ISBN 978-3-540-40493-4, recuperado el 28 de abril de 2023
13. Bender, Michael A.; Farach-Colton, Martín; Kuszmaul, Juan; Kuszmaul, William; Liu, Mingmou (9 de junio de 2022). "Sobre la compensación óptima 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, Estados Unidos: ACM. págs. 1284-1297. arXiv : 2111.00602 . doi :10.1145/3519935.3519969. hdl :1721.1/146419. ISBN 9781450392648. S2CID  240354692.
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 un equilibrio óptimo entre tiempo y almacenamiento de datos". Revista Quanta .
16. Pagh, Rasmus (28 de enero de 1998). "Baja redundancia en diccionarios con O (1) peor tiempo de búsqueda de casos". 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 Computación . 31 (2): 353–363. doi :10.1137/s0097539700369909. ISSN  0097-5397.
18. Patrascu, Mihai (octubre de 2008). "Resumen". 2008 49º Simposio anual del IEEE sobre fundamentos de la informática . IEEE. págs. 305–313. doi :10.1109/focs.2008.83. ISBN 978-0-7695-3436-7. S2CID  257721481.
19. Yu, Huacheng (22 de junio de 2020). "Diccionario sucinto estático casi óptimo de Las Vegas". Actas del 52º Simposio Anual ACM SIGACT sobre Teoría de la Computación . Nueva York, NY, Estados Unidos: ACM. págs. 1389-1401. arXiv : 1911.01348 . doi :10.1145/3357713.3384274. ISBN 9781450369794. S2CID  207780523.
20. Belazzougui, Djamal. "Hash, desplazar y comprimir" (PDF) .