Cómo crear un corrector ortográfico

Mientras buscaba cosas para mi tesis de grado el año pasado, y me preguntaba cómo funciona el "did you mean" de google, me encontré con algo re loco, el código de un corrector ortográfico. Por qué digo re loco? bueno, resulta que el susodicho código requiere sólo de 21 líneas en python! Realmente no podía salir de mi asombro, algo tan eficaz que requiera de tan poco código. Por supuesto que no me iba a convencer así nomas, así que lo testié, y efectivamente, funciona perfecto!
Despues de jugar un rato con el programa y serenarme un poco, me puse a analizar la "magia" con un poco de cuidado y por supuesto, descubrí que no hay magia, es todo muy lógico.
Para no ponerme a divagar despues de un día largo, simplemente les transcribo las palabras que utilicé en mi tesis para describir el algoritmo:

La corrección de palabras se logra utilizando un algoritmo basado en la distancia Levenshtein, también conocida como edit distance, que es una métrica para medir la cantidad de diferencias entre dos palabras. Esta diferencia está dada por el mínimo número de operaciones necesarias para transformar una palabra en otra, donde las operaciones son inserción, borrado o sustitución de un carácter, y transposición de dos caracteres.
El algoritmo genera el conjunto de palabras que se encuentran a una distancia d de la palabra a corregir, de este conjunto descarta las que no pertenezcan al diccionario utilizado y entre las restantes, selecciona la de mayor frecuencia. Con una alta probabilidad la palabra elegida será la que se deseaba. Este algoritmo es la base de los correctores ortográficos utilizados por Google, Office, Mozilla, etc.

Por supuesto, para que el algoritmo funcione, necesitaremos de un diccionario de palabras. Todos los correctores funcionan así, por un lado tienen el corrector y por otro lado los diccionarios.

Como sé que se están muriendo por ver y utilizar ese código, me dejo de palabreríos. El código que les transcribo, pueden encontrarlo en su página original http://www.norvig.com/spell-correct.html junto con una explicación de probabilidad sobre por qué el algoritmo funciona tan bien. Para poder utilizar el algoritmo, necesitarán, o bien crear un diccionario de palabras propio (que se llame big.txt), o bien descargar el ejemplo incluído en la misma página big.txt.

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):
   s = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in s if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in s if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in s for c in alphabet if b]
   inserts    = [a + c + b     for a, b in s 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)

Dado que el código está pensado para ser usado dentro de otros programas, no le crearon un lector de argumentos, así que para probarlo, abran una consola python (simplemente ejecuten el comando python en linea de comandos), y pegen el código anterior. Luego ejecuten la función correct y pasenle como parámetro la palabra que quieran corregir.
Si por ejemplo tipeamos:
>>>correct('speling')
la función nos devolverá:
'spelling'


Como para mi tesis necesitaba un corrector en java, me puse a buscar una versión del código anterior y encontré ésta página, donde trasladan las funciones a java. Este código utiliza 35 líneas, pero sigue siendo espectacular. Al igual que en el anterior, se utiliza el archivo big.txt como diccionario de palabras.

import java.io.*;
import java.util.*;
import java.util.regex.*;

class Spelling {

 private final HashMap nWords = new HashMap();

 public Spelling(String file) throws IOException {
  BufferedReader in = new BufferedReader(new FileReader(file));
  Pattern p = Pattern.compile("\\w+");
  for(String temp = ""; temp != null; temp = in.readLine()){
   Matcher m = p.matcher(temp.toLowerCase());
   while(m.find()) nWords.put((temp = m.group()), nWords.containsKey(temp) ? nWords.get(temp) + 1 : 1);
  }
  in.close();
 }

 private final ArrayList edits(String word) {
  ArrayList result = new ArrayList();
  for(int i=0; i < word.length(); ++i) result.add(word.substring(0, i) + word.substring(i+1));
  for(int i=0; i < word.length()-1; ++i) result.add(word.substring(0, i) + word.substring(i+1, i+2) + word.substring(i, i+1) + word.substring(i+2));
  for(int i=0; i < word.length(); ++i) for(char c='a'; c <= 'z'; ++c) result.add(word.substring(0, i) + String.valueOf(c) + word.substring(i+1));
  for(int i=0; i <= word.length(); ++i) for(char c='a'; c <= 'z'; ++c) result.add(word.substring(0, i) + String.valueOf(c) + word.substring(i));
  return result;
 }

 public final String correct(String word) {
  if(nWords.containsKey(word)) return word;
  ArrayList list = edits(word);
  HashMap candidates = new HashMap();
  for(String s : list) if(nWords.containsKey(s)) candidates.put(nWords.get(s),s);
  if(candidates.size() > 0) return candidates.get(Collections.max(candidates.keySet()));
  for(String s : list) for(String w : edits(s)) if(nWords.containsKey(w)) candidates.put(nWords.get(w),w);
  return candidates.size() > 0 ? candidates.get(Collections.max(candidates.keySet())) : word;
 }

 public static void main(String args[]) throws IOException {
  if(args.length > 0) System.out.println((new Spelling("big.txt")).correct(args[0]));
 }

}

A diferencia del código anterior, en este se encuentra un lector de argumentos, así que pueden utilizar el código directamente desde línea de comandos. Simplemente compilen el código con javac Spelling.java y luego ejecuten java Spelling para ver los resultados.


Si les interesó todo esto del corrector ortográfico pueden chequear algunos de los correctores que se utilizan en Linux, como ser aspell, ispell o myspell, entre otros.