Tries (árvores digitais)

Livro de Sedgewick e Wayne: primeira parte da sec.5.2, p.730.  Website do livro: resumo sec.5.2, slides.  Código fonte, documentação, e dados de teste de todos os programas do livro: veja algs4.cs.​princeton.edu/​code/.

Estrutura de uma trie

• Uma trie (pronuncie trái) é um tipo de árvore usado para implementar TSs de strings  (veja a API StringST).
• Nome completo: R-way trie (cada nó pode ter até R filhos).
• Tries também são conhecidas como árvores digitais e como árvores de prefixos.
• Exemplo de uma trie para um alfabeto de 26 caracteres:

  

• Outra figura da mesma trie:

  

• Nesse exemplo, o conjunto de chaves é  sea, sells, she.  (As strings sh e sell, por exemplo, estão representadas na trie mas não são chaves.)
• Tries são compostas por nós do tipo Node  (o campo val é um Object porque pode eventualmente ser um vetor e Java não permite vetores genéricos):

     private static class Node {
        private Object val;
        private Node[] next = new Node[R];
     }
  

• O único nó não apontado por nenhum link é a raiz da trie:

     private Node root;
  

• Exemplo:

  

• Duas observações importantes sobre tries:
  • As chaves não são armazenadas explicitamente;  elas ficam codificadas nos caminhos que começam na raiz.
  • Todos os prefixos de chaves estão representados na trie (ainda que alguns prefixos não sejam chaves).
• Os links da estrutura correspondem a caracteres e não a chaves.  Nas figuras, o caractere escrito dentro de um nó é o caractere do link que entra no nó.
• Ao descer da raiz até um nó x, soletramos uma string, digamos s.  Dizemos que s leva ao nó x.  Dizemos também que o nó x é localizado pela string s.  (Por exemplo, o nó localizado pela string vazia é root.)
• A string que leva a um nó x é uma chave se e somente se  x.val != null.
• Subtries.  Cada nó x da trie é a raiz de uma subtrie, digamos X.  A subtrie X representa o conjunto de todas as chaves da trie que têm como prefixo a string que leva da raiz da trie até x.

Busca (search)

• Busca em uma trie:

  

• Código de busca (sutil, ainda que pareça óbvio):

     public Value get(String key) {
        Node x = get(root, key, 0);
        if (x == null) return null;
        return (Value) x.val;
     }
  
     private Node get(Node x, String key, int d) { 
        if (x == null) return null;
        if (d == key.length()) return x;
        char c = key.charAt(d);
        return get(x.next[c], key, d+1);
     }
  

• O que faz o segundo método get()?  Ao receber um inteiro  d  ≤  key.length(),  o método devolve o nó localizado pela string key.substring(d) na subtrie cuja raiz é x ;  se tal nó não existe, devolve null.
• Observações sobre o segundo método get():
  • O método nunca é invocado com argumentos arbitrários:  key.substring(0,d) sempre leva da raiz da trie até o nó x.
  • Se d == key.length(), o método dá a resposta correta, pois na subtrie cuja raiz é x o nó localizado pela string vazia é x.
  • O método ignora a distinção entre chaves e as strings que não são chaves, pois nunca consulta o campo val dos nós.

Inserção (insert)

• Exemplo: Inserção das chaves   she sells sea shells by the sea shore   numa trie inicialmente vazia:

  

• Veja Trie construction demo no website do livro.
• Código de inserção (sutil, ainda que pareça simples):

     public void put(String key, Value val) { 
        root = put(root, key, val, 0); 
     }
  
     private Node put(Node x, String key, Value val, int d) { 
        if (x == null) x = new Node();
        if (d == key.length()) { 
           x.val = val; 
           return x; 
        }
        char c = key.charAt(d);
        x.next[c] = put(x.next[c], key, val, d+1);
        return x;
     }
  

• O que faz o segundo método put()?  Ao receber um inteiro  d  ≤  key.length(),  o método acrescenta a chave key.substring(d) ao conjunto de chaves representadas na subtrie cuja raiz é x.  Mais especificamente, o método expande a subtrie cuja raiz é x de modo a acomodar a string key.substring(d) e associa o valor val a essa string.  O método devolve a raiz da subtrie resultante da inserção; essa raiz é igual a x, a menos que o método tenha sido invocado com primeiro argumento igual a null.
• Observações sobre o segundo método put():
  • A expansão da subtrie pode envolver a criação de zero, um, dois, ou mais novos nós. Se a string key.substring(d) já estava representada na subtrie, nenhum novo nó é criado.
  • O método nunca é invocado com argumentos arbitrários:  temos sempre d  ≤  key.length() e a string key.substring(0,d) leva da raiz da trie até o nó x.
  • Se d == key.length(), o método dá a resposta correta, pois key.substring(d) é "" e x é o nó localizado pela string vazia.
