| Home | Administração | Fórum | Livros | WWW | Diário | Tarefas | Alunos |
Esta página é uma versão simplificada do capítulo 11 (Symbol Tables) do livro de Eric Roberts. O capítulo discute tabelas de símbolos (=symbol tables) e o conceito de tabela de dispersão (=hash table).
Problema: Determinar o número de ocorrência de cada palavra em um arquivo texto. Em seguida, dizer quantas vezes cada palavra de uma lista de palavras ocorreu no texto.
Por exemplo, considere o seguinte trecho de "The Secret Adversary" de Agatha Christie (o Projeto Gutenberg tem o texto completo do livro):
IT was 2 p.m. on the afternoon of May 7, 1915. The Lusitania had been struck by two torpedoes in succession and was sinking rapidly, while the boats were being launched with all possible speed. The women and children were being lined up awaiting their turn. Some still clung desperately to husbands and fathers; others clutched their children closely to their breasts. One girl stood alone, slightly apart from the rest. She was quite young, not more than eighteen. She did not seem afraid, and her grave, steadfast eyes looked straight ahead.
Quantas vezes cada palavra da lista abaixo aparece no texto?
children lusitania ship she
Resposta:
children 2 lusitania 1 ship 0 she 2
Um conceito importante para a solução de nosso problema é o de tabela de símbolos.
Imagine que temos uma grande coleção de objetos, cada um dotado de uma chave (= key) e um valor (= value). [Acho que seria mais sugestivo usar a palavra "rótulo" no lugar de "chave".] Em geral,
Nesta página, vamos supor que os valores são do tipo int *. No problema proposto acima, as chaves são palavras e o valor associado com cada chave é um ponteiro para o número de ocorrências da palavra no texto.
Uma coleção de objetos desse tipo merece o nome de tabela de símbolos (= symbol table = dictionary) se
A operação de consulta recebe uma chave k e devolve o valor associado a k na tabela (ou devolve a informação de que não há objeto com chave k na tabela). A operação de inserção recebe uma chave k e um valor v e acrescenta o par (k,v) à tabela (se a tabela já tiver um objeto com chave k, ele será substituído pelo novo par).
Eis uma implementação simplória de uma tabela de símbolos para resolver nosso problema de contagem de palavras. A tabela residirá em uma lista encadeada com células do tipo cellT:
typedef char *string;
typedef struct cellT {
string key;
int *value;
struct cellT *link;
} cellT;
O campo key é uma palavra do texto que estamos analisando. O campo value é o endereço de um inteiro cujo valor é o número de ocorrências de key no texto. Assim, se c é uma variável do tipo cellT* então temos *(c->value) ocorrências de c->key.
/////////////////////////////////////////////////////////// // Implementação simplória de uma tabela de símbolos // A tabela é representada por um registro do tipo symbtabT. // O registro contém o endereço de uma lista encadeada de // células do tipo cellT. /////////////////////////////////////////////////////////// typedef struct { cellT *list; } symbtabT; // A função abaixo coloca na tabela de símbolos t a chave k // associada com o valor v. Se a tabela já tinha a chave k // (associada com alguma valor), o valor antigo é substituído // por v. void Enter( symtabT *t, string k, int *v) { cellT *cp; cp = t->list; while (cp != NULL && strcmp( cp->key, k) != 0) cp = cp->link; if (cp == NULL) { cp = malloc( sizeof (cellT)); cp->key = copyString( k); cp->link = t->list; t->list = cp; } cp->value = v; } // Esta função auxiliar faz uma cópia da string s. O espaço // para a cópia é alocado por malloc. Esta função foi inspirada // na CopyString da biblioteca strlib de Eric Roberts. string copyString( string s) { string newstr; newstr = malloc( strlen( s) + 1); if (newstr == NULL) exit( EXIT_FAILURE); strcpy( newstr, s); return newstr; } // A função abaixo devolve o valor que a tabela t associa com // a chave k. Se k não estiver associado com valor algum, // a função devolve NULL. int *Lookup( symbtabT *t, string k) { cellT *cp; cp = t->list; while (cp != NULL && strcmp( cp->key, k) != 0) cp = cp->link; if (cp == NULL) return NULL; return cp->value; }
Além das funções "principais" Enter e Lookup, é importante que nossa implementação de tabela de símbolos tenha algumas funções "auxiliares":
// Esta função cria uma tabela de símbolos vazia. symbtabT *NewSymbolTable( void) { symbtabT *t; t = malloc( sizeof (symbtabT)); t->list = NULL; return t; } // Esta função destrói a tabela de símbolos t. void FreeSymbolTable( symbtabT *t) { cellT *cp, *next; cp = t->list; while (cp != NULL) { next = cp->link; free( cp->key); free( cp); cp = next; } free( t); }
Infelizmente, essa implementação da tabela de símbolos é muito ineficiente, pois cada invocação de Enter e Lookup percorre a tabela toda.
Vamos à solução do problema proposto no começo da página. Além da tabela de símbolos discutida acima, nosso programa usa o token scanner que discutimos em outra página.
Observe que o programa de contagem de palavras (que é o "cliente" da tabela se símbolos) faz questão de manipular a tabela de símbolos apenas através das funções
Enter, Lookup, NewSymbolTable e FreeSymbolTable.
Em particualr, o programa-cliente faz questão de não se referir diretamente as campos key, value e link da estrutura da tabela se símbolos.
// O programa recebe, via linha de comando, o nome de um // arquivo que contém um texto e o nome de um arquivo que // contém uma lista de palavras. O programa faz uma tabela // do número de ocorrências de cada palavra do segundo // arquivo no primeiro. int main( int argc, char *argv[]) { FILE *infile, queriesfile; string line, token; scannerT *scanner; symtabT *table; scanner = NewScanner(); table = NewSymbolTable(); infile = fopen( argv[1], "r"); if (infile == NULL) exit( EXIT_FAILURE); while ((line = readLine( infile)) != NULL) { int i; for (i = 0; line[i] != '\0'; i++) line[i] = tolower( line[i]); SetScannerString( scanner, line); while (MoreTokensExist( scanner)) { token = GetNextToken( scanner); if (isalpha( token[0])) RecordWord( table, token); } } fclose( infile); FreeScanner( scanner); queriesfile = fopen( argv[2], "r"); if (queriesfile == NULL) exit( EXIT_FAILURE); printf( "Número de ocorrências de palavras no texto:\n"); AnswerQueries( queriesfile, table); fclose( queriesfile); return 0; } // Esta função registra a palavra word na tabela // de símbolos table. void RecordWord( symbtabT *table, string word) { int *v; v = Lookup( table, word); if (v == NULL) { v = malloc( sizeof (int)); if (v == NULL) exit( EXIT_FAILURE); *v = 0; Enter( table, word, v); } (*v)++; } // Esta função imprime uma tabela com o número de // ocorrências de cada palavra do arquivo q na tabela // de símbolos t. void AnswerQueries( FILE *q, symbtabT *t) { string line, word; scannerT *scanner; scanner = NewScanner(); while ((line = readLine( q)) != NULL) { int i; for (i = 0; line[i] != '\0'; i++) line[i] = tolower( line[i]); SetScannerString( scanner, line); while (MoreTokensExist( scanner)) { word = GetNextToken( scanner); if (isalpha( word[0])) { int *v, ocurr; v = Lookup( table, word); ocurr = (v == NULL) ? 0 : *(v); printf( "%-15s%5d\n", word, ocurr); } } } FreeScanner( scanner); } // Essa função auxiliar lê uma linha do arquivo infile e // devolve a linha na forma de uma string. A linha deve ter // no máximo 100 caracteres. A função devolve NULL se o // arquivo infile não tiver mais linhas. Esta função foi // inspirada na ReadLine da biblioteca simpio de Eric // Roberts, mas é bem mais simples que aquela. string readLine( FILE *infile) { string line; int n, ch; n = 0; line = malloc( 100+1); while ((ch = getc( infile)) != '\n' && ch != EOF) { if (n >= 100) { free( line); exit( EXIT_FAILURE); } line[n++] = ch; } if (n == 0 && ch == EOF) { free( line); return NULL; } line[n] = '\0'; return line; }
A implementação da tabela de símbolos que fizemos acima é muito ineficiente pois cada invocação de Enter e Lookup percorre a tabela toda. Uma implementação bem mais eficiente usa o conceito de tabela de dispersão (= hash table).
Ao invés de uma única lista t->list teremos várias listas. Os endereços dessas listas serão armazenadas em um vetor buckets. Portanto, o tipo-de-dados symbtabT será redefinido assim:
#define NBuckets 101
typedef struct {
cellT *buckets[NBuckets];
} symbtabT;
Para determinar a particular a lista em que uma dada chave será armazenada, ou seja, para determinar o índice h tal que a chave key será armazenada na lista buckets[h], usaremos a função Hash. Essa função
recebe uma chave k e
devolve um número no intervalo fechado [0..NBuckets-1].
É fundamental que Hash seja uma função no sentido matemático do termo, isto é, que para cada chave k ela devolva sempre o mesmo número. A função será tanto mais útil quando melhor espalhar as chaves pelo intervalo [0..NBuckets-1].
/////////////////////////////////////////////////////////// // Função de dispersão (= hash function) /////////////////////////////////////////////////////////// #define Multiplier -1664117991L // A função abaixo calcula um número hashcode a partir de // uma string k. O número hashcode calculado pertence ao // intervalo [0 .. n-1]. int Hash( string k, int n) { int i; unsigned long hashcode; hashcode = 0; for (i = 0; k[i] != '\0'; i++) hashcode = hashcode * Multiplier + k[i]; return hashcode % n; }
O valor de Multiplier não é crítico para o funcionamento do algoritmo. Mas a experiência mostra que o valor adotado acima contribui para fazer com que o índice calculado por Hash pareça aleatório. (Algumas pessoas preferem usar um número primo grande como valor de Multiplier.)
Por razões que não vou tentar explicar aqui, o resultado do processo de hashing é melhor (ou seja, produz um índice com aparência aleatória) se a constante
NBuckets é um número primo.
int Hash( string k, int n) {
static int i = 0;
return (i + 1) % n;
}