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

中文分词基本算法主要分类：基于词典的方法、基于统计的方法、基于规则的方法
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);} }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

正向最大匹配算法和反向最大匹配算法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));
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

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

研_究_生
研_究_生命
研究生_命_起源
研究_生命_起源
1
2
3
4

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

长春市_长春_药店_
长春市_长_春药_
长春_市长_春药_
长春_市_长春_
长_春_市长_
1
2
3
4
5

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

国际化_
国际_化_
国_际_化_
1
2
3

显然规则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
2
3
4
5

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

北京大学_生_
北京_大学生_
1
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

经过规则1过滤得到

设施_和服_务_
设施_和_服务_
1
2

规则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.sina.com.cn/s/blog_3d37a5690100z0qp.html
最大概率分词法
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;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168