algorithm - 语法发现，或者，句子树构建器

Question

我通常非常擅长算法，但我这里有一个非常抽象的问题，这可能是某个人的博士项目，并且接近 NP 完整性。但也许这是一个比我想象的更普遍的问题。

我有一个包含 25000 个字符串的列表，是使用一堆下拉列表和文本字段创建的。所以，为了简化讨论，假设这是，呃，单向图:

{我的猫/我的狗} 有 {小猫，小狗}。

所以，这就像一个树结构，其 4 条路径代表 4 个可能的句子。

如何从(可能不完整的)句子列表中逆向工程树结构？

即

So that from
My Cat had kittens
My Cat had puppies
My Dog had kittens, you could still recreate the original syntax tree.

显然，对于 25000 个字符串，这需要一段时间。但是有没有软件可以做到这一点？或者，这是一个足够普遍的问题，以至于有已知的算法可以做到这一点吗？

它本质上看起来像是一个正则表达式解析器，但我不知道从哪里开始。我在工作中处理这个问题，每次我发现一个新模式时，我都会自己分析句子以解析另外 500 个左右。但我想如果我有树状结构，我可以把它剁碎。

有什么想法吗？ 谢谢

Answer 1

可以 templatemaker对你来说是朝着正确方向迈出的一步吗？它的目标是推断类似格式字符串背后的模板，稍后允许您使用此模板从其他字符串中提取数据。