Estructura de datos concisa

En informática , una estructura de datos sucinta es aquella que utiliza una cantidad de espacio cercana al límite inferior teórico de la información , pero que (a diferencia de otras representaciones comprimidas) permite realizar consultas eficientes. El concepto fue introducido originalmente por Jacobson ^{[ 1 ]} para codificar vectores de bits , árboles (sin etiquetar) y grafos planares . A diferencia de los algoritmos generales de compresión de datos sin pérdida , las estructuras de datos sucintas conservan la capacidad de utilizarlas directamente, sin necesidad de descomprimirlas previamente. Un concepto relacionado es el de estructura de datos comprimida , en el que el tamaño de los datos almacenados o codificados depende igualmente del contenido específico de los mismos.

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

• implícito si se toma${\displaystyle Z+O(1)}$trozos de espacio,
• sucinto si hace falta${\displaystyle Z+o(Z)}$trozos de espacio, y
• compacto si se necesita${\displaystyle O(Z)}$trozos de espacio.

Por ejemplo, una estructura de datos que utiliza${\displaystyle 2Z}$El almacenamiento de bits es compacto,${\displaystyle Z+{\sqrt {Z}}}$bits es conciso,${\displaystyle Z+\lg Z}$bits también es sucinto, y${\displaystyle Z+3}$bits es implícito.

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

Los diccionarios indexables sucintos, también llamados diccionarios de rango/selección , forman la base de varias técnicas de representación sucinta, incluidos los árboles binarios ,${\displaystyle k}$árboles y multiconjuntos -arios , ^{[ 2 ]} así como árboles y arreglos de sufijos . ^{[ 3 ]} El problema básico es almacenar un subconjunto${\displaystyle S}$de un universo${\displaystyle U=[0\dots n)=\{0,1,\dots ,n-1\}}$, generalmente representado como una matriz de bits${\displaystyle B[0\dots n)}$dónde${\displaystyle B[i]=1}$si y solo si${\displaystyle i\in S.}$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:

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

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

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

Existe una representación simple ^{[ 4 ]} que utiliza${\displaystyle n+o(n)}$bits de espacio de almacenamiento (la matriz de bits original y una${\displaystyle o(n)}$estructura auxiliar) y admite clasificación y selección en tiempo constante. Utiliza una idea similar a la de las consultas de mínimo de rango ; hay un número constante de recursiones antes de detenerse en un subproblema de tamaño limitado. La matriz de bits${\displaystyle B}$está dividido en grandes bloques de tamaño${\displaystyle l=\lg ^{2}n}$trozos y pequeños bloques de tamaño${\displaystyle s=\lg n/2}$bits. Para cada bloque grande, el rango de su primer bit se almacena en una tabla separada.${\displaystyle R_{l}[0\dots n/l)}$; cada entrada de este tipo toma${\displaystyle \lg n}$bits para un total de${\displaystyle (n/l)\lg n=n/\lg n}$bits de almacenamiento. Dentro de un bloque grande, otro directorio${\displaystyle R_{s}[0\dots l/s)}$almacena el rango de cada uno de los${\displaystyle l/s=2\lg n}$pequeños bloques que contiene. La diferencia aquí es que solo necesita${\displaystyle \lg l=\lg \lg ^{2}n=2\lg \lg n}$bits para cada entrada, ya que solo es necesario almacenar las diferencias con respecto al rango del primer bit en el bloque grande contenedor. Por lo tanto, esta tabla toma un total de${\displaystyle (n/s)\lg l=4n\lg \lg n/\lg n}$bits. Una tabla de búsqueda${\displaystyle R_{p}}$Luego se puede utilizar que almacena la respuesta a cada posible consulta de clasificación en una cadena de bits de longitud${\displaystyle s}$para${\displaystyle i\in [0,s)}$; esto requiere${\displaystyle 2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)}$bits de espacio de almacenamiento. Por lo tanto, dado que cada una de estas tablas auxiliares ocupa${\displaystyle o(n)}$espacio, esta estructura de datos admite consultas de clasificación en${\displaystyle O(1)}$tiempo y${\displaystyle n+o(n)}$trozos de espacio.

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

