Un rápido y compacto corrector ortográfico en Scala

Construir un corrector ortográfico no es realmente una tarea muy difícil. Muchos inmediatamente mencionarán la distancia de Levenshtein para saber la distancia de edición entre 2 palabras.

Tomando el ejemplo de Wikipedia:

La distancia de Levenshtein entre “casa” y “calle” es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.

1. casa → cala (sustitución de ‘s’ por ‘l’)
2. cala → calla (inserción de ‘l’ entre ‘l’ y ‘a’)
3. calla → calle (sustitución de ‘a’ por ‘e’)

Entonces, buscar los posibles candidatos de una palabra mal escrita se convierte en buscar las palabras que tengan la menor distancia de edición con ella. Es simple, pero en el peor de los casos tendríamos que buscar entre todo el conjunto de palabras que tengamos (como un diccionario), lo cual hace que la búsqueda sea O(n).

Para alivianar el problema, existen los BK-Tree, que básicamente son árboles cuyos nodos son palabras y las aristas tienen el valor de la distancia de edición entre esos nodos. Acá hay una explicación (en inglés) que cubre lo necesario para entenderlos: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees

El caso es que usar un BK-Tree para esta tarea acelera mucho la búsqueda de candidatos, puesto que no es necesario cubrir todos los nodos si la distancia máxima que se busca es relativamente pequeña (digamos, 1 o 2).

Buscando implementaciones en Scala, me doy cuenta de que en Scalaz existe la clase BKTree (aunque está deprecated en la versión 7). Viendo el código, y teniendo una lista de 90,000 palabras en inglés, me di a la tarea de implementar un muy sencillo corrector ortográfico en ese lenguaje. La distancia máxima entre palabras la puse en 1. El resultado:

package org.mmg.tests

import scala.io.Source._
import scalaz._
import Scalaz._

object SpellCorrector {

  def main(a: Array[String]) {
	  val words = fromFile("EnglishWords.txt").getLines.toList	  
	  val bt = words.foldLeft(BKTree[String]())((acc, w) => acc + w) 	  	  
	  val MAX_DIST = 1

	 while (true) {
    	print("Input the word you want to check (Ctrl-C to end): ")
    	Option(Console.readLine) filterNot {_.isEmpty} foreach {s => 
        	bt.valuesApproximate(s, MAX_DIST) foreach println
    	}
     }
  }

}

Y probando:

Input the word you want to check (Ctrl-C to end): tail
ail
til
bail
fail
Gail
hail
jail
kail
mail
nail
pail
rail
sail
tail
vail
wail
tall
tael
tain
toil
trail

Los resultados se obtienen relativamente rápido. El ejemplo anterior toma sólo algunas décimas de segundo (casi 90,000 palabras). Por supuesto que esto no quiere decir que sea óptimo, pero si no se busca un desempeño en áreas críticas, funciona.

Obviamente esto es muy simple, pero puede mejorar si por ejemplo le asignamos menos peso a operaciones de la distancia de Levenshtein entre letras que frecuentemente se escriben mal, como por ejemplo, entre la “o” y la “p”, que están juntas en un teclado QWERTY. Eso haría que la distancia fuera menor entre ciertas palabras y reduciría el número de candidatos que se muestran.

Por supuesto, si tenemos un modelo probabilístico podemos usar el teorema de Bayes para buscar mejores candidatos, y aunque no es en sí tan complicado, sí me tomaría más tiempo escribirlo aquí.

Como sea, esta implementación es rápida, y puede sacar de algún apuro.