Gatos em caixas ou estruturas de dados compactas

O que devo fazer se a árvore de pesquisa tiver crescido para toda a RAM e estiver prestes a criar racks vizinhos na sala do servidor? O que fazer com um índice invertido e sedento de recursos? Devo me conectar ao desenvolvimento do Android se o usuário receber "Memória do telefone cheia" e o aplicativo tiver apenas metade da carga de um contêiner importante?

Em geral, é possível compactar a estrutura de dados para ocupar significativamente menos espaço, mas não perder suas vantagens inerentes? Para que o acesso à tabela de hash permaneça rápido e a árvore equilibrada mantenha suas propriedades. Sim você pode! Para isso, surgiu a direção da ciência da computação “Estruturas de dados sucintas”, explorando a representação compacta das estruturas de dados. Está em desenvolvimento desde o final dos anos 80 e, atualmente, está no auge da glória do big data e do highload.

Enquanto isso, haverá um herói em Habr que poderá re-falar três vezes seguidas
[səkˈsɪŋkt]?

Porta para o mundo da compacidade

Portanto, uma estrutura de dados é considerada compacta (sucinta) se:

• Ocupa um número de bits próximo ao limite inferior teórico da informação.
• Não requer desembalagem preliminar para uso total.

Isso significa que algoritmos de compactação sem perdas não têm nada a ver com estruturas de dados compactas. Afinal, eles envolvem a restauração de dados de um estado compactado para processamento.

As implementações familiares e tradicionais de gráficos, tabelas de hash e outras coisas também não são boas. Leve pelo menos ponteiros para elementos filho na árvore de pesquisa. Eles comem lugares decentes: $$$O (MN)$onde $$$M$- o comprimento do ponteiro, e $$$N$- o número de nós na árvore. Mas a implementação sucinta da árvore nos permite melhorar o comportamento assintótico para $$$2N + o (N)$que está próximo do limite inferior teórico $$$2N - Θ (log N)$para madeira de $$$N$nós. Com comprimento do ponteiro $$$M = 8$byte isso significa passar de $$$O (8N)$a uma ordem completamente diferente de assintóticos - apenas $$$2N$, considerando que $$$o (N)$- valor insignificante em relação a $$$N$.

Estruturas de dados compactas (sucintas) são representações compactadas para vetores de bits, multisets, gráficos planares e outras estruturas clássicas favoritas. Muitas vezes, são estáticos, construídos uma vez e não mudam durante o uso. Há exceções - estruturas sucintas com operações rápidas de adição e remoção de elementos.

A maioria das estruturas compactas é baseada no conceito do chamado dicionário indexável compacto. Este é um caso especial de um bitmap (bitmap, bitset). O próprio bitmap é ideal para verificar se os elementos estão em um determinado conjunto. Se um elemento for incluído em um conjunto, o valor do bit em um determinado índice será definido como 1; caso contrário, será redefinido para 0. Um exemplo vital é o inode-bitmap ext4, UFS e outros sistemas de arquivos Unix. Ele armazena dados sobre quais entradas na tabela de inodes estão ocupadas e quais são gratuitas.

Um dicionário indexável compacto é o mesmo bitmap, mas complementado por duas operações: classificar e selecionar. Essas operações são os elefantes sobre os quais repousa o mundo sucinto. Grosso modo, a classificação é uma contagem do número de elementos e select é uma pesquisa por um elemento:

• $$$rank_x (i)$retorna o número de bits igual a $$$x$cujos índices estão em um segmento $$$[0; i]$. Desde $$$x$- o valor do bit, então ele pode ser igual exclusivamente a 0 ou 1.
• $$$select_x (j)$retorna índice $$$j$pouco igual a $$$x$. O senso comum diz que não há ocorrência zero, há apenas a primeira. Portanto,$$ $ inline $ j> 0 $ inline $ : o cálculo é realizado a partir de um. Também $$$j$não pode exceder o número total de bits no dicionário igual a $$$x$.

Suponha que tenhamos um dicionário indexável no qual 4 dos 7 bits estão definidos. Então $$$rank_1$e $$$select_1$assumirá os seguintes valores:

