♏️ 👧 👩🏽‍🏭 Gatos en cajas o estructuras de datos compactas 🙋🏿 ☀️ 🖇️

imagen

¿Qué debo hacer si el árbol de búsqueda ha crecido a toda la RAM y está a punto de enraizar racks vecinos en la sala de servidores? ¿Qué hacer con un índice invertido que consume recursos? ¿Debo conectarme con el desarrollo de Android si el usuario recibe "Memoria del teléfono llena" y la aplicación es solo la mitad de la carga de un contenedor importante?

En general, ¿es posible comprimir la estructura de datos para que ocupe mucho menos espacio, pero no pierda sus ventajas inherentes? De modo que el acceso a la tabla hash sigue siendo rápido y el árbol equilibrado conserva sus propiedades. Si puedes! Para esto, apareció la dirección de la informática "Estructuras de datos sucintas", explorando la representación compacta de las estructuras de datos. Se ha estado desarrollando desde finales de los años 80 y en este momento está en su mejor momento en la gloria del big data y la alta carga.

Mientras tanto, ¿habrá un héroe en Habr que pueda volver a hablar tres veces seguidas?
[səkˈsɪŋkt]?

Puerta al mundo de la compacidad.

Entonces, una estructura de datos se considera compacta (sucinta) si:

Ocupa varios bits cerca del límite inferior teórico de la información.
No requiere desembalaje preliminar para su uso completo.

Esto significa que los algoritmos de compresión sin pérdida no tienen nada que ver con estructuras de datos compactas. Después de todo, implican la restauración de datos desde un estado comprimido para su procesamiento.

Las implementaciones familiares, "convencionales" de gráficos, tablas hash y otras cosas tampoco son buenas. Tome al menos punteros a elementos secundarios en el árbol de búsqueda. Se comen lugares decentes: $O (MN)$ donde $M$ - la longitud del puntero, y $N$ - el número de nodos en el árbol. Pero la implementación sucinta del árbol nos permite mejorar el comportamiento asintótico para $2N + o (N)$ que está cerca del límite inferior teórico $2N - Θ (log N)$ para madera de $N$ nodos Con longitud de puntero $M = 8$ byte esto significa pasar de $O (8N)$ a un orden completamente diferente de asintóticos, solo $2N$ considerando que $o (N)$ - valor insignificante en relación con $N$ .

Las estructuras de datos compactas (sucintas) son representaciones comprimidas para vectores de bits, conjuntos múltiples, gráficos planos y otras estructuras clásicas favoritas. A menudo son estáticos, se construyen una vez y no cambian durante el uso. Hay excepciones: estructuras sucintas con operaciones rápidas de agregar y quitar elementos.

La mayoría de las estructuras compactas se basan en el concepto del denominado diccionario indexable compacto. Este es un caso especial de un mapa de bits (mapa de bits, conjunto de bits). El mapa de bits en sí mismo es ideal para verificar si los elementos están en un conjunto determinado. Si se incluye un elemento en un conjunto, el valor de bit en un índice dado se establece en 1; de lo contrario, se restablece a 0. Un ejemplo vital es el inode-bitmap ext4, UFS y otros sistemas de archivos Unix. Almacena datos sobre qué entradas en la tabla de inodo están ocupadas y cuáles están libres.

Un diccionario indexable compacto es el mismo mapa de bits, pero complementado por dos operaciones: clasificar y seleccionar. Estas operaciones son los elefantes sobre los que descansa el mundo sucinto. En términos generales, el rango es un recuento del número de elementos, y select es una búsqueda de un elemento:

$rank_x (i)$ devuelve el número de bits igual a $x$ cuyos índices se encuentran en un segmento $[0; i]$ . Desde $x$ - el valor del bit, entonces puede ser igual exclusivamente a 0 o 1.
$select_x (j)$ índice de devoluciones $j$ poco igual a $x$ . El sentido común dice que no hay ocurrencia cero, solo hay la primera. Por lo tanto $ en línea $ j> 0 $ en línea $ : el cálculo se realiza desde uno. También $j$ no puede exceder el número total de bits en el diccionario igual a $x$ .

Supongamos que tenemos un diccionario indexable en el que se establecen 4 de los 7 bits. Entonces $rank_1$ y $select_1$ tomará los siguientes valores:

Un ejemplo de diccionario indexable y cálculo para él. $rank_1$ , $select_1$ .

