Prolog応用プログラム

それでは、いよいよ知識処理っぽいプログラムに挑戦しましょう。先ずはグラフの探索です。これは知識処理としては基本中の基本となるような概念なのできちんと学習するように。次は構文解析です。「コーブンカイセキってなに?」という声が聞こえてきそうですが、これも自然言語処理(つまり、人間の言葉(文章)をコンピュータが理解するにはどうしたらいいかっていう研究)の基本となる概念ですので頑張ってください。

13.1 無向グラフの探索

先ず、無向グラフの探索を行うプログラムを示します。
          %
          %   problem11.pl
          %
          %   無向グラフ上の始点から終点までのパス(経路)を探す

          graph(Goal,Goal,Log,H,T):-
              H=[[Goal|Log]|T].
          graph(Goal,Start,Log,H,T):-
              neighb(Start,Neighb),
              check_next(Goal,Start,Neighb,Log,H,T).

          check_next(_,Node,[],_,H,T):-
              H=T.
          check_next(Goal,Node,[N|Ns],Log,H,T):-
              passed(N,Log,Result),
              go_next(Result,Goal,N,[Node|Log],H,T1),
              check_next(Goal,Node,Ns,Log,T1,T).

          go_next(true,_,_,_,H,T):-
              H=T.
          go_next(false,Goal,Node,Log,H,T):-
              graph(Goal,Node,Log,H,T).

          passed(_,[],false).
          passed(X,[X|_],true).
          passed(X,[A|Y],R):-
              passed(X,Y,R).

          neighb(a,[b,c]).
          neighb(b,[a,c,d]).
          neighb(c,[a,b,e]).
          neighb(d,[b]).
          neighb(e,[c]).
neighb節がグラフのデータです。グラフのノード(節点)とそのノードに隣接するノードのリストを引数としています。ですから、このグラフは下図に示すようなものとなります。

無向グラフ
図13.1 無向グラフ




そして、ノードaからdまでのパスを求めるためには、以下のようにプログラムに質問します。
          ?- graph(a,d,[],Ans,[]).
          Ans=[[a,b,d],[a,c,b,d]]
Prologの答えは[a,b,d]つまりノードaからbを通ってdへ至るパスと、[a,c,b,d]つまりノードaからcへ行ってからbを通ってdへ至るパスと2通りのパスがあることを示しています。



《演習問題》

13.2 構文解析

構文解析ははじめてなので、例から入りましょう。例えば、
          the girl smiles
という文章があります。「彼女、こっち見て笑ってるぜ」って状況です。さて、この文章を理解するためには、[the]が定冠詞で名詞[girl]にかかっている、[girl]は今言った通りに名詞、そしてこの[the]と[girl]が名詞部になって、動詞部は動詞[smiles]である、ということが把握できなければなりません。厳密には動詞の変化とかいろいろあるのですが、ここでは割愛しましょう。そして、[girl]が名詞だということが判るためには名詞の辞書を持っていなければなりません。ということは、この名詞の辞書には[girl]の他にも多くの単語が記載されていなければなりませんね。でも、辞書があまりに膨大になると処理が遅くなりますし、第一みんなが理解しにくくなるので、ここでは簡単にするために辞書は大変にコンパクトなものにしましょう。

次の構文規則を見てください。これが「構文」の規則、即ち「文法」と考えてください。[文]が[名詞部]と[動詞部]から構成されていること、[名詞部]が[冠詞]と[名詞]から構成されていること、[動詞]には[likes],[kicks],[smiles],[admires],[eats]があること、[冠詞]には[the],[a],[an]があること、などが規定されています。この構文規則では動詞の変化形は規定しておらず、また、ここに記載されていない単語は認識できません。例えば、smileやtalksなどは動詞と認識できません。
          [構文規則]
          sentence->gtnoun_phrase+verb.
          sentence->gtnoun_phrase+verb_phrase.
          noun_phrase->gtdeterminer+noun_expression.
          noun_expression->gtnoun.
          noun_expression->gtadjective+noun_expression.
          verb_phrase->gtverb_expression+noun_phrase.
          verb_expression->gtverb.
          verb_expression->gtadverb+verb.

          verb->gtlikes|kicks|smiles|admires|eats.
          determiner->gtthe|a|an.
          noun->gtboy|girl|table|tree|apple|ball.
          adverb->gtquickly|easily.
          adjective->gtbig|small|lazy|eager|bad|good.
