（2）中文分词——基于词典的方法

客官°小女子只卖身不卖艺 2022-07-29 08:50 299阅读 0赞

中文分词基本算法主要分类：基于词典的方法、基于统计的方法、基于规则的方法  
1、基于词典的方法（字符串匹配，机械分词方法）  
定义:按照一定策略将待分析的汉字串与一个“大机器词典”中的词条进行匹配，若在词典中找到某个字符串，则匹配成功。  
按照扫描方向的不同：正向匹配和逆向匹配  
按照长度的不同：最大匹配和最小匹配  
1.2基于统计的分词（无字典分词）  
主要思想：上下文中，相邻的字同时出现的次数越多，就越可能构成一个词。因此字与字相邻出现的概率或频率能较好的反映词的可信度。  
主要统计模型为：N元文法模型（N-gram）、隐马尔科夫模型(Hidden Markov Model, HMM)。  
**最大正向匹配算法**:从左向右扫描寻找词的最大匹配。首先我们规定一个词的最大长度，每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配，如果没有找到，就缩短长度继续寻找，直到找到或者成为单字。

一个简单的Java正向匹配算法示例

import java.util.*;
    import java.io.*;
    public class MM {
        static int MaxLen=5;
        public static void main(String[] args){
            String dic="计算语言学、课程、课时";
            String str="计算语言学课程是三个课时";
            String s="";
            int begin=0,end;
            while(begin<str.length()){
                end=begin+MaxLen;
                if(end>str.length())end=str.length();
                while(begin<end&&!dic.contains(str.substring(begin,end))){
                    end--;
                }
                if(begin==end)end++;
                s=s+str.substring(begin,end)+"/";
                System.out.println(s);
                begin=end;
            }
            System.out.println(s);} }

正向最大匹配算法和反向最大匹配算法Java实现代码

import java.io.BufferedReader;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.HashSet;
    import java.util.Set;
    import java.util.logging.Level;
    import java.util.logging.Logger;
    
    /** * * @author Angela */
    public class BiMaxSegment { 
    
        /**最大分词长度**/
        private int max_len;
        /**词典**/
        private Set<String> dict;
    
        /**** * 初始化max_len和词典 * @param max_len */
        public BiMaxSegment(int max_len){
            this.max_len=max_len;
            dict=initDict("dic/chineseDic.txt","gb2312");
        }
    
        /** * 读取词典 * @param dictPath 词典文件路径 * @param charset 词典文件编码 * @return 词典Set */
        private Set<String> initDict(String dictPath,String charset){
            Set<String> dict=new HashSet<String>();
            try{           
                BufferedReader br = new BufferedReader(new InputStreamReader(
                        new FileInputStream(dictPath),charset));
                String s;
                //一行一行地读取文本内容
                while((s=br.readLine())!=null){   
                    //只读取词
                    dict.add(s.split(",")[0]);
                }
                br.close();
            }catch (IOException ex) {
                Logger.getLogger(BiMaxSegment.class.getName()).log(Level.SEVERE, null, ex);
            }
            return dict;
        }
    
        /** * 正向最大匹配算法 * @param text 要分词的文本内容 * @return 分词结果 */
        public String mm_segment(String text){
            StringBuilder sb=new StringBuilder();
            int begin=0,end;
            int len=text.length();
            while(begin<len){
                end=begin+max_len;
                if(end>len)end=len;
                //不匹配则指针前移
                while(begin<end&&!dict.contains(text.substring(begin,end))){
                    end--;
                }
                //一个字
                if(begin==end)end++;
                sb.append(text.substring(begin,end)+"/");
                begin=end;
            }
            return sb.toString();
        }
    
        /** * 反向最大匹配算法 * @param text 要分词的文本内容 * @return 分词结果 */
        public String rmm_segment(String text){
            StringBuilder sb=new StringBuilder();
            int right=text.length();
            int left;
            while(right>0){
                left=right-max_len;
                if(left<0)left=0;
                //不匹配则指针后移
                while(right>left&&!dict.contains(text.substring(left,right))){
                    left++;
                }
                //一个字
                if(right==left)left--;
                sb.insert(0,text.substring(left,right)+"/");
                right=left;
            }
            return sb.toString();              
        }
    
        public static void main(String[] args){
            BiMaxSegment bimax=new BiMaxSegment(3);
            String text="我在餐厅吃饭，饭菜好难吃啊！";
            System.out.println(bimax.rmm_segment(text));
        }
    
    }