Un lector atento notará que select es el inverso del rango. Si $rango_1 (5) = 4$ entonces $select_1 (4) = 5$ .

Alguien tuvo deja vu a la vista de $rango_1 (i)$ ? Y todo porque esta operación generaliza el peso de Hamming: el número de caracteres distintos de cero en la secuencia. Para secuencias binarias, el peso de Hamming también se llama popcount (conteo de población).

La clasificación / selección también es aplicable para bits descartados. Aquí hay un ejemplo de cálculo $rank_0$ y $select_0$ para bits iguales a 0:

Un ejemplo de un diccionario indexable compacto y su cálculo. $rank_0$ , $select_0$ .

Vi un árbol en bitiks

¡Usamos este conocimiento para construir un árbol de prefijos compacto! Los árboles de prefijos son buenos para encontrar cadenas por prefijo. Con su ayuda, a menudo se implementa una lista desplegable de sugerencias de búsqueda (sjest). El enfoque para la succinctización del árbol de prefijos es extremadamente generalizado y al máximo demuestra todas las pasas de las estructuras compactas. A diferencia de un árbol binario, para el cual se derivan fórmulas particulares que interfieren con la imagen general.

Tres métodos de representación compacta de árboles son los más populares:

BP (paréntesis equilibrados): secuencias de paréntesis equilibradas.
DFUDS (secuencia de grados unarios de profundidad primero): una secuencia de nodos codificados por unidad ordenados por búsqueda de profundidad.
LOUDS (secuencias de grados unarios ordenados por nivel): secuencias de nodos codificados por unidad ordenados por nivel.

¿Cuál es la cadena lógica sospechosa de traducir "grado unario" a "nodo codificado único"? Pues bien. El grado unario en estos nombres significa una forma de codificar nodos de árbol con una secuencia de unidades de acuerdo con el número de nodos secundarios, siempre con un cero en el avance.

Estos tres métodos para representar árboles están unidos por la presencia de operaciones rápidas: encontrar un padre; encuentra el primer descendiente; encuentra el último descendiente; Encuentra los nodos adyacentes izquierdo y derecho. La posibilidad fundamental y la efectividad de otras operaciones difieren de un método a otro.

Detengámonos en el método LOUDS. Habiéndolo entendido, no será difícil tratar con los otros dos. ¡Además, el año pasado, los árboles LOUDS celebraron su 30 cumpleaños! Se implementan operaciones útiles adicionales para árboles LOUDS en $O (1)$ : encuentra el número de descendientes del nodo; calcular el número descendiente del nodo entre todos sus descendientes (primer descendiente, segundo, $i$ th, etc.); encontrar $i$ th descendencia. La desventaja de LOUDS es la falta de un algoritmo efectivo para contar el número de nodos de subárbol.

La esencia del método es simple: almacenar las claves de los nodos del árbol y toda la información valiosa en una matriz regular, y representar la estructura del árbol como una secuencia de bits. Total tenemos dos estructuras estáticas. Pero no es necesario asignar memoria para punteros a nodos de árbol: las transiciones entre ellos se implementan mediante fórmulas con el uso activo de rango / selección.

Advertencia, árbol de prefijos:

Árbol de prefijos listo para la compresión utilizando el método LOUDS.

Prepare el árbol para su presentación en forma binaria:

Adjunte el árbol a la raíz falsa. Él desempeñará su papel muy pronto.
Numeramos todos los nodos del árbol, nivel por nivel, de izquierda a derecha, como en BFS (búsqueda de amplitud). La raíz falsa se ignora y la real se indexa por cero.
Codificar los nodos. El nodo del árbol está codificado por una secuencia de unidades que corresponden a descendientes directos, más cero. Si el nodo tiene cuatro hijos, se codifica como 11110 y, si no tiene ninguno, como 0. La raíz falsa se codifica primero. Tiene un solo descendiente, por lo que su código es 10.

Un árbol de prefijos con nodos numerados. Los nodos están codificados.

En el proceso de recorrido de árbol de nivel por nivel, se forma un diccionario indexable compacto: una secuencia de bits de nodos codificados pegados de arriba a abajo y de izquierda a derecha. Tenemos una secuencia de 21 bits. Por cierto, se llama LBS (LOUDS Bit String).

Diccionario indexable compacto para árbol de prefijos.

