Analizador de gramática eficiente sin contexto, preferiblemente compatible con Python

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 (1 nivel) ( ejemplo ) y necesito hacerlo de manera eficiente.

Ahora mismo estoy usando el analizador de NLTK que produce la salida correcta pero es muy lento. Para mi gramática de ~ 450 reglas bastante no ambiguas de no léxico y medio millón de entradas léxicas, analizar 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 cargar la gramática + léxico (25MB) al principio puede demorar hasta un minuto.

De lo que puedo encontrar en la literatura, el tiempo de ejecución del algoritmo utilizado para analizar dicha 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 perjudica al rendimiento, no al tamaño absoluto de la gramática.

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

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

Por todos los medios echar un vistazo a Pyparsing . Es la implementación más sintética de análisis que he encontrado, y es un gran diseño desde un punto de vista puramente académico.

Utilicé tanto ANTLR como JavaCC para enseñar la teoría del traductor y el comstackdor en una universidad local. Ambos son buenos y maduros, pero no los usaría en un proyecto de Python.

Dicho esto, a diferencia de los lenguajes de progtwigción, los lenguajes naturales tienen mucho más que ver con la semántica que con la syntax, por lo que podría estar mucho mejor saltándose las curvas de aprendizaje de las herramientas de análisis existentes, yendo con un producto hecho en casa (de arriba a abajo, de vuelta atrás, ilimitado lookahead) analizador y analizador léxico, y pasa la mayor parte de su tiempo escribiendo el código que determina qué significa una oración analizada, pero ambigua, en lenguaje natural.

Herramientas a un lado …

Quizás recuerdes de la teoría que hay infinitas gramáticas que definen el mismo lenguaje. Existen criterios para categorizar las gramáticas y determinar cuál es el “canónico” o “mínimo” para un idioma dado, pero al final, la “mejor” gramática es la que es más conveniente para la tarea y las herramientas disponibles (recuerde el ¿Transformaciones de CFGs en gramáticas LL y LR?).

Entonces, probablemente no necesite un gran léxico para analizar una oración en inglés. Hay mucho que saber sobre una palabra en idiomas como el alemán o el latín (o incluso el español), pero no en el inglés arbitrario y ambiguo. Debería poder salir con un pequeño léxico que contenga solo las palabras clave necesarias para llegar a la estructura de una oración. En cualquier caso, la gramática que elija, independientemente de su tamaño, puede almacenarse en la memoria caché de manera que las herramientas puedan usarla directamente (es decir, puede omitir el análisis de la gramática).

Teniendo en cuenta esto, podría ser una buena idea echar un vistazo a un analizador más simple que ya haya trabajado otra persona. Debe haber miles de esos en la literatura. Estudiar diferentes enfoques le permitirá evaluar los suyos y puede llevarlo a adoptar los de otra persona.

Finalmente, como ya mencioné, interpretar lenguajes naturales es mucho más sobre la inteligencia artificial que sobre el análisis. Debido a que la estructura determina el significado y el significado determina la estructura, debes 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 decisiones para resolver el problema contra una ” pizarra “. Con ese enfoque el análisis sintético y semántico se produce de forma concurrente.

Recomendaría usar bitpar, un analizador de PCFG muy eficiente escrito en C ++. He escrito un contenedor Python basado en shell para él, consulte https://github.com/andreasvc/eodop/blob/master/bitpar.py

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

He utilizado pyparsing para un análisis de comandos de vocabulario limitado, pero aquí hay un pequeño marco de trabajo sobre pyparsing que aborda 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 desacelere a medida que amplíe el vocabulario. ¿Medio millón de entradas? Pensé que un vocabulario funcional razonable era del orden de 5-6 mil palabras. Y estará bastante limitado en las estructuras de oraciones que puede manejar: el lenguaje natural es para lo que sirve NLTK.

Un poco tarde en esto, pero aquí hay dos opciones más para ti:

Spark es un analizador de Earley escrito en Python.

Elkhound es un analizador GLR escrito en C ++. Elkhound usa una syntax similar a Bison

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

Si puede expressse como un lenguaje PEG (no creo que todos los CFG puedan, pero supuestamente muchos pueden), entonces puede usar pyPEG , que se supone que es de tiempo lineal cuando se utiliza una implementación de análisis de paquetes (aunque potencialmente prohibitivo en uso de memoria).

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