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).
- 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.
- 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").
- 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:
- 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
- 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.
- 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
- Começe com a parte de busca interativa, fazendo esta parte funcionar.
- Construa uma função achaPalavra(char texto[], char palavra[], int inicio), que,
- 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).
- Se "palavra[]" não ocorrer em "texto[]", o sistema retornará o valor -1.
- Faça um programa que chama a função acima para testá-la.
- 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.
|