Igrep - Um Sistema para Busca Aproximada em Textos Indexados

• Márcio Drumond Araújo UFMG
• Nivio Ziviani UFMG

DOI: https://doi.org/10.5753/sbes.1997.24065

Resumo

O presente trabalho apresenta o sistema IGREP para busca aproximada em textos de grande porte desenvolvido através da dissertação [Ara97]. O IGREP faz uso de uma lista invertida, composta por uma tabela contendo o vocabulário de palavras do texto e uma lista de endereços no texto correspondendo às ocorrências no mesmo de cada palavra do vocabulário. O tamanho do vocabulário é menos do que 1% do tamanho do texto como um todo, fazendo com que seja possível a sua manutenção em memória principal durante todo o processo de busca. Para consultas contendo uma palavra, a busca fica restrita apenas ao vocabulário. Para consultas contendo mais de uma palavra, a busca fica restrita ao vocabulário e respectivas listas de endereços, não havendo pois nenhum acesso ao texto na fase de pesquisa. O sistema permite desde a busca com erros ou não de palavras e frases até buscas de sequências complexas contendo conjuntos de caracteres, caracteres coringa e expressões regulares arbitrárias. O tempo de busca é O(√n) para casos típicos. Os resultados experimentais mostram que o sistema funciona bem na prática: para um texto de 1 gigabyte, casamentos compostos por 3 palavras com até 1 erro são recuperados em aproximadamente 6 segundos. No caso de busca sem erro, as ocorrências são obtidas em menos de meio segundo. O sistema contém duas ferramentas: O IGREPINDEX destinado a construção da lista invertida e o IGREP responsável pela parte de busca de padrões.

Referências

M. D. Araújo. Igrep - um sistema para busca aproximada em textos indexados. Master's thesis, Department of Computer Science, Universidade Federal de Minas Gerais, March 1997. (Supervisor: N. Ziviani).

D. K. Harman. Overview of the third text retrieval conference. In Proc. Third Tezt REtrieval Conference (TREC-S), pages 1-19, Gaithersburg, Maryland, USA, 1995. National Institute of Standards and Technology Special Publication.

A. Moffat and T. Bell. In situ generations of compressed inverted files. Journal of the American Society for Information Science, 46(7):537-550, 1995.

W. Manber and S. Wu. Glimpse: A tool to search through entire file systems. Technical Report 93-34, Dept. of Computer Science, The University of Arizona, Oct. 1993.