Verificador ortográfico

Video desta aula

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.

O verificador de ortografia recebe um texto lido da entrada padrão (stdin) e verifica se suas palavras estão em um dicionário. A saída padrão (stdout) 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:

   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".

O programa deve gerar esta saída:

   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".

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.

A forma de chamada do programa é:

./ortografia < entrada.txt > saida.txt

Exemplos de arquivos de texto com erros de ortografia, no formato ISO-8859-1 (baixe com “salvar como”, para evitar conversões de caracteres indesejadas):

Os arquivos acima e o dicionário estão no formato ISO-8859-1, que usa um byte por caractere para representar letras e sinais gráficos na tabela ASCII estendida (com 256 caracteres). Se for usar outros textos, assegure-se de que também estejam no formato ISO-8859-1, para facilitar seu trabalho.

No Linux, use o comando sudo locale-gen pt_BR para adicionar o locale ISO-8859-1 ao seu sistema operacional.

As palavras encontradas que não constam no dicionário são colocadas entre colchetes e a palavra mais próxima encontrada é sugerida entre parênteses, como mostra este exemplo:

[pocessador (processador)]

Para encontrar a palavra mais próxima no dicionário deve ser usada a distância Levenshtein.

A implementação deve atender os seguintes requisitos:

  • Funcionar corretamente com os exemplos desta página m(
  • Ler o dicionário de /usr/share/dict/brazilian (não precisa copiar o arquivo para seu diretório); no Ubuntu e derivados, esse arquivo é provido pelo pacote wbrazilian. Se o dicionário não estiver disponível, pode obtê-lo aqui: brazilian.gz.
  • 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 árvore de prefixos).
  • Ler a entrada de stdin e escrever a saída em stdout.
  • A localização das palavras no dicionário deve usar um algoritmo de 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.

Para medir o tempo de execução do programa, use o comando time:

time ./ortografia < brascubas.txt > output.txt

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, rewind, …
  • Manipulação de strings: strcpy, strlen, strchr, index, strpbrk, strstr, …
  • Busca binária: bsearch

Consulte as páginas de manual para aprender a usar essas funções.

Por pseudocódigo:

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

Por máquina de estados:

state = 0
while state ≠ 2 do

   read input

   case (state)

      0: case (input)

            letter:
               store input in word
               state = 1

            not letter:
               print input

            eof:
               state = 2

         end case

      1: case (input)

            letter:
               store input in word

            not letter:
               check word
               print work
               reset word
               state = 0

            eof:
               check word
               print word
               state = 2

         end case

   end case
end while