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

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

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

来源

2013-04-05 Jackson Rubbo

可能很有趣：这个前面的问题（http://stackoverflow.com/questions/13728581/pseudocode-for-cyk-algorithm-please）引用了这个C++实现http://nitishkr.wordpress.com/2011/03/29/cyk-algorithm-implementation/ – 2013-04-05 18:46:38

你用什么地图和集合？这里的伪代码：http://en.wikipedia.org/wiki/CYK_algorithm使用一组布尔值。唯一出现的是套规则，... – Sebastian 2013-04-05 20:44:39

你不提供很多细节，一个简单的实现（甚至伪代码）可以帮助很多给你提示。

维基百科：

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

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

语法包含[R终结符R1 ...路由反射器。

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

nonterminal [static_cast（'C'）] = true; 你对终端也一样，你有一个非常快速的查找机制。

该语法包含作为开始符号集合的子集Rs。让P [n，n，r] 是一组布尔值。初始化P的所有元素为false。对于每个i = 1到n，每个单元生产Rj - > ai 集合P [i，1，j] =对于每个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 [1，n，x]中的任何一个为真（x在集合s上迭代，其中s是所有R的指数），则设置P [j，i，A] =真，那么S是其他语言S是不是语言

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

来源

2014-05-29 18:26:40

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

回答

相关问题