python parsing nlp grammar nltk

Analizador gramatical sin contexto eficiente, preferiblemente compatible con Python



parsing nlp (8)

Necesito analizar un pequeño subconjunto de inglés para uno de mis proyectos, descrito como una gramática libre de contexto con estructuras de características (de 1 nivel) ( ejemplo ) y necesito hacerlo de manera eficiente.

En este momento estoy usando el analizador NLTK que produce el resultado correcto pero es muy lento. Para mi gramática de ~ 450 reglas no-léxicas bastante ambiguas y medio millón de entradas léxicas, el análisis de oraciones simples puede tomar de 2 a 30 segundos, dependiendo de la cantidad de árboles resultantes. Las entradas léxicas tienen poco o ningún efecto en el rendimiento.

Otro problema es que la carga de la gramática + léxico (25 MB) al comienzo puede tomar hasta un minuto.

Según lo que puedo encontrar en la literatura, el tiempo de ejecución del algoritmo utilizado para analizar esa gramática (Earley o CKY) debe ser lineal al tamaño de la gramática y cúbico al tamaño de la lista de token de entrada. Mi experiencia con NLTK indica que la ambigüedad es lo que más lastima el rendimiento, no el tamaño absoluto de la gramática.

Así que ahora estoy buscando un analizador CFG para reemplazar NLTK. He estado considerando PLY pero no puedo decir si es compatible con estructuras de características en CFG, que son necesarias en mi caso, y los ejemplos que he visto parecen estar haciendo un gran análisis de procedimientos en lugar de solo especificar una gramática. ¿Alguien puede mostrarme un ejemplo de PLY, que admite estructuras de funciones y usa una gramática declarativa?

También estoy de acuerdo con cualquier otro analizador que pueda hacer lo que necesito de manera eficiente. Una interfaz de Python es preferible pero no absolutamente necesaria.

Creo que ANTLR es el mejor generador de analizadores que conozco para Java. No sé si Jython le proporcionará una buena forma para que Python y Java interactúen.

He utilizado pyparsing para el análisis de comandos de vocabulario limitado, pero aquí hay un pequeño marco además de pyparsing que se dirige a su ejemplo publicado:

from pyparsing import * transVerb, transVerbPlural, transVerbPast, transVerbProg = (Forward() for i in range(4)) intransVerb, intransVerbPlural, intransVerbPast, intransVerbProg = (Forward() for i in range(4)) singNoun,pluralNoun,properNoun = (Forward() for i in range(3)) singArticle,pluralArticle = (Forward() for i in range(2)) verbProg = transVerbProg | intransVerbProg verbPlural = transVerbPlural | intransVerbPlural for expr in (transVerb, transVerbPlural, transVerbPast, transVerbProg, intransVerb, intransVerbPlural, intransVerbPast, intransVerbProg, singNoun, pluralNoun, properNoun, singArticle, pluralArticle): expr << MatchFirst([]) def appendExpr(e1, s): c1 = s[0] e2 = Regex(r"[%s%s]%s/b" % (c1.upper(), c1.lower(), s[1:])) e1.expr.exprs.append(e2) def makeVerb(s, transitive): v_pl, v_sg, v_past, v_prog = s.split() if transitive: appendExpr(transVerb, v_sg) appendExpr(transVerbPlural, v_pl) appendExpr(transVerbPast, v_past) appendExpr(transVerbProg, v_prog) else: appendExpr(intransVerb, v_sg) appendExpr(intransVerbPlural, v_pl) appendExpr(intransVerbPast, v_past) appendExpr(intransVerbProg, v_prog) def makeNoun(s, proper=False): if proper: appendExpr(properNoun, s) else: n_sg,n_pl = (s.split() + [s+"s"])[:2] appendExpr(singNoun, n_sg) appendExpr(pluralNoun, n_pl) def makeArticle(s, plural=False): for ss in s.split(): if not plural: appendExpr(singArticle, ss) else: appendExpr(pluralArticle, ss) makeVerb("disappear disappears disappeared disappearing", transitive=False) makeVerb("walk walks walked walking", transitive=False) makeVerb("see sees saw seeing", transitive=True) makeVerb("like likes liked liking", transitive=True) makeNoun("dog") makeNoun("girl") makeNoun("car") makeNoun("child children") makeNoun("Kim", proper=True) makeNoun("Jody", proper=True) makeArticle("a the") makeArticle("this every") makeArticle("the these all some several", plural=True) transObject = (singArticle + singNoun | properNoun | Optional(pluralArticle) + pluralNoun | verbProg | "to" + verbPlural) sgSentence = (singArticle + singNoun | properNoun) + (intransVerb | intransVerbPast | (transVerb | transVerbPast) + transObject) plSentence = (Optional(pluralArticle) + pluralNoun) + (intransVerbPlural | intransVerbPast | (transVerbPlural |transVerbPast) + transObject) sentence = sgSentence | plSentence def test(s): print s try: print sentence.parseString(s).asList() except ParseException, pe: print pe test("Kim likes cars") test("The girl saw the dog") test("The dog saw Jody") test("Kim likes walking") test("Every girl likes dogs") test("All dogs like children") test("Jody likes to walk") test("Dogs like walking") test("All dogs like walking") test("Every child likes Jody")