• Tries limpas. Uma folha de uma trie é um nó sem filhos, ou seja, um nó z tal que z.next[c] == null para todo caractere c.  Diremos que uma trie é limpa se cada uma de suas folhas corresponde a uma chave, ou seja, se z.val != null para cada folha z.  [O livro não dá nome a esse conceito e varre o assunto todo para debaixo do tapete… ]  As tries produzidas pelo método put() são limpas.

Exercícios 1

1. Quanto vale get("")?  Quanto vale put("", val)?
2. Quanto vale get(null)?  Quanto vale put(null, val)?
3. Que acontece se o método get(Node x, String key, int d) for invocado com d estritamente maior que key.length()?
4. De quantas maneiras diferentes pode terminar uma busca (bem- ou malsucedida) numa trie?
5. (SW 5.2.5)  Escreva uma versão não recursiva do método get(). Diga quais são os invariantes do processo iterativo.
6. (SW 5.2.5)  Escreva uma versão não recursiva do método put().
7. As chaves de uma trie precisam ser comparáveis?
8. Trie limpa?  Escreva um método limpa() (que fará parte da classe TrieST) para verificar se a trie é limpa.

Remoção (delete)

• A operação delete() remove uma dada chave k do conjunto de chaves da trie.  (A operação também pode ser aplicada a uma string k que não é chave; nesse caso, a operação não faz nada.)  Em princípio, a implementação da operação delete() é fácil: basta encontrar o nó x localizado pela string k e fazer

  x.val = null;
  

• Infelizmente, a trie resultante dessa operação pode não ser limpa, mesmo que a trie original seja limpa.  Para manter a trie limpa, é preciso fazer algo mais complexo:

     public void delete(String k) { 
        root = delete(root, k, 0); 
     }
  
     private Node delete(Node x, String k, int d) {
        if (x == null) return null;
        if (d == k.length())
           x.val = null;
        else {
           char c = k.charAt(d);
           x.next[c] = delete(x.next[c], k, d+1);
        }
        if (x.val != null) return x;
        for (char c = 0; c < R; c++)
           if (x.next[c] != null) return x;
        return null;
     }
  

• O que faz o segundo método delete()?  O método recebe um nó x de uma trie limpa, uma string k (que pode não ser uma chave) e um inteiro  d  ≤  k.length().  O método supõe que k.substring(0, d-1) leva da raiz da trie até x.  Digamos que X é a subtrie com raiz x e K' é o conjunto de todas as chaves da trie que têm prefixo k.substring(0, d-1).  Pois bem: o segundo método delete() remove k do conjunto K' (e portanto também do conjunto de chaves da trie) e devolve a raiz de uma subtrie limpa (parte da subtrie X) que representa o conjunto de chaves K' − {k} :
  • se K' − {k} for vazio, devolve null;
  • senão, devolve x.

  (Se k não é chave, o método efetivamente não faz nada.)

• Exemplo: Remoção da chave shells (e o valor associado):

  

Exercícios 2

1. Mostre que a trie produzida pelo método delete() é limpa (desde que a trie original seja limpa).

Implementação trie da TS de strings

• Algoritmo 5.4: TS implementada com uma trie (chaves são strings sobre o alfabeto 0 . . R−1):

  public class TrieST<Value> {
  
     private static int R = 256; // base: tamanho do alfabeto
     private Node root;          // raiz da trie
  
     private static class Node // veja acima
  
     public Value get(String key) // veja acima
  
     private Node get(Node x, String key, int d) // veja acima
  
     public void put(String key, Value val) // veja acima
  
     private Node put(Node x, String key, Value val, int d) // veja acima
  
     public void delete(String k) // veja acima
  
     public Iterable<String> keys() // veja abaixo
  
  }
  

• Veja documentação completa da classe TrieST do livro.

Exercícios 3

1. (SW 5.2.1)  Insira as chaves  no is th ti fo al go pe to co to th ai of th pa  numa trie inicialmente vazia. Faça um desenho da trie resultante. (Não desenhe os links de valor null.)
2. (SW 5.2.3)  Insira as chaves  now is the time for all good people to come to the aid of  numa trie inicialmente vazia. Faça um desenho da trie resultante. (Não desenhe os links de valor null.)
3. Size.  Escreva uma implementação (recursiva) preguiçosa do método size(). (É claro que método deve devolver o número de chaves e não o número de nós.)
4. (SW 5.2.10) Size. Escreva uma implementação ansiosa do método size() que mantenha, em cada nó x, o número de nós na subtrie cuja raiz é x. (A classe TrieST deverá ser reescrita para acomodar essa implementação.)