Se construye el árbol de prefijos LOUDS compacto. LBS para madera con $N$ nodos (falso no cuenta) toma $2N + 1$ poco Lo más interesante sigue siendo: las fórmulas para atravesar un árbol convertido en un mapa de bits.

Busca el primer hijo . Transición desde un nodo $i$ a su primer nodo hijo se lleva a cabo de acuerdo con la fórmula:

$firstChild (i) = select_0 (i + 1) - i$

$i$ - este es el número de nodo en la placa anterior colocada en púrpura.

Encuentre el primer descendiente del nodo con el índice 3 (la letra "a"):

$firsthild (3) = select_0 (3 + 1) - 3 = select_0 (4) - 3 = 9 - 3 = 6$

El primer nodo hijo está en el índice 6, y esta es la letra "k". Aplicamos la fórmula para la raíz del árbol:

$firstChild (0) = select_0 (0 + 1) - 0 = select_0 (1) = 1$

Encontramos una hoja con el índice 1, la letra "y". ¡Converge! Quedó claro por qué se necesitaba una raíz falsa: por la magia de los nodos de indexación. Para evitar errores extraños antes de pasar a los descendientes del nodo $i$ Sería bueno saber el número de estos descendientes. De hecho, para las hojas del árbol, lo cual no es sorprendente, la fórmula da un resultado inadecuado. Para encontrar el siguiente descendiente después del primero, debe agregar 1. A su índice, esto es lógico porque los descendientes de un nodo siempre están cerca, sin espacios. Pero al iterar sobre ellos, debe detenerse a tiempo: determine qué descendiente se considera el último.

Buscar el último descendiente de un nodo $i$ pasa en dos etapas: determinar el índice de la última unidad en el código de nodo: es el que designa el descendiente dado; y luego determinar el índice del niño mismo:

$lastChildPos (i) = select_0 (i + 2) -1$

Habiendo recibido el índice de la última unidad en el código de nodo, es necesario verificar que el bit en este índice esté realmente establecido. Si no, entonces la conclusión se sugiere a sí misma: este es un nodo sin descendientes, una hoja. Si el bit está configurado, entonces continúe:

$lastChild (i) = rank_1 (lastChildPos (i) -1)$

Encuentre el último descendiente del nodo 2 (la letra "k").

$lastChildPos (2) = select_0 (2 + 2) -1 = select_0 (4) -1 = 9-1 = $$

El bit en el índice 8 es 1, por lo tanto, el nodo 2 no es una hoja, y podemos encontrar el índice de su último hijo:

$lastChild (i) = rank_1 (8-1) = 5$

El número de descendientes. La forma más sencilla de determinar el número de descendientes es restar el índice de su primer descendiente del índice del último descendiente del nodo y sumar 1:

$childrenCount (i) = lasthild (i) - firsthild (i) + 1$

Pero supongamos que el nodo $i$ hay un nodo vecino $i + 1$ ubicado en el mismo nivel de árbol que $i$ . Entonces el número de descendientes $i$ se puede definir como la diferencia entre los índices de los primeros descendientes de nodos $i + 1$ y $i$ :

$childrenCount (i) = firsthild (i + 1) - firsthild (i)$

Los descendientes del nodo también se numeran secuencialmente. Si el primer descendiente $i$ Es eso $j$ entonces el segundo $j + 1$ y así sucesivamente hasta el descendiente de un nodo vecino a este nivel $i + 1$ (si hay)

El número de descendientes de la hoja "y" con el índice 1 es probablemente cero:

$childrenCount (1) = (select_0 (2 + 1) - 2) - (select_0 (1 + 1) - 1) = 3 - 3 = 0$

Búsqueda principal de un nodo $i$ organizado por la fórmula:

$parent (i) = rank_0 (select_1 (i + 1) - 1) -1$

Lo usaremos para buscar el padre del nodo 6 (la letra "k"):

$parent (6) = rank_0 (select_1 (7) - 1) -1 = rank_0 (9) -1 = 3$

Este es el nodo 3, la letra "a".

Con el conocimiento de las fórmulas para los índices de padres e hijos, no es difícil recorrer todo el árbol. Lo principal es no olvidarse del procesamiento de las condiciones límite para la raíz y las hojas.

Un par de kopecks sobre los métodos BP y DFUDS. Ambos métodos tienen asintóticas espaciales: $2N + o (N)$ poco para la madera de $N$ nodos, y ambos son similares en representación de un nodo de árbol en forma de corchetes de apertura y cierre.

