以平为期

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

Title: A Top-Down Chart Parser With Feathers Design (Implement of NLP TextBook Chapter4 Section4.5)
Author:lijun
Date: 2006-4-23

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() }

Symbol: class{String CAT,ArrayList AGR,ArrayList SUBCAT,ArrayList VFORM; 
Copy() // 注意要完全复制， 用Clone会有问题.
boolean NoContrary(Symbol other); // 表示 CAT同，其他实例化的属性不冲突,是包含或相等，非实例化的不管.
// 但是对于Rule中有的，但是C(也就是X)中没有的，则需要只判断C 的所有特征是否都能在Rule.Next中发现，
// 也就是说只用判断 !=null && size()>0的情况
Instantiation(Rule) // 由本Symbol对其他Rule进行空变量的实例化，
}
// Symbol中除CAT外，其他变量的状态表示: size==0表未知，等待实例化; =null 表没有此属性; size==1表已有值,size>1则表示另一种形式的未知，多个值可选,也需实例化.(如果2个都是>1则取交集)
// 这种表示方法的缺陷是: 如果碰到 VP1-> AUX VP补足语 时，VP的VFROM 用AUX的 COMPFORM来表示时，无法表现出2者的关系。
// 可以添加一个专门的变量 equal来表示2者关系, ArrayList of equal; 0=1, 2=3,..
用在Rule中如果

// 按照课本的做法，认为一个单词只有一个CAT,因为其他属性都不一定一样， 多个时，可以用ROOTID之类的来扩展
LexiconWord: class{String word, Symbol sym}
Lexicon: class{HashMap lexicons,LexiconWord getLexiconWord(str); String[] getLexiconWordCat(str) Load()}

Rule: class{Symbol[] thisRule; Symbol getHead(), Symbol[] getBody(), Rule copy() }  // e.g. S -> NP VP
RuleManager class{Rule[] getRightStartWith(String catStr) Load()}

//  0<= rulepos <= rule.length  e.g.  S -> 0 NP 1 VP 2
Arc: class{Rule thisRule; addRule(); int start,end; int rulepos; isFullActive(); isLastPos(); isConstituent(); Arc(rule,start,end,rulepos); Arc(left,right,start,end,rulepos=1) ;
}
isFullActive(): rulepos< thisRule.size()-1; // S-> w1,...C,...Wn-1,Wn
isLastPos(): ruleepos==thisRulesize()-1;   // S-> w1,....C,Wn
isConstituent(): rulepos == thisRule.Size(); //  S->w1,...Wn-1,C  , or C->C

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

// 这里的ArcManager 包括 ActiveArc 和 Constituent 2种类型的 Arc.
ArcManager: class{ArrayList arcs; ArrayList cons; addArc(); addConstituent() }

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

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

      而Rule的开始位置是从 0 到 rule.length.
//为了统一处理，将Rule的 Head和Body 都放到一个Symbol数组中了,所以对于rulepos来说，访问body的0位置等于现在访问 Symbol[1]了，
为了不影响原来的程序，getHead(), getBody(),
getBody(rpos) // 内部将rpos+1,取Symbol[rpos+1];
// 或者等程序写完了，统一将 rpos 的值都+1, 按照1---Symbol.length的范围来处理.

Agenda中存已经完成的Constiuent.同时也是要处理的.
Chart包括 Arc 和 Constiuent两部分，与原来写的bottom-up 不一样，把Arc和Constituent用Arc类型统一来处理了。
extension算法得到新的 Active Arc 以及匹配完成的Constiuent 分别加入到Arc和Agenda中。
每次Parser循环时，把单词向后移一位，然后从Agenda中取出一个来。处理完agenda中的所有Constiuent后才再取单词。
对于一个单词的词性 Arc的形式是: N -> N o ( start,end)
算法中的ArcManager 和ConstituentManager都是 ArcManager类型的类,都用来存储Arc，

这里是一步一步地处理。每步把此步的单词词性以及派生出来的成分处理完.

