最短路径分词程序 - JAVA

最短路径分词法
public class SPM2 extends M
{
public static final HashMap dic = Dictionary.loadFreqDictionary("sogou.txt");

/**
* @return 返回可能匹配词的长度, 没有找到返回 0.
*/
public ArrayList maxMatch(TreeNode node,char[] sen, int offset)
{
ArrayList list=new ArrayList();
for(int i=offset; i {
node = node.subNode(sen[i]);
if(node != null)
{
if(node.isAlsoLeaf())
list.add(i+1);
}
else
break;
}
return list;
}

@Override
public ArrayList getToken(ArrayList list)
{
ArrayList tokenlist=new ArrayList();
for(Sentence sen:list)
{
AdjList g = new AdjList(sen.getText().length+1);//存储所有被切分的可能的词
int i=0;
while(i {
Token token = new Token(new String(sen.getText(),i,1),i,i+1);
token.setWeight(1);
g.addEdge(token);

TreeNode n=dic.get(sen.getText()[i]);
if(n!=null)
{
ArrayList ilist =maxMatch(n, sen.getText(),i);
if(ilist.size()>0)
for(int j=0;j {
token = new Token(new String(sen.getText(),i,ilist.get(j)-i),i,ilist.get(j));
token.setWeight(1);
g.addEdge(token);
}
}
i++;
}
//System.out.println(g);
ArrayList ret=maxProb(g);

Collections.reverse(ret);
int first=0;
for(Integer last:ret)
{
Token token = new Token(new String(sen.getText(),first,last-first),sen.getStartOffset()+first,sen.getStartOffset()+last);
tokenlist.add(token);
first=last;
}
}
return tokenlist;
}

int[] prevNode;
double[] prob;

//计算出路径最短的数组
public ArrayList maxProb(AdjList g)
{
prevNode = new int[g.verticesNum]; //最佳前驱节点
prob = new double[g.verticesNum]; //节点路径
prob[0] = 0;//节点0的初始路径是0

//按节点求最佳前驱
for (int index = 1; index < g.verticesNum; index++)
getBestPrev(g,index);//求出最大前驱

ArrayList ret = new ArrayList();
for(int i=(g.verticesNum-1);i>0;i=prevNode[i]) // 从右向左找最佳前驱节点
ret.add(i);
return ret;
}

//计算节点i的最佳前驱节点
void getBestPrev(AdjList g,int i)
{
Iterator it = g.getPrev(i);//得到前驱词集合，从中挑选最佳前趋词
double maxProb = 1000;
int maxNode = -1;

while(it.hasNext())
{
Token itr = it.next();
double nodeProb = prob[itr.getStart()]+itr.getWeight();//候选节点路径
//System.out.println(itr.getWord()+","+nodeProb);
if (nodeProb < maxProb)//路径最短的算作最佳前趋
{
maxNode = itr.getStart();
maxProb = nodeProb;
}
}
prob[i] = maxProb;//节点路径
prevNode[i] = maxNode;//最佳前驱节点
}
}