prolog - 是什么让 DCG 谓词变得昂贵？

Question

我正在构建一个明确的从句语法来解析 20,000 条半自然文本。随着我的谓词数据库的大小增长(现在多达 1,200 条规则)，解析一个字符串可能需要相当长的时间——特别是对于 DCG 当前无法解释的字符串，由于我还没有编码的语法。对于包含 30 个单词的字符串，当前的最坏情况是 3 分钟。我正在尝试弄清楚如何优化它，或者我是否应该开始研究云计算。

我正在使用 SWI-Prolog，它提供了一个“配置文件”目标，它提供了一些统计信息。我惊讶地发现数据库中最简单的规则占用了大部分执行时间。我的语料库包含表示数字的字符串，我想在 scalar/3 中捕获这些字符串。谓词。这些占用了总执行时间的 50-60%。

一开始，我的 scalars.pl 中有 70 行。 ，代表我的语料库中数字的数字和自然语言表示。像这样:

scalar(scalar(3)) --> ["three"].
scalar(scalar(3)) --> ["3"].
scalar(scalar(4)) --> ["four"].
scalar(scalar(4)) --> ["4"].

...等等。

考虑到文件的长度是问题所在，我添加了一个新规则来自动解析任何数字表示:

scalar(scalar(X)) --> [Y], { atom_number(Y, X) }.

多亏了这一点，我已经从 70 条规则变成了 31 条规则，并有所帮助——但这并不是一笔巨大的节省。还有什么可以做的吗？我的感觉可能不是，因为还有什么比列表中的单个原子更简单的呢？

这些标量在整个语法中的很多地方都被调用，我认为这是问题的根源。虽然它们是简单的规则，但它们无处不在，而且不可避免。高度通用的语法不适用于我的应用程序，如果我最终得到 3,000 条或更多规则，我也不会感到惊讶。

我从来没有 build 过这么大的 DCG，所以我不确定在性能方面我能期待多少。很高兴就此提出任何建议:是否有其他编码这些规则的方法？我应该接受一些解析需要很长时间，并弄清楚如何并行运行解析吗？

先感谢您!

编辑:我被要求提供一个可重现的示例，但要做到这一点，我必须将 SO 链接到整个项目，因为这是一个规模问题。为了完整起见，这是我正在做的事情的玩具版本。想象一下，有描述数百个名词、数百个动词和数百个句法结构的大文件。

sent(sent(VP, NP)) --> vp(VP), np(NP).
vp(vp(V)) --> v(V).
np(np(Qty, Noun)) --> qty(Qty), n(Noun).
scalar(scalar(3)) --> ["three"].
scalar(scalar(X)) --> [Y], { atom_number(Y, X) }.

qty(qty(Scalar)) --> scalar(Scalar).
v(v(eat)) --> ["eat"].
n(n(pie)) --> ["pie"].

Answer 1

您可能要调查的程序的一个方面是确保单个谓词快速成功并快速失败。这对于检查具有许多子句的谓词特别有用。

例如，当 scalar(X) 在一个不是标量的标记上求值时，程序必须尝试 31 次(按您的最后一次计数)才能确定 scalar//1 失败。如果您的程序的结构是针对每个 token 检查 scalar(X) ，那么这可能非常昂贵。

此外，如果 scalar(X) 确实发现 token 匹配但后续目标失败，那么您的程序似乎将重试 scalar(X)，直到所有 scalar//1 子句都已尝试。

明智地使用 cut (!) 或 if-then-else (C1->G1;C2->G2;G3) 可以提供巨大的性能改进。
或者您可以构建您的谓词，以便它们依靠索引来选择适当的子句。例如。:

scalar(scalar(N)) --> [Token], {scalar1(Token, scalar(N))}.

scalar1("3", scalar(3)) :- !.
scalar1(Y, scalar(X)) :- atom_number(Y, X).

这将 cut 和子句索引(如果编译器提供)与 scalar1/1 谓词一起使用。

编辑:您应该阅读 R. A. O'Keefe 的 The Craft of Prolog。它是 Prolog 实践方面的极好指南。