Operações especiais: keysWithPrefix(), longestPrefixOf(), etc.

• Segunda parte da interface de TS de strings:

  public class StringST<Value>
  Iterable<String>	keysWithPrefix(String s)	todas as chaves que têm prefixo s
  Iterable<String>	keysThatMatch(String s)	todas as chaves que casam com s     quando '.' é usado como curinga
  String	longestPrefixOf(String s)	a chave mais longa que é prefixo de s, isto é,     o maior prefixo de s que é uma chave

• Exemplos para o conjunto de chaves   she sells sea shells by the sea shore :
  • keysWithPrefix("she") devolve she e shells
  • keysWithPrefix("se") devolve sells e sea
  • keysThatMatch(".he") devolve she e the
  • keysThatMatch("s..") devolve she e sea
  • longestPrefixOf("shell") devolve "she"
  • longestPrefixOf("shellsort") devolve "shells"

Exercícios 4

1. Numa trie arbitrária, qual deve ser o valor de keysWithPrefix("a")?  Qual deve ser o valor de keysWithPrefix("")?
2. Numa trie arbitrária, qual deve ser o valor de keysThatMatch(".")?  Qual deve ser o valor de keysThatMatch("")?
3. Numa trie arbitrária, qual deve ser o valor de longestPrefixOf("a")?  Qual deve ser o valor de longestPrefixOf("")?

Implementação de keysWithPrefix() e collect()

• O método keysWithPrefix() funciona como o autocomplete dos telefones celulares ou de um browser.
• O método keysWithPrefix() recebe uma string pre e devolve o conjunto (iterável) de todas as chaves cujo prefixo é pre.  Nossa implementação depende do método auxiliar collect():

  public Iterable<String> keysWithPrefix(String pre) {
     Queue<String> q = new Queue<String>();
     collect(get(root, pre, 0), pre, q);
     return q;
  }
  
  private void collect(Node x, String pre, Queue<String> q) {
     if (x == null) return;
     if (x.val != null) q.enqueue(pre);
     for (char c = 0; c < R; c++)
        collect(x.next[c], pre + c, q);
  }
  

• O que faz o método auxiliar collect()?   O método coloca na fila q todas as chaves da subtrie cuja raiz é x depois de acrescentar o prefixo pre a todas essas chaves.   (Mas collect() nunca é invocado com argumentos arbitrários:  o segundo argumento, pre, é sempre a string que leva da raiz da trie até o nó que é o primeiro argumento.)
• Exemplo de collect():

  

• Exemplo de keysWithPrefix("sh"):

  

• A implementação de um iterador keys(), que devolve todas as chaves da trie, é um caso particular de keysWithPrefix():

  public Iterable<String> keys() { 
     return keysWithPrefix(""); 
  }
  

Exercícios 5

1. (SW 5.2.5)  Escreva uma versão não recursiva do método collect().
2. Casamento com curinga.  Implemente o método keysThatMatch(). O método recebe uma string s e imprime todas as chaves que casam com s quando os caracteres '.' em s são interpretados como curingas, ou seja, casam com qualquer caractere. No nosso exemplo padrão, a resposta de keysThatMatch(.he) é she e the. A resposta de keysThatMatch(s..) é sea e she.

Implementação de longestPrefixOf()

• Para simplificar o bla-bla-bla, vamos dizer que um prefixo de uma string s é bom se for uma chave da trie.
• Nosso problema:  Dada uma string s, encontrar o mais longo prefixo bom de s.
• Exemplos de longestPrefixOf():

  

• Que fazer se o problema não tem solução, ou seja, se nenhum prefixo de s, nem mesmo "", é bom?  [O livro varre essa questão para debaixo do proverbial tapete… ]  Devemos devolver algo que não possa ser confundido com uma resposta normal.  Uma boa decisão de projeto é devolver null nesse caso:

  public String longestPrefixOf(String s) {
     int max = -1;
     Node x = root;
     for (int d = 0; x != null; d++) {
        if (x.val != null) max = d;
        if (d == s.length()) break;
        x = x.next[s.charAt(d)];
     }
     if (max == -1) return null;
     else return s.substring(0, max);
  }
  