**MMSEG分词算法**  
MMSEG分为**“匹配算法（Matching algorithm）”和“消除歧义的规则（Ambiguity resolution rules）”**这两部分。“匹配算法”是说如何根据词典里保存的词语，对要切分的语句进行匹配（正向？逆向？粒度？）；“消除歧义的规则”是说当一句话可以这样分，也可以那样分的时候，用什么规则来判定使用哪种分法，比如“设施和服务”这个短语，可以分成“设施*和服*务”，也可以分成“设施*和*服 务”，选择哪个分词结果，就是“消除歧义的规则”的功能。  
MMSEG的“匹配方法”有两种：  
1.Simple方法，即简单的正向匹配，根据开头的字，列出所有可能的结果。比如“一个劲儿的说话”，可以得到  
一个  
一个劲  
一个劲儿  
一个劲儿的  
这四个匹配结果（假设这四个词都包含在词典里）。  
2.Complex方法，匹配出所有的“三个词的词组”，即从某一既定的字为起始位置，得到所有可能的“以三个词为一组”的所有组合。比如“研究生命起源”，可以得到

研_究_生
    研_究_生命
    研究生_命_起源
    研究_生命_起源

MMSEG的“消除歧义的规则”有四个：  
1. 组合长度最大  
2. 组合中平均词语长度最大  
3. 词语长度的变化率最小  
4. 计算组合中所有单字词词频的自然对数，然后将得到的值相加，取总和最大的词组  
MMSEG的核心思想是抽取3个可能的词（存在多个组合），然后根据4个消除歧义规则确定到底选择那个组合。  
下面分别举例说明  
1.组合长度最大Maximum matching (最大匹配)，有两种情况，分别对应于使用“simple”和“complex”的匹配方法。对“simple”匹配方法，选择长度最大的词，用在上文的例子中即选择“一个劲儿的”；对“complex”匹配方法，选择“词组长度最大的”那个词组，然后选择这个词组的第一个词，作为切分出的第一个词，  
比如长春市长春药店，这个会有如下几种组合

长春市_长春_药店_
    长春市_长_春药_
    长春_市长_春药_
    长春_市_长春_
    长_春_市长_

第一种组合长度最长，所以就以第一种方式分词， 实际效果看起来也合理  
2.组合中平均词语长度最大Largest average word length（最大平均词语长度）。经过规则1过滤后，如果剩余的词组超过1个，那就选择平均词语长度最大的那个（平均词长＝词组总字数／词语数量）。  
比如国际化，这个会有如下几种组合

国际化_
    国际_化_
    国_际_化_

显然规则1无法过滤，长度都是3 经过规则2,之后发现第一个组合平均长度为3/1=3,第二个是3/2=1.5,第三个3/3=1 第一个平均长度最大，所以胜出  
这个规则和规则1看上去没啥区别，但因为有的时候句子不够被分成3个词的组合，有可能只够分2个词 上面就是个例子，国际化被分别分成了1个词的组合/2个词的组合/3个词的组合，优选词个数最少的组合  
3.词语长度的变化率最小Smallest variance of word lengths（词语长度的最小变化率），由于词语长度的变化率可以由标准差反映，所以此处直接套用标准差公式即可。  
比如北京大学生，这个会有如下几种集合

北京大学_生_
    北京_大学生_
    北京_大学_生_
    北京_大_学生_
    北_京_大学生_

