A estrutura de dados Trie: uma jóia negligenciada

Desde os primeiros dias de nossas vidas como programadores, todos nós lidamos com estruturas de dados: Arrays, listas vinculadas, árvores, conjuntos, pilhas e filas são nossos companheiros diários, e o programador experiente sabe quando e por que usá-los. Neste artigo veremos como uma estrutura de dados frequentemente negligenciada, o trie , realmente brilha em domínios de aplicativos com recursos específicos, como jogos de palavras.

Jogos de palavras como exemplo Trie

Para começar, vamos considerar um quebra-cabeça de palavras simples: encontre todas as palavras válidas em um quadro de letras 4x4, conectando as letras adjacentes horizontalmente, verticalmente ou diagonalmente. Por exemplo, no quadro a seguir, vemos as letras 'W', 'A', 'I' e 'T' conectando-se para formar a palavra “WAIT”.

A solução ingênua para encontrar todas as palavras válidas seria explorar o tabuleiro começando no canto superior esquerdo e depois movendo a profundidade primeiro para as sequências mais longas, começando novamente da segunda letra da primeira linha e assim por diante. Em um tabuleiro 4x4, permitindo movimentos verticais, horizontais e diagonais, existem 12.029.640 sequências, variando de um a dezesseis caracteres.

Agora, nosso objetivo é encontrar a melhor estrutura de dados para implementar esse verificador de palavras válidas, ou seja, nosso vocabulário. Alguns pontos a ter em conta:

• Precisamos apenas de uma única cópia de cada palavra, ou seja, nosso vocabulário é um conjunto, do ponto de vista lógico.
• Precisamos responder as seguintes perguntas para qualquer palavra:
  • A sequência de caracteres atual compreende uma palavra válida?
  • Existem palavras mais longas que começam com esta sequência? Caso contrário, podemos abandonar nossa exploração em profundidade, pois ir mais fundo não produzirá palavras válidas.

Para ilustrar o segundo ponto, considere o quadro a seguir: Não adianta explorar os movimentos subsequentes, pois não há palavras no dicionário que comecem com “ASF”.

Adoraríamos que nossa estrutura de dados respondesse a essas perguntas o mais rápido possível. ~O(1) tempo de acesso (para verificar uma sequência) seria o ideal!

Podemos definir a interface do Vocabulary assim (veja aqui o repositório do GitHub):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Tentar Estrutura de Dados vs. Alternativas

Implementar o método contains() requer uma estrutura de dados de apoio que permite encontrar elementos de forma eficiente, enquanto o método isPrefix() exige que encontremos o “próximo elemento maior”, ou seja, precisamos manter o vocabulário ordenado de alguma forma.

Podemos excluir facilmente conjuntos baseados em hash de nossa lista de candidatos: embora essa estrutura nos dê uma verificação em tempo constante para contains() , ela teria um desempenho muito ruim em isPrefix() , no pior caso exigindo que varrimos todo o arquivo definir.

Pelo motivo oposto, também podemos excluir listas encadeadas ordenadas, pois elas exigem a varredura da lista pelo menos até o primeiro elemento que é maior ou igual à palavra ou prefixo pesquisado.

Duas opções válidas estão usando uma lista ordenada baseada em array ou uma árvore binária.
Na lista ordenada baseada em array, podemos usar a busca binária para encontrar a sequência atual se estiver presente ou o próximo elemento maior a um custo de O(log2(n)) , onde n é o número de palavras no dicionário.

Podemos implementar um vocabulário baseado em array que sempre mantém a ordenação assim, usando o padrão java.util.ArrayList e java.util.Collections.binarySeach :

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

Se decidirmos usar uma árvore binária, a implementação pode ser ainda mais curta e elegante (mais uma vez, aqui está um link para o código):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

Em ambos os casos, podemos esperar desempenho O(log n) para cada método de acesso ( contains() e isPrefix() ). Quanto aos requisitos de espaço, tanto a implementação baseada em array quanto a implementação baseada em árvore requerem O(n+M) onde n é o número de palavras no dicionário e M é o tamanho de bytes do dicionário, ou seja, a soma do comprimento de as cordas no dicionário.