Um exemplo de dicionário indexável e cálculo para ele $$$rank_1$, $$$select_1$.

Um leitor atento perceberá que selecionar é o inverso da classificação. Se $$$rank_1 (5) = 4$então $$$select_1 (4) = 5$.

Alguém teve deja vu ao ver $$$rank_1 (i)$? E tudo porque essa operação generaliza o Peso de Hamming - o número de caracteres diferentes de zero na sequência. Para seqüências binárias, o peso de Hamming também é chamado de contagem pop-up (contagem populacional).

A classificação / seleção também é aplicável aos bits descartados. Aqui está um exemplo de cálculo $$$rank_0$e $$$select_0$para bits iguais a 0:

Um exemplo de um dicionário indexável compacto e cálculo para ele $$$rank_0$, $$$select_0$.

Vi uma árvore em bitiks

Utilizamos esse conhecimento para construir uma árvore de prefixos compacta! Árvores de prefixo são boas para encontrar seqüências de caracteres por prefixo. Com a ajuda deles, uma lista suspensa de dicas de pesquisa (sjest) é frequentemente implementada. A abordagem à sucintificação da árvore de prefixos é extremamente generalizada e, ao máximo, demonstra todas as passas de estruturas compactas. Ao contrário de uma árvore binária, para a qual derivam fórmulas específicas que interferem na imagem geral.

Três métodos de representação compacta de árvores são os mais populares:

• BP (parênteses balanceados) - seqüências de parênteses balanceadas.
• DFUDS (sequência do primeiro grau unário de profundidade) - uma sequência de nós codificados por unidade, classificados por pesquisa de profundidade.
• LOUDS (sequências de graus unários ordenadas por nível) - sequências de nós codificados por unidade, classificados por nível.

Qual é a cadeia lógica suspeita de traduzir "grau unário" em "nó codificado único"? Bem então. Grau unário nesses nomes significa uma maneira de codificar nós da árvore com uma sequência de unidades de acordo com o número de nós filhos, sempre com um zero no trailer.

Esses três métodos de representação de árvores são unidos pela presença de operações rápidas: encontrar um pai; encontre o primeiro descendente; encontre o último descendente; Encontre os nós adjacentes esquerdo e direito. A possibilidade fundamental e a eficácia de outras operações diferem de método para método.

Vamos nos debruçar sobre o método LOUDS. Tendo entendido, não será difícil lidar com os outros dois. Além disso, no ano passado, as árvores do LOUDS comemoraram seu aniversário de 30 anos! Operações úteis adicionais para árvores LOUDS são implementadas em $$$O (1)$: encontre o número de descendentes do nó; calcule o número descendente do nó entre todos os seus descendentes (primeiro descendente, segundo, $$$i$th, etc.); encontrar $$$i$th prole. A desvantagem do LOUDS é a falta de um algoritmo eficaz para contar o número de nós da subárvore.

A essência do método é simples: armazene as chaves dos nós da árvore e todas as informações valiosas em uma matriz regular e represente a estrutura da árvore como uma sequência de bits. Total, temos duas estruturas estáticas. Mas não há necessidade de alocar memória para ponteiros para nós de árvore: as transições entre eles são implementadas usando fórmulas com o uso ativo de classificação / seleção.

Aviso, árvore de prefixo:

Árvore de prefixos pronta para compactação usando o método LOUDS.

Prepare a árvore para apresentação em formato binário:

1. Anexe a árvore à raiz falsa. Ele fará sua parte muito em breve.
2. Nós numeramos todos os nós da árvore, nível por nível, da esquerda para a direita, como no BFS (pesquisa pela primeira vez). A raiz falsa é ignorada e a raiz real é indexada por zero.
3. Codifique os nós. O nó da árvore é codificado por uma sequência de unidades correspondentes aos descendentes diretos, mais zero. Se o nó tiver quatro filhos, ele será codificado como 11110 e, se não houver - como 0. A raiz falsa será codificada primeiro. Ele tem um único descendente, portanto, seu código é 10.

Uma árvore de prefixo com nós numerados. Nós são codificados.

