Disciplina Estruturas de Dados - Prof. Aldo von Wangenheim

Home
Árvores e Multilistas

Projeto de Implementação II: Utilizando Arquivos Invertidos para Suporte à Busca Textual Indexada

Requisitos

FAQ

Pesquisa de Co-Ocorrência em duas Listas Não-Ordenadas
Eliminando Acentuação
Lendo arquivo texto até o fim em C++
Como saber os nomes de todos os arquivos de Portarias?

Links para Dados

Requisitos

Como foi visto em aula, as formas de indexação de arquivos utilizando listas são muito úteis para indexação por chave secundária. Quando os dados se encontram na forma de arquivos-texto contendo palavras-chave ou referências por metadados, então a Lista Invertida ou Arquivo Invertido é a forma de representação de nossa escolha.

Neste trabalho você implementará um sistema de recuperação de informações de um banco de dados contendo portarias de diversos órgãos da UFSC. Para tanto você utilizará o arquivo .rar abaixo, o qual contém 805 portarias na forma de arquivos-texto.

O software que você vai desenvolver deverá satisfazer os seguintes requisitos:

Dados:

As Portarias serão armazenadas em um arquivo de dados.
O texto completo de cada Portaria será armazenado em um campo de um registro. O registro deverá conter, além disso, um campo para a chave primária e outrros que o programador considerar necessários.
Todos os índices secundários referenciarão o campo texto como um todo, sem se preocupar com onde esteja a palavra-chave indexada no texto.

Indexação

Manter um índice primário em arquivo separado e que referencia as portarias por nome, ex: 0010_GR_1973. Este índice pode ser baseado em uma estrutura que você já programou como a árvore-B ou AVL.
Manter um conjunto de índices de chave secundária na forma de arquivo invertido. Este índice indexará um conjunto de 20 palavras pré-definidas: Reitor, Vice, Professor, Chefe, Departamento, Mecânica, Elétrica, Química, Letras, Filosofia, Humanas, Ciências, Computação, Sanitária, Materiais, Engenharia, Inglês, Alemão, Italiano, Direito.

O software desenvolvido deverá ser capaz de realizar as seguintes buscas:

Por chave primária, retornando o texto da portaria para um nome-de-portaria ou a mensagem de que uma portaria com aquele nome não existe (3 pontos)
Busca simples por chave secundária, retornando todas as portarias que contém uma determinada chave secundária, ex.: Reitor (4 pontos)
Busca conjuntiva com duas chaves secundárias, retornando todas as portarias que contenham ambas as chaves. Ex.: Vice e Reitor (3 pontos)

Para satisfazer estes requisitos o sistema deverá gerenciar um arquivo de dados, um arquivo de índices de chave primária e tantos arquivos de índices de chave secundárfia quantos forem necessários.

Lembre-se que para a pesquisa conjuntiva você deve gerar uma tabela temporária. Esta pode ser gerada na memória como um vetor. Para realizar a pesquisa comparativa você pode usar o algoritmo de Pesquisa de Co-Ocorrência em duas Listas Não-Ordenadas.

A entrada dos dados deverá ser realizada da seguinte forma:

Cada arquivo-texto de uma portaria é lido e armazenado em um registro, cujo endereço é guardado
Percorre-se o texto (na memória) palavra a palavra e verifica-se, para cada palavra, se ela se encontra na lista de palavras-chave.
Para cada palavra-chave encontrada, atualiza-se uma lista de endereços de chave secundária com o endereço do registro
Finalmente o índice de chave primária e alimentado.

FAQ

Pesquisa de Co-Ocorrência em duas Listas Não-Ordenadas

O algoritmo abaixo pressupõe que as listas a serem pesquisadas são armazenadas em vetores, sendo chamadas lista1 e lista2, sendo que lista1 é a maior das duas. Se você usar listas encadeadas a referência lista_n[posição] deve ser substituída pela função que retorna o próximo elemento da lista.

tipoLista: função coOcorrencia( lista1, lista2: tipoLista )
VARIÁVEIS

INTEIRO
i, j;

tipoLista   saida;

INÍCIO

PARA i de 1 até
tamanho(lista1) FAÇA
procurado <- lista1[i];
PARA j de 1
até tamanho(lista2) FAÇA
SE  lista2[j] = procurado
ENTÃO
adicione(saida, procurado);

      
FIM SE

      
FIM PARA

      

FIM PARA

RETORNE( saída );