• Qual a relação entre x, d e max no começo de cada iteração?   (O começo de uma iteração é o ponto imediatamente anterior ao teste x != null.)  A resposta está nos seguintes invariantes:
  • s.substring(0,d) leva da raiz até x ,
  • max é o comprimento do mais longo prefixo bom de s.substring(0,d-1).

  (É preciso ter jogo de cintura para ler o segundo invariante.  Se max == -1, devemos entender que nenhum prefixo de s.substring(0,d-1) é bom.  Por outro lado, devemos imaginar que s.substring(0,d-1) vale null quando d == 0 e portanto nenhum prefixo de s.substring(0,d-1) é bom nesse caso.)

Exercícios 6

1. Prove que os invariantes de longestPrefixOf() dados acima estão corretos. (Verifique que as propriedades valem no início da primeira e continuam valendo no início de cada iteração subsequente.)  Mostre que a validade dos invariantes no início da última iteração garante que longestPrefixOf() está correto.
2. Critique os seguintes invariantes de longestPrefixOf():  (1) max é o tamanho do maior prefixo bom de s encontrado até agora e (2) depois que saímos do for, a variável max é o tamanho do maior prefixo bom de s encontrado até agora.
3. Critique o seguinte código alternativo de longestPrefixOf():

   public String longestPrefixOf(String s) {
      int max = -1;
      Node x = root;
      for (int d = 0; x != null && d < s.length(); d++) {
         if (x.val != null) max = d;
         x = x.next[s.charAt(d)];
      }
      if (max == -1) return null;
      else return s.substring(0, max);
   }
   

4. Escreva uma versão recursiva do método longestPrefixOf().
5. O livro escreve o código de longestPrefixOf() em estilo recursivo e trata do caso em que nenhum prefixo de s é bom de maneira diferente da minha. O método longestPrefixOf() do livro devolve a string vazia se nenhum prefixo de s for bom e também se a string vazia for o único prefixo bom de s:

   public String longestPrefixOf(String s) {
      int len = search(root, s, 0, 0);
      return s.substring(0, len);
   }
   private int search(Node x, String s, int d, int max) {
      if (x == null) return max;
      if (x.val != null) max = d;
      if (d == s.length()) return max;
      char c = s.charAt(d);
      return search(x.next[c], s, d+1, max);
   }
   

   Analise o código.  Tente dizer o que, exatamente, o método search() faz.  (Na minha opinião, a versão do livro é um exemplo clássico de como não se deve escrever um método recursivo.)

Análise

• A aparência de uma BST (árvore binária de busca) depende muito da ordem em que as chaves são inseridas e removidas. Não é o que acontece com tries (e portanto a expressão¨trie balanceada não faz sentido).
• Proposição F:  A estrutura de uma trie não depende da ordem em que as chaves são inseridas e removidas.  (Prova fácil por indução.)
• O consumo de tempo das operações sobre uma trie não depende do número, N, de chaves:
• Proposição G:  O número de nós visitados para buscar ou inserir uma chave de comprimento W em uma trie é no máximo  1 + W.   (Prova fácil por indução.)
• O consumo de tempo médio em uma busca malsucedida é bem menor que 1 + W, pois a busca termina tão logo encontramos um link null.
• Proposição H:  O número esperado de nós visitados durante uma busca malsucedida em uma trie com N chaves aleatórias sobre um alfabeto de tamanho R é aproximadamente  log_R N.   (Em termos mais técnicos: se o número de nós examinados é E então E / log_R N tende a 1 quando N tende a infinito.)
• A prova da proposição envolve apenas teoria das probabilidades elementar. O ponto de partida é a hipótese de que cada caractere de uma chave aleatória tem a mesma probabilidade de ser qualquer um dos R caracteres do alfabeto.
• Consequência pouco intuitiva: se as chaves são aleatórias, o consumo de tempo médio não depende do comprimento das chaves.

Exercícios 7

