問題タブ [cyk]

私は自然言語解析に興味があり、Brill Part of Speech Tagger を作成しました。これを文法規則に基づいた POS タガーと組み合わせて拡張したいと考えています。英語のオープン ソース ルールセット ファイルを知っている人はいますか? CYK (Cocke-Younger-Kasami) アルゴリズム、特に C# に関連するものに特に興味があります。ありがとう。

CYK 構文解析アルゴリズムを学習しようとしています。

この一連の文法規則について、結果として得られる表は、与えられた 2 つの文に対して正しいでしょうか?

チョムスキー標準形の特定の文脈自由から文字列を導出できるかどうかを確認する必要があります。私はC++を使用しています。

ウィキペディアの記事には CYK アルゴリズムをカバーする非常に優れた疑似コードがありますが、よく理解できません。

CYKアルゴリズムの別の擬似コードを教えてくれるか、wiki記事で説明してくれる人が親切でしょうか?

そのため、ウィキペディアや多くのパワーポイント/pdfでCYKアルゴリズムについて読んでいます。

ウィキペディアには、私が言おうとしていることを 100% 理解していない部分があります。分解してくれませんか？

私を本当に混乱させる部分は、「P[1、n、x]のいずれかが真である場合（xはセットsに対して反復され、sはRsのすべてのインデックスです）、Sは言語のメンバーです。そうでない場合、Sはメンバーではありません言語の」

存在する n と x が true の場合、それはメンバーであると言っていますか? それとも、文字列の長さ n と x が true の場合、それはメンバーですか? または完全に異なる何か？

また、Xとは正確には何ですか？

編集：

みんなありがとう、私は間違いなくそれを行う方法を学びました。両方の回答を選択した回答として取得できれば幸いです。

文字列がCFGが提供されているCFLの一部であるかどうかを確認するために、さまざまなアルゴリズム（CYKおよびEarley）に出くわしました。簡単に理解して実装できるものを探しています。私が知る必要があるのは、文字列が CFG にあるかどうかです。CFG は通常次の形式で与えられます。

ソリューションは、イプシロン遷移も受け入れることになっています。たとえば、S1-> a | e

何か案は？

C/C++ でCYK アルゴリズムを実装したいのですが、さまざまな Web サイトで入手できる擬似コードでは、効率的に実装する方法がわかりません。map や sets のようないくつかの stl 構造を使用するバージョンを作成しましたが、非常に遅いです。二項演算のみを使用して実装を改善することを考えていましたが、セットを使用してテーブルを格納する方法がわかりません。非端末には 8 つのシンボルしかなく、端末には 26 のシンボルがあるとしましょう。プロダクションに関する情報を格納するために unsigned chars (2^8 -> 0-1 の場合は 8 桁) のテーブルを使用することを考えていましたが、格納方法がわかりません。

助けや手がかりを教えてもらえますか？

CYK アルゴリズムについて読んでいましたが、理解できない疑似コードの一部があります。疑似コード全体は次のとおりです。

これらの部分は私が混乱しているものです:

誰かがこれらの疑似コードについてヒントをくれますか?

現在、イプシロン遷移でCYK を実装しようとしています。提供されたアルゴリズムはイプシロン遷移をどのように処理しますか? そうでない場合、どのように実装しますか？(私は Java を使用しています)