Árvore de prefixos com índices de bitmap

Há pouco tempo, eu precisava implementar uma funcionalidade que já havia sido implementada por outras pessoas e mais de uma vez, mas que não se adequava a algumas características. Nesse caso, era necessário algum tipo de estrutura de dados com a capacidade de pesquisar por uma chave de cadeia ou vários caracteres iniciais da chave. A chave é uma sequência de letras latinas em qualquer caso, espaços e números.

Outras implementações não se adequavam, em primeiro lugar, à memória consumida. E, de qualquer forma, outra implementação da árvore de prefixos não será supérflua.

A ideia provavelmente foi inspirada neste artigo , pois foi decidido usar o índice de bitmap para indexar links para nós subsequentes no nó.

Obviamente, o número de links em um nó não pode ser superior a 63 (10 dígitos, 26 letras em cada caso, mais um espaço). Portanto, para um índice de bitmap, um número de 64 bits é usado em cada nó. O bit definido em qualquer posição significa a presença do símbolo e nó correspondentes (subárvore).

A distribuição no índice de bitmap é a seguinte: números de 0 a 9 ocupam de 0 a 9 bits, letras az de 10 a 35 bits, letras AZ de 36 a 62 bits e um espaço ocupa 63 bits. Para obter o número do bit, o código de caractere ASCII é simplesmente usado, reduzido por um determinado número. Para cada intervalo de caracteres, o número é diferente: para os números 48 (o intervalo de dígitos nos códigos ASCII começa com 48), para as letras az 87 (o intervalo de letras az começa com menos 10 bits já ocupados por 10 dígitos) e assim por diante.

A tabela correspondente é mostrada abaixo.


O nó é representado pelo código abaixo:

type Trie struct { rw sync.RWMutex characters uint64 subTries []*Trie data interface{} } 

Assim, cada nó armazena o índice de bitmap dos seguintes caracteres, uma fatia com links para subárvores e os próprios dados. Vou falar brevemente sobre os mecanismos de busca, inserção e remoção.

Ao inserir a entrada, a chave passa simbolicamente pela árvore, iniciando no nó raiz. Para cada caractere de seu código ASCII, o número de bits é calculado e, com base no índice, é calculado na fatia de links (subtries) para subárvores. O valor do índice é o número de bits antes do bit desejado. Por exemplo, temos esse índice: 00 ... 101. Isso significa que no índice de bitmap existem os números 0 e 2. Em seguida, o índice para o número 0 será zero e, para o número 2, será 1, ou seja, subTries armazenará 2 links para subárvores: subtries [0] e subtries [1] .

O código para obter o número do bit para o caractere:

 func calcBitNum(char rune) (uint64, bool) { // Characters az use bit positions 10-35 if char > 96 && char < 123 { return uint64(char - 87), true } // Characters AZ use bit positions 36-61 if char > 64 && char < 91 { return uint64(char - 29), true } // digits 0-9 use bit positions 0-9 if char > 47 && char < 58 { return uint64(char - 48), true } // space uses 62 bit position if char == 32 { return 62, true } return 0, false } 

O código para obter o índice do nó para o caractere:

 func (trie *Trie) getSubTreeIndex(bitNum uint64) int { shifted := trie.characters << (64 - bitNum) return bits.OnesCount64(shifted) } 

O código para obter o nó para o caractere fornecido:

 func (trie *Trie) getSubTrie(char rune) (uint64, int, *Trie) { bitNum, _ := calcBitNum(char) subTrieId := trie.getSubTreeIndex(bitNum) // There is no subTrie under given character since the corresponding bit is zero if trie.characters&(1<<bitNum) == 0 { return bitNum, subTrieId, nil } return bitNum, subTrieId, trie.subTries[subTrieId] } 

Inserir

Uma árvore é atravessada para inserir um elemento. Se algum caractere (e, portanto, todos os subsequentes) estiver ausente, ele será inserido no índice de bitmap. Uma subárvore é criada, cujo link é inserido no lugar certo das sub-tentativas de fatia (o lugar certo é determinado pelo número de bits do desejado). Quando atingem o último caractere da chave, os dados são inseridos na última subárvore.

Pesquisar

Para pesquisar, a chave simbolicamente "percorre" a árvore. Assim que terminar, o resultado será retornado. Se não houver dados para a chave, mas houver mais subárvores, os resultados serão selecionados de todas as subárvores subseqüentes que possuem dados. O limite do número de dados retornados pode ser definido. Assim, é possível procurar um nó pela coincidência de toda a chave ou um conjunto de nós pela coincidência de vários caracteres iniciais.

Excluir

O procedimento de remoção saiu mais complicado (como esperado) do que o resto. Para excluir uma chave, uma árvore é percorrida, durante a qual os nós que não têm dados são registrados em uma fatia separada. Se um nó com dados for encontrado, a fatia será redefinida para zero e a passagem pela árvore continuará mais. Ou seja, a fatia de nós para exclusão deve conter uma sequência de nós que não possuem dados. Se, no final, a fatia não estiver vazia, será na ordem inversa e os bits correspondentes serão removidos do índice de bitmap e os nós serão excluídos.

Sumário

O resultado é uma árvore de prefixos que é superior a outros equivalentes em velocidade e consumo de memória (em média, 30% menos em memória e muito mais rápido). Além disso, não tive preguiça de possibilitar operações multithread com uma árvore, o que aumenta significativamente a produtividade, especialmente em operações de pesquisa. Obviamente, a solução é bastante especializada (limitação na forma de caracteres latinos, números e um espaço como componentes principais).

Com base no objetivo da árvore de prefixos, esta solução pode ser usada para criar um dicionário, índice de pesquisa.

Eu não citei a inserção, procure e exclua códigos, para não confundir o artigo, além disso, o código fonte está disponível no github .