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

Question

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

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

Answer 1

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

维基百科：

让输入是由n个字符组成的字符串S: a1 .一个。让

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

语法包含r个非终端符号R1 .Rr.

我会将非终端符号存储在bools的数组std::array {}中；然后因为yu有字符，所以可以用true初始化与char对应的位置。

nonterminalstatic_cast('C') = true；您对终端也这样做，并且有一个非常快速的查找机制。

该语法包含子集Rs，这是一组开始符号。设Pn，n，r是一组布尔值。将P的所有元素初始化为false。对于每个单位生产的Rj -> ai集Pi,1，j=真，对于每一个i=2到n-跨度长度，对于每一个j=1到n-i+1 --每一个k=1到i-1 --对于每个生产RA -> RB，如果Pj，k，B和Pj+k，i-k，C，设Pj，i，A= true，如果P1，n，x是真的(x在集合s上迭代，其中s是Rs的所有索引)那么S是语言的成员，否则S不是语言的成员

在那之后，算法看起来相当简单。只需确保不要在紧循环中初始化临时值，就可以了。