Aplicações de TSs

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

Esta página trata de aplicações de TSs (tabelas de símbolos).  A maioria das aplicações tem duas fases:

• a primeira fase pré-processa os dados a constrói uma TS;
• a segunda fase responde consultas do usuário.

Qual implementação de TS devo usar?

• Devo usar SequentialSearchST?  BinarySearchST?  BST?  RedBlackBST?  SeparateChainingHashST?  LinearProbingHashST?
• Se sua TS é pequena, escolha uma implementação simples (uma das primeiras).  Senão, escolha uma das três últimas.
• Os exemplos abaixo usam a implementação  ST,  que é uma versão apimentada de RedBlackBST. Você pode trocar ST por qualquer outra implementação.
• Velocidade não é o único critério.  Se você precisa de operações como min() ou floor(), por exemplo, implementações com hashing não servem.

Implementação de conjuntos e a classe SET

• Alguns clientes de tabelas de símbolos não precisam dos valores associados às chaves. Uma tal TS representa um conjunto (no sentido matemático), pois nossas TSs não têm chaves repetidas.  Nesse caso, convém chamar a operação de inserção de add e a operação de busca de contains. Eis a API dessa TS simplificada:

  public class SET<Key>
  	SET()	cria um conjunto vazio
  void	add(Key key)	insere key neste conjunto
  void	delete(Key key)	remove key deste conjunto
  boolean	contains(Page p)	key está neste conjunto?
  boolean	isEmpty()	este conjunto está vazio?
  int	size()	número de chaves neste conjunto
  String	toString()	string que descreve este conjunto

• Um SET não se confunde com um Bag pois as chaves de um SET são distintas duas a duas.
• Para converter a implementação de uma TS ordinária em uma implementação de SET, basta ignorar os valores associados às chaves.
• (A classe SET no website do livro é bem mais rica: ela implementa as operações de união e interseção de conjuntos, bem como várias outras.)
• (Cuidado para não confundir SET com a abreviatura ST de symbol table.)

Exercícios 1

1. (SW 3.5.1)  Implemente SET como uma classe invólucro de BST ou de RedBlackST.  Implemente a classe SET como uma classe invólucro de LinearProbingHashST.
2. (SW 3.5.2)  Transforma a classe SequentialSearchSET em uma classe SequentialSearchSET que implemente a API SET. Baste eliminar a parte do código que envolve val.
3. (SW 3.5.3)  Transforma a classe BinarySearchSET em uma classe BinarySearchSET que implemente a API SET. Nesse caso, o conjunto é ordenado pois as chaves são comparáveis.

Filtros

• Verificador ortográfico (spell checker).  Recebe arquivo de palavras corretas, depois imprime as palavras da entrada padrão que não estão no arquivo:

  public class BlackFilter {
     public static void main(String[] args) {
        SET<String> conjunto = new SET<String>();
        In dicionario = new In(args[0]);
  
        while (!dicionario.isEmpty())
           conjunto.add(dicionario.readString());
  
        while (!StdIn.isEmpty()) {
           String palavra = StdIn.readString();
           if (!conjunto.contains(palavra))
              StdOut.println(palavra);
        }
     }
  }
  

Exercícios 2

1. (SW 3.5.31) Verificador ortográfico. Use BlackFilter para encontrar as palavras do livro tale.txt (0.73MB) que não estão no vocabulário (= lista de palavras) words.utf-8.txt (645288 palavras, 6.75MB). Use o ADT Stopwatch do website do livro para comparar o desempenho das implementações RedBlackBST, SeparateChainingHashST, e LinearProbingHashST de tabela de símbolos.
2. (SW 3.5.30) Filtro de repetidos. Escreva um programa Dedup que receba uma lista de números e elimine os repetidos. Escreva um programa AleatoriosRepetidos que receba inteiros M, N e T na linha de comando e repita o seguinte experimento T vezes: gere N inteiros aleatórios entre 0 e M−1 e veja quantos repetidos são gerados.  (A teoria da probabilidades diz que o número de repetidos deve ser aproximadamente 1 − e^−N/M.)  Use o seu programa com T igual a 10 e N igual a 10⁷, 10⁸, e 10⁹, e com M igual a N/2, N e 2N. Cronometre seus experimentos com Stopwatch.

Consulta a vocabulário (dictionary lookup)

• Formato CSV (comma-separated values):  arquivo texto cujas linha consistem em campos separados por vírgulas.
• Exemplo: Lista de triplas de nucletídeos e correspondentes aminoácidos:

  % more amino.csv
  TTT,Phe,F,Phenylalanine
  TTC,Phe,F,Phenylalanine
  TTA,Leu,L,Leucine
  TTG,Leu,L,Leucine
  TCT,Ser,S,Serine
  ...
  GAA,Gly,G,Glutamic Acid
  GAG,Gly,G,Glutamic Acid
  GGT,Gly,G,Glycine
  GGC,Gly,G,Glycine
  GGA,Gly,G,Glycine
  GGG,Gly,G,Glycine
  