显然规则1无法过滤，长度都是5  
在经过规则2之后剩下

北京大学_生_
    北京_大学生_

因为上面2个组合的平均长度为5/2=2.5,其他为5/3=1.66  
经过规则3之后剩下  
北京*大学生*  
这是我们想要的，因为第一条是变化是sqrt(((4-2.5)^2+(1-2.5)^2))/2)=1.5,后面是sqrt(((3-2.5)^2+(2-2.5)^2))/2)=0.5,第二条变化小，所以后面胜出  
4.单字词词频自然对数累加计算Largest sum of degree of morphemic freedom of one-character words，这个规则的意思是“计算词组中的所有单字词词频的自然对数，然后将得到的值相加，取总和最大的词组”。  
比如设施和服务，这个会有如下几种组合

设施_和服_务_
    设施_和_服务_
    设_施_和服_

经过规则1过滤得到

设施_和服_务_
    设施_和_服务_

规则2和规则3都无法确定谁胜出，只能走最后一个规则：第一条中的务和第二条中的和，从直观看，显然是和的词频在日常场景下要高，这依赖一个词频字典 和的词频决定了最后的分词是设施*和*服务\_  
为什么要取自然对数之和而不是简单的求和? 比如某个组合有两个单字,词频为3和7，另一个为5和5，3+7=5+5，但ln3+ln7小于ln5+ln5  
小结  
从4个规则来看，算法处处强调长度和均衡：  
1.3个词的组合要尽可能长  
2.每个词也要尽可能长  
3.每个词要尽可能长度接近  
4.单个词的词频也要较为接近  
这个四个过滤规则中，如果使用simple的匹配方法，只能使用第一个规则过滤，如果使用complex的匹配方法，则四个规则都可以使用。实际使用中，一般都是使用complex的匹配方法＋四个规则过滤。（simple的匹配方法实质上就是正向最大匹配，实际中很少只用这一个方法）

