Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

c:verificador_ortografico [2023/08/01 19:11] – criada mazieroc:verificador_ortografico [2023/08/01 19:26] (atual) – edição externa 127.0.0.1
Linha 1: Linha 1:
 +====== Verificador ortográfico ======
 +
 +:!: Este projeto foi aprimorado e atualizado para o formato UTF-8.
 +
 +{{ spell-checker.png?150|}} Este projeto visa implementar um verificador ortográfico simples, que verifica se as palavras de um texto de entrada estão em um dicionário predefinido e sugere correções para as palavras não encontradas.
 +
 +===== Descrição =====
 +
 +O verificador de ortografia recebe um texto de entrada e verifica se suas palavras estão em um dicionário. A saída deve **reproduzir fielmente o texto de entrada** (inclusive espaços e quebras de linha), mas colocando entre colchetes as palavras não encontradas no dicionário.
 +
 +Por exemplo, para esta entrada:
 +
 +<code>
 +   Para que o pocessador possa interromper a execução de uma
 +tarefa e retornar a ela mais tarde, sem corromper seu estado
 +interno, é necessário definir operações para salvar e
 +restaurrar o contexto da tarefa.
 +===
 +   O ato de salvar os valores do contexto atual em seu TCB e
 +possivelmente restaurar o contexto de outra tarefa, previamente
 +salvo em outro TCB, é denominado "troca de contexto".
 +</code>
 +
 +O programa deve gerar esta saída:
 +
 +<code>
 +   Para que o [pocessador] possa interromper a execução de uma
 +tarefa e retornar a ela mais tarde, sem corromper seu estado
 +interno, é necessário definir operações para salvar e 
 +[restaurrar] o contexto da tarefa.
 +===
 +   O ato de salvar os valores do contexto atual em seu [TCB] e
 +possivelmente restaurar o contexto de outra tarefa, previamente
 +salvo em outro [TCB], é denominado "troca de contexto".
 +</code>
 +
 +Consideram-se como palavras as sequências contíguas de letras (A-Z, a-z) com ou sem acentos e as cedilhas; os demais caracteres (números, espaços e outros símbolos) não fazem parte de palavras.
 +
 +Exemplos de arquivos de texto com erros de ortografia, no formato UTF-8 (baixe com "salvar como", para evitar conversões de caracteres indesejadas):
 +
 +  * {{plutao.txt|}}, 2.283 bytes
 +  * {{memoria.txt|}}, 3.203 bytes
 +  * {{brascubas.txt|}}, 360.681 bytes
 +  * {{montesquieu.txt|}}, 1.288.323 bytes
 +  * {{brazilian.gz}}, dicionário com ~275 mil palavras
 +
 +<note important>
 +Os arquivos acima e o dicionário estão no formato UTF-8, que é o padrão da maioria dos sistemas atuais. Esse formato pode usar mais de um byte por caractere para representar letras acentuadas e sinais gráficos. Se for usar outros textos, assegure-se de que também estejam no formato UTF-8.
 +</note>
 +
 +===== Sugestões =====
 +
 +Um bom verificador ortográfico deve **sugerir correções** para as palavras incorretas. Programe o verificador para informar as palavras conhecidas mais próximas das palavras não encontradas no dicionário, como mostra este exemplo:
 +
 +<code>
 +   Para que o [pocessador (processador)] possa interromper a execução de uma
 +tarefa e retornar a ela mais tarde, sem corromper seu estado
 +interno, é necessário definir operações para salvar e
 +[restaurrar (restaurar)] o contexto da tarefa.
 +===
 +   O ato de salvar os valores do contexto atual em seu [TCB (aba)] e
 +possivelmente restaurar o contexto de outra tarefa, previamente
 +salvo em outro [TCB (aba)], é denominado "troca de contexto".
 +</code>
 +
 +Para encontrar a palavra mais próxima no dicionário, sugere-se usar a [[https://pt.wikipedia.org/wiki/Dist%C3%A2ncia_Levenshtein|distância Levenshtein]], que permite calcular a distância entre duas strings.
 +
 +<note important>
 +O algoritmo de Levenshtein é lento, portanto evite comparar palavras de comprimentos muito diferentes (por exemplo, evite calcular a distância entre "uva" e "laranja").
 +</note>
 +
 +===== Forma de chamada =====
 +
 +<code>
 +$ ortografia [-s] [ -d dicionário ] [ -i entrada ] [ -o saída ]
 +</code>
 +
 +Opções:
 +
 +  * ''-i'' : indica o arquivo de entrada; se não for informado, assume-se a entrada padrão (//stdin//).
 +  * ''-o'' : indica o arquivo de saída; se não for informado, assume-se a saída padrão (//stdout//).
 +  * ''-d'' : indica o arquivo de dicionário, em formato UTF-8; se não for informado, assume-se o dicionário do sistema operacional em ''/usr/share/dict/brazilian''.
 +  * ''-s'' : ativa a sugestão de correções usando a distância de Levenshtein (por default desativada).
 +  * ''-h'' : gera uma mensagem de ajuda na saída de erro (//stderr//), explicando o que o programa faz e quais as opções disponíveis.
 +  * Todas as mensagens de erro devem ser enviadas para a saída de erro (//stderr//).
 +
 +Essas opções podem ser usadas em qualquer ordem:
 +
 +<code>
 +// entrada e saída em arquivos
 +ortografia -i input.txt  -o output.txt
 +ortografia -o output.txt -i input.txt
 +
 +// entrada em arquivo, saída em stdout, vice-versa ou ambos
 +ortografia -i input.txt  > output.txt
 +ortografia -o output.txt < input.txt
 +ortografia <  input.txt  > output.txt
 +
 +// as opções podem estar em qualquer ordem
 +ortografia -d brazilian -i input.txt -o output.txt
 +ortografia -i input.txt -d brazilian -o output.txt -s
 +ortografia -o output.txt -s -i input.txt -d brazilian
 +</code>
 +
 +===== Atividade =====
 +
 +A implementação deve atender os seguintes requisitos:
 +
 +  * Funcionar corretamente com os exemplos desta página m(
 +  * O dicionário deve ser totalmente carregado em um vetor de palavras na memória RAM antes de ser usado, usando alocação dinâmica (os mais ousados podem tentar implementar este projeto usando uma [[https://pt.wikipedia.org/wiki/Trie|árvore de prefixos]]).
 +  * A localização das palavras no dicionário deve usar um algoritmo de [[https://en.wikipedia.org/wiki/Binary_search_algorithm|busca binária]].
 +  * O executável deve se chamar ''ortografia''.
 +  * Usar ''Makefile'' com ao menos os alvos ''all'', ''clean'' e ''purge''.
 +  * Não gerar //warnings// ao compilar com a opção ''-Wall''.
 +  * Processar o arquivo ''brascubas.txt'' em **menos de 1 segundo** (com sugestões desativadas).
 +
 +Para medir o tempo de execução do programa, use o comando ''time'':
 +
 +<code>
 +time ./ortografia -i brascubas.txt -o output.txt
 +</code>
 +
 +Arquivos a entregar ao professor:
 +
 +  * ''ortografia.c'' : programa principal
 +  * ''dicionario.c'' : funções relativas ao dicionário (carregar o dicionário na memória, verificar se uma palavra está no dicionário, etc);
 +  * ''dicionario.h'' : interface (protótipos) das funções implementadas em ''dicionario.c'';
 +  * ''Makefile''
 +
 +**Dica**: as funções da biblioteca C padrão (StdLib) podem facilitar a implementação de seu programa:
 +
 +  * Acesso a arquivos: ''fopen'', ''fclose'', ''fgetchar'' ''fscanf'', ''feof'', ...
 +  * Uso de caracteres e strings largas: ''getwchar'', ''putwchar'', ''iswalpha'', ''towlower'', ''wcslen'', ''fwscanf'', ''wcscpy'', ''wcscasecmp'', ... 
 +  * Busca binária: ''bsearch''
 +  * Ordenação: ''qsort''
 +
 +Consulte as páginas de manual para aprender a usar essas funções.
 +
 +===== Sugestões de implementação =====
 +
 +Por pseudocódigo:
 +
 +<code>
 +ler o dicionário em um vetor de palavras
 +
 +c = ler caractere da entrada
 +
 +enquanto não for o fim da entrada faça
 +  
 +  // avançar até encontrar uma letra ou o fim da entrada 
 +  enquanto (c não for uma letra) e (não for o fim da entrada) faça
 +    escrever c em stdout
 +    c = ler caractere da entrada
 +  fim enquanto
 +
 +  // encontrou uma letra, ler a palavra inteira
 +  palavra = ""
 +  enquanto (c for uma letra) e (não for o fim da entrada) faça
 +    palavra = palavra + c
 +    c = ler caractere da entrada
 +  fim enquanto
 +
 +  // tratar a palavra encontrada 
 +  se palavra <> "" então
 +    se minúscula(palavra) está no dicionário então
 +      escrever palavra na saída
 +    senão
 +      escrever "[", palavra, "]" na saída
 +    fim se
 +  fim se
 +
 +fim enquanto
 +</code>
 +
 +Por máquina de estados:
 +
 +{{ fsm-verificador.png |}}
 +
 +<code>
 +state = 0
 +while state ≠ 2 do
 +
 +   read input
 +
 +   case (state)
 +
 +      0: case (input)
 +
 +            letter:
 +               append input to word
 +               state = 1
 +
 +            not letter:
 +               print input
 +
 +            eof:
 +               state = 2
 +
 +         end case
 +
 +      1: case (input)
 +
 +            letter:
 +               append input to word
 +
 +            not letter:
 +               check word
 +               print word
 +               reset word
 +               state = 0
 +
 +            eof:
 +               check word
 +               print word
 +               state = 2
 +
 +         end case
 +
 +   end case
 +end while
 +</code>