Aplicativos Trie: Quando e por que usar Tries

Desempenho logarítmico e memória linear não são ruins. Mas existem mais algumas características do nosso domínio de aplicação que podem nos levar a um melhor desempenho:

• Podemos assumir com segurança que todas as palavras são minúsculas.
• Aceitamos apenas letras az - sem pontuação, sem hífens, sem acentos etc.
• O dicionário contém muitas formas flexionadas: plurais, verbos conjugados, palavras compostas (por exemplo, casa –> governanta). Portanto, muitas palavras compartilham o mesmo radical .
• As palavras têm um comprimento limitado. Por exemplo, se estivermos trabalhando em um tabuleiro 4x4, todas as palavras com mais de 16 caracteres podem ser descartadas.

É aqui que entra o trie (pronuncia-se “try”). Mas o que exatamente é um trie? As tentativas são estruturas de dados negligenciadas, encontradas em livros, mas raramente em bibliotecas padrão.

Para motivação, vamos primeiro considerar o garoto-propaganda da Ciência da Computação: a árvore binária. Agora, quando analisamos o desempenho de uma árvore binária e dizemos que a operação x é O(log(n)) , estamos constantemente falando de log base 2. Mas e se, em vez de uma árvore binária, usássemos uma árvore ternária, onde cada nó tem três filhos (ou, um fan-out de três). Então, estaríamos falando da base de log 3. (Isso é uma melhoria de desempenho, embora apenas por um fator constante.) Essencialmente, nossas árvores se tornariam mais largas, mas mais curtas, e poderíamos realizar menos pesquisas, pois não precisamos descer muito tão profundo.

Levando as coisas um passo adiante, e se tivéssemos uma árvore com fan-out igual ao número de valores possíveis do nosso tipo de dados?

Esta é a motivação por trás da tentativa. E como você deve ter adivinhado, um trie é de fato uma árvore, uma árvore trie, por assim dizer!

Mas, ao contrário da maioria das árvores binárias que você usaria para classificar strings, aquelas que armazenam palavras inteiras em seus nós, cada nó de uma trie contém um único caractere (e nem mesmo isso, como veremos em breve) e tem um fan-out máximo igual ao comprimento do alfabeto. No nosso caso, o comprimento do alfabeto é 26; portanto, os nós da trie têm um fan-out máximo de 26. E, enquanto uma árvore binária balanceada tem profundidade log2(n) , a profundidade máxima da trie é igual ao comprimento máximo de uma palavra! (Novamente, mais largo, mas mais curto.)

Dentro de uma trie, palavras com o mesmo radical (prefixo) compartilham a área de memória que corresponde ao radical.

Para visualizar a diferença, vamos considerar um pequeno dicionário feito de cinco palavras. Suponha que as letras gregas indiquem ponteiros e observe que, na trie, os caracteres vermelhos indicam nós contendo palavras válidas .

Implementação Java Trie

Como sabemos, na árvore os ponteiros para os elementos filhos geralmente são implementados com uma variável esquerda e direita, porque o fan-out máximo é fixado em dois.

Em uma tentativa de indexar um alfabeto de 26 letras, cada nó possui 26 possíveis filhos e, portanto, 26 possíveis ponteiros. Cada nó apresenta, portanto, uma matriz de 26 (apontadores para) subárvores, onde cada valor pode ser nulo (se não houver tal filho) ou outro nó.

Como, então, procuramos uma palavra em uma tentativa? Aqui está o método que, dado um String s , identificará o nó que corresponde à última letra da palavra, caso exista na árvore:

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

O método LOWERCASE.getIndex(s.charAt(i)) simplesmente retorna a posição do i- ésimo caractere no alfabeto. No nó retornado, um node de propriedade booleana indica que o nó corresponde à última letra de uma palavra, ou seja, uma letra marcada em vermelho no exemplo anterior. Como cada nó mantém um contador do número de filhos, se esse contador for positivo, então há palavras mais longas no dicionário que têm a string atual como prefixo. Nota: o nó não precisa realmente manter uma referência ao caractere ao qual ele corresponde, pois está implícito em sua posição na trie.

