domingo, 13 de abril de 2008

Um corretor ortográfico em gawk

Ano passado eu publiquei uma pequena nota sobre um pequeno corretor ortográfico feito em Python.

No artigo do Peter Norwig, ele explica o principio estatístico do algoritmo. No final, ele mostra varias implementações do algoritmo (em D, Java, Ruby e até Erlang).

Depois de muito pesquisar, decidi fazer uma versão em gawk. A primeira tinha 30 linhas e não funcionava muito bem, arrumando e testando cheguei a esta forma final com apenas 15 linhas.

Eu chamo de linha um statement completo do awk. Perceba que nenhuma linha dessas possui o separador de statement ; (ponto-e-virgula), exceto quando estou utilizando o for no estilo C.

# Usage: gawk -v word=something -f thisfile.awk [ big.txt [ big2.txt ... ]]
# Gawk version with 15 lines -- 04/13/2008
# Author: tiago (dot) peczenyj (at) gmail (dot) com
# Based on : http://norvig.com/spell-correct.html
function edits(w,max,candidates,list, i,j){
for(i=0;i< max ;++i) ++list[substr(w,0,i) substr(w,i+2)]
for(i=0;i< max-1;++i) ++list[substr(w,0,i) substr(w,i+2,1) substr(w,i+1,1) substr(w,i+3)]
for(i=0;i< max ;++i) for(j in alpha) ++list[substr(w,0,i) alpha[j] substr(w,i+2)]
for(i=0;i<= max ;++i) for(j in alpha) ++list[substr(w,0,i) alpha[j] substr(w,i+1)]
for(i in list) if(i in NWORDS) candidates[i] = NWORDS[i] }

function correct(word ,candidates,i,list,max,temp){
edits(word,length(word),candidates,list)
if (!asort(candidates,temp)) for(i in list) edits(i,length(i),candidates)
return (max = asorti(candidates)) ? candidates[max] : word }

BEGIN{ if (ARGC == 1) ARGV[ARGC++] = "big.txt" # http://norvig.com/big.txt
while(++i<=length(x="abcdefghijklmnopqrstuvwxyz")) alpha[i]=substr(x,i,1)
IGNORECASE=RS="[^"x"]+" }

{ ++NWORDS[tolower($1)] }

END{ print (word in NWORDS) ? word : "correct("word")=> " correct(tolower(word)) }


Veja o script em funcionamento:
$ time gawk -v word=somethink -f spelling.awk
correct(somethink)=> something

real 0m4.862s
user 0m4.702s
sys 0m0.093s

2 comentários:

Tiago Albineli Motta disse...

Corretor ortográfico, tatuagem... esse foi um final de semana divertido pra você heim! hahahha

Unknown disse...

Tiago, mais uma vez, parabéns!
É muito divertido mexer com estas coisas, não?
Ah, eu não esqueci de te mandar a versão otimizada em Java... eu só não achei seu email pra enviar! :P
Me manda um email, e eu te dou reply!