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

Question

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

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

Answer 1

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

来自维基百科:

let the input be a string S consisting of n characters: a1 ... an. let

为此你可以使用一个简单的字符串，或者一个字符 vector

the grammar contain r nonterminal symbols R1 ... Rr.

我会将非终结符号存储在 bool 数组中std::array 非终结符 {};然后因为你有字符，你可以用 true 初始化与字符对应的位置。

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

This grammar contains the subset Rs which is the set of start symbols. let P[n,n,r] be an array of booleans. Initialize all elements of P to false. for each i = 1 to n for each unit production Rj -> ai set P[i,1,j] = true for each i = 2 to n -- Length of span for each j = 1 to n-i+1 -- Start of span for each k = 1 to i-1 -- Partition of span for each production RA -> RB RC if P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true if any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs) then S is member of language else S is not member of language

此后算法看起来非常简单。只要确保不要在紧密循环内初始化临时值就可以了。