No processo de passagem de árvore nível a nível, um dicionário indexável compacto é formado - uma sequência de bits de nós codificados colados de cima para baixo e da esquerda para a direita. Temos uma sequência de 21 bits. A propósito, ele é chamado LBS (LOUDS Bit String).

Dicionário indexável compacto para árvore de prefixos.

A árvore de prefixos LOUDS compacta é construída. LBS para madeira com $$$N$nós (falso não conta) leva $$ pouco. A coisa mais interessante permanece - fórmulas para atravessar uma árvore transformada em um bitmap.

Procure o primeiro filho . Transição de um nó $$$i$ao seu primeiro nó filho é realizado de acordo com a fórmula:

$$

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

$$$i$- este é o número do nó na placa anterior afixado em roxo.

Encontre o primeiro descendente do nó com o índice 3 (a letra "a"):

$$

$$firstild (3) = selecionar_0 (3 + 1) - 3 = selecionar_0 (4) - 3 = 9 - 3 = 6$$

O primeiro nó filho está no índice 6 e esta é a letra "k". Aplicamos a fórmula para a raiz da árvore:

$$

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

Encontramos uma planilha com o índice 1, a letra “e”. Converge! Ficou claro por que uma raiz falsa era necessária: para a mágica dos nós de indexação. Para evitar erros estranhos antes de passar para os descendentes do nó $$$i$Seria bom descobrir o número desses descendentes. De fato, para as folhas da árvore, o que não é surpreendente, a fórmula fornece um resultado inadequado. Para encontrar o próximo descendente após o primeiro, você precisa adicionar 1. Ao seu índice, isso é lógico, porque os descendentes de um nó estão sempre próximos, sem lacunas. Mas ao iterá-las, é preciso parar a tempo - determinar qual descendente é considerado o último.

Procure o último descendente de um nó $$$i$passa em dois estágios: determinando o índice da última unidade no código do nó - é ele que designa esse filho e, em seguida, determinando o índice da própria criança:

$$

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

Tendo recebido o índice da última unidade no código do nó, é necessário verificar se o bit nesse índice está realmente definido. Caso contrário, a conclusão sugere-se: este é um nó sem descendentes, uma folha. Se o bit estiver definido, prossiga:

$$

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

Encontre o último descendente do nó 2 (a letra "k").

$$

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

O bit no índice 8 é 1, portanto, o nó 2 não é uma folha e podemos encontrar o índice de seu último filho:

$$

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

O número de descendentes. A maneira mais simples de determinar o número de descendentes é subtrair o índice do primeiro descendente do índice do último descendente do nó e adicionar 1:

$$

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

Mas suponha que o nó $$$i$existe um nó vizinho $$$i + 1$localizado no mesmo nível de árvore que $$$i$. Então o número de descendentes $$$i$pode ser definido como a diferença entre os índices dos primeiros descendentes de nós $$$i + 1$e $$$i$:

$$

$$childrenCount (i) = primeiro filho (i + 1) - primeiro filho (i)$$

Os descendentes do nó também são numerados sequencialmente. Se o primeiro descendente $$$i$É isso $$$j$então o segundo - $$$j + 1$e assim por diante até o descendente de um nó vizinho neste nível $$$i + 1$(se houver).

O número de descendentes da folha “e” com o índice 1 é esperado como zero:

$$

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

Pesquisa pai para um nó $$$i$organizado pela fórmula:

$$

$$pai (i) = classificação_0 (selecione_1 (i + 1) - 1) -1$$

Vamos usá-lo para procurar o pai do nó 6 (a letra "k"):

$$

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

Este é o nó 3, a letra "a".

Com o conhecimento das fórmulas para os índices filho e pai, não é difícil contornar a árvore inteira. O principal é não esquecer o processamento das condições de contorno para a raiz e as folhas.

Alguns elogios sobre os métodos BP e DFUDS. Ambos os métodos têm assintóticos espaciais - $$$2N + o (N)$broca para madeira de $$$N$nós, e ambos são semelhantes na representação de um nó de árvore na forma de colchetes de abertura e fechamento.