**最大概率分词算法**  
参考内容：基于Tire树和最大概率法的中文分词功能的Java实现  
[http://blog.csdn.net/sadfishsc/article/details/9152647][http_blog.csdn.net_sadfishsc_article_details_9152647]  
最大概率分词原理和代码  
[http://blog.sina.com.cn/s/blog\_3d37a5690100z0qp.html][http_blog.sina.com.cn_s_blog_3d37a5690100z0qp.html]  
最大概率分词法  
[http://blog.csdn.net/zoohua/article/details/4687074][http_blog.csdn.net_zoohua_article_details_4687074]

Java实现代码

import java.io.BufferedReader;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.logging.Level;
    import java.util.logging.Logger;
    
    /** * 本程序采用的是候选词的累计相乘概率 * @author Angela */
    public class MaxProbSegment { 
    
        /**最大分词长度**/
        private int max_len;
        /**分词词典**/
        private Map<String,Double> dict;
        /****/
        private List<Candidate> candidateWord;
    
        /**初始化最大分词长度和词典**/
        public MaxProbSegment(){
            max_len=4;
            initDict("dic/WordFrequency.txt","gb2312");
        }
    
        /** * 初始化词典 * @param dictPath 词典文件路径 * @param charset 词典文件编码 */
        private void initDict(String dictPath,String charset){
            dict=new HashMap<String,Double>();
            try{           
                BufferedReader br = new BufferedReader(new InputStreamReader(
                        new FileInputStream(dictPath),charset));
                String s;
                //一行一行地读取文本内容
                while((s=br.readLine())!=null){
                    String[] info=s.split(",");
                    //System.out.println(info[0]+" "+Double.parseDouble(info[2].replace("%","")));
                    //存入词和词的概率
                    dict.put(info[0],Double.parseDouble(info[2].replace("%","")));
                }
                br.close();
            }catch (IOException ex) {
                Logger.getLogger(BiMaxSegment.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
    
        /** * 得到所有候选词 * @param text 文本 */
        private void getCandidateWord(String text){
            candidateWord=new ArrayList<Candidate>();
            int rest_len;
            int n=text.length();
            String word;
            for(int offset=0;offset<n;offset++){
                rest_len=n-offset;
                //长度应小于剩余长度 
                for(int len=1;len<=max_len&&len<=rest_len;len++){                
                    //截取部分词串
                    word=text.substring(offset,offset+len);    
                    //如果词典含有该词，则该词为一个候选词
                    if(dict.containsKey(word)){
                        Candidate candidate=new Candidate();
                        candidate.offset=offset;
                        candidate.length=len;
                        candidate.cost=dict.get(word);
                        candidateWord.add(candidate);
                    }
                }
            }
        }
    
        /** * 计算每一个候选词的最佳前趋词，以及当前词的最大累计概率 * @param index 第index个候选词 */
        private void getPrev(int index){
            Candidate candidate=candidateWord.get(index);
            int maxID=-1;
            if(candidate.offset==0){
                candidate.prev=-1;
                candidate.total_cost=candidate.cost;
            }else{
                //向左查找所有候选词，得到前驱词集合，从中挑选最佳前趋词
                for(int i=index-1;i>=0;i--){
                    Candidate temp=candidateWord.get(i);
                    //得到前驱词
                    if(temp.offset+temp.length==candidate.offset){
                        //找到累计概率最大的前驱词
                        if(maxID==-1||
                                temp.total_cost>=candidateWord.get(maxID).total_cost)
                            maxID=i;
                    }
                    if(candidate.offset-temp.offset>=max_len)
                        break;//向左查找候选词最远不超过max_len个汉字
                }
                candidate.prev=maxID;
                //概率累乘
                candidate.total_cost=candidate.cost*candidateWord.get(maxID).total_cost;
            }
        }
    
        /** * 最大概率分词算法 * @param text 文本 * @return 分词结果 */
        public String segment(String text){        
            int len=text.length();
            //初始化所有的候选词
            getCandidateWord(text);
            int n=candidateWord.size();
            int maxID=-1;
            //得到每一个候选词的最佳前缀词
            for(int i=0;i<n;i++){            
                getPrev(i);
                Candidate candidate=candidateWord.get(i);
                //如果当前词是text中最后一个可能的候选词
                if(candidate.offset+candidate.length==len){
                    // 如果这个末尾候选词的累计概率最大
                    if(maxID==-1||
                            candidate.total_cost>candidateWord.get(maxID).total_cost)
                        maxID=i;// 把当前词的序号赋给minID，这就是最大概率路径的终点词的序号
                        // 这就是最后分词结果最右边的那个词的序号
                }
            }
            StringBuilder sb=new StringBuilder();
            //从右向左取词候选词
            for(int i=maxID;i>=0;i=candidateWord.get(i).prev){
                Candidate candidate=candidateWord.get(i);
                sb.insert(0, text.substring(candidate.offset,
                        candidate.offset+candidate.length)+"/");
            }
            return sb.toString();
        }
    
        public static void main(String[] args){
            MaxProbSegment mp=new MaxProbSegment();
            String text="有意见分歧";
            System.out.println(mp.segment(text));
        }
    
        /**候选词类**/
        private class Candidate{ 
            /**候选词在字符串中的起始位置**/
            int offset;
            /**候选词长度**/
            int length;
            /**候选词的最佳前缀候选词的下标**/
            int prev;
            /**候选词的概率**/
            double cost;
            /**候选词的累计概率**/
            double total_cost;
        }
    
    }

[http_blog.csdn.net_sadfishsc_article_details_9152647]: http://blog.csdn.net/sadfishsc/article/details/9152647
[http_blog.sina.com.cn_s_blog_3d37a5690100z0qp.html]: http://blog.sina.com.cn/s/blog_3d37a5690100z0qp.html
[http_blog.csdn.net_zoohua_article_details_4687074]: http://blog.csdn.net/zoohua/article/details/4687074