如何加速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算法？

回答

相關問題