当前位置:编程学习 > JAVA >>

最短路径分词程序

最短路径分词法
public class SPM2 extends M
{
    public static final HashMap<Character,TreeNode> dic = Dictionary.loadFreqDictionary("sogou.txt");
   
    /**
     * @return 返回可能匹配词的长度, 没有找到返回 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);//存储所有被切分的可能的词
            int i=0;
            while(i<sen.getText().length)
            {
                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<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));
                            token.setWeight(1);
                            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;
   
    //计算出路径最短的数组
    public ArrayList<Integer> 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<Integer> ret = new ArrayList<Integer>();
        for(int i=(g.verticesNum-1);i>0;i=prevNode[i]) // 从右向左找最佳前驱节点
            ret.add(i);
        return ret;
    }
   
    //计算节点i的最佳前驱节点
    void getBestPrev(AdjList g,int i)
    {
        Iterator<Token> it = g.getPrev(i);//得到前驱词集合,从中挑选最佳前趋词
        double maxProb = 1000;
    &nbs
补充:软件开发 , Java ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,