Tabelas de símbolos (TSs)

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

Introdução

• Um tabela de símbolos é uma tabela com duas colunas:  uma coluna de chaves (= keys) e uma de valores (= values).  Dizemos que cada linha da tabela é um item.  Cada item associa um valor a uma chave.
• (A terminologia é infeliz porque a expressão valor da chave k pode ser entendida de duas maneiras: como o valor que a tabela associa com k e como o valor da variável k. Nem sempre a interpretação é óbvia.)
• Exemplo simples:  tabela que associa nomes de alunos aos seus números de identificação:

       chave   valor
       8536152 Antonio Silva
       7210629 Arthur Costa
       8536339 Bruno Carvalho
       8536002 Bruno Lima
       8067490 Bruno Aires
       8536106 Caio Oliveira
       ...
       7581374 Vinicius Lima
       8535922 Vitor Sales
       5992240 Wellington Lima
       8536023 Yan Ferreira
  

• Outro exemplo: tabela que associa números IP a endereços na Internet:

       chave                valor
       www.ebay.com         66.135.192.87
       www.princeton.edu    128.112.128.15
       www.cs.princeton.edu 128.112.136.35
       www.harvard.edu      128.103.60.24
       www.yale.edu         130.132.51.8
       www.cnn.com          64.236.16.20
       www.google.com       216.239.41.99
       www.nytimes.com      199.239.136.200
       www.apple.com        17.112.152.32
       www.slashdot.org     66.35.250.151
       www.espn.com         199.181.135.201
       www.weather.com      63.111.66.11
       www.yahoo.com        216.109.118.65
       ...                  ...
       www.ime.usp.br       143.107.45.37
  

• Definição mais completa:  Uma tabela de símbolos (= symbol table) é um ADT que consiste em um conjunto de itens, sendo cada item um par (chave, valor), munido de duas operações fundamentais:
  • put, que insere um novo item no conjunto,  e
  • get, que busca o valor associado a uma dada chave.
• Abreviatura:  TS ou ST.
• Nossas convenções sobre TSs:
  • não há chaves repetidas (as chaves são duas a duas distintas),
  • null nunca é usado como chave,
  • null nunca é usado como valor associado a uma chave.
• API de tabela de símbolos (com algumas operações auxiliares além das fundamentais):

  public class ST<Key,Value>
  	ST()	cria uma tabela de símbolos vazia
  void	put(Key key, Value val)	insere o item (key,val) nesta tabela
  Value	get(Key key)	busca o valor associado a key
  boolean	isEmpty()	esta tabela está vazia?
  boolean	contains(Key key)	a chave key está nesta tabela?
  Iterable<Key>	keys()	lista todas as chaves desta tabela

• Key e Value são tipos genéricos, ou seja, parâmetros de tipo.
• Uma busca pode terminar em  acerto (search hit)  ou  falha  (search miss).  No primeiro caso, a busca é bem-sucedida;  no segundo caso, a operação é malsucedida e get devolve null.
• Se a tabela já tem um item com chave igual a key, a operação put(key, val) substitui o item antigo pelo novo.
• Esta aula trata de uma implementação muito simples (e bem conhecida) da classe ST.  Antes, examinaremos dois clientes simples mas importantes da classe.

Exemplo: dois clientes simples de TS

• Cliente trivial: recebe palavras, coloca-as numa TS, e imprime a TS e resultante:

  public static void main(String[] args) {
     ST<String, Integer> st;
     st = new ST<String, Integer>();
     for (int i = 0; !StdIn.isEmpty(); i++) {
        String key = StdIn.readString();
        st.put(key, i);
     }
     for (String s : st.keys())  // foreach
        StdOut.println(s + " " + st.get(s));
  }
  

  A primeira palavra lida recebe valor 1, e segunda recebe valor 2, etc.  Como não permitimos chaves repetidas, apenas a cópia mais recente de cada palavra fica na TS.  Exemplo de entrada (cada palavra tem uma só letra):

  key     S  E  A  R  C  H  E  X  A  M  P  L  E
  i       0  1  2  3  4  5  6  7  8  9 10 11 12
  

  Saída:

  L  11
  P  10
  M   9
  X   7
  H   5
  C   4
  R   3
  A   8
  E  12
  S   0
  