1. Min. Implemente a operação min() na classe TrieST. Esse método deve devolver a menor chave (no sentido lexicográfico) da trie. Você pode supor que a trie é limpa. Escreva uma versão recursiva e uma iterativa do método. Escreva os invariantes da versão iterativa.
2. Max. Implemente a operação max() na classe TrieST. Esse método deve devolver a maior chave (no sentido lexicográfico) da trie. Você pode supor que a trie é limpa. Escreva uma versão recursiva e uma iterativa. Escreva os invariantes da versão iterativa.
3. (SW 5.2.8) Operações que envolvem ordem. Implemente as operações floor(), ceiling(), rank() e select() na classe TrieST.
4. (SW 5.2.14) Contagem de substrings de comprimento L. Escreva um cliente de TrieST que leia um texto da entrada padrão e calculate o número de substrings de comprimento L distintas que o texto contém.  Por exemplo, o texto cgcgggcgcg tem cinco substrings de comprimento 3 distintas:  cgc, cgg, gcg, ggc e ggg.  Dica: Insira cada substring de comprimento L em uma tabela de símbolos.
5. (SW 5.2.15) Substrings distintas. Escreva um cliente de TrieST que leia um texto da entrada padrão e calcule o número de substrings distintas de qualquer comprimento. (Isso pode ser feito muito eficientemente com a árvore de sufixos. Veja suffix arrays na página 875 do livro.)
6. (SW 5.2.16) Semelhança de documentos. A L-semelhança de dois arquivos de texto é a distância euclidiana entre os vetores de frequência definidos pelo número de ocorrências de cada L-grama (sequência de L caracteres consecutivos) dividido pelo número total de L-gramas.  Escreva um cliente de TrieST com um método estático que receba, pela linha de comando, um inteiro L e os nomes de dois arquivos de texto e calcule a L-semelhança dos dois arquivos. Escreva também um método estático main() que receba um inteiro L pela linha de comando e uma lista de arquivos texto pela entrada padrão e imprima uma matriz que mostre a L-semelhança de todos os pares de arquivos.
7. (SW 5.2.21) Substring matches. Suponha dada uma lista L de palavras (separadas por espaços em branco) na entrada padrão. Dada uma string s (na linha de comando), queremos todas as palavras em L que contêm s (como substring). Projete uma API para essa tarefa e desenvolva um clente de TrieST que implemente a API. Dica: Insira todos os sufixos de cada palavra da lista na tabela de símbolos.
8. (SW 5.2.22) Macacos digitadores. Suponha que um macaco digita palavras aleatórias anexando cada uma de 26 possíveis letras, com probabilidade p, ao final da palavra corrente e termina a palavra com probabilidade 1 − 26p. Escreva um programa para estimar a distribuição de frequência dos comprimentos de palavras produzidas. Se abc, por exemplo, é produzida mais de uma vez, conte-a somente uma vez.
9. Qual era mesmo o título daquele filme?  Escreva um programa que receba uma string s e devolva os títulos de filmes que se aproximam de s.  Mais precisamente, o programa deve devolver (1) os títulos dos filmes que tenham s como prefixo, (2) o mais longo prefixo de s que seja um título de filme, e (3) os títulos dos filmes que casam com s quando os caracteres '.' em s são interpretados como curingas.  Detalhes ténicos:  Extraia os títulos de filmes do arquivo movies.txt.  Não queremos nos atrapalhar com letras maiúsculas, letras acentuadas, pontuação, etc. Assim, todos os títulos devem ser convertidos para o alfabeto   a b … y z ? 0 1 … 8 9   mais o espaço em branco (total de 38 caracteres).  O alfabeto de consulta tem um caractere adicional, o ponto, que funciona como curinga.   Converta cada um dos 256 caracteres do ASCII estendido no correspondente caractere do nosso alfabeto.  Por exemplo, as letras A e ä serão levadas em a; a letra Ç será levada em c; etc. Todos os caracteres sem um correspondente natural devem ser levados em ?.  Armazene tudo numa trie para responder consultas rapidamente.  As consultas devem ser feitas pela linha de comando e a string de consulta deve ser embrulhada em aspas simples (caracteres ') para que a string possa conter espaços em branco. (Portanto a string de consulta não pode conter aspas simples.)  Tanto quanto possível, use as classes Java do livro sem alteração.  Aproveite trechos de código do livro quando apropriado.  Faça testes.  No fim do seu programa, coloque (em forma de comentário) o resultado de testes interessantes (o que você digitou no terminal e qual foi a resposta do programa).

O lado negativo

• A implementação TrieST só é boa para alfabetos pequenos (R pequeno).
• Se o alfabeto é grande, a implementação TrieST gasta espaço excessivo. Melhor usar TST (ternary search trie). Veja o livro de SW.

Exercícios 8

1. (SW p.741)  Escreva uma generalização de TrieST que trabalhe com um alfabeto especificado.  Dicas: Implemente um constructor que receba um objeto Alphabet como argumento. Use o método toIndex() de Alphabet para converter caracteres em índices no conjunto 0..R-1. Use o método toChar() de Alphabet para converter índices do conjunto 0..R-1 em carateres.