Buscando palabras similares

Estoy tratando de escribir un módulo de corrector ortográfico.Buscando palabras similares

Carga un texto, crea un diccionario a partir de un archivo de 16 mb y luego comprueba si la palabra encontrada es similar a la del diccionario (similar = varía hasta dos caracteres) si es así lo cambia al formulario del diccionario.

En este momento estoy usando un algoritmo de Levenshtein Distancia y el procesamiento de unas 50 palabras configurado tendrá 3 min ...

Estoy bastante seguro de que debe haber una solución más rápida. Profiler me dijo que mi aplicación pasa más del 80% de su tiempo en la función Distancia de Levenshtein.

¿Hay mejores soluciones/algoritmos?

Aquí está el implementarse de versión del algoritmo que utilizo:

def levenshteinDistance(s1, s2): 
    l_s1 = len(s1) 
    l_s2 = len(s2) 
    d = [[a for a in genM(x, l_s2 + 1)] for x in xrange(l_s1 + 1)] 
    for i in xrange(1, l_s1 + 1): 
     for j in xrange(1, l_s2 + 1): 
      d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + decide_of_equality(s1[i - 1],s2[j - 1])) 
    return d[l_s1][l_s2]

Fuente

2012-04-08 Michal

Suena como "Autocorrección" que la corrección ortográfica, ya que los correctores ortográficos generalmente crean opciones y permiten que los usuarios seleccionen entre ellas. La autocorrección es obviamente imposible de hacer bien, un hecho ahora casi universalmente reconocido, incluso en comerciales de televisión. :-) –

Si hace la suposición de que la primera letra de la palabra es siempre correcta, entonces puede verificar en el diccionario las palabras que comienzan con esa letra. Disminuirá su tiempo en más o menos un factor o 26 – Doboy

No sé mucho sobre python, pero su función de distancia usa la solución de programación dinámica estándar. Aquí está mi versión en C++: http://codereview.stackexchange.com/questions/10130/edit-distance-between-two-strings tal vez pueda detectar alguna diferencia. –

he utilizado corrector ortográfico de Norvig, mencionado en los comentarios y es impresionante.

Sin embargo, al llegar a su problema, ha escrito un algoritmo de distancia de edición de programación dinámica. Su algoritmo califica para ser un algoritmo paralelo de datos. En una memoria compartida, es decir, en una sola máquina, si tiene múltiples núcleos, puede explotarlos. ¿Sabes algo llamado map-reduce? Por favor, no piense distribuido y ahora mismo, solo considere una sola máquina de cuatro núcleos y una memoria compartida. Como paso 1, puede dividir el diccionario y asignar una porción a cada hilo que ejecutará la distancia de edición en una parte del diccionario (similar a un paso del mapa). Más tarde, todos tus hilos te devolverán todas las palabras a una distancia de edición de 2 (similar al paso de reducción). De esta manera, su programa se beneficiará de la arquitectura multi core.

Otra cosa que podría pensar es dentro de su código python escribir el algoritmo de distancia de edición intensiva de la CPU en C i.e escribiendo una extensión de python.

Fuente

2012-04-08 20:15:40 Yavar

Desafortunadamente no puedo usar múltiples núcleos, pero la solución de Norvig fue el truco. – Michal

Quizás el problema esté en un nivel superior. Cuando un generador de perfiles le dice que se ha gastado mucho tiempo en una función, es posible que lo esté llamando con demasiada frecuencia. ¿Estás comparando cada palabra en el texto con cada palabra en el diccionario? Pruébelo al revés: para las palabras en el texto, genere directamente palabras de distancia < = 2 y compruebe si están en el diccionario.

Fuente

2012-04-08 21:06:40

Tiene razón en que, a veces, el problema radica en demasiadas llamadas, pero ese no es mi caso. Solo puedo usar palabras de un diccionario, por eso no necesito generar palabras nuevas, pero en cambio puedo usar palabras del diccionario que tienen una distancia <= 2 desde mi palabra encontrada. Pero señaló algunas cosas buenas para otros casos. – Michal

Buscando palabras similares

Respuesta

Cuestiones relacionadas