C/C++ でCYK アルゴリズムを実装したいのですが、さまざまな Web サイトで入手できる擬似コードでは、効率的に実装する方法がわかりません。map や sets のようないくつかの stl 構造を使用するバージョンを作成しましたが、非常に遅いです。二項演算のみを使用して実装を改善することを考えていましたが、セットを使用してテーブルを格納する方法がわかりません。非端末には 8 つのシンボルしかなく、端末には 26 のシンボルがあるとしましょう。プロダクションに関する情報を格納するために unsigned chars (2^8 -> 0-1 の場合は 8 桁) のテーブルを使用することを考えていましたが、格納方法がわかりません。
助けや手がかりを教えてもらえますか？
多くの詳細を提供しません。単純な実装 (擬似コードであっても) は、ヒントを提供するのに大いに役立ちます。
ウィキペディアから：
入力を n 文字 (a1 ... an) からなる文字列 S とします。させて
これには、単純な文字列または文字のベクトルを使用できます
文法には r 個の非終端記号 R1 ... Rr が含まれています。
非終端記号を bools std::array nonterminal {}; の配列に格納します。次に、文字があるので、文字に対応する位置を true で初期化できます。
非端末[static_cast('C')] = true; ターミナルでも同じことを行うと、非常に高速な検索メカニズムが得られます。
この文法には、開始記号のセットであるサブセット Rs が含まれています。P[n,n,r] をブール値の配列とします。P のすべての要素を false に初期化します。for each i = 1 to n 各単位生産量 Rj -> ai set P[i,1,j] = true for each i = 2 to n -- 各 j = 1 to n-i+1 のスパンの長さ - - 各 k のスパンの開始 = 1 から i-1 -- 各プロダクション RA のスパンの分割 -> RB RC if P[j,k,B] and P[j+k,ik,C] then set P[ j,i,A] = true P[1,n,x] のいずれかが true の場合 (x はセット s に対して反復処理され、s は Rs のすべてのインデックス)、S は language のメンバーである、そうでない場合、S はメンバーではない言語の
その後、アルゴリズムはかなり単純に見えます。タイトなループ内で一時的な値を初期化しないようにしてください。問題ありません。