エントリー
私の以前の記事では、形態素解析器とその使用について検討しました。 この記事をよりよく理解するために、これを読むことを強くお勧めします。 また、NLTKパッケージのインストールと構成についても説明します。
さあ始めましょう
解析とは何ですか？ 解析は、トークンのシーケンスが文法によって生成された言語に属するかどうかを判断するプロセスです。 通常、理解しやすいようにツリー形式で表示されます。
英語のいくつかの文法的特徴を考慮してください。
- 無限の可能性
たとえば、提案の興味深い特徴は、大規模なオファーに投資できることです。 以下の提案を考慮してください。
- ウサインボルトが100mの記録を破った
- ジャマイカのオブザーバーは、ウサイン・ボルトが100m記録を破ったと報告した
- アンドレは、ジャマイカのオブザーバーがウサイン・ボルトが100mの記録を破ったと報告したと言いました
- アンドレはジャマイカのオブザーバーがウサイン・ボルトが100m記録を破ったと報告したと思う
前の文を記号Sで置き換えると、 AndreがSを言った後に次の文が作成されます。 これらのテンプレートおよび他の類似のテンプレート（たとえば、 SがSの場合はSまたはSの場合はS ）を使用すると、1つの文に基づいてより多くの文を作成できます。
そのようなテンプレートの助けを借りて、おとぎ話「くまのプーさん」（AAミルンによるくまのプーさんの物語、ピグレットは水に完全に囲まれています）に大きな提案が作成されました。
ついに船が彼を目にしたときのピグレットの喜びを想像できます。]数年後、彼はひどい洪水の間に非常に大きな危険にさらされていたと思うのが好きでしたが、彼が本当にいた唯一の危険は最後でした刑務所の30分、飛び立ったばかりのフクロウが木の枝に座って彼を慰め、誤ってカモメの卵を産んだ叔母についての非常に長い話と、その話この文のように、ずっと望みなく窓の外で聞いていたピグレットが静かに自然に眠り、窓からゆっくりと滑り出て、つま先だけでぶら下がるまでその瞬間、幸運なことに、フクロウからの突然の大声でのスコークは、実際にはストーリーの一部であり、彼の叔母が言ったことであり、ピグレットを目覚めさせて、安全に戻って、彼女？」-よく-ついに彼が良い船を見たとき、彼の喜びを想像することができます、脳o fプー（キャプテン、C。ロビン; 1番メイト、P。ベア）海を越えて彼を救いに来て......
これは、実際にはシンプルな構造のオファーです。 Sから始まる単純なパターンを使用しますが 、 Sの場合は S 、 Sの場合はSです。 この例から、言語には文を無制限に拡張できるように見える固有の構造があると結論付けることができます。
- 文のあいまいさ
映画「グルーチョ・マルクス」の「動物クラッカー」（1930）のあいまいさの有名な例：
アフリカで狩りをしているときに、パジャマで象を撃ちました。 象がどのように私のパジャマに入ったのか、私にはわかりません。
プログラムでは曖昧さを考慮することができます。 この記事の後半で、文法の作成とツリーの構築のプロセスを詳しく見ていきます。 次に、あいまいさの例を見てみましょう。
まず、簡単な文法を定義してツリーを構築します。
>>> grammar = nltk.parse_cfg(""" S -> NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) >>> sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas'] >>> parser = nltk.ChartParser(grammar) >>> trees = parser.nbest_parse(sent) >>> for tree in trees: print tree (S (NP I) (VP (V shot) (NP (Det an) (N elephant) (PP (P in) (NP (Det my) (N pajamas)))))) (S (NP I) (VP (VP (V shot) (NP (Det an) (N elephant))) (PP (P in) (NP (Det my) (N pajamas)))))
プログラムは2つの提案構造で構成されていました。 これはあいまいさの兆候です。
文脈自由文法
- 簡単な文法
最も単純な文脈自由文法を検討してください。 定義により、最初の文法規則の左側の最初の文字は特殊文字Sであり、すべての木はこの文字をルートとして持つ必要があります。
次のリストは、文法定義の例と、Mary See Bob文を分析するためのその使用例を示しています。
>>> grammar1 = nltk.parse_cfg(""" S -> NP VP VP -> V NP | V NP PP PP -> P NP V -> "saw" | "ate" | "walked" NP -> "John" | "Mary" | "Bob" | Det N | Det N PP Det -> "a" | "an" | "the" | "my" N -> "man" | "dog" | "cat" | "telescope" | "park" P -> "in" | "on" | "by" | "with" """) >>> sent = "Mary saw Bob".split() >>> rd_parser = nltk.RecursiveDescentParser(grammar1) >>> for tree in rd_parser.nbest_parse(sent): print tree (S (NP Mary) (VP (V saw) (NP Bob)))
この例の文法には、次の表の異なる構文カテゴリを含むルールが含まれています。
記号 価値 例 S 文 男は歩いた NP 名詞句 犬 VP 動詞句 公園を見た PP 前置詞句 望遠鏡で デット 決定者 その N 名詞 犬 V 動詞 歩いた P 前置詞 で
- 構文構造の再帰
ルールの左側のカテゴリが右側にも表示される場合、文法は再帰と呼ばれます。 次のリストでは、ルールNom-> Adj NomにはカテゴリNomの直接再帰が含まれていますが、直接再帰Sは2つのルールS-> NP VPおよびVP-> VSの組み合わせから発生します。
grammar2 = nltk.parse_cfg(""" S -> NP VP NP -> Det Nom | PropN Nom -> Adj Nom | N VP -> V Adj | V NP | VS | V NP PP PP -> P NP PropN -> 'Buster' | 'Chatterer' | 'Joe' Det -> 'the' | 'a' N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log' Adj -> 'angry' | 'frightened' | 'little' | 'tall' V -> 'chased' | 'saw' | 'said' | 'thought' | 'was' | 'put' P -> 'on' """)
この文法の再帰により、たとえば、ネストされた主格表現とネストされた文を持つツリーを構築できます。
文脈自由文法解析
パーサーは、文法の規則に従って入力文を処理し、この文法に対応する1つ以上の構文構造を構築するプログラムです。
再帰降下アルゴリズム（トップダウン戦略）と移動崩壊アルゴリズム（ボトムアップ戦略）の2つの単純な解析アルゴリズムを検討します。
それぞれをさらに詳しく見てみましょう。
- 再帰降下アルゴリズム。
文法をより高いレベルの要素を変換するための仕様として解釈する最も単純なアナライザーアルゴリズムは、いくつかのより低いレベルの要素ではありません。 たとえば、タスクは要素Sを見つけることです。 ルールS-> NP VPにより、アナライザーはこの要素を他の2つに置き換えることができます（最初にNPを見つけ、次にVPを見つけます）。 これらの各要素は、文法規則に基づいて他の要素に変換できます。 このプロセスは、タスクが要素を単語（たとえば、 望遠鏡 ）に置き換えるまで続きます。 次に、この単語が入力シーケンスの単語と比較され、これらの単語間に対応関係が確立された場合、アルゴリズムは引き続き機能します。 そうでない場合、アナライザーはステップに戻り、他のオプションを検討しようとします。
再帰降下アルゴリズムは、メソッドによって実行されます
nltk.RecursiveDescentParser(grammar)
このメソッドには、オプションのトレースパラメータがあります。 このパラメーターの値がゼロより大きい場合、アナライザーはすべての解析ステップの結果を表示します。
彼の作品を見てみましょう。 「メアリーは犬を見た」という文を分析します。 最初に文法を定義し、次にメソッドを使用します：
>>> import nltk >>> grammar = nltk.parse_cfg(""" S -> NP VP VP -> V NP | V NP PP PP -> P NP V -> "saw" | "ate" | "walked" NP -> "John" | "Mary" | "Bob" | Det N | Det N PP Det -> "a" | "an" | "the" | "my" N -> "man" | "dog" | "cat" | "telescope" | "park" P -> "in" | "on" | "by" | "with" """) >>> rd_parser = nltk.RecursiveDescentParser(grammar) >>> sent = 'Mary saw a dog'.split() >>> for t in rd_parser.nbest_parse(sent): print t (S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))
特定のパラメーターtrace = 2でメソッドをテストします。 完全な出力は非常に長いため、スポイラーの下に隠されます。
プログラムコードと出力>>> rd_parser = nltk.RecursiveDescentParser(grammar, trace=2) >>> sent = 'Mary saw a dog'.split() >>> for t in rd_parser.nbest_parse(sent): print t Parsing 'Mary saw a dog' [ * S ] E [ * NP VP ] E [ * 'John' VP ] E [ * 'Mary' VP ] M [ 'Mary' * VP ] E [ 'Mary' * V NP ] E [ 'Mary' * 'saw' NP ] M [ 'Mary' 'saw' * NP ] E [ 'Mary' 'saw' * 'John' ] E [ 'Mary' 'saw' * 'Mary' ] E [ 'Mary' 'saw' * 'Bob' ] E [ 'Mary' 'saw' * Det N ] E [ 'Mary' 'saw' * 'a' N ] M [ 'Mary' 'saw' 'a' * N ] E [ 'Mary' 'saw' 'a' * 'man' ] E [ 'Mary' 'saw' 'a' * 'dog' ] M [ 'Mary' 'saw' 'a' 'dog' ] + [ 'Mary' 'saw' 'a' 'dog' ] E [ 'Mary' 'saw' 'a' * 'cat' ] E [ 'Mary' 'saw' 'a' * 'telescope' ] E [ 'Mary' 'saw' 'a' * 'park' ] E [ 'Mary' 'saw' * 'an' N ] E [ 'Mary' 'saw' * 'the' N ] E [ 'Mary' 'saw' * 'my' N ] E [ 'Mary' 'saw' * Det N PP ] E [ 'Mary' 'saw' * 'a' N PP ] M [ 'Mary' 'saw' 'a' * N PP ] E [ 'Mary' 'saw' 'a' * 'man' PP ] E [ 'Mary' 'saw' 'a' * 'dog' PP ] M [ 'Mary' 'saw' 'a' 'dog' * PP ] E [ 'Mary' 'saw' 'a' 'dog' * P NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'in' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'on' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'by' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'with' NP ] E [ 'Mary' 'saw' 'a' * 'cat' PP ] E [ 'Mary' 'saw' 'a' * 'telescope' PP ] E [ 'Mary' 'saw' 'a' * 'park' PP ] E [ 'Mary' 'saw' * 'an' N PP ] E [ 'Mary' 'saw' * 'the' N PP ] E [ 'Mary' 'saw' * 'my' N PP ] E [ 'Mary' * 'ate' NP ] E [ 'Mary' * 'walked' NP ] E [ 'Mary' * V NP PP ] E [ 'Mary' * 'saw' NP PP ] M [ 'Mary' 'saw' * NP PP ] E [ 'Mary' 'saw' * 'John' PP ] E [ 'Mary' 'saw' * 'Mary' PP ] E [ 'Mary' 'saw' * 'Bob' PP ] E [ 'Mary' 'saw' * Det N PP ] E [ 'Mary' 'saw' * 'a' N PP ] M [ 'Mary' 'saw' 'a' * N PP ] E [ 'Mary' 'saw' 'a' * 'man' PP ] E [ 'Mary' 'saw' 'a' * 'dog' PP ] M [ 'Mary' 'saw' 'a' 'dog' * PP ] E [ 'Mary' 'saw' 'a' 'dog' * P NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'in' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'on' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'by' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'with' NP ] E [ 'Mary' 'saw' 'a' * 'cat' PP ] E [ 'Mary' 'saw' 'a' * 'telescope' PP ] E [ 'Mary' 'saw' 'a' * 'park' PP ] E [ 'Mary' 'saw' * 'an' N PP ] E [ 'Mary' 'saw' * 'the' N PP ] E [ 'Mary' 'saw' * 'my' N PP ] E [ 'Mary' 'saw' * Det N PP PP ] E [ 'Mary' 'saw' * 'a' N PP PP ] M [ 'Mary' 'saw' 'a' * N PP PP ] E [ 'Mary' 'saw' 'a' * 'man' PP PP ] E [ 'Mary' 'saw' 'a' * 'dog' PP PP ] M [ 'Mary' 'saw' 'a' 'dog' * PP PP ] E [ 'Mary' 'saw' 'a' 'dog' * P NP PP ] E [ 'Mary' 'saw' 'a' 'dog' * 'in' NP PP ] E [ 'Mary' 'saw' 'a' 'dog' * 'on' NP PP ] E [ 'Mary' 'saw' 'a' 'dog' * 'by' NP PP ] E [ 'Mary' 'saw' 'a' 'dog' * 'with' NP PP ] E [ 'Mary' 'saw' 'a' * 'cat' PP PP ] E [ 'Mary' 'saw' 'a' * 'telescope' PP PP ] E [ 'Mary' 'saw' 'a' * 'park' PP PP ] E [ 'Mary' 'saw' * 'an' N PP PP ] E [ 'Mary' 'saw' * 'the' N PP PP ] E [ 'Mary' 'saw' * 'my' N PP PP ] E [ 'Mary' * 'ate' NP PP ] E [ 'Mary' * 'walked' NP PP ] E [ * 'Bob' VP ] E [ * Det N VP ] E [ * 'a' N VP ] E [ * 'an' N VP ] E [ * 'the' N VP ] E [ * 'my' N VP ] E [ * Det N PP VP ] E [ * 'a' N PP VP ] E [ * 'an' N PP VP ] E [ * 'the' N PP VP ] E [ * 'my' N PP VP ] (S (NP Mary) (VP (V saw) (NP (Det a) (N dog)))) >>>
再帰降下アナライザーには、3つの重大な欠点があります。
- NP-> NP PPという形式の左再帰規則は、無限ループになります。
- 分析中に、入力文に対応しない単語や構造を考慮するには多くの時間がかかります（これは、 トレース= 2パラメーターを使用してリストで確認できます）。
- リターンを伴う検索プロセスは、分析されたコンポーネントを破棄し、再びそれらを構築する義務があります。
- 移動折りたたみアルゴリズム。
これはボトムアップアナライザーです。 他のアナライザーと同様に、これは文法規則の右側に対応する単語とフレーズのシーケンスを見つけようとし、文が記号Sに 「カール」されるまでそれらを規則の左側に置き換えます。
move-collapseアナライザーは、次の単語を繰り返しスタックにプッシュします。この操作は「移動」と呼ばれます。 スタックの最上部のN個の要素がルールの右側のN個の要素に対応する場合、それらはスタックから削除され、ルールの左側の要素はスタックに移動します。 スタックの最上部にあるN個の要素を1つの要素に置き換えることを「折りたたみ」と呼びます。 この操作は、スタックの最上部に対してのみ実行されます。より深い要素の削減は、新しいデータが最上部に到達する前に完了する必要があります。 アナライザーは、入力に到着したすべての要素が処理され、スタックに1つの要素（要素Sを持つ解析ツリー）だけが残ったときに作業を終了します。 ところで、 nltk.app.srparser（）デモでアナライザーを詳細に調べることができます。
NLTKでは、移動崩壊アルゴリズムがメソッドに実装されています
nltk.ShiftReduceParser(grammar)
おなじみの文「メアリーは犬を見た」ですぐに確認しましょう（前の例の文法も使用します）。
>>> sr_parse = nltk.ShiftReduceParser(grammar) >>> sent = 'Mary saw a dog'.split() >>> print sr_parse.parse(sent) (S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))
move-collapseアナライザーは行き止まりになる可能性があり、入力文が文法に矛盾しない場合でも、分析結果を取得できません。 これが発生した場合、入力語はなく、スタックにはSに縮小できない要素が含まれます。 これらの問題は、前の手順の手順から発生します。
再帰降下アナライザーに対するこのアナライザーの利点は、単語の入力シーケンスに対応する構文構造を構築することです。 さらに、彼は各下部構造を個別に構築します。 たとえば、 NP（Det（the）、N（man））は、ルールVP-> V NP PPを折り畳むときに使用されるか、 NP-> NP PPに関係なく構築されます。
おわりに
この記事では、NLTKパッケージを使用した文の解析について説明しました。 解析のための2つのアルゴリズムも検討されました。移動崩壊アルゴリズムと再帰降下アルゴリズムです。
ご清聴ありがとうございました。