Ortografía

Hace poco discutía los detalles de un proyecto sobre: análisis sintáctico, recolección y clasificación de información. No fue sino hasta estar enfrente de twitter, que pude ver la calidad de la información que circula por la red ¡Mentiría! Si dijera haber encontrado un twit con buena ortografía y ni hablar de la gramática.

En parte esto se debe al limite de caracteres de algunas páginas web y que la mayoría de los usuarios publican desde sus dispositivos móviles mientras hacen otras cosas. Bueno entrando en materia; un corrector ortográfico podría resultar muy práctico. Buscando información al respecto me topé con el blog de un tío (el Google's Director of Research) quién implementó un corrector ortográfico en el avión camino a casa en tan solo 22 líneas de Python-2.5, con una precisión de ~89%

import re, collections

def words(text): return re.findall('[a-z]+', text.lower()) 

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(file('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(word):
   splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in splits if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   inserts    = [a + c + b     for a, b in splits for c in alphabet]
   return set(deletes + transposes + replaces + inserts)

def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words): return set(w for w in words if w in NWORDS)

def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)

Peter Norvig, el autor, para sus fines solo necesitó un fichero de texto (cuentos de Sherlock Homes) y el Teorema de Bayes. En vista de la aceptación que tuvo y lo divertido que se veía, decidí intentarlo con Ruby y hacer una entrada con mis resultados. Sin mas, les dejo mi versión. (en 23 líneas)

def words(text); text.downcase.scan(/[a-z]+/); end

def train(wds)
  model = Hash.new(1)
  wds.each {|w| model[w] += 1}
  model
end

$alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(wd)
  del=[]; tras=[]; alt=[]; ins=[]; len=wd.length; allen=$alphabet.length + 1
  len.times    {|i| del << wd.delete(wd[i]) }
  (len-1).times{|i| w=wd+''; w[i],w[i+1]=w[i+1],w[i]; tras << w }
  len.times    {|i| w=wd+''; allen.times{|j| w[i]=$alphabet[j].to_s; alt.push w+''}}
  (len+1).times{|i| allen.times{|j|  w=wd+''; w.insert(i,$alphabet[j].to_s); ins.push w+''}}
  ret = del+tras+alt+ins; ret.empty? ? nil : ret
end

File.open('./big.txt') {|fd| $nwords=train( words( fd.read ) )}

def known_edits2(wd, re=[])
  edits1(wd).each{|e1| edits1(e1).each{|e2| re << e2 if $nwords.has_key?(e2)}}; re.empty? ? nil : re
end

def known(wds, re=[]); wds.each{|w| re << w if $nwords.has_key?(w)}; re.empty? ? nil: re; end

def correct(wd)
  (known([wd])||known(edits1(wd))||known_edits2(wd)||[wd]).max{|a,b| $nwords[a] <=> $nwords[b]}
end

 Comparando ambos códigos

Python25

~ $ time python spell.py 'eviroment'
environment

real    0m1.015s
user    0m0.960s
sys     0m0.053s

Ruby19

~ $ time ruby spell.rb 'eviroment'
environment

real    0m2.128s
user    0m2.027s
sys     0m0.087s

Ruby19        (  Brian Edkins )

~ $ time ruby spell_edkins.rb 'eviroment'
environment

real    0m2.173s
user    0m2.080s
sys     0m0.077s

A simple vista se puede ver que la versión de Norving es más rápida. También tomé la versión de Edkins y la sometí, logrando un tiempo semejante al nuestro. Sin lugar a duda la versión de Norving es mejor, pero no quiere decir que nos quedaremos de brazos cruzados, lo que pasa es que el algoritmo que él utilizó es muy eficiente. Tratemos de reimplementar el método edits1 lo más semejante posible a la versión de Norving:

# Opción 1, este es un poco más limpio
def edits1(word, set=[])
  splits      = (0..word.length).map{|i| [ word[0...i],word[i..-1] ] }
  splits.each {|a,b| set << (a + b[1..-1]) if b!='' }
  splits.each {|a,b| set << (a + b[1] + b[0] + b[2..-1].to_s) if b.length>1 }
  splits.each {|a,b| $alphabet.each_char{|c| set << (a + c + b[1..-1].to_s)} if b!=''}
  splits.each {|a,b| $alphabet.each_char{|c| set << (a + c + b) } }
  set
end

# Opción 2
def edits1(word, del=[], tra=[], rep=[], ins=[])
  splits      = (0..word.length).map{|i| [ word[0...i],word[i..-1] ] }
  splits.each {|a,b| del << (a + b[1..-1]) if b!='' }
  (word.length-1).times{|i| w=word.dup; w[i],w[i+1]=w[i+1],w[i]; tra << w }
  splits.each {|a,b| j=-1;  rep << (a + $alphabet[j] + b[1..-1].to_s) while $alphabet[j+=1]  if b!=''}
  splits.each {|a,b| j=-1;  ins << (a + $alphabet[j] + b) while $alphabet[j+=1] }
  del+tra+rep+ins
end

Como ven imprudentemente utilicé el espacio de los argumentos de los métodos para poder declarar algunas variables y optimizar un poco de espacio, todo sigue igual,  veamos que tal van las cosas:

~ $ time ruby spell.rb 'envroment'
environment

real    0m1.527s
user    0m1.480s
sys     0m0.047s

Aunque hubo una mejora apreciable de 0.601s ó 39.36%, Python sigue siendo 0.512s o 33.36% mas rápido, acercándose mucho a los tiempo de la implementación en C de Toledo. Por más vuelta que le di al asunto, no pude optimizar más el método edits1, después de todo, sigo siendo un newbie. Si tienes alguna implementación que me ayude a batallar los Pythonistas hacédmela llegar.

Ideas

• Utilizar este algoritmo y la librería Link-Grammar para obtener basados en el número de null-links, la palabra adecuada al contexto.

Despedida

Bueno, creo que eso es todo, solo me queda por decir, que este corrector funciona con otros idiomas también, solo debes alimentarlo con texto adecuado y modificar la variable alphabet (agregando la ñ y las respectivas vocales acentuadas en el caso del español). Si decides hacerlo con Ruby, sería buena idea utilizar el comentario mágico  encoding: <codificación> para evitar problemas de codificación.

Referencias  
«Peter Norvig»  How to Write a Spelling Corrector
                      ~  Archivo de prueba big.txt
«Brian Edkins» http://lojic.com/blog/2008/09/04/how-to-write-a-spelling-corrector-in-ruby/ 
«Marcelo Toledo» http://marcelotoledo.com/2007/08/10/how-to-write-a-spelling-corrector/