我想在C/C++中实现CYK算法，但是网站上提供的伪代码并没有有效的实现方法。我写了一个使用了一些stl结构（如map和set）的版本，但是速度非常慢。我考虑通过只使用二进制运算来改进我的实现，但是我不知道如何存储我的带有集合的表格。假设我们只有8个符号用于非终端和26个用于终端。我考虑使用无符号字符表（2^8 -> 0-1的8个位置）来存储关于产生式的信息，但是我不知道如何存储它。
你能给我一些帮助或提示吗？
你能给我一些帮助或提示吗？
如何在C++中加速CYK算法？
3
- Jackson Rubbo
2
可能会很有趣：这个之前的问题（https://dev59.com/ymvXa4cB1Zd3GeqPL7ec）引用了这个C++实现http://nitishkr.wordpress.com/2011/03/29/cyk-algorithm-implementation/。 - Vitor Py
1你使用地图和集合做什么？这里的伪代码：http://en.wikipedia.org/wiki/CYK_algorithm 使用布尔数组。唯一出现的集合是规则集合，... - Sebastian
1个回答
0
你没有提供很多细节，一个简单的实现（即使是伪代码）可以帮助我们给出提示。
来自维基百科：
让输入为由n个字符组成的字符串S：a1 ... an。让
对于此问题，您可以使用一个简单的字符串或char向量。
语法包含r个非终结符R1 ... Rr。
我会将非终结符存储在bool数组中std::array nonterminal{};然后，由于您有字符，您可以使用true初始化对应于该字符的位置。
nonterminal[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,i-k,C]则设置P[j,i,A] = true。如果任何P[1,n,x]为true（其中x迭代整个Rs集合的索引），则S是语言的成员，否则S不是语言的成员。之后，该算法似乎非常简单明了。只需确保不在紧密循环内初始化临时值即可。
来自维基百科：
让输入为由n个字符组成的字符串S：a1 ... an。让
对于此问题，您可以使用一个简单的字符串或char向量。
语法包含r个非终结符R1 ... Rr。
我会将非终结符存储在bool数组中std::array nonterminal{};然后，由于您有字符，您可以使用true初始化对应于该字符的位置。
nonterminal[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,i-k,C]则设置P[j,i,A] = true。如果任何P[1,n,x]为true（其中x迭代整个Rs集合的索引），则S是语言的成员，否则S不是语言的成员。之后，该算法似乎非常简单明了。只需确保不在紧密循环内初始化临时值即可。
- dau_sama
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接