FIM coOcorrencia

Eliminação de Acentuação

Existe uma discussão neste fórum: http://stackoverflow.com/questions/144761/how-to-remove-accents-and-tilde-in-a-c-stdstring

Eu já prefiro pegar a tabela ASCII Latin 1 (abaixo) e simplesmente escrever uma função que toma um string caracter a caracter (em "C" pode ser referenciado pelo seu código ASCII se você comparar seu valor numérco) e simplesmente fazer tabelas de substituição, tipo: todos os valores ASCII entre 192 e 198 e entre 224 e 230 são substituídos por ASCII 65 "A". Para passar o resto do texto da portaria para maiúsculo use a função "C" toupper().

Latin 1 character set

 32             160         Non-breaking space
 33    !        161    ¡    Inverted exclamation
 34    "        162    ¢    Cent sign
 35    #        163    £    Pound sterling
 36    $        164    ¤    General currency sign
 37    %        165    ¥    Yen sign
 38    &        166    ¦    Broken vertical bar
 39    '        167    §    Section sign
 40    (        168    ¨    Umlaut (dieresis)
 41    )        169    ©    Copyright
 42    *        170    ª    Feminine ordinal
 43    +        171    «    Left angle quote, guillemotleft
 44    ,        172    ¬    Not sign
 45    -        173        Soft hyphen
 46    .        174    ®    Registered trademark
 47    /        175    ¯    Macron accent
 48    0        176    °    Degree sign
 49    1        177    ±    Plus or minus
 50    2        178    ²    Superscript two
 51    3        179    ³    Superscript three
 52    4        180    ´    Acute accent
 53    5        181    µ    Micro sign
 54    6        182    ¶    Paragraph sign
 55    7        183    ·    Middle dot
 56    8        184    ¸    Cedilla
 57    9        185    ¹    Superscript one
 58    :        186    º    Masculine ordinal
 59    ;        187    »    Right angle quote, guillemotright
 60    <        188    ¼    Fraction one-fourth
 61    =        189    ½    Fraction one-half
 62    >        190    ¾    Fraction three-fourths
 63    ?        191    ¿    Inverted question mark
 64    @        192    À    Capital A, grave accent ("&Agrave;")
 65    A        193    Á    Capital A, acute accent ("&Aacute;")
 66    B        194    Â    Capital A, circumflex accent ("&Acirc;")
 67    C        195    Ã    Capital A, tilde ("&Atilde;")
 68    D        196    Ä    Capital A, dieresis or umlaut mark ("&Auml;")
 69    E        197    Å    Capital A, ring ("&Aring;")
 70    F        198    Æ    Capital AE dipthong (ligature) ("&AElig;")
 71    G        199    Ç    Capital C, cedilla ("&Ccedil;")
 72    H        200    È    Capital E, grave accent ("&Egrave;")
 73    I        201    É    Capital E, acute accent ("&Eacute;")
 74    J        202    Ê    Capital E, circumflex accent ("&Ecirc;")
 75    K        203    Ë    Capital E, dieresis or umlaut mark ("&Euml;")
 76    L        204    Ì    Capital I, grave accent ("&Igrave;")
 77    M        205    Í    Capital I, acute accent ("&Iacute;")
 78    N        206    Î    Capital I, circumflex accent ("&Icirc;")
 79    O        207    Ï    Capital I, dieresis or umlaut mark ("&Iuml;")
 80    P        208    Ð    Capital Eth, Icelandic ("&ETH;")
 81    Q        209    Ñ    Capital N, tilde ("&Ntilde;")
 82    R        210    Ò    Capital O, grave accent ("&Ograve;")
 83    S        211    Ó    Capital O, acute accent ("&Oacute;")
 84    T        212    Ô    Capital O, circumflex accent ("&Ocirc;")
 85    U        213    Õ    Capital O, tilde ("&Otilde;")
 86    V        214    Ö    Capital O, dieresis or umlaut mark ("&Ouml;")
 87    W        215    ×    Multiply sign
 88    X        216    Ø    Capital O, slash ("&Oslash;")
 89    Y        217    Ù    Capital U, grave accent ("&Ugrave;")
 90    Z        218    Ú    Capital U, acute accent ("&Uacute;")
 91    [        219    Û    Capital U, circumflex accent ("&Ucirc;")
 92    \        220    Ü    Capital U, dieresis or umlaut mark ("&Uuml;")
 93    ]        221    Ý    Capital Y, acute accent ("&Yacute;")
 94    ^        222    Þ    Capital THORN, Icelandic ("&THORN;")
 95    _        223    ß    Small sharp s, German (sz ligature) ("&szlig;")
 96    `        224    à    Small a, grave accent ("&agrave;")
 97    a        225    á    Small a, acute accent ("&aacute;")
 98    b        226    â    Small a, circumflex accent ("&acirc;")
 99    c        227    ã    Small a, tilde ("&atilde;")
100    d        228    ä    Small a, dieresis or umlaut mark ("&auml;")
101    e        229    å    Small a, ring ("&aring;")
102    f        230    æ    Small ae dipthong (ligature) ("&aelig;")
103    g        231    ç    Small c, cedilla ("&ccedil;")
104    h        232    è    Small e, grave accent ("&egrave;")
105    i        233    é    Small e, acute accent ("&eacute;")
106    j        234    ê    Small e, circumflex accent ("&ecirc;")
107    k        235    ë    Small e, dieresis or umlaut mark ("&euml;")
108    l        236    ì    Small i, grave accent ("&igrave;")
109    m        237    í    Small i, acute accent ("&iacute;")
110    n        238    î    Small i, circumflex accent ("&icirc;")
111    o        239    ï    Small i, dieresis or umlaut mark ("&iuml;")
112    p        240    ð    Small eth, Icelandic ("&eth;")
113    q        241    ñ    Small n, tilde ("&ntilde;")
114    r        242    ò    Small o, grave accent ("&ograve;")
115    s        243    ó    Small o, acute accent ("&oacute;")
116    t        244    ô    Small o, circumflex accent ("&ocirc;")
117    u        245    õ    Small o, tilde ("&otilde;")
118    v        246    ö    Small o, dieresis or umlaut mark ("&ouml;")
119    w        247    ÷    Division sign
120    x        248    ø    Small o, slash ("&oslash;")
121    y        249    ù    Small u, grave accent ("&ugrave;")
122    z        250    ú    Small u, acute accent ("&uacute;")
123    {        251    û    Small u, circumflex accent ("&ucirc;")
124    |        252    ü    Small u, dieresis or umlaut mark ("&uuml;")
125    }        253    ý    Small y, acute accent ("&yacute;")
126    ~        254    þ    Small thorn, Icelandic ("&thorn;")
127            255    ÿ    Small y, dieresis or umlaut mark ("&yuml;")

Lendo arquivo texto até o fim em C++

http://www.cplusplus.happycodings.com/code_snippets/code11.html

Como saber os nomes de todos os arquivos de Portarias?

Use o sistema operacional para isso: Existem dois parâmetros-padrão da função main, argc e argv:

argc (argument count) indica quantos argumentos de linha de comando foram passados ao programa. O valor default é 1 pois o programa em C sempre recebe seu próprio nome como parâmetro. Se o valor for maior do que um é porque foi passada alguma coisa a mais.
argv (argumento vector) é um vetor de ponteiros para strings que contém cada um dos argumentos passados como parâmetro. Os critérios de separação de argumentos são os do scanf: tudo o que for separador gera argumentos separados. Tipicamente utilizamos espaços em branco.

Um típico código usando argc e argv é esse (programa testeparam.c):

#include <stdio.h>
main (int argc, char* argv[]) {
	int i;
	printf("\n Arquivos: %d \n", argc - 1);

	for (i=1; i < argc; i++) {

   		printf("--> %s\n", argv[i]);

Esse código serve para imprimir todos os nomes de arquivo de um diretório ou para imprimir qualquer coisa que você passe como parâmetro. Observe que eu estou iniciando o contador i em 1 porque argv[0] é o nome do programa e não me interessa.

Se eu fizer: venus{92}/home/professores/awangenh> ./testeparam *.gz

 Arquivos: 8

--> Cyclops-DMI.st.gz

--> Cyclops-ErrorHandling.st.gz

--> Cyclops-funca-DMI.st.gz

--> Cyclops.ppt.gz

--> cyclopsDicomUS.xml.gz

--> cyclopsErrorMessagesBR.xml.gz

--> materialalden.html.gz

--> Page.ws.gz

venus{93}/home/professores/awangenh>

Se eu fizer:

venus{93}/home/professores/awangenh> ./testeparam banana abacaxi Arquivos: 2 --> banana --> abacaxi venus{94}/home/professores/awangenh>