E01 Verificador ortográfico simplificado
Escreva um programa chamado Ortho.java, que pode ser usado para fazer verificação ortográfica. Por exemplo, considere os arquivos
https://www.ime.usp.br/~yoshi/DATA/GUTENBERG/mobydick.txt
https://www.ime.usp.br/~yoshi/DATA/GUTENBERG/Braz_Cubas.txt
https://www.ime.usp.br/~yoshi/DATA/LEIPZIG_PT_BR/10k/por-br_newscrawl_2011_10K-sentences.txt
https://www.ime.usp.br/~yoshi/DATA/LEIPZIG_PT_BR/100k/por-br_newscrawl_2011_100K-sentences.txt
https://www.ime.usp.br/~yoshi/DATA/LEIPZIG_PT_BR/1M/por-br_newscrawl_2011_1M-sentences.txt
https://www.ime.usp.br/~yoshi/DATA/DICT/words
https://www.ime.usp.br/~yoshi/DATA/DICT/words_pt
Os primeiros cinco são textos que usaremos como exemplo. Os dois últimos são os "dicionários" que usaremos. A seguir, supomos que os arquivos acima estão no subdiretório DATA.
Suponha que executamos Ortho.java como segue:
$ java-introcs Ortho DATA/words < DATA/mobydick.txt | sort | uniq > moby_list.txt
O arquivo moby_list.txt resultante deve passar a conter as palavras em mobydick.txt que não ocorrem em words (veja o arquivo moby_list.txt resultante abaixo). Ademais, por termos passado a saída de Ortho.java por sort e uniq, o arquivo moby_list.txt está ordenado e não tem repetições.
Seguem mais exemplos:
$ java-introcs Ortho DATA/words_pt < DATA/Braz_Cubas.txt | sort | uniq > BC_list.txt
$ time java-introcs Ortho DATA/words_pt < DATA/por-br_newscrawl_2011_10K-sentences.txt | sort | uniq > pt_BR_10k.txt
real 0m1.071s
user 0m1.606s
sys 0m0.245s
$ time java-introcs Ortho DATA/words_pt < DATA/por-br_newscrawl_2011_100K-sentences.txt | sort | uniq > pt_BR_100k.txt
real 0m2.263s
user 0m3.362s
sys 0m0.316s
$ time java-introcs Ortho DATA/words_pt < DATA/por-br_newscrawl_2011_1M-sentences.txt | sort | uniq > pt_BR_1M.txt
real 0m15.784s
user 0m22.000s
sys 0m1.502s
$
Os arquivos BC_list.txt e pt_BR_*.txt seguem abaixo. Você pode achar o uso do programa md5 útil para comparar arquivos (md5sum no GNU/Linux):
$ md5 pt_BR_10k.txt
MD5 (pt_BR_10k.txt) = d8f872f4049ba1a982dbd170993123a3
$ java-introcs Ortho DATA/words_pt < DATA/por-br_newscrawl_2011_10K-sentences.txt | sort | uniq | md5
d8f872f4049ba1a982dbd170993123a3
$
Observação 1. Aqui, interprete uma palavra como sendo um segmento maximal de letras.
Observação 2. Se você não encontrar uma palavra p no dicionário, pode ser que a versão de p com todas as letras minúsculas ocorra. Por exemplo, p = "It" não ocorre em words, mas "it" ocorre. Assim, "It" deve ser considerado válido. Este algoritmo ingênuo não funciona corretamente no seguinte caso: se seu texto contém "AFEGANISTÃO", este algoritmo não percebe que "Afeganistão" está em words_pt. Assim, seu algoritmo deve ter um passo adicional: tente também ver se consta no dicionário a palavra p com todas as letras, exceto a primeira, convertidas para minúsculas.
Neste exercício, use, obrigatoriamente, o algoritmo acima para lidar com o problema de palavras escritas com letras maiúsculas.
Funções úteis: .toLowerCase() e .toUpperCase() de String:
https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html#toLowerCase%28%29
https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html#toUpperCase%28%29
Observação 3. Os arquivos words e words_pt estão ordenados. Tecnicamente falando, se p e q são palavras que ocorrem em words (por exemplo) então p vem antes de q em words se e só se p.compareTo(q) < 0.
Observação 4. Os exemplos acima servem também para ilustrar tempos de execução esperados. Para obter tempos comparáveis, use um algoritmo de busca nos dicionários eficiente. Você deve implementar seu algoritmo de busca explicitamente (isto é, você não pode usar funções prontas do Java).
Observação 5. Você pode achar o programa GetWords.java abaixo de interesse.
Entrega. Neste exercício, você deve entregar seu programa Ortho.java.
Execuções em uma máquina GNU/Linux (Adicionado [2021-08-27 Fri 08:31])
Achei que seria interessante incluir a execução de meu Ortho.java em outra máquina, que também roda outro sistema: veja o arquivo experimentsGNU.txt (usei uma máquina GNU/Linux da rede do IME).
Também notei que o sort de minha máquina tem um comportamento diferente do GNU sort da máquina da rede do IME, e assim também incluí a execução de Ortho.java sem passar o resultado por "sort | uniq". Os arquivos resultantes seguem em E01_GNU.
- 24 agosto 2021, 12:07 PM
- 27 agosto 2021, 08:36 AM
- 27 agosto 2021, 08:36 AM
- 24 agosto 2021, 12:07 PM
- 27 agosto 2021, 08:36 AM