最大概率分詞程序，在所有可能分詞路徑中選擇概率最大的一條路徑最為分詞結(jié)果
public class MPM extends M
{
public static final HashMap<Character,TreeNode> dic = Dictionary.loadFreqDictionary("sogou.txt");
public static final HashMap<String,Long> map=Dictionary.loadFreq("sogou.txt");
/** *//**
* @return 返回可能匹配詞的長(zhǎng)度, 沒有找到返回 0.
*/
public ArrayList<Integer> maxMatch(TreeNode node,char[] sen, int offset)
{
ArrayList<Integer> list=new ArrayList<Integer>();
for(int i=offset; i<sen.length; i++)
{
node = node.subNode(sen[i]);
if(node != null)
{
if(node.isAlsoLeaf())
list.add(i+1);
}
else
break;
}
return list;
}
@Override
public ArrayList<Token> getToken(ArrayList<Sentence> list)
{
ArrayList<Token> tokenlist=new ArrayList<Token>();
for(Sentence sen:list)
{
AdjList g = new AdjList(sen.getText().length+1);//存儲(chǔ)所有被切分的可能的詞
int i=0;
while(i<sen.getText().length)
{
Token token = new Token(new String(sen.getText(),i,1),i,i+1);
if(map.containsKey(token.getWord()))
token.setWeight(Math.log(map.get(token.getWord())));
g.addEdge(token);
TreeNode n=dic.get(sen.getText()[i]);
if(n!=null)
{
ArrayList<Integer> ilist =maxMatch(n, sen.getText(),i);
if(ilist.size()>0)
for(int j=0;j<ilist.size();j++)
{
token = new Token(new String(sen.getText(),i,ilist.get(j)-i),i,ilist.get(j));
if(map.containsKey(token.getWord()))
token.setWeight(Math.log(map.get(token.getWord())));
g.addEdge(token);
}
}
i++;
}
//System.out.println(g);
ArrayList<Integer> 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;
//計(jì)算出最大概率的數(shù)組
public ArrayList<Integer> maxProb(AdjList g)
{
prevNode = new int[g.verticesNum]; //最佳前驅(qū)節(jié)點(diǎn)
prob = new double[g.verticesNum]; //節(jié)點(diǎn)概率
prob[0] = 0;//節(jié)點(diǎn)0的初始概率是1,取log后是0
//按節(jié)點(diǎn)求最佳前驅(qū)
for (int index = 1; index < g.verticesNum; index++)
getBestPrev(g,index);//求出最佳前驅(qū)
ArrayList<Integer> ret = new ArrayList<Integer>();
for(int i=(g.verticesNum-1);i>0;i=prevNode[i]) // 從右向左找最佳前驅(qū)節(jié)點(diǎn)
ret.add(i);
return ret;
}
//計(jì)算節(jié)點(diǎn)i的最佳前驅(qū)節(jié)點(diǎn)
void getBestPrev(AdjList g,int i)
{
Iterator<Token> it = g.getPrev(i);//得到前驅(qū)詞集合，從中挑選最佳前趨詞
double maxProb = 0;
int maxNode = -1;
while(it.hasNext())
{
Token itr = it.next();
double nodeProb = prob[itr.getStart()]+itr.getWeight();//候選節(jié)點(diǎn)概率
if (nodeProb > maxProb)//概率最大的算作最佳前趨
{
maxNode = itr.getStart();
maxProb = nodeProb;
}
}
prob[i] = maxProb;//節(jié)點(diǎn)概率
prevNode[i] = maxNode;//最佳前驅(qū)節(jié)點(diǎn)
}
}posted on 2012-08-31 10:12
nianzai 閱讀(2452)
評(píng)論(0) 編輯 收藏 所屬分類:
中文分詞