Construyendo un lemmatizador: optimización de velocidad

Question

Estoy construyendo un lematizador en python. Como necesito ejecutar en tiempo real/procesar una cantidad bastante grande de datos, la velocidad de procesamiento es esencial. Datos: Tengo todos los sufijos posibles que están vinculados a todos los tipos de palabras con los que se pueden combinar. Además, tengo lemas formales que están vinculados tanto a su (s) tipo (s) de palabra (s) como a su (s) lema (s). El programa toma una palabra como entrada y saca su lema. palabra = lemmafrom + sufijo

Por ejemplo (Nota: Aunque el ejemplo se da en Inglés No estoy construyendo un lematizador de Inglés):

palabra: prohibiendo

lemmaform: Forbidd

sufijo: ing

lema: prohibir

Mi solución:

que se han convertido los datos a dicts (anidados):

suffixdict : {suffix1:[type1,type2, ... , type(n)], suffix2:[type1,type2, ... , 
type(n)]}  
lemmaformdict : {lemmaform:{type1:lemma}} 

1) Buscar Todos los sufijos posibles y tipos de palabras que están vinculados a. Si el sufijo más largo posible tiene 3 caracteres, el programa intenta hacer coincidir 'ing', 'ng', 'n' con las claves en sufijodecifrado. Si la clave existe, devuelve un valor (un conjunto de tipos de palabras).

2) Para cada búsqueda de sufijo coincidente, el lemaform del dict. Si existe el lemaform, devuelve los tipos de palabras.

3) Finalmente, el programa intenta interceptar los tipos de palabras producidos en los pasos 1) ans 2) y si la intersección es exitosa, devuelve el lema de la palabra.

Mi pregunta: ¿podría haber una mejor solución a mi problema desde la perspectiva de la velocidad? (Sin tener en cuenta la opción de mantener palabras y lemas frecuentes en el diccionario) Ayuda muy solicitada.

Answer 1

Esta sería una aplicación maravillosa para transductores de estado finito. ¿Por qué? Porque le permiten hacer una reescritura de cadenas de manera eficiente (en el tiempo lineal al tamaño de la entrada). Considerar los siguientes s [ia] transductor MPLE:

Se toma una cadena como entrada y comprueba si existe un camino desde el estado inicial (en este caso, 0) a un estado final (10, 12 y 17, respectivamente) dada la secuencia de caracteres de entrada. Si alcanza un estado final, produce el resultado apropiado, p. (Prohibido, ing) si la entrada fue "prohibida".

No sé si tiene algún fondo de autómatas de estado finito. Si no, pruébalos; valdrá la pena el esfuerzo. :) Tries son un tipo especial de autómata de estado finito (el transductor de muestra anterior es un trie), por lo que podría ser un buen comienzo.

Answer 2

Considere utilizar no deterministatrie automaton cubriendo el conjunto completo de sufijos reconocidos, pero analizando la palabra al revés. Ser no determinista significa que la máquina puede estar en múltiples estados a la vez, y la máquina como un todo está en un estado de aceptación si cualquiera de esos estados está aceptando.

El estado inicial sería un estado de aceptación por lo que no podría reconocer ningún sufijo (como en inglés be). Desde el estado inicial, las transiciones (), ('e', 'z', 'i'), ('e', 'd', 'a') y ('e', 'v', 'o') por ejemplo, todas llegarían a estados aceptables, y no tiene que preocuparse por los conflictos 'e' s al usar un NFA.

Desde el estado inicial, los "caracteres" de cada palabra se introducen hacia atrás. Cada vez que la máquina aterriza en un estado de aceptación, la parte restante de la palabra se busca en su lemmaformdict y se guardan todos los resultados. Luego, el procesamiento continúa hasta que el estado de la máquina es nulo (no simplemente no acepta).

En ese punto, las elecciones totales de lemas indicadas a lo largo del camino conducen a las posibles interpretaciones de esa palabra eliminada del contexto (y eso siempre debe ser un número pequeño).

La manera exacta de implementar un NFA determinará el rendimiento. Los NFA pueden convertirse en DFA una vez construidos, de modo que la máquina tenga solo un estado en un momento dado, de modo que pueda ayudar al rendimiento sin complicar la construcción de la máquina. En el lado negativo, debe trabajar con la entrada en un nivel de personaje individual, lo que para Python puede costarle en rendimiento. (Pero si el rendimiento es que precioso, tal vez debería cambiar a C++.)