• Outro cliente de TS:  FrequencyCounter conta o número de ocorrências de palavras de comprimento pelo menos minlen e imprime uma palavra de frequência máxima:

  public class FrequencyCounter {
  
     public static void main(String[] args) {
        int minlen = Integer.parseInt(args[0]);
        ST<String, Integer> st = new ST<String, Integer>();
        while (!StdIn.isEmpty()) {
           String word = StdIn.readString();
           if (word.length() < minlen) continue;
           if (!st.contains(word)) st.put(word, 1);
           else st.put(word, st.get(word) + 1);
        }
        String max = "";
        st.put(max, 0);
        for (String word : st.keys())  // foreach
           if (st.get(word) > st.get(max))
              max = word;
        StdOut.println(max + " " + st.get(max));
     }
  }
  

  Testes:

  % java FrequencyCounter 1 < tinyTale.txt
  it 10
  
  % java FrequencyCounter 8 < tale.txt
  business 122
  
  % java FrequencyCounter 10 < leipzig1M.txt
  government 24763
  

Dados para testes

• Para testar implementações, usaremos o livro A Tale of Two Cities (1859) de Charles Dickens:

  

• O arquivo tale.txt (797kB) contém o texto completo do livro A Tale of Two Cities.  O arquivo tinyTale.txt contém as cinco primeiras linhas de tale.txt:

  % more tinyTale.txt
  it was the best of times it was the worst of times
  it was the age of wisdom it was the age of foolishness
  it was the epoch of belief it was the epoch of incredulity
  it was the season of light it was the season of darkness
  it was the spring of hope it was the winter of despair
  

• Mais material para testes: o arquivo leipzig1M.txt contém uma amostra aleatória de 1 milhão de sentenças recolhidas na teia WWW. (Veja as primeiras linhas de leipzig1M.txt.)
• Resumo:

  	tinyTale.txt		tale.txt		leipzig1M.txt
  	palavras	diferentes	palavras	diferentes	palavras	diferentes
  todas as palavras	60	20	135 635	10 679	21 191 455	534 580
  8 letras ou mais	3	3	14 350	5 737	4 239 597	299 593
  10 letras ou mais	2	2	4 582	2 260	1 610 829	165 555

Exercícios 1

1. Qual a saída de FrequencyCounter se todas as palavras tiverem comprimento menor que minlen letras? Essa saída é razoável?
2. (SW 3.1.19)  Modifique FrequencyCounter de modo que o programa devolva todas as palavras que têm frequência máxima. (Use uma fila.)
3. Modifique FrequencyCounter de modo que o programa imprima o número total de palavras lidas e o número de palavras distintas.
4. Otimização miúda.  Reescreva a parte final de FrequencyCounter de modo a não inserir a palavra vazia max em st.
5. Otimização miúda.  Reescreva o loop interno de FrequencyCounter de modo que as expressões st.get e st.put apareçam só uma vez cada e st.contains desapareça.
6. Repita os experimentos do livro de SW para confirmar os números da tabela acima.
7. Quantas palavras de 5 letras ou mais há no livro Quincas Borba de Machado de Assis?  (Pontos extra se sua contagem não fizer distinção entre maiúsculas e minúsculas e ignorar os sinais de pontuação.)
8. Acrescente código a FrequencyCounter de modo que o programa imprima uma amostra aleatória de 50 das palavras que estão na TS.
9. (SW 3.1.9)  Acrescente código a FrequencyCounter de modo que o programa imprima a última palavra inserida na TS e o número total de palavras processadas antes da última inserção. Qual a resposta para tale.txt com minlen igual a 1, 8, e 10?
10. Dedup.  Escreva um programa cliente que filtre as palavras repetidas da entrada padrão.

TS implementada com lista sequencial não ordenada

• Exemplo de rastreamento (chaves são strings e valores associados são inteiros):

  

• Nossa implementação troca por SequentialSearchST o nome ST da classe descrita na API.
• [Algoritmo 3.1]  Classe SequentialSearchST: implementação de tabela de símbolos em uma lista ligada não ordenada:

  public class SequentialSearchST<Key,Value> {
  
     private Node first;
  
     // nó da lista ligada
     private class Node {
        private Key key;
        private Value val;
        private Node next;
        public Node(Key key, Value val, Node next) { // construtor
           this.key = key;
           this.val = val;
           this.next = next;
        }
     }
  
     public Value get(Key key) { 
        for (Node x = first; x != null; x = x.next)
           if (key.equals(x.key))
              return x.val;      // acerto
        return null;             // falha
     }
  
     public void put(Key key, Value val) { 
       for (Node x = first; x != null; x = x.next)
          if (key.equals(x.key)) { 
             x.val = val;
             return; 
       }                                   // acerto: atualiza val
       first = new Node(key, val, first);  // falha: acrescenta novo nó
     }
  }
  