BP (parênteses balanceados) converte uma árvore em uma sequência de colchetes, um par para cada nó. Para fazer isso, a árvore vai fundo; cada nó é visitado duas vezes. Na primeira visita, o colchete de abertura é registrado, na segunda visita - o colchete de fechamento. Entre eles estão os parênteses das crianças.

É conveniente representar a sequência de colchetes na forma de um bitmap, onde 1 é o colchete de abertura e 0 é o colchete de fechamento. Todas as fórmulas para trabalhar com a BP são aprimoradas para uma pesquisa rápida. Diferentemente de LOUDS, o BP permite calcular rapidamente o tamanho de uma subárvore e determinar o ancestral comum mais próximo de dois nós. Mas encontre $$$i$- o descendente é muito mais complicado do que em LOUDS.

DFUDS (sequência do primeiro grau unário de profundidade) é semelhante à BP e ao LOUDS. Com a BP, combina uma caminhada em árvore em profundidade e sua representação entre colchetes. E o princípio dos colchetes é o mesmo que o princípio da codificação de nós no LOUDS. Antes de percorrer a árvore, adicionamos um parêntese de abertura à sequência de colchetes com antecedência. Então, ao atravessar nós, escrevemos colchetes abertos de acordo com o número de descendentes, mais um que fecha. Acontece que a localidade de armazenamento de descendentes no DFUDS é maior que a da BP. O cálculo do tamanho da subárvore e a busca pelo ancestral comum mais próximo são realizados para $$$O (1)$. Mas determinar a altura da subárvore e encontrar o pai no $$$j$nível - operações pesadas para DFUDS.

Para maior clareza, comparamos os métodos LOUDS, BP e DFUDS usando a mini-árvore como exemplo.

Os nós da árvore são numerados em laranja como se estivessem caminhando em largura (para LOUDS), em azul - como quando caminhamos em profundidade (para BP e DFUDS).

Visualizações de árvore LOUDS, BP e DFUDS.

Não se surpreenda se você encontrar diferenças nas fórmulas nos trabalhos em inglês. Entre os matemáticos, há amantes da indexação a partir de um. E alguns desenvolvedores consideram as palavras consoante e consoante, portanto, classificam-na metade do tempo. $$$[0; i)$. Devido à necessidade de manter a simetria da classificação / seleção, eles calculam $$$selecionar (i)$como $$$selecionar (i + 1)$. Mas algumas fórmulas neste formulário parecem mais curtas.

Matriz esparsa: agite, mas não misture

Uma matriz esparsa é outra estrutura criada literalmente para compactação. Às vezes, o tamanho de uma matriz desse tipo é maior que o número de elementos preenchidos. E os elementos vazios assumem um valor padrão ou são marcados com algo como nulo. Uma matriz esparsa aparece no horizonte sempre que necessário para armazenar muitos objetos e os relacionamentos entre eles. Os gráficos de amigos nas redes sociais, algoritmos de classificação de mecanismos de busca, tabelas do tipo Excel, simuladores de circuitos elétricos com bilhões de transistores em um chip imediatamente vêm à mente.

Freqüentemente, essas matrizes são ciclópicas no estilo Lovecraft, com uma implementação ingênua que não cabem na RAM, permanecendo praticamente vazias. Dependendo dos requisitos de memória e velocidade, matrizes esparsas se transformam em tabelas de hash muito mais compactas, listas de adjacências, árvores binárias ... ou sucintas.

Digamos que temos uma matriz esparsa de strings. Anexe um dicionário indexável compacto a ele. O que vai dar?

Matriz esparsa com um bitmap.

Agora, sem acessar diretamente a matriz original, é fácil verificar se um elemento está presente nela no índice de interesse. Nada impede que a matriz original seja reduzida ao eliminar todos os elementos não preenchidos:

Uma matriz sem elementos vazios.

Computando um índice em uma matriz compactada. Após verificar a presença de um elemento, seria bom acessar seu valor na matriz original, ou seja, mapear o índice $$$i$no índice indexado do dicionário $$$j$em uma matriz compactada. Não é surpresa que essa classificação seja usada para isso:

$$

$$j = rank_1 (i) -1$$