// 弧导入算法,为了便于处理，没有传入一个Arc,而是传入Arc.Rule, arc.end, arc.rule.rulepos,以便当一个单词词性的弧导入时，方便写传入参数.
// arc.start 用不到，所以就省去了。
// 第一次时， S -> NP VP , 1 , 0
//递归导入新弧, 分别传入 这条弧的规则Rule, 这条弧的结束位置arcEnd, 以及规则进行到了第几个位置rpos
// S -> C1 ... o Ci ...Cn  (start,end) =====> Ci -> o X1 X2...Xk ( end, end )
//             rpos                                 0
ArcIntroduction(Rule newRule,int arcEnd,int rpos)
{
 for(each rule[i]){
    if(rule[i].gethead.CAT.equals(newRule.getRuleBodyConstiuent(rpos).CAT)
       && noContrary() ) // 只需判断 noContrary 即可，因为两者的CAT都不为空.
    { // 这里是导入新弧，下一个单词还未确定，所以无需进行各类属性的判断，只需与Rule中有值属性无冲突即可.
      // 但是为了彻底减少垃圾边，newRule是实例化后的更好.
 Arc arcNew=new Arc(rule[i],arcEnd,arcEnd,0); // 新弧以规则的0位置开始.
 arcManager.AddArc(arcNew);
 if(Symbol.getType(rule[i].body[0])!=Symbol.TERMINAL)
     ArcIntroduction(tmprule,arcEnd,rpos);  // 递归非终结符
    }
 }
}

Main Algorithm:( Inside ChartParser class Parser Method )

// 第一次运行导入所有S的规则:
for(each rule)
  if(rule.left=='S')
  {
    Arc arcNew =new Arc(rule[i],1,1,0);
    arcManager.add(arcNew);
    ArcIntroduction(rule[i],1,0);
  }

Sentence --> word[] or SentenceObj
spos=1;
Constiuent c
While(pos<=word.length){
  // 得到一个单词以及成分.
  if(aggendaManager.isEmpty()){
 if(spos<=length){
  // 这里可以删除那些肯定没用的边
  for(each are)
   if( sentence.spos > arc.end && arc.rule[rpos]==terminal )
     arcManager.remove(thisarc);

  //对于下一个词的多种词性，只添加在当前活动弧的下一个位置上的词性
   sym =lexcion.getLexiconWordCat(words[spos-1]).symbol;
  for(each catstr)
  {
     for(each arc)
     {
        if(arc[j].RuleNextCons==catstr[i] && arc.end==sendten.spos
          && noContrary() ==true )
   // 这里无需复制Symbol.因为词性不会变化
   c = new Arc(sym,sym,spos,spos+1);
   aggendaManger.add(c);
   break;
     }
  }
 }//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; }
   //进行弧扩展
   extension()
  }
  spos=spos+1;
}//While
if(succeed)
 out.pirntln("Ok!");

// 弧扩展算法, 两个for可以合并到一起.
extension(){
  // 从待处理表agenda中取出的成分Constiuent放入constiuent.
  constientManger.add(c);
  // 包含以C开头的活动边并不处于末尾位置的边再产生新活动边加入arcManager. 同时进行边导入算法 ArcIntro
  //  S-> w1,...o C,...Wn-1,Wn ===> S-> w1,....C o ...Wn
  //          rulepos                         rulepos+1
  for(each arc in arcManger){
 if(isFullActive && arc.end==c.start && arc.rule[rulepos]==c.rule.left
    && noContrary()
   cRule = arc.Rule.copy();
   c.head.instantiation(cRule);
   arcNew=new arc(cRule,arc.start,c.end,rulepos+1);
   arcManger.addArc(arcNew); 
          // 对于新加入的的弧进行导入新弧, 无论传入arc.thisRule，还是实例化后的cRule， 都可以。因为
          ArcIntroduction(cRule,c.end,arc.rulePos+1);

  }
  // 以C cat结尾的活动边 产生新的完全匹配的成分Constiuent加入到aggendaManager中.
  for(each arc in arcManager){
 if(isinLastPos() && arc.end==c.start && arc.rule[rulepos]==c.cat
    && noContrary())
  {
   cRule = arc.Rule.copy();
   c.head.instantiation(cRule);
   arcNew=new arc(cRule,arc.start,c.end,rule.size());
   agendaManger.addCons(cNew);
 }
  }
}