• A palavra reservada this no construtor da classe Node serve para resolver ambiguidade:  this.key é a variável key da classe que estamos definindo, enquanto key é o primeiro parâmetro do método Node().
• Cuidado:  if (key == x.key) não faz sentido.
• Cada put começa com uma busca igual à de get;  se a busca for malsucedida, um novo nó é acrescentado à lista.
• O código funciona (não é preciso fazer nada especial) quando a lista está vazia.
• Os métodos get() e put() são métodos de instância:  cada instância da classe tem os seus próprios put() e get().

Exercícios 2

1. Escreva um método recursivo limpa() que receba uma lista ligada e elimine os elementos repetidos da lista.
2. Escreva uma implementação do método contains().
3. (SW 3.1.2)  Escreva uma implementação ArrayST de tabela de símbolos baseado em um vetor não ordenado. Quais as vantagens e desvantages?
4. Implemente o método Iterable<Key> keys().

Como estimar o desempenho de uma implementação de TS?

• Como estimar o tempo gasto em uma operação de inserção ou busca?
• O tempo é proporcional ao número de chaves tocadas.
• Diremos que o número de chaves tocadas durante uma operação é o custo da operação.
• O custo médio de uma busca bem-sucedida, também conhecido como custo de uma busca aleatória bem-sucedida, é o quociente  c/N,  onde c é a soma dos custos das busca de todas as chaves na tabela e N é o número total de chaves na tabela.

Desempenho de SequentialSearchST

• Aplique SequentialSearchST a uma lista com N chaves.  Durante a execução de get(k) ou put(k,v), uma chave da TS é tocada quando comparada com k.  Quantas chaves o método put() toca?  quantas get() toca?

  	número máximo de chaves tocadas
  get()	N
  put()	N

  Portanto, as duas operações, busca e inserção, são muito lentas. (A inserção é lenta em virtude de nossa convenção de não inserir chaves repetidas na TS.)

• Consequência: Inserir N chaves distintas numa TS inicialmente vazia implementada em lista ligada consome  1 + 2 + … + N ≅ N²/2  unidades de tempo no pior caso.
• O custo de uma busca aleatória bem-sucedida é  N/2.
• Exemplo: A livro aplicou FrequencyCounter com SequentialSearchST no lugar de ST às palavras de comprimento 8 ou mais no arquivo tale.txt.  Segue o gráfico do número de chaves tocadas por cada chamada de put(). Os pontos vermelhos dão a média corrente:

  

• Como o gráfico acima foi feito? Basta que FrequencyCounter chame uma versão ligeiramente adaptada de Visual​Accumulator.
• Embora tale.txt não seja aleatório, o comportamento indicado pelo gráfico é semelhante ao de um arquivo de chaves aleatórias.
• Gráfico confirma que um put() em uma tabela de tamanho N toca N/2 chaves em média.

Exercícios 3

1. Acrescente um método a SequentialSearchST que calcule o custo de uma busca aleatória bem-sucedida, supondo que todas as chave têm a mesma probabilidade de ser buscada.
2. Acrescente um método a SequentialSearchST que calcule o custo de uma busca aleatória malsucedida.
3. (SW 3.1.38, p.394) Gráficos de custo amortizado. Aparelhe FrequencyCounter e SequentialSearchST para produzir gráficos como os vistos acima.

Exercícios 4

1. (SW 3.1.22, p.391) Self-organizing search. Um busca é auto-organizada se rearranja os itensda tabela de modo que aqueles mais frequentemente usados sejam mais fáceis de encontrar. Modifique a implementação do Exercício 3.1.2 da seguinte maneira: a cada busca bem-sucedida, coloque o item (chave,valor) encontrado no começo do vetor e desloque os outros itens uma posição para a direita. Esse procedimento é conhecido como move-to-front heuristic.
2. (SW 3.1.25) Caching em software. A implementação padrão de contains() chama get(). Assim, o loop interno de FrequencyCounter

        if (!st.contains(word)) st.put(word, 1);
        else st.put(word, st.get(word) + 1);
   

   resulta em duas ou três buscas pela mesma chave. Para evitar isso sem mudar o código de FrequencyCounter, podemos usar a técnica de software caching: armazenamos a localização da chave mais recentemente encontrada em uma variável de instância. Faça isso em SequentialSearchST.

3. (SW 3.1.39, p.394) Tempo real.  Aparelhe FrequencyCounter com Stopwatch e StdDraw para fazer um gráfico em que o eixo x corresponde às sucessivas chamadas de get() e put() e o eixo y é o tempo total de execução. Um ponto é marcado no gráfico para representar o tempo acumulado depois de cada chamada. Rode o seu programa com tale.txt usando SequentialSearchST. Discuta os resultados. (Observação: Saltos acentuados na curva podem ser explicados pelo caching, coisa que está além do escopo deste exercício.)