Você pode ter chegado a muitos sites com sugestões de autocompletar, principalmente do Google.

Adicionar essa opção para seu site ou aplicativo pode parecer assustador, mas há uma estrutura de dados recursiva muito simples que resolve o problema. Existe uma tonelada de literatura na net sobre como fazer isso utilizando abordagens caixa preta, como Lucene, Solr, Esfinge, Redis etc, mas todos esses pacotes exigem um monte de configurações e você também perde flexibilidade. Tries podem ser implementadas em algumas linhas de código em qualquer linguagem de sua escolha.

Uma trie é basicamente uma árvore, na qual cada nó representa uma letra, como ilustrado na figura acima. As palavras são caminhos ao longo dessa árvore, e o nó raiz não tem caracteres associados.

1. O valor de cada nó é o caminho ou a sequência de caracteres que leva até ele.
2. Os filhos em cada nó estão idealmente representada usando uma tabela hash mapeando o caractere ao lado dos nós filhos.
3. É também útil para definir um sinalizador em cada nó para indicar se uma palavra/frase termina aí.

Agora podemos definir métodos para inserir uma string e para procurar por uma.

class Trie(object):
    def __init__(self, value=None):
        self.children = {}
        self.value = value
        self.flag = False # Flag to indicate that a word ends at this node

    def add(self, char):
        val = self.value + char if self.value else char
        self.children[char] = Trie(val)

    def insert(self, word):
        node = self
        for char in word:
            if char not in node.children:
                node.add(char)
            node = node.children[char]
        node.flag = True

    def find(self, word):
        node = self
        for char in word:
            if char not in node.children:
                return None
            node = node.children[char]
        return node.value

O custo de inserção tem uma relação linear com o comprimento da string. Agora vamos definir os métodos para listar todas as strings que começam com um prefixo certo. A ideia é percorrer até o nó transversalmente para baixo e de lá fazer uma busca em largura primeiro de todos os nós que são descendentes do nó prefixo. Verificamos se o nó está em um limite de palavra da bandeira que definimos anteriormente e acrescentamos o valor do nó com os resultados. Uma advertência da abordagem recursiva é que você pode um problema de estouro de pilha de profundidade quando o comprimento máximo de uma corda atinge dezenas de milhares de caracteres.

class Trie(object):
    ...
    def all_prefixes(self):
        results = set()
        if self.flag:
            results.add(self.value)
        if not self.children: return results
        return reduce(lambda a, b: a | b,
                     [node.all_prefixes() for
                      node in self.children.values()]) | results

    def autocomplete(self, prefix):
        node = self
        for char in prefix:
            if char not in node.children:
                return set()
            node = node.children[char]
        return node.all_prefixes()

Para excluir um item, primeiro vá até a folha da palavra-chave e, em seguida, trabalhe indo de trás para frente, verificando caminhos comuns.

E aí está um meio eficaz de recuperação de strings com um prefixo comum em menos de 40 linhas de código Python. Também escrevi uma versão C++ utilizando as estruturas de dados STL em cerca de 90 linhas. A complexidade de tempo para essa versão, porém, é O (n log n) como a STL usa uma implementação de árvore rubro-negra para um array associativo. Colin Dean escreveu uma versão do Ruby, e Marcus McCurdy, uma do Java. Você pode encontrá-los todos aqui – https://github.com/vivekn/autocomplete. Leia mais sobre Tries da Wikipédia.

?

Texto original disponível em http://v1v3kn.tumblr.com/post/18238156967/roll-your-own-autocomplete-solution-using-tries