BP (paréntesis equilibrados) convierte un árbol en una secuencia de paréntesis, un par para cada nodo. Para hacer esto, el árbol se profundiza; cada nodo se visita dos veces. En la primera visita, se registra el corchete de apertura, en la segunda visita, el corchete de cierre. Entre ellos hay paréntesis de niños.

Es conveniente representar la secuencia de corchetes en forma de mapa de bits, donde 1 es el corchete de apertura y 0 es el corchete de cierre. Todas las fórmulas para trabajar con BP se agudizan para una búsqueda rápida. A diferencia de LOUDS, BP le permite calcular rápidamente el tamaño de un subárbol y determinar el ancestro común más cercano de dos nodos. Pero encontrar $i$ -th descendiente es mucho más complicado que en LOUDS.

DFUDS (secuencia de primer grado unario en profundidad) es similar a BP y LOUDS. Con BP, combina una caminata de árbol en profundidad y su representación de soporte. Y el principio de paréntesis es el mismo que el principio de codificación de nodos en LOUDS. Antes de atravesar el árbol, agregamos un paréntesis de apertura a la secuencia de paréntesis de antemano. Luego, al atravesar nodos, escribimos corchetes abiertos de acuerdo con el número de descendientes, más uno de cierre. Resulta que la localidad de almacenamiento de descendientes en DFUDS es más alta que la de BP. El cálculo del tamaño del subárbol y la búsqueda del ancestro común más cercano se llevan a cabo para $O (1)$ . Pero determinar la altura del subárbol y encontrar el padre en $j$ nivel - operaciones pesadas para DFUDS.

Para mayor claridad, comparamos los métodos LOUDS, BP y DFUDS utilizando el mini-árbol como ejemplo.

Los nodos del árbol están numerados en naranja como si caminaran en ancho (para LOUDS), azul - como cuando caminan en profundidad (para BP y DFUDS).

Vistas de árbol LOUDS, BP y DFUDS.

No se sorprenda si ve diferencias en las fórmulas en las obras en inglés. Entre los matemáticos, hay amantes de la indexación a partir de uno. Y algunos desarrolladores consideran que las palabras rango y rango son consonantes, por lo que clasifican la mitad del tiempo. $[0; i)$ . Debido a la necesidad de mantener la simetría de rango / selección, calculan $select (i)$ como $select (i + 1)$ . Pero algunas fórmulas en esta forma parecen más cortas.

Matriz dispersa: agite pero no mezcle

Una matriz dispersa es otra estructura creada literalmente para la compresión. El tamaño de una matriz de este tipo es a veces un orden de magnitud mayor que el número de elementos rellenos. Y los elementos vacíos toman un valor predeterminado o están marcados con algo como nulo. Una matriz dispersa se cierne en el horizonte cuando sea necesario para almacenar muchos objetos y las relaciones entre ellos. Los gráficos de amigos en las redes sociales, los algoritmos de clasificación de motores de búsqueda, las tablas tipo Excel, los simuladores de circuitos eléctricos con miles de millones de transistores en un chip me vienen a la mente de inmediato.

A menudo, estas matrices son ciclópeas en estilo lovecraftiano, con una implementación ingenua que no encajan en la RAM, permaneciendo prácticamente vacías. Dependiendo de los requisitos de memoria y velocidad, las matrices dispersas se convierten en tablas hash mucho más compactas, listas de adyacencia, árboles binarios ... o sucintas.

Digamos que tenemos una escasa variedad de cadenas. Adjunte un diccionario indexable compacto. ¿Qué le dará?

Escasa matriz con un mapa de bits.

Ahora, sin acceder directamente a la matriz original, es fácil verificar si un elemento está presente en él en el índice de interés. Nada impide reducir la matriz original al descartar todos los elementos sin rellenar:

Una matriz sin elementos vacíos.

Calcular un índice en una matriz comprimida. Después de verificar la presencia de un elemento, sería bueno acceder a su valor en la matriz original, es decir, asignar el índice $i$ en índice indexado del diccionario $j$ en una matriz comprimida No sorprende que se use el rango para esto:

$j = rango_1 (i) -1$

Veamos cómo están las cosas con el octavo elemento: $mapa de bits [8] = 0$ . Entonces, en la matriz original no existe tal elemento. ¿Qué pasa con el elemento 7? $mapa de bits [7] = 1$ . Obtenga su valor: $rango_1 (7) - 1 = 3-1 = 2$ . En el índice 2 es "ir".

