pesquisa de prefixo em uma árvore patricia / trie patricia

StackOverflow https://stackoverflow.com/questions/794601

Pergunta

Atualmente estou implementando uma árvore patricia / trie patricia (o que você quiser chamá-lo). Eu quero usá-lo para pesquisas de prefixo em um dicionário em um pedaço severamente underpowered de hardware. É suposto a trabalhar mais ou menos como auto-completar, i. e. mostrando uma lista de palavras que o digitado prefixo partidas.

Meu implementação é baseada sobre este artigo , mas o código nele doesn 't incluem pesquisas de prefixo, embora o autor diz:

[...] Digamos que você queira enumerar todos os nós que possuem as chaves com um prefixo comum "AB". Você pode realizar uma busca em profundidade a partir de que raiz, parando sempre que se deparar bordas de volta.

Mas eu não vejo como isso é suposto para trabalhar. Por exemplo, se eu construir uma árvore de raiz a partir destas palavras:

doença
imaginária
imaginação
imagine
imitação

imediato imediatamente
imensa
em

I terá exatamente o mesmo "melhor jogo" para os prefixos "i" e "em" modo que parece difícil de me reunir todas as palavras correspondentes apenas atravessando a árvore que melhor jogo.

Além disso, há um radix implementação de árvore em Java que tem uma pesquisa de prefixo implementado em RadixTreeImpl.java . Esse código explicitamente verifica todos nós (a partir de um certo nó) para uma correspondência de prefixo -. Ele realmente compara bytes

Pode alguém me aponte para uma descrição detalhada sobre a implementação de uma pesquisa de prefixo na árvore patricia? É o algoritmo usado na implementação Java a única maneira de fazê-lo?

Foi útil?

Solução

Pense sobre o que seu codifica Trie. Em cada nó, você tem o caminho que levará a esse nó, então no seu exemplo, você começa a ? (que é um Lambda capital, este tipo de fonte grego de sucções) o nó raiz correspondente a uma cadeia vazia. ? tem filhos para cada letra utilizado, portanto, em seu conjunto de dados, você tem um ramo, de "i".

  • ?
  • ? ? "i"

No "i" nó, existem dois filhos, um de "m" e uma para "n". A próxima letra é "n", assim que você toma que,

  • ? ? "i" ? "n"

e desde que a única palavra que começa com "i", "n" em seu conjunto de dados é "in", não há crianças de "n". Isso é um jogo.

Agora, vamos dizer que o conjunto de dados, em vez de ter "in", tinha "infindibulum". (O que SF eu estou fazendo referência é deixado como um exercício.) Você ainda chegar ao "n" nó da mesma forma, mas, em seguida, se a próxima letra que você recebe é "q", você sabe que a palavra não aparece no seu conjunto em tudo, porque não há nenhum ramo "q" de dados. Nesse ponto, você diz "tudo bem, não jogo." (Talvez você, em seguida, começar a adicionar a palavra, talvez não, dependendo da aplicação.)

Mas se a próxima letra é "f", você pode continuar. Você pode curto-circuito que, com uma pequena embarcação, no entanto: uma vez que você chegar a um nó que representa um caminho único, você pode pendurar o string inteira fora desse nó. Quando você chegar a esse nó, você sabe que o resto da cadeia deve ser "findibulum", então você já usou o prefixo para coincidir com a corda toda, e devolvê-lo.

Como o que você usa isso? em um monte de intérpretes de comando non-UNIX, como o velho VAX DCL, você pode usar qualquer prefixo único de um comando. Então, o equivalente a ls (1) foi DIRECTORY, mas nenhum outro comando começou com DIR, assim você pode digitar DIR e que era tão bom quanto fazendo a palavra inteira. Se você não conseguia lembrar o comando correto, você pode digitar apenas 'D', e hit (eu acho) ESC; o DCL CLI voltaria você todas os comandos que começaram com D, que poderia procurar extremamente rápido.

Outras dicas

Acontece que as extensões GNU para o padrão C ++ lib inclui uma implementação trie Patricia. É encontrado sob a extensão de estruturas de dados baseada em políticas. Consulte http://gcc.gnu.org/onlinedocs/libstdc++/ext /pb_ds/trie_based_containers.html

Um algoritmo alternativo: Keep It Simple Stupid

Basta fazer uma lista ordenada de suas palavras-chave. Quando você tem um prefixo, binário de busca para encontrar onde esse prefixo estaria localizada na lista. Todas as suas conclusões possíveis serão encontrados começando nesse índice, pronto para ser acessado no lugar.

Este algoritmo irá exigirá apenas 5% do código de um trie Patricia e será fácil de manter, entender e atualização. É quase certo esta pesquisa simples lista vai ser mais eficiente também.

A única desvantagem é que se você tem um grande número de longas palavras-chave com prefixos semelhantes, um trie pode poupar algum armazenamento uma vez que não precisa manter o prefixo completo para cada entrada. Na prática, se você tem menos de alguns milhões de palavras, esta não é uma poupança porque a sobrecarga ponteiro da árvore vai dominar. Essa economia é mais para aplicações como pesquisar bases de dados de seqüências de DNA com milhões de caracteres, não palavras-chave texto.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top