c++ - 如何在 C++ 中加速 CYK 算法？

Question

我想在 C/C++ 中实现CYK 算法，但在各种网站上提供的伪代码并没有回答如何有效地实现它。我写了一个版本，它使用了一些 stl 结构，比如 map 和 sets，但是速度很慢。我正在考虑通过仅使用二进制操作来改进我的实现，但我不知道如何用集合存储我的表。假设我们只有 8 个非终端符号和 26 个终端符号。我正在考虑使用无符号字符表（0-1 的 2^8 -> 8 个位置）来存储有关产品的信息，但我不知道如何存储它。

你能给我一些帮助或线索吗？

Answer 1

您没有提供很多细节，一个简单的实现（甚至是伪代码）可以为您提供很多提示。

来自维基百科：

令输入为由 n 个字符组成的字符串 S：a1 ... an。让

为此，您可以使用简单的字符串或字符向量

该文法包含 r 个非终结符号 R1 ... Rr。

我会将非终结符号存储在布尔数组 std::array nonterminal {}; 那么由于 yu 有字符，你可以用 true 来初始化对应于 char 的位置。

非终端[static_cast('C')] = true; 你对终端做同样的事情，你有一个非常快速的查找机制。

该文法包含子集 Rs，它是开始符号的集合。令 P[n,n,r] 为布尔数组。将 P 的所有元素初始化为 false。对于每个 i = 1 到 n 对于每个单位生产 Rj -> ai 设置 P[i,1,j] = true 对于每个 i = 2 到 n -- 每个 j = 1 到 n-i+1 的跨度长度 - - 每个 k = 1 到 i-1 的跨度开始 - 每个生产 RA 的跨度分区 -> RB RC 如果 P[j,k,B] 和 P[j+k,ik,C] 然后设置 P[ j,i,A] = true 如果任何 P[1,n,x] 为真（x 在集合 s 上迭代，其中 s 是 Rs 的所有索引）然后 S 是语言的成员，否则 S 不是成员语言的

在那之后，该算法似乎非常简单。只要确保不要在紧密循环中初始化临时值，你会没事的。