• Cliente LookupCSV: Recebe arquivo CSV, o número do campo que será a chave, e o número do campo que será o valor associado. Depois, responde consultas pela entrada/saída padrão.
• Exemplo:

  % java LookupCSV amino.csv 0 3
  TCT
  Serine
  

• Código de LookupCSV:

  public class LookupCSV {
  
     public static void main(String[] args) {
        In in = new In(args[0]);
        int keyField = Integer.parseInt(args[1]);
        int valField = Integer.parseInt(args[2]);
  
        ST<String,String> st = new ST<String,String>();
  
        while (in.hasNextLine()) {
           String line = in.readLine();
           String[] tokens = line.split(",");
           String key = tokens[keyField];
           String val = tokens[valField];
           st.put(key, val);
        }
        while (!StdIn.isEmpty()) {
           String query = StdIn.readString();
           if (st.contains(query))
              StdOut.println(st.get(query));
        }
     }
  }
  

• Exemplo: Consulta a lista de URLs e correspondentes números IP:

  % more ip.csv
  ...
  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
  ...
  

  % java LookupCSV ip.csv 1 0
  128.112.136.35
  www.cs.princeton.edu
  

• Exemplo: Valores de fechamento da Bolsa de Valores:

  % more DJIA.csv
  ...
  20-Oct-87,1738.74,608099968,1841.01
  19-Oct-87,2164.16,604300032,1738.74
  16-Oct-87,2355.09,338500000,2246.73
  15-Oct-87,2412.70,263200000,2355.09
  ...
  30-Oct-29,230.98,10730000,258.47
  29-Oct-29,252.38,16410000,230.07
  28-Oct-29,295.18,9210000,260.64
  25-Oct-29,299.47,5920000,301.22
  ...
  

  % java LookupCSV DJIA.csv 0 3
  29-Oct-29
  230.07
  

• Exemplo: Códigos de produtos de consumo (como os usados em códigos de barra):

  % more UPC.csv
  ...
  0002058102040,,"1 1/4"" STANDARD STORM DOOR"
  0002058102057,,"1 1/4"" STANDARD STORM DOOR"
  0002058102125,,"DELUXE STORM DOOR UNIT"
  0002082012728,"100/ per box","12 gauge shells"
  0002083110812,"Classical CD","'Bits and Pieces'"
  002083142882,CD,"Garth Brooks - Ropin' The Wind"
  0002094000003,LB,"PATE PARISIEN"
  0002098000009,LB,"PATE TRUFFLE COGNAC-M&H 8Z RW"
  0002100001086,"16 oz","Kraft Parmesan"
  0002100002090,"15 pieces","Wrigley's Gum"
  0002100002434,"One pint","Trader Joe's milk"
  ...
  

  % java LookupCSV UPC.csv 0 2
  0002100001086
  Kraft Parmesan
  

Exercícios 3

1. (SW 3.5.32) Dicionário. Estude o desempenho de LookupCSV em um ambiente onde bom desempenho é importante. Especificamente, construa um cenário em que as consultas não são feitas manualmente mas geradas por um aplicativo, muitas por segundo (como as consultas a URLs em um roteador). Faça experimentos de desempenho.

Construção de índices invertidos

• Dada uma TS, queremos a lista de todas as chaves que têm um certo valor associado.
• Cliente LookupIndex:  Recebe arquivo de palavras e a string (por exemplo, ",") que separa as palavras em cada linha. Constrói duas tabelas de símbolos:
  • na tabela st, a primeira palavra de cada linha do arquivo é a chave e o conjunto das demais palavras da linha é o valor associado;
  • na tabela ts, a segunda, terceira, etc. palavras da linha são as chaves e a primeira palavra é o valor associado.

  Depois, responde consultas pela entrada/saída padrão.

• Exemplo: Aminoácidos e correspondentes triplas de nucleotídeos:

  % java LookupIndex aminoI.csv ","
  Serine
    TCT
    TCA
    TCG
    AGT
    AGC
  TCG
    Serine
  

  % more aminoI.csv
  Alanine,AAT,AAC,GCT,GCC,GCA,GCG
  Arginine,CGT,CGC,CGA,CGG,AGA,AGG
  . . .
  Serine,TCT,TCA,TCG,AGT,AGC
  Stop,TAA,TAG,TGA
  Threonine,ACT,ACC,ACA,ACG
  Tyrosine,TAT,TAC
  Tryptophan,TGG
  Valine,GTT,GTC,GTA,GTG
  