後に構文解析を行うプログラムを示しますが、そのプログラムの中にgrammer節とdictionary節としてこの構文規則を記述してあります。

次に[構文解析木]について説明しておきます。これは文を構文解析した結果を木構造で表現したものです。[the girl smiles]ならば、下図のようになります。

構文解析木
図13.2 構文解析木




[the girl smiles]という文がどのように構成されているかを木構造の図にしたのが構文解析木というわけです。勿論、Prologでこのような図を作成する方法は学習していませんから、プログラムでは以下のように示すこととします。カッコが多くなって見にくいので注意してください。
P=sentence(noun_phrase(determiner(the),noun_expression(noun(girl))),verb(smiles)).
さて、最後にこの構文解析を行うPrologのプログラムを示します。長いですから頑張ってね。
     %
     %   problem12.pl
     %
     %   簡単な構文解析を行う

     parse(S,P):-
         parse_sub(S,sentence,P).

     parse_sub([],_,_):-false.
     parse_sub([Word],Form,Parse):-
         dictionary(Form,Dict),
         member(Word,Dict),
         Parse=..[Form,Word].
     parse_sub(Words,Form,Parse):-
         grammar(Form,Exp),
         expanisions(Words,Exp,ParseList),
         Parse=..[Form|ParseList].

     expanisions(Word,[Exp1,Exp2],Parse):-
         one_expanision(Words,Exp1,Parse)
         ;
         one_expanision(Words,Exp2,Parse).
     expanisions(Words,[Exp],Parse):-
         one_expanision(Words,Exp,Parse).

     one_expanision(Words,[Form1,Form2],[Parse1,Parse2]):-
         splittings(Words,Splits),
         splits_parse(Splits,Form1,Form2,Parse1,Parse2).
     one_expanision(Words,[Form],[Parse]):-
         parse_sub(Words,Form,Parse).

     splits_parse([pair(Front,Back)|Splits],Form1,Form2,Parse1,Parse2):-
         parse_sub(Front,Form1,Parse1),
         parse_sub(Back,Form2,Parse2).
     splits_parse([Split|Splits],Form1,Form2,Parse1,Parse2):-
         splits_parse(Splits,Form1,Form2,Prase1,Parse2).

     splittings([],[pair([],[])]).
     splittings([H|T],[pair([],[H|T])|Insertions]):-
         splittings(T,Tsplits),
         front_insert(H,Tsplits,Insertions).

     front_insert(T,[],[]).
     front_insert(T,[pair(F,B)|Pairs],[pair([T|F],B)|InsertedPairs]):-
         front_insert(T,Pairs,InsertedPairs).

     grammar(sentence,[[noun_phrase,verb],[noun_phrase,verb_phrase]]).
     grammar(noun_phrase,[[determiner,noun_expression]]).
     grammar(noun_expression,[[noun],[adjective,noun_expression]]).
     grammar(verb_phrase,[[verb_expression,noun_phrase]]).
     grammar(verb_expression,[[verb],[adverb,verb]]).

     dictionary(verb,[likes,kicks,smiles,admires,eats]).
     dictionary(determiner,[the,a,an]).
     dictionary(noun,[boy,girl,table,tree,apple,ball]).
     dictionary(adverb,[quickly,easily]).
     dictionary(adjective,[big,small,lazy,eager,bad,good]).
このプログラムの実行するには、以下のように入力します。
          ?- parse([the,girl,smiles],P).

          ?- parse([the,boy,eats,the,apple],P).




《演習問題》
目次に戻る目次に戻る