Analisando o desempenho

O que faz a estrutura trie realmente funcionar bem nessas situações é que o custo de procurar uma palavra ou prefixo é fixo e depende apenas do número de caracteres da palavra e não do tamanho do vocabulário.

Em nosso domínio específico, como temos strings com no máximo 16 caracteres, são necessários exatamente 16 passos para encontrar uma palavra que esteja no vocabulário, enquanto qualquer resposta negativa, ou seja, a palavra ou prefixo não está na trie, pode ser obtida em no máximo 16 passos também! Considerando que ignoramos anteriormente o comprimento da string ao calcular a complexidade do tempo de execução para a lista ordenada baseada em array e a árvore, que está oculta nas comparações de string, também podemos ignorá-lo aqui e afirmar com segurança que a pesquisa foi concluída em tempo O(1) .

Considerando os requisitos de espaço (e lembrando que indicamos com M o tamanho de bytes do dicionário), a trie poderia ter M nós no pior caso, se duas strings não compartilhassem um prefixo. Mas como observamos que há alto grau de redundância no dicionário, há muita compactação a ser feita. O dicionário de inglês usado no código de exemplo tem 935.017 bytes e requer 250.264 nós, com uma taxa de compactação de cerca de 73%.

No entanto, apesar disso, mesmo uma trie compactada geralmente exigirá mais memória do que uma árvore ou array. Isso ocorre porque, para cada nó, são necessários pelo menos 26 x sizeof(pointer) bytes, além de alguma sobrecarga para o objeto e atributos adicionais. Em uma máquina de 64 bits, cada nó requer mais de 200 bytes, enquanto um caractere de string requer um único byte, ou dois se considerarmos strings UTF.

Tentativas e testes de desempenho

Então, e o desempenho? As implementações de vocabulário foram testadas em duas situações diferentes: verificar 20.000.000 strings aleatórias e encontrar todas as palavras em 15.000 quadros gerados aleatoriamente a partir da mesma lista de palavras.

Quatro estruturas de dados foram analisadas: uma lista ordenada baseada em array, uma árvore binária, o trie descrito acima e um trie usando arrays de bytes correspondentes ao índice alfabético dos próprios caracteres (uma otimização de desempenho menor e facilmente implementada). Aqui estão os resultados, em ms:

O número médio de movimentos feitos para resolver o tabuleiro é 2.188. Para cada movimento é feito um lookup de palavras e um lookup de prefixo, ou seja, para checagem de todos os tabuleiros foram realizados mais de 32M de buscas de palavras e 32M de prefixos. Nota: estes poderiam ser feitos em uma única etapa, mantive-os separados para maior clareza na exposição. Compactá-los em uma única etapa reduziria o tempo de resolução das placas quase pela metade e provavelmente favoreceria ainda mais a tentativa.

Como pode ser visto acima, a pesquisa de palavras tem um desempenho melhor com o trie mesmo quando usando strings, e é ainda mais rápido quando usando índices alfabéticos, com o último executando mais de duas vezes mais rápido que uma árvore binária padrão. A diferença na resolução dos quadros é ainda mais evidente, com a solução rápida trie-alphabet-index sendo mais de quatro vezes mais rápida que a lista e a árvore.

Empacotando

O trie é uma estrutura de dados muito especializada que requer muito mais memória do que árvores e listas. No entanto, quando características de domínio específicas se aplicam, como um alfabeto limitado e alta redundância na primeira parte das strings, isso pode ser muito eficaz para abordar a otimização do desempenho.

Referências

Uma extensa explicação sobre tentativas e alfabetos pode ser encontrada no capítulo 5 do livro de Robert Sedgewick “Algorithms, 4th edition”. O site complementar em Princeton tem o código para uma implementação do Alphabet e TrieST que é mais extensa do que o meu exemplo.

A descrição do trie e as implementações para vários idiomas também podem ser encontradas na Wikipedia e você também pode dar uma olhada neste recurso trie da Universidade de Boston.