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.

30 comentarios:

JaviZ dijo...

... y efectivamente funciona, casi diría que parece magia! Muy buen post.

Salu2,
Javi

Nickar dijo...

Si eso te sorprende, mirate esta presentación de PyConAR 2009 sobre como hacer una hoja de cálculo en 9 lineas de python: http://lateral.netmanagers.com.ar/static/hoja.pdf

El mismo desarrollador (Roberto Alsina) dió una charla sobre este mismo algoritmo de ortografía el día anterior! :D
Buenisimo post!
Saludos,

Anónimo dijo...

muy buen aporte es increible que en tan pocas lines de codigo realize tan proceso me imaginaba muchas lineas de codigo!

Anónimo dijo...

tienes razon muy buen aporte me funciono tambien att. francisco evenor

Anónimo dijo...

holz...
esto esta rrbueno boy a revisar y lueog les digo lo que pase ps...

Anónimo dijo...

Oe men talvez me puedas dar un link a una pagina donde pueda encontrar para un algoritmo de excel en c++ o java plz...
te lo agradecere mucho...

Anónimo dijo...

Hola q tal, una pregunta tendras el archivo big.txt para el español?

d3m4s1@d0v1v0 dijo...

No, no tengo ese archivo, pero sirve cualquiera de los diccionarios disponibles en la web y en las distribuciones de GNU/Linux.

Miguel Araujo dijo...

HOla, es posible sacar del codigo las palabras candidatas, por que lo bueno seria que me devuelva sugerencias como funcionan todos los correctores. Y que el usuario seleccione el resultado deseado. Gracias.

yerko cabello dijo...

Como puedo lograr que corrija palabras con tilde, asumiendo que tengo big.txt en español? Es decir, cuando intento corregir "tambien" el resultado que obtengo es "tambi" en vez de "también"

d3m4s1@d0v1v0 dijo...

No lo he probado, pero debería funcionar si utilizas un diccionario codificado en UTF-8 que incluya las palabras con tilde, y además incluis las letras con tilde en variable alphabet. Para esto último, el código del programa debe estar guardado en un archivo que también esté codificado con UTF-8, y vas a tener que utilizar la función unicode (en python, en Java debe haber un equivalente) para los strings.
Espero haberte orientado un poco.

Sergio dijo...

Disculpen que sea un poco ignorante pero como compilo y corro el prograna de antemano gracias

d3m4s1@d0v1v0 dijo...

Sergio,
el programa en python no necesita ser compilado, dado que es interpretado.
Por otra parte, el programa en java, lo compilas con el compilador de Java (javac).

Sergio dijo...

Pero que pasos debo seguir para poder compilarlo en Javac???

d3m4s1@d0v1v0 dijo...

Sergio te recomiendo que leas algún tutorial de programación en Java porque estás necesitando conceptos básicos de programación. Google es tu amigo. Saludos!

Sergio dijo...

Otra pregunta, como creen que puede sacar la función para poder pasar el código pasado a una interface gráfica, es decir, que el usuario ingrese su palabra y la cambie.
De antemano gracias!

Anónimo dijo...

joo exelente ase unos dias empece con python y al = que tu tenia la misma duda de como funcionaba el corrector de google xD

ahora mi duda es si nesesito alguna libreria adicional para que funcione este codigo (el primero que esta en python)y en donde debo poner el libro big.txt????

gracias de antemano (Y)

d3m4s1@d0v1v0 dijo...

Por como está definido el programa, el archivo big.txt debe ponerse en el mismo directorio donde se encuentra el script de python. Igual esto se puede cambiar fácilmente modificando el código.

Miguel Angel dijo...
Este comentario ha sido eliminado por el autor.
Miguel Angel dijo...

En el diccionario big.txt, ¿se deben incluir las formas verbales y los plurales de las palabras?
Si es que sí, ¿dónde puedo encontrar un diccionario completo con todas las distintas formas?

d3m4s1@d0v1v0 dijo...

Hola Miguel,
no se qué formato tendrán, pero supongo que podes descargar diccionarios existentes para otros programas como firefox, o los mismos que vienen para correctores como aspell (Linux).

Srita. Ángeles dijo...

Para que el corrector identifique palabras en español con acentos es necesario trabajarlo durante el programa mediante unicode (http://farmdev.com/talks/unicode/), obviamente tener el archivo "big.txt" con texto en español. Sin embargo me he encontrado que este algoritmo no trabaja bien con español Y unicode, puesto que al intentar corregir palabras que les hacen falta acentos, el algoritmo encuentra una distancia más cercana con aquellas palabras que les hace falta otra letra y no precisamente con la palabra que es más semejante pero con acento...por ejemplo:

correct('zocalo')

me regresa: zocato
(tiene 2 ocurrencias en "big.txt")
en vez de: zócalo
(tiene 3 ocurrencias en "big.txt")

Saludos d3m4s1@d0v1v0 y gracias por la aportación

d3m4s1@d0v1v0 dijo...

Hola Angeles, gracias por el aporte. Es correcto lo que comentás, para correcciones en idiomas que requieran caracteres especiales (como nuestro idioma con los acentos) es necesario usar UTF o alguna codificación que acepte caracteres con acento. Tendría que hacer algún debugging para entender por qué retorna una palabra sin acento como más cercana.

Lidya Cota dijo...

Ya está, solo faltaba actualizar el alfabeto :)
Aquí el código para trabajar con el idioma español. Sólo necesita previamente prepararse el archivo big.txt en español y guardado con codificación utf-8

# -*- coding: utf-8 -*-
import re, collections



def to_unicode_or_bust(obj, encoding='utf-8'):
if isinstance(obj, basestring):
if not isinstance(obj, unicode):
obj = unicode(obj, encoding)
return obj

def words(text):

palabras = re.findall(u'[a-záéíóú]+', text.lower(), re.UNICODE)

return palabras

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

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

alphabet = u'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)

Lidya Cota dijo...

*falta la ñ

d3m4s1@d0v1v0 dijo...

Muchas gracias Lidya por compartir el resultado! Hace tanto que publiqué esto que no recordaba bien como era el código.
Saludos!

Lidya Cota dijo...

Al contrario, muchas gracias a ti d3m4s1@d0v1v0

Polguis dijo...

Hola gracias por el post! me gustaría saber que hiciste de tesis y si tienes algún link donde pueda encontrarla!

Anónimo dijo...

Hola esta excelente el programa Como le hago para que funcione con palabras en mayusculas y símbolos como ejemplo <>, -, y _, &?... “HELLP” no es igual a “hellp” pero quiero que las marque como correctas y cambie el diccionario a mayúsculas pero las sigue tomando como minúsculas

Anónimo dijo...

jejejeje muy pendejo gracias por ahorarme la busqueda :) espero que te haya ido bien en tu tesis

Publicar un comentario