• ${\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${\displaystyle R_{p}}$puede reemplazarse 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 se utilizan en grandes conjuntos de datos, en cuyo caso los fallos de caché se vuelven mucho más frecuentes y las posibilidades de que la tabla de búsqueda sea desalojada de las cachés de CPU más cercanas aumentan. ^{[ 5 ]} Las consultas de selección se pueden admitir fácilmente realizando una búsqueda binaria en la misma estructura auxiliar utilizada para el rango ; sin embargo, esto lleva${\displaystyle O(\lg n)}$tiempo en el peor de los casos. Una estructura más complicada que utiliza${\displaystyle 3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)}$Se 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 el${\displaystyle O(\cdot )}$notación que domina antes de que se haga evidente cualquier ventaja asintótica; las implementaciones que utilizan operaciones de palabras amplias y bloques alineados a palabras suelen tener un mejor rendimiento en la práctica. ^{[ 7 ]}

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

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

La primera tabla hash estática sucinta se debe a Pagh en 1999. ^{[ 17 ] [ 18 ]} En el caso donde${\displaystyle n={\text{poly}}(m)}$, su solución utiliza espacio${\displaystyle {\mathcal {B}}(m,n)+O(m(\log \log m)^{2}/\log m)}$bits, y admite consultas de tiempo constante en el peor de los casos . Este límite se mejoró posteriormente a${\displaystyle {\mathcal {B}}(m,n)+m/{\text{poly}}\log m}$bits, ^{[ 9 ]} y luego a${\displaystyle {\mathcal {B}}(m,n)+{\text{poly}}\log m}$bits. ^{[ 19 ]} Mientras que las dos primeras soluciones ^{[ 18 ] [ 9 ]} 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${\displaystyle n^{\epsilon }}$, pero esta tabla de búsqueda es independiente del conjunto de elementos que se almacenan. ^{[ 19 ]} Más recientemente, Hu et al. ^{[ 20 ]} idearon una solución que utiliza espacio${\displaystyle {\mathcal {B}}(m,n)+n^{\epsilon }}$al tiempo que admite consultas de tiempo constante en el peor de los casos.

Una cadena con una longitud arbitraria ( cadena Pascal ) ocupa Z + log( Z ) espacio y, por lo tanto, es concisa. Si existe una longitud máxima, lo cual ocurre en la práctica, ya que ^2³² = 4 GiB de datos es una cadena muy larga, y ^2⁶⁴ = 16 EiB de datos es mayor que cualquier cadena en la práctica, entonces una cadena con una longitud también es implícita, ocupando Z + k espacio, 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 consiste en almacenar una longitud y un elemento en cada registro; estos se pueden colocar uno tras otro. Esto permite una búsqueda eficiente del siguiente elemento, pero no la búsqueda del 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 son eficientes en cuanto a espacio. Un enfoque alternativo es la separación fuera de banda: los elementos se pueden colocar simplemente uno tras otro, sin delimitadores. Los límites de los elementos se pueden almacenar como una secuencia de longitud, o mejor, desplazamientos dentro de esta secuencia. Alternativamente, se codifica junto con él una cadena binaria separada que consta de 1s en las posiciones donde comienza un elemento y 0s en todas partes. Dada esta cadena,${\displaystyle seleccionar}$La función puede determinar rápidamente dónde comienza cada elemento, dado su índice. ^{[ 21 ]} Esto es compacto pero no conciso, ya que ocupa 2 Z espacio, que es O( Z ).

Otro ejemplo es la representación de un árbol binario : un árbol binario arbitrario en${\displaystyle n}$Los nodos pueden representarse en${\displaystyle 2n+o(n)}$bits mientras admite 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 una en tiempo constante. El número de árboles binarios diferentes en${\displaystyle n}$nodos es${\displaystyle {\tbinom {2n}{n}}}$${\displaystyle /(n+1)}$Para grandes${\displaystyle n}$, esto es sobre${\displaystyle 4^{n}}$; por lo tanto necesitamos al menos aproximadamente${\displaystyle \log _{2}(4^{n})=2n}$bits para codificarlo. Por lo tanto, un árbol binario sucinto ocuparía solo${\displaystyle 2}$bits por nodo.

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