• Código de LookupIndex:

  public class LookupIndex {
  
     public static void main(String[] args) {
  
        In in = new In(args[0]); // banco de dados
        String sp = args[1];     // separador
        ST<String,Queue<String>> st = new ST<String,Queue<String>>();
        ST<String,Queue<String>> ts = new ST<String,Queue<String>>();
  
        while (in.hasNextLine()) {
           String[] a = in.readLine().split(sp);
           String key = a[0];
           for (int i = 1; i < a.length; i++) {
              String val = a[i];
              if (!st.contains(key)) st.put(key, new Queue<String>());
              if (!ts.contains(val)) ts.put(val, new Queue<String>());
              st.get(key).enqueue(val);
              ts.get(val).enqueue(key);
           }
        }
        while (!StdIn.isEmpty()) {
           String query = StdIn.readLine();
           if (st.contains(query))
              for (String s : st.get(query))  // foreach
                 StdOut.println("  " + s);
           if (ts.contains(query))
              for (String s : ts.get(query))  // foreach
                 StdOut.println("  " + s);
        }
     }
  }
  

• Exemplo: Filmes de cinema (banco de dados IMDB):

  % java LookupIndex movies.txt "/"
  Bacon, Kevin
    Animal House (1978)
    Apollo 13 (1995)
    Beauty Shop (2005)
    Diner (1982)
    ...
  Tin Men (1987)
    DeBoy, David
    Blumenfeld, Alan
    ...
  

  % more movies.txt
  Abducted (1986)/Borland, Skip/Brown, Jim/Camiro...
  . . .
  Animal House (1978)/Allen, Karen/Bacon, Kevin/Baur, Lisa/Belushi...
  . . .
  Apollo 13 (1995)/Allen, Ivan/Andrews, David/Bacon, Kevin/Barry...
  Apology (1986)/Allen, Seth/Andrei, Damir/Barber, Ellen/Bassett...
  . . .
  

  (As linhas desta amostra de movies.txt foram truncadas para que caibam na página.)

Exercícios 4

1. No código de LookupIndex, os comandos foreach, se referem a um iterador de ST ou de Queue?
2. (SW 3.5.14)  Escreva e teste um método estático invert() que receba um ST<String,Bag<String>> como argumento e produza o inverso da TS (que também é uma ST<String,Bag<String>>).
3. (SW 3.5.20) Concordância. Escreva um cliente Concordance de TS que leia um arquivo texto e responda consultas de concordância feitas pela entrada padrão: para cada palavra digitada, o programa imprime o contexo (digamos, 4 palavras antes e 4 depois) de cada ocorrência da palavra no arquivo. Por exemplo,

   % java Concordance tale.txt
   majesty
     their turnkeys and the *majesty* of the law fired
     me treason against the *majesty* of the people in
     of his most gracious *majesty* king george the third
   
   princeton
     sem ocorrencias
   

Indexação de arquivos

• Cliente FileIndex: Recebe lista de nomes de arquivos.  Depois, responde consultas: dada palavra x na entrada padrão, imprime os arquivos que contêm x:
• Exemplo:

  % java FileIndex ex*.txt
  age
    ex3.txt
    ex4.txt
  best
    ex1.txt
  was
    ex1.txt
    ex2.txt
    ex3.txt
    ex4.txt
  

  % more ex1.txt
  it was the best of times
  
  % more ex2.txt
  it was the worst of times
  
  % more ex3.txt
  it was the age of wisdom
  
  % more ex4.txt
  it was the age of foolishness
  

• Código do FileIndex:

  import java.io.File;
  
  public class FileIndex {
  
     public static void main(String[] args) {
  
        ST<String,SET<File>> st = new ST<String,SET<File>>();
  
        for (String filename : args) {  // foreach
           File file = new File(filename);
           In in = new In(file);
           while (!in.isEmpty()) {
              String word = in.readString();
              if (!st.contains(word)) 
                 st.put(word, new SET<File>());
              SET<File> set = st.get(word);
              set.add(file);
           }
        }
        while (!StdIn.isEmpty()) {
           String query = StdIn.readString();
           if (st.contains(query)) {
              SET<File> set = st.get(query);
              for (File file : set.keys())  // foreach
                 StdOut.println("  " + file.getName());
           }
        }
     }
  }
  

• A linha de código for (File file : set.keys()) se refere a um iterador da classe SET.  No lugar dessa linha, o livro escreve for (File file : set), que é mais bonita e mais legível mas não parece funcionar (eu devo estar fazendo algo errado).  Então vou continuar usando a minha versão e incluir na implementação de SET um método keys() que itera sobre os elementos do conjunto.

Exercícios 5

1. (SW 3.5.24) Busca em intervalos disjuntos. Dada uma lista de intervalos disjuntos dois a dois, escreva um programa que receba um número como argumento e determine o intervalo a que o número pertence. Por exemplo, se os intervalos são 1643-2033, 5532-7643, 8999-10332, 5666653-5669321, o número 9122 pertence ao terceiro intervalo e 8122 não petence a intervalo algum. O programa deve ser escrito como uma classe Intervalos.java que seja capaz de tratar não só de intervalos de números inteiros mas de intervalos de quaisquer tipos de dados comparáveis.  Essa classe deve conter um cliente de teste que responda consultas sobre intervalos de strings.  (Se precisar iterar sobre um objeto da classe SET, sugiro consultar a observação no fim da seção anterior.)