問題タブ [cyk]

指定された文法で入力文字列をチェックする CYK アルゴリズムを実装しました。
そして、次の文法がある場合

文字列をチェックするabと、アルゴリズムはそれが文法にあると言います。しかし、以下のような文法がある場合、

string を渡すとaih、アルゴリズムはそれが文法にないと言います。しかし、ご覧のとおり、明らかに非終端記号aihが作成され、ABCそれらは等しいS. だから私はこれについて混乱しています。私が間違っている場合は指摘してください.. よろしくお願いします。

EDIT：上記は、アルゴリズムが単語を構築する方法を示しています。(1,3) では null です。したがって、文法にはありません。私の文法の問題ですか？

私は Erlang を始めたばかりで、演習としてCYK アルゴリズムを実装しようとしました。

メインコード (cyk.erl):

文法ファイル (grammar.txt)

コードは erlang シェルからテストできます

この例のコードは問題なく動作しているように見えますが、私はそれを改善する方法 (より erlang 風にする方法) と、特に処理を複数のプロセス/ノードに分散させる方法を探していました。

各ステップのすべての process_subtree 実行は同時に実行できると思いますが、その方法がわかりません。

どんな提案でも大歓迎です！

文脈自由文法のための CYK 解析アルゴリズムの実装に取り​​組んでいます。

ただし、難しいのは、Java のように、私がよく知っている手続き型言語とは対照的に、XSL (関数型言語) でこれを行う必要があることです。

Java でアルゴリズムを実装していますが、これを Xsl に変換したいと考えています。

どんな助けでも大歓迎です。前もって感謝します。

CYK/CKY アルゴリズムが文法を Chomsky Normal Form (CNF) にする必要がある場所をいくつか読んだことがあります。

CYK の標準バージョンは、チョムスキー正規形 (CNF) で与えられた文脈自由文法でのみ動作します ~ウィキペディア

ただし、文法が CNF にない CKY アルゴリズムの例もいくつか見てきました。Christopher Manning が使用する一般的な例は、単項規則を含む「fish people fish tanks」(参照: PPT スライド #19 ) です。

また、プロダクションの RHS で 3 つの非終端記号を使用する CKY を示す他の例も見てきました (例: VP -> Verb NP NP reference )。なぜ不一致なのですか？

私が作成しているメソッドの場合、行末にある単語を取り込みたいのですが、見つかった単語をその左側 (行頭からスペースまで) に追加したいと考えています。文字) を配列に追加します。

これまでの私のコードは次のとおりです。

これまでのところ、出力された配列は常に空になります。私の論理のどこが間違っているのかわからない。

grammarFile の行は、たとえば次のようになります。

VP -> V NP

NP -> N

VP -> VPP

-> の右側の部分を入力として取り、左側を配列に追加して、プログラムの他の部分で使用したいと考えています。