Cálculo del índice en la matriz fuente. ¡Seguramente en la matriz necesitarás buscar elementos por valor! Si los datos no están ordenados, la búsqueda se reduce a la búsqueda de $O (N)$ donde $N$ - el número de elementos no vacíos. Por artículo encontrado $j$ puede necesitar obtener su índice $i$ como si la matriz no estuviera reducida. Para hacer esto, use select, el inverso de rango:

$i = select_1 (j + 1)$

Por ejemplo, busque la línea "C ++". En una matriz compacta, se encuentra en el índice 0. Y su índice en la matriz original es $select_1 (0 + 1) = 3$ .

Ya en un ejemplo con líneas notables ahorros de memoria. Si la matriz está diseñada para almacenar clases con muchos campos, los ahorros se vuelven mucho más significativos. Además, la búsqueda en una matriz compacta es más rápida que en una amplia y dispersa: el procesador la almacena mejor en caché. Es más probable que un diccionario indexado en bits se ajuste a una línea de caché que una matriz regular de números, cadenas o tipos personalizados elegantes.

Por supuesto para el almacenamiento $2 ^ {30}$ El método de los elementos descritos no es adecuado. Su aplicabilidad termina donde comienzan los problemas con el crecimiento del índice. Pero, por supuesto, este método de compresión de matrices y sus variaciones tiene su propio nicho. Un ejemplo cotidiano es la implementación del protocolo BitTorrent. El mapa de bits contiene información sobre los segmentos de archivo descargados, y los pares intercambian los índices de sus segmentos. Un ejemplo de espacio son las opciones de transmisión de datos segmentados utilizados por los rovers, Voyagers y la estación New Horizons, arando los espacios abiertos trans-Neptuno.

Los ejemplos descritos de succinctización de un árbol de prefijos y una matriz dispersa se basan en una base común. Se basa en una creencia inquebrantable en la efectividad de las operaciones de rango / selección. Sin ella, toda la teoría de estructuras compactas pero suficientemente rápidas irrumpe en las costuras. La idoneidad del uso de estructuras compactas fuera de las disertaciones depende del rango y la velocidad de selección.

De hecho, estas operaciones se pueden implementar de manera extremadamente eficiente: rango - para $O (1)$ ; seleccione - para $O (log (log N))$ , que también es casi constante. Y, por supuesto, no está exento de algunos trucos. Y dado que debe haber una leve subestimación en cualquier trabajo con una trama complicada, me detendré aquí.

Hechos interesantes

¿Cuál es el límite inferior teórico de los recursos ocupados en términos de teoría de la información? Digamos que una estructura de datos almacena una gran cantidad de $N$ elementos Para identificarlos sin colisiones, necesita una cantidad de bits, no menos de $X = log_2N$ . $X$ y existe ese límite muy bajo determinado por la fórmula de Hartley. En algunos casos especiales, al tener información sobre la naturaleza de los datos almacenados, la estructura se puede comprimir de manera aún más eficiente.

¿Es la cadena sucinta una estructura de datos? Contiene $N$ caracteres y termina con un carácter ASCII nulo. Entonces toma $N + 1$ lugares, y por lo tanto ... ella es sucinta, y más específicamente, ¡implícita! Lo que nos lleva a la siguiente pregunta.

¿Son todas las estructuras sucintas igualmente compactas? El área de investigación sucinta define hasta tres tipos de estructuras compactas que difieren en complejidad espacial:

compacto $O (N)$ . Complejidad lineal de $N$ — . «» . . , : . , . , 0 , . $O(2N)$ ( 2 , ) select .
succinct — $N + o(N)$ . — , succinct data structures . : (Pascal string), . $N + log(N)$ .
implicit — $N + O(1)$ . , . : (heap) . $N + 1$ .

? , , . succinct- . , -, FM-, RMQ (range minimum queries), LCP (longest common prefix), , succinct'. -.

, , . Y no solo eso. , , X, .

succinct — , «- ». Succinct — . , , succinct. , . (IME) Google, . MAPS.ME succinct- .

, . ., 97 % -: . 3 %.

Que sigue

, succinct:

, :

Gatos en cajas o estructuras de datos compactas

Puerta al mundo de la compacidad.

Vi un árbol en bitiks

Matriz dispersa: agite pero no mezcle

Hechos interesantes

Que sigue

More articles: