MAC110 - TURMA 42 - www.ime.usp.br/~leo/mac110 cab-mac110-2004.gif
MAC 110 - 2004 Prof. Leônidas


Construir um sistema para buscas em textos

Atenção: Como NÃO teremos o EP3, foi acrescentado ao EP2 mais uma tarefa que é ordenar (lexicograficamente) a lista de palavras (em [06/12/2004]). Entretanto o prazo também foi extendido.


Última alteração em: 07/12/2004

Data de entrega: até 20/12/2004

Sistema

O sistema a ser construido trabalhará com processamento de palavras. Por exemplo, ele deverá ser capaz de determinar o número de ocorências de uma lista de palavras dadas dentro de um texto (também fornecido de algum modo).

Observação:: neste sistema NENHUMA função da biblioteca "string" deve utilizada, a menos de duas exceções:
  • pode-se utilizar, em qualquer parte, a função strlen(str) (que devolve comprimento da "string" str) e
  • pode-se utilizar, APENAS na função que ordena o vetor de palvras, a função strcmp(str1, str1) (que devolve: -1 se str1 "<=" str2; 0 se str1 "==" str2 e -1 se str1 ">=" str2, considerando a ordem léxica).

  1. palavra: Neste sistema, palavra deve ser entendido como qualquer sequência de letras, números e o símbolo '_', desde que começando com uma letra ou com '_'. Por exemplo,
    palavras não palavras
    while 0while
    _if 0if
    palavra 2*3
    _23 23_
    esta_é_uma_palavra esta_NÃO_é_uma_palavra!
    A última sequência não é palavra por ter um caractere '!' ao final.

  2. As "palavras" devem ser entendidas como na lingua portuguesa, por exemplo, ao procurar a palavra eu dentro do texto 1000.como o seu ou eu,vai, deve produzir como resposta positiva o último "eu" (o "eu" dentro da palavra "seu", não deve ser considerado, já que a palavra é "seu").
  3. A listagem das palavras e suas respectivas frequências deve ser feita em ordem lexicografica crescente (este é o adendo ao enunciado original para substituir o EP3)

Recursos

Se o arquivo executável receber o nome sistema.o, ele deve ser chamado via linha de comando com 3, 2 ou 0 parâmetros, respectivamente:

     [.../mac110/ep2/> ./sistema2.o texto.txt palavras.txt saida.txt
     [.../mac110/ep2/> ./sistema2.o texto.txt saida.txt
     [.../mac110/ep2/> ./sistema2.o

sendo saida.txt o arquivo que guardará as respostas produzidas (em formato texto padrão), texto.txt o arquivo de entrada com o texto onde as palavras serão procuradas e palavras.txt o arquivo de entrada com as palavras que serão buscadas dentro de texto.txt.

Assim, o número de parâmetros determinar automaticamente como seu programa deve atuar, sendo uma das três seguintes:

  1. Parâmetro externo: leitura de arquivos, com nomes fornecidos em linha de comando.
    O usuário poderá colocar uma lista de palavras, uma por linha, num arquivo de nome, digamos palavras.txt, e instruir o programa a procurar o número de ocorrências de cada uma destas palavras num outro arquivo texto, por exemplo, de nome texto.txt.
    No arquivo texto.txt, as palavras devem aparecer em ordem lexicografica crescente. Veja abaixo como esta ordenação deve ser feita.
    Isso deverá ser feito numa linha de comando. Por exemplo, se o executável tiver o nome sistema2.o, a chamada será do tipo:
         [.../mac110/ep2/> ./sistema2.o texto.txt palavras.txt saida.txt
         
  2. Parâmetro externo: entrada/saída de dados via arquivos (com três nomes de arquivo válidos), fornecidos em linha de comando.
         [.../mac110/ep2/> ./sistema2.o texto.txt saida.txt
         
    Neste caso o sistema lerá o arquivo de entrada e construirá uma lista de frequência para todas as diferentes palavras que aparecem no texto.
  3. Busca interativa: entrada/saída de dados via teclado, o sistema deve permitir que o usuário digite uma frase e depois digite várias palavras separadas por espaço em branco. O sistema devolverá a frequência de cada uma delas no frase inicial.

Veja aqui: exemplo de parâmetro passado para a função main e exemplo de leitura/escrita de arquivos.

Implementação

  1. Começe com a parte de busca interativa, fazendo esta parte funcionar.
  2. Construa uma função achaPalavra(char texto[], char palavra[], int inicio), que,
    1. Se a palavra ocorrer no texto, devolve o primeiro índice de coincidência, ou seja, devolve i, tal que texto[i]=palavra[0], texto[i+1]=palavra[1] e assim por diante até texto[i+k-1]=palavra[k-1]   (supondo que palavra tem k caracteres). Por exemplo, se
                  //            0         1         2         3         4
                  //            01234567890123456789012345678901234567890
                  char texto = "esta é a frase, onde buscaremos a palavra";
                  palavra    = "onde";
                  
      o sistema devolverá o inteiro 16 (veja a contagem de caracteres em comentário).
    2. Se "palavra[]" não ocorrer em "texto[]", o sistema retornará o valor -1.
  3. Faça um programa que chama a função acima para testá-la.
  4. Construa uma função que recebe um vetor de palavras (e seu tamanho em termos de número de palavras) e um vetor de índices ordem ("permutação") e ordena as palavras de acordo com o vetor de permutação.
    Por exemplo, considerando um vetor de inteiros v que precisa ser ordenado, a função deveria devolver um vetor ord de tal modo que
    v[ ord[ i ] ] <= v[ ord[ j ] ], quaisquer que sejam i e j, i<=j.


MAC 110 Prof. Leônidas

Compilado em: 7 de Dezembro de 2004