Vamos verificar como estão as coisas com o 8º elemento: $$$bitmap [8] = 0$. Portanto, na matriz original não existe esse elemento. E o elemento 7? $$$bitmap [7] = 1$. Obtenha seu valor: $$$rank_1 (7) - 1 = 3-1 = 2$. No índice 2 é "ir".

Cálculo do índice na matriz de origem. Certamente na matriz você precisará procurar elementos por valor! Se os dados não forem classificados, a pesquisa será reduzida para a pesquisa de $$$O (N)$onde $$$N$- o número de elementos não vazios. Para o item encontrado $$$j$pode precisar obter seu índice $$$i$como se a matriz não tivesse sido reduzida. Para fazer isso, use select, o inverso da classificação:

$$

$$i = selecionar_1 (j + 1)$$

Por exemplo, encontre a linha "C ++". Em uma matriz compacta, ela está localizada no índice 0. E seu índice na matriz original é $$$select_1 (0 + 1) = 3$.

Já em um exemplo com linhas notáveis ​​economias de memória. Se a matriz for projetada para armazenar classes com muitos campos, a economia se tornará muito mais significativa. Além disso, a pesquisa em uma matriz compacta é mais rápida do que em uma matriz grande e esparsa: é melhor armazenada em cache pelo processador. É mais provável que um dicionário indexado por bits caiba em uma linha de cache do que uma matriz regular de números, seqüências de caracteres ou tipos personalizados sofisticados.

Claro para armazenamento $$$2 ^ {30}$elementos descritos método não é adequado. Sua aplicabilidade termina onde começam os problemas com o crescimento do índice. Mas é claro que esse método de compactar matrizes e suas variações tem seu próprio nicho. Um exemplo cotidiano é a implementação do protocolo BitTorrent. O bitmap contém informações sobre os segmentos de arquivos baixados e os pares trocam os índices de seus segmentos. Um exemplo de espaço são as opções de transmissão de dados segmentadas usadas pelos rovers, Voyagers e a estação New Horizons, abrindo espaços abertos trans-Netuno.

Os exemplos descritos de sucintificação de uma árvore de prefixos e de uma matriz esparsa são construídos sobre uma base comum. É baseado em uma crença inabalável na eficácia das operações de classificação / seleção. Sem ela, toda a teoria das estruturas compactas, mas rápidas o suficiente, explode nas costuras. A adequação do uso de estruturas compactas fora das dissertações depende da classificação e da velocidade selecionada.

De fato, essas operações podem ser implementadas com extrema eficiência: classificação - por $$$O (1)$; selecione - para $$$O (log (log N))$, que também é quase constante. E, claro, não é sem alguns truques. E como deve haver um discreto eufemismo em qualquer trabalho com um enredo complicado, vou parar por aqui.

Fatos interessantes

Qual é o limite inferior teórico dos recursos ocupados em termos de teoria da informação? Digamos que uma estrutura de dados armazena muitos $$$N$elementos. Para identificá-los sem colisões, você precisa de um número de bits, não menos que $$$X = log_2N$. $$$X$e existe esse limite muito baixo determinado pela fórmula de Hartley. Em alguns casos especiais, com informações sobre a natureza dos dados armazenados, a estrutura pode ser compactada ainda mais eficientemente.

A sequência sucinta é uma estrutura de dados? Contém $$$N$caracteres e termina com um caractere ASCII nulo. Então é preciso $$$N + 1$lugares e, portanto ... ela é sucinta e, mais especificamente, implícita! O que nos leva à próxima pergunta.

Todas as estruturas sucintas são igualmente compactas? A área de pesquisa sucinta define até três tipos de estruturas compactas que diferem na complexidade espacial:

• compacto - $$$O (N)$. Complexidade linear 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'. -.

, , . E não é só isso. , , X, .

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

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

O que vem a seguir?

, succinct:

• rank/select Bitmagic Library.
• , succinct. .
• MIT, succinct.
• , 18 .
• , succinct.
• RRR — .

, :

• Projeto da Succinct Data Structures Library em C ++.
• Projeto BitMagic em C ++.
• Pacote com implementação sucinta do Elias-Fano em Python.
• Implementação de algumas estruturas sucintas no Rust.