Huellas dactilares:

Kim likes cars [''Kim'', ''likes'', ''cars''] The girl saw the dog [''The'', ''girl'', ''saw'', ''the'', ''dog''] The dog saw Jody [''The'', ''dog'', ''saw'', ''Jody''] Kim likes walking [''Kim'', ''likes'', ''walking''] Every girl likes dogs [''Every'', ''girl'', ''likes'', ''dogs''] All dogs like children [''All'', ''dogs'', ''like'', ''children''] Jody likes to walk [''Jody'', ''likes'', ''to'', ''walk''] Dogs like walking [''Dogs'', ''like'', ''walking''] All dogs like walking [''All'', ''dogs'', ''like'', ''walking''] Every child likes Jody [''Every'', ''child'', ''likes'', ''Jody'']

Es probable que esto se vuelva lento a medida que expande el vocabulario. ¿Medio millón de entradas? Pensé que un vocabulario funcional razonable era del orden de 5-6 mil palabras. Y será bastante limitado en las estructuras de las oraciones que puede manejar: el lenguaje natural es para lo que NLTK es.

Herramientas a un lado ...

Puede recordar por la teoría que hay gramáticas infinitas que definen el mismo idioma. Existen criterios para categorizar gramáticas y determinar cuál es el "canónico" o "mínimo" para un idioma determinado, pero al final, la "mejor" gramática es la más conveniente para la tarea y las herramientas a mano (recuerde el transformaciones de CFG en las gramáticas LL y LR?).

Entonces, probablemente no necesites un enorme léxico para analizar una oración en inglés. Hay mucho que se sabe acerca de una palabra en idiomas como el alemán o el latín (o incluso el español), pero no en el inglés muchas veces arbitrario y ambiguo. Debería poder salirse con la suya con un pequeño léxico que contiene solo las palabras clave necesarias para llegar a la estructura de una oración. En cualquier caso, la gramática que elijas, sin importar su tamaño, se puede almacenar en caché de forma tal que la herramienta pueda usarla directamente (es decir, puedes omitir el análisis sintáctico de la gramática).

Dado que, podría ser una buena idea echar un vistazo a un analizador simple ya trabajado por otra persona. Debe haber miles de ellos en la literatura. Estudiar diferentes enfoques te permitirá evaluar el tuyo y puede llevarte a adoptar el de otra persona.

Finalmente, como ya mencioné, la interpretación de los lenguajes naturales tiene mucho más que ver con la inteligencia artificial que con el análisis sintáctico. Debido a que la estructura determina el significado y el significado determina la estructura, debe jugar con ambos al mismo tiempo. Un enfoque que he visto en la literatura desde los años 80 es permitir que diferentes agentes especializados tomen fotos para resolver el problema contra una " pizarra ". Con ese enfoque, el análisis sintáctico y semántico suceden simultáneamente.

Intente ejecutarlo en PyPy, podría ser mucho más rápido.

Si se puede expresar como un lenguaje PEG (no creo que todos los CFG puedan, pero supuestamente muchos pueden), entonces podrías usar pyPEG , que se supone que es un tiempo lineal cuando se usa una implementación de análisis de paquetes (aunque potencialmente prohibitiva para uso de memoria).

No tengo ninguna experiencia con él, ya que estoy empezando a investigar el análisis y la compilación de nuevo después de un largo tiempo fuera de él, pero estoy leyendo un buen zumbido acerca de esta técnica relativamente actualizada. YMMV.

Algo tarde en esto, pero aquí hay dos opciones más para usted:

Spark es un analizador de Earley escrito en Python.

Elkhound es un analizador de GLR escrito en C ++ Elkhound usa una sintaxis similar a Bison

Por supuesto, eche un vistazo a Pyparsing . Es la implementación más pitónica de análisis que he encontrado, y es un gran diseño desde un punto de vista puramente académico.

Utilicé ANTLR y JavaCC para enseñar teoría de traductores y compiladores en una universidad local. Ambos son buenos y maduros, pero yo no los usaría en un proyecto de Python.

Dicho esto, a diferencia de los lenguajes de programación, los lenguajes naturales son mucho más acerca de la semántica que de la sintaxis, por lo que sería mucho mejor omitir las curvas de aprendizaje de las herramientas de análisis existentes, yendo con una preparación casera (de arriba hacia abajo, retrocediendo, ilimitada lookahead) analizador léxico y analizador, y pasar la mayor parte de su tiempo escribiendo el código que averigua lo que significa una oración analizada, pero ambigua, en lenguaje natural.