TSs de strings

Livro de Sedgewick e Wayne: introdução da sec.5.2, p.730. Website do livro: resumo sec.5.2, slides.

Esta página faz considerações gerais sobre TSs (tabelas de símbolos) cujas chaves são strings. Trataremos de implementações nas páginas seguintes.

Destaques:

Pré-requisitos:

Grande parte do trabalho de computadores envolve o processamento de strings.
TS de strings (string symbol table): TS cujas chaves são strings.
Exemplos: nomes de pessoas, palavras de um livro, DNA, etc.
Troca tipo genérico Key por tipo concreto String.
Por que estudar TSs de strings em separado?
- Tratamento mais eficiente que TS genérica.
- Métodos especiais importantes, como longestPrefixOf.
O que chaves do tipo string têm de especial?
- Os caracteres das chaves podem ser examinados um a um (coisa que não faz sentido com chaves de tipo genérico).
- Cada chave tem um comprimento (= número de caracteres).
- O alfabeto (= conjunto de caracteres) das chaves é conhecido a priori.
Vamos supor que o alfabeto das chaves tem R caracteres e que R = 256 (às vezes só 26, mas não 65536).
O desempenho de TSs de strings é medido em termos de
- número N de chaves,
- comprimento máximo W das chaves,
- comprimento médio w das chaves,
- tamanho R do alfabeto.
Em muitas aplicações, o tempo de get(key) não depende de N mas é
- proporcional ao comprimento de key no caso de busca bem-sucedida
- essencialmente constante em busca malsucedida (porque nem chega a examinar todos os caracteres da chave).

Interface

API (= interface) de TS de strings:

public class StringST<Value>
	StringST()	cria uma TS de strings vazia
void	put(String key, Value val)	insere o par `(key, val)` nesta tabela
Value	get(String key)	valor associado à chave `key`
void	delete(String key)	remove `key` e seu valor desta tabela
boolean	isEmpty()	esta tabela de símbolos está vazia?
int	size()	número de pares (chave, valor) desta tabela
Iterable<String>	keys()	todas as chaves desta tabela

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`

As três últimas operações só fazem sentido numa TS de strings (não numa TS genérica).
Seguiremos as convenções já adotadas para TSs genéricas:
- não há chaves repetidas,
- null nunca é usado como chave,
- null nunca é usado como valor associado a uma chave.
Em geral, a string vazia não é usada como chave em TSs, mas isso não significa que as implementações de TSs de strings não esbarrem frequentemente em "".

Há várias implementações de TSs de strings:
- tries (diga tráiss), também conhecidas como árvores de prefixos ou árvores digitais,
- tries ternárias, ou TSTs (ternary search tries).