以平为期

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://skyhorse.blogbus.com/logs/2578955.html

Title: A Bottom-Up Chart Parser Design (Implement of NLP TextBook Chapter3 Section3.4)
Author:lijun
Date: 2006-4-16

OutLine:
DataStructure & Main Algorithm.
Object oriented.

Note:
A class is denoted as: classname : class{ data, method() }
Usually a dateSturce Collection with relevant methods is named after : xxManager
The Main Class is ChartParser

DataStructure:

Sentence: words[] or class{ string[] word, int spos, init(),length(),next(),curword(), toString() }

LexiconWord: class{String word, ArrayList catStr}
Lexicon: class{HashMap lexicons,LexiconWord getLexiconWord(str); String[] getLexiconWordCat(str) Load()}

Constiuent: class{String catStr; int start, int end}
Rule: class{String head; String[] body}  // e.g. S -> NP VP
RuleManager class{Rule[] getRightStartWith(String catStr) Load()}

//  0<= rulepos < rule.length
Arc: class{Rule thisRule; addRule(); int start,end; int rulepos; isFullActive(); isLastPos()}
isFullActive(): rulepos< thisRule.size()-1; // S-> w1,...C,...Wn-1,Wn
isLastPos(): ruleepos==thisRulesize()-1;   // S-> w1,....C,Wn

//这里用Stack实现
AggendaManager: class{ArrayList agendaConstiuent; add(), cons Pop(); isEmpty()}

ArcManager: class{ArrayList arcs; addArc()}

ConstiuentManager: class{ArrayList consArr; addCons()}

ChartParser: class{AggendaManager,ArcManager,ConstiuentManager,Load(), Parser(sentence), extension() extensionStep2(), extensionStep3()}

上面的Constiuent和Arc中的 start, end 分别代表 Sentence的word的位置。
假设n个word组成sentence.
1<= start <= n;
1 < end <= n+1;
注意: word[i] 中的i 则是按照java的数组下表从 0 -->n-1

Agenda中存已经完成的Constiuent.同时也是要处理的.
Chart包括 Arc 和 Constiuent两部分，
extension算法得到新的 Active Arc 以及匹配完成的Constiuent 分别加入到Arc和Agenda中。
每次Parser循环时，把单词向后移一位，然后从Agenda中取出一个来。处理完agenda中的所有Constiuent后才再取单词。

与刘群的算法不一样，他是一次全部取出。这里是一步一步地处理。每步把此步的单词词性以及派生出来的成分处理完.
另外刘群是把Constiuent的构成无论是词类Cat还是Arc 都作为Arc来处理了。
而NLP Textbook 上好像为了易于理解没有这么说明算法,缺点是多占用了一点空间。

Main Algorithm:( Inside ChartParser class Parser Method )

Sentence --> word[] or SentenceObj
spos=1;
Constiuent c
While(pos<=word.length){
  // 得到一个单词以及成分.
  if(aggendaManager.isEmpty()){
 if(spos<=length){
   catStrs=lexcion.getLexiconWordCat(words[spos-1]);
  for(each catstr){
   c = new Constiuent(catStr,spos,spos+1);
   aggendaManger.add(c);
  }
 }//if(spos
 else{ //栈空，且到了句子末尾，解析失败.
   failed! break;
 }
  }//if(aggendaMan
  //把本次构成的所有成分c处理完.
  while(agendaManger.isEmpty()){
   c=agendaManger.pop();
   //如果执行到弹出的一个成分是S,1-end, 表示解析完成。
   if(c.substar='S' && c.start==1 && c.end= n+1 )
   { succeed! break; }
   //将成分开头的规则加入弧中。
   MatchedRules=RuleManager.getRightStartWith(c.catStr);
   for(each MatchedRule){
  arc=new arc(rule[i],c.start,c.end,pos=1)
  arcManger.addArc(arc);
   }
   //进行弧扩展
   extension()
  }
  spos=spos+1;
}//While
if(succeed)
 out.pirntln("Ok!");

// 弧扩展算法, 两个for可以合并到一起.
extension(){
  // 从待处理表agenda中取出的成分Constiuent放入constiuent.
  constientManger.add(c);
  // 包含以C开头的活动边并不处于末尾位置的边再产生新边加入arcManager.
  for(each arc in arcManger){
 if(isFullActive && arc.end==c.start && arc.rule[rulepos]==c.cat )
   arcNew=new arc(arc.rule,arc.start,c.end,rulepos+1);
   arcManger.add(arcNew); 
  }
  // 以C cat结尾的活动边 产生新的完全匹配的成分Constiuent加入到aggendaManager中.
  for(each arc in arcManager){
 if(isinLastPos() && arc.end==c.start && arc.rule[rulepos]==c.cat ){
   Constiuent cNew=new Constiuent(arc.rule.head,arc.start,c.end)
   agendaManger.add(cNew);
 }
  }
}