中文分词引擎 java 实现 — 正向最大、逆向最大、双向最大匹配法

<article class="baidu&#95;pl">

正向最大匹配法

</article>

分词目标：

在词典中进行扫描，尽可能地选择与词典中最长单词匹配的词作为目标分词，然后进行下一次匹配。

算法流程：

假设词典中最长的单词为 5 个（MAX_LENGTH），那么最大匹配的起始子串字数也为 5 个

（1）扫描字典，测试读入的子串是否在字典中

（2）如果存在，则从输入中删除掉该子串，重新按照规则取子串，重复（1）

（3）如果不存在于字典中，则从右向左减少子串长度，重复（1）

分词实例：

比如说输入 “北京大学生前来应聘”，

  1. 第一轮：取子串 “北京大学生”，正向取词，如果匹配失败，每次去掉匹配字段最后面的一个字
    • “北京大学生”，扫描 5 字词典，没有匹配，子串长度减 1 变为“北京大学”
    • “北京大学”，扫描 4 字词典，有匹配，输出“北京大学”，输入变为“生前来应聘”
  2. 第二轮：取子串“生前来应聘”
    • “生前来应聘”，扫描 5 字词典，没有匹配，子串长度减 1 变为“生前来应”
    • “生前来应”，扫描 4 字词典，没有匹配，子串长度减 1 变为“生前来”
    • “生前来”，扫描 3 字词典，没有匹配，子串长度减 1 变为“生前”
    • “生前”，扫描 2 字词典，有匹配，输出“生前”，输入变为“来应聘””
  3. 第三轮：取子串“来应聘”
    • “来应聘”，扫描 3 字词典，没有匹配，子串长度减 1 变为“来应”
    • “来应”，扫描 2 字词典，没有匹配，子串长度减 1 变为“来”
    • 颗粒度最小为 1，直接输出“来”，输入变为“应聘”
  4. 第四轮：取子串“应聘”
    • “应聘”，扫描 2 字词典，有匹配，输出“应聘”，输入变为“”
  5. 输入长度为0，扫描终止


正向匹配法最终的切分结果为：”北京大学 / 生前 / 来 / 应聘”

正向匹配法实现代码如下：

public List<String> leftMax(String str) {

        List<String> results = new ArrayList<String>();
        String input = str;

        while( input.length() > 0 ) {

            String subSeq;
            // 每次取小于或者等于最大字典长度的子串进行匹配
            if( input.length() < MAX_LENGTH) 
                subSeq = input;
            else
                subSeq = input.substring(0, MAX_LENGTH);

            while( subSeq.length() > 0 ) {
                // 如果字典中含有该子串或者子串颗粒度为1，子串匹配成功
                if( dictionary.contains(subSeq) || subSeq.length() == 1) {
                    results.add(subSeq);
                    // 输入中从前向后去掉已经匹配的子串
                    input = input.substring(subSeq.length());
                    break;      // 退出循环，进行下一次匹配
                } else {
                    // 去掉匹配字段最后面的一个字
                    subSeq = subSeq.substring(0, subSeq.length() - 1);
                }   
            }

        }
        return results;
    }
 
    
  
  • 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


逆向最大匹配法

分词目标：

在词典中进行扫描，尽可能地选择与词典中最长单词匹配的词作为目标分词，然后进行下一次匹配。

在实践中，逆向最大匹配算法性能优于正向最大匹配算法。

算法流程：

假设词典中最长的单词为 5 个（MAX_LENGTH），那么最大匹配的起始子串字数也为 5 个

（1）扫描字典，测试读入的子串是否在字典中

（2）如果存在，则从输入中删除掉该子串，重新按照规则取子串，重复（1）

（3）如果不存在于字典中，则从左向右减少子串长度，重复（1）

分词实例：

比如说输入 “北京大学生前来应聘”，

  1. 第一轮：取子串 “生前来应聘”，逆向取词，如果匹配失败，每次去掉匹配字段最前面的一个字
    • “生前来应聘”，扫描 5 字词典，没有匹配，字串长度减 1 变为“前来应聘”
    • “前来应聘”，扫描 4 字词典，没有匹配，字串长度减 1 变为“来应聘”
    • “来应聘”，扫描 3 字词典，没有匹配，字串长度减 1 变为“应聘”
    • “应聘”，扫描 2 字词典，有匹配，输出“应聘”，输入变为“大学生前来”
  2. 第二轮：取子串“大学生前来”
    • “大学生前来”，扫描 5 字词典，没有匹配，字串长度减 1 变为“学生前来”
    • “学生前来”，扫描 4 字词典，没有匹配，字串长度减 1 变为“生前来”
    • “生前来”，扫描 3 字词典，没有匹配，字串长度减 1 变为“前来”
    • “前来”，扫描 2 字词典，有匹配，输出“前来”，输入变为“北京大学生”
  3. 第三轮：取子串“北京大学生”
    • “北京大学生”，扫描 5 字词典，没有匹配，字串长度减 1 变为“京大学生”
    • “京大学生”，扫描 4 字词典，没有匹配，字串长度减 1 变为“大学生”
    • “大学生”，扫描 3 字词典，有匹配，输出“大学生”，输入变为“北京”
  4. 第四轮：取子串“北京”
    • “北京”，扫描 2 字词典，有匹配，输出“北京”，输入变为“”
  5. 输入长度为0，扫描终止


逆向匹配法最终的切分结果为：”北京/ 大学生/ 前来 / 应聘”

逆向匹配法实现如下：

public List<String> rightMax(String str) {
        // 采用堆栈处理结果，后进先出
        Stack<String> store=new Stack<String>();
        List<String> results = new ArrayList<String>();
        String input = str;

        while( input.length() > 0 ) {

            String subSeq;
            // 每次取小于或者等于最大字典长度的子串进行匹配
            if( input.length() < MAX_LENGTH)
                subSeq = input;
            else 
                subSeq = input.substring(input.length() - MAX_LENGTH);

            while( subSeq.length() > 0 ) {
                // 如果字典中含有该子串或者子串颗粒度为1，子串匹配成功
                if( dictionary.contains(subSeq) || subSeq.length() == 1) {
                    store.add(subSeq);
                    // 输入中从后向前去掉已经匹配的子串
                    input = input.substring(0, input.length() - subSeq.length());
                    break;
                } else {
                    // 去掉匹配字段最前面的一个字
                    subSeq = subSeq.substring(1);
                }
            }
        }
        // 输出结果
        int size = store.size();
        for( int i = 0; i < size; i ++) {
            results.add(store.pop());
        }

        return results;
    }
 
    
  
  • 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


双向最大匹配法

分词目标：

将正向最大匹配算法和逆向最大匹配算法进行比较，从而确定正确的分词方法。

算法流程：

  1. 比较正向最大匹配和逆向最大匹配结果
  2. 如果分词数量结果不同，那么取分词数量较少的那个
  3. 如果分词数量结果相同
    • 分词结果相同，可以返回任何一个
    • 分词结果不同，返回单字数比较少的那个


分词实例：

就上例来看，

正向匹配最终切分结果为：北京大学 / 生前 / 来 / 应聘，分词数量为 4，单字数为 1

逆向匹配最终切分结果为：”北京/ 大学生/ 前来 / 应聘，分词数量为 4，单字数为 0

逆向匹配单字数少，因此返回逆向匹配的结果。

双向最大匹配法实现如下：

public List<String> segment() {
        List<String> fmm = this.leftMax();
        List<String> bmm = this.rightMax();

        // 如果分词的结果不同，返回长度较小的
        if( fmm.size() != bmm.size()) {
            if ( fmm.size() > bmm.size())
                return bmm;
            else 
                return bmm;
        }
        // 如果分词的词数相同
        else {
            int fmmSingle = 0, bmmSingle = 0;
            boolean isEqual = true;
            for( int i = 0; i < bmm.size(); i ++) {
                if( !fmm.get(i).equals(bmm.get(i))) {
                    isEqual = false;
                }
                if( fmm.get(i).length() == 1)
                    fmmSingle ++;
                if( bmm.get(i).length() == 1)
                    bmmSingle ++;
            }
            // 如果正向、逆向匹配结果完全相等，返回任意结果
            if ( isEqual ) {
                return fmm;
            // 否则，返回单字数少的匹配方式
            } else if ( fmmSingle > bmmSingle)      
                return bmm;
            else 
                return fmm;     
        }

    }
 
    
  
  • 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


载入字典和自定义添加词

这里的字典文件采用的是

http://download.csdn.net/download/yuanlulu/2380141

载入字典和自定义添加词实现如下：

private static Set<String> dictionary;  
    // 初始化字典，采用 hashset 存储
    public void getDictionary() {
        dictionary = new HashSet<String>();  
        String dicpath = "data/worddict2.txt";  
        String line = null;  

            BufferedReader br;
            try {
                // 按照 gbk 编码读入文件
                br = new BufferedReader(new InputStreamReader(new FileInputStream(dicpath),"gbk"));
                try {
                    while(((line = br.readLine())!=null)) {
                        // 按照空格切分，只读取第二部分
                        String[] str = line.split("\\s+");
                        line = str[1];
                        dictionary.add(line);   
                    }
                    br.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            } catch (UnsupportedEncodingException | FileNotFoundException e) {
                e.printStackTrace();
            }       
    }
    // 自定义添加词汇
    public void addWord(String str) {
        dictionary.add(str);    
    }
 
    
  
  • 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


歧义句测试

可以看到效果还不错，最大匹配法的效果还是取决于字典的质量。

整体代码如下：

package mm;
import java.io.BufferedReader;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.UnsupportedEncodingException; 
public class MMSegment {

    private String request;
    private int MAX_LENGTH = 5;
    private static Set<String> dictionary;  

    public void getDictionary() {
        dictionary = new HashSet<String>();  
        String dicpath = "data/worddict2.txt";  
        String line = null;  

            BufferedReader br;
            try {
                br = new BufferedReader(new InputStreamReader(new FileInputStream(dicpath),"gbk"));
                try {
                    while(((line = br.readLine())!=null)) {
                        String[] str = line.split("\\s+");
                        line = str[1];
                        dictionary.add(line);   
                    }
                    br.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            } catch (UnsupportedEncodingException | FileNotFoundException e) {
                e.printStackTrace();
            }       
    }

    public void addWord(String str) {
        dictionary.add(str);    
    }

    public List<String> leftMax() {

        List<String> results = new ArrayList<String>();
        String input = request;

        while( input.length() > 0 ) {

            String subSeq;
            if( input.length() < MAX_LENGTH) 
                subSeq = input;
            else
                subSeq = input.substring(0, MAX_LENGTH);

            while( subSeq.length() > 0 ) {
                if( dictionary.contains(subSeq) || subSeq.length() == 1) {
                    results.add(subSeq);
                    input = input.substring(subSeq.length());
                    break;  
                } else {
                    subSeq = subSeq.substring(0, subSeq.length() - 1);
                }   
            }

        }
        return results;
    }
    public List<String> rightMax() {

        Stack<String> store=new Stack<String>();
        List<String> results = new ArrayList<String>();
        String input = request;

        while( input.length() > 0 ) {

            String subSeq;
            if( input.length() < MAX_LENGTH)
                subSeq = input;
            else 
                subSeq = input.substring(input.length() - MAX_LENGTH);

            while( subSeq.length() > 0 ) {
                if( dictionary.contains(subSeq) || subSeq.length() == 1) {
                    store.add(subSeq);
                    input = input.substring(0, input.length() - subSeq.length());
                    break;
                } else {
                    subSeq = subSeq.substring(1);
                }
            }
        }
        int size = store.size();
        for( int i = 0; i < size; i ++) {
            results.add(store.pop());
        }

        return results;
    }

    public List<String> segment() {
        List<String> fmm = this.leftMax();
        List<String> bmm = this.rightMax();

        if( fmm.size() != bmm.size()) {
            if ( fmm.size() > bmm.size())
                return bmm;
            else 
                return fmm;
        }

        else {
            int fmmSingle = 0, bmmSingle = 0;
            boolean isEqual = true;
            for( int i = 0; i < bmm.size(); i ++) {
                if( !fmm.get(i).equals(bmm.get(i))) {
                    isEqual = false;
                }
                if( fmm.get(i).length() == 1)
                    fmmSingle ++;
                if( bmm.get(i).length() == 1)
                    bmmSingle ++;
            }

            if ( isEqual ) {
                return fmm;
            } else if ( fmmSingle > bmmSingle)      
                return bmm;
            else 
                return fmm; 
        }
    }

    public void test(String str) {
        request = str;
        System.out.println(this.segment());
    }

    public static void main(String[] args) {
        MMSegment f = new MMSegment();
        f.getDictionary();
        f.test("研究生命科学");
        f.test("研究生命令本科生");
        f.test("我从马上下来");
        f.test("北京大学生喝进口红酒");
        f.test("美军中将竟公然说");
        f.test("阿美首脑会议将讨论巴以和平等问题");
        f.addWord("巴以和平");
        System.out.println("---------------------------");
        System.out.println("向字典中添加'巴以和平'后");
        f.test("阿美首脑会议将讨论巴以和平等问题");
        f.test("我不想吃东西");
    }

}

 
    
  
  • 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

参考资料

[1] http://blog.csdn.net/worldwindjp/article/details/18085725

[2] http://blog.csdn.net/hu948162999/article/details/43608107

[3] http://blog.csdn.net/xiaoyeyopulei/article/details/25194021

[4] http://blog.csdn.net/chenlei0630/article/details/40710441

全部评论

相关推荐

11-27 15:27
北京交通大学 商家运营
运营“偷感很重”
啊啊啊我现在……&nbsp;一边在工位上明目张胆地刷小红书……&nbsp;一边轻轻地奔溃了……&nbsp;为什么，我的工作看起来这么像摸鱼啊！！&nbsp;作为运营我的工作内容之一是发小红书，&nbsp;而发小红书要有网感，&nbsp;于是为了培养网感，&nbsp;我开始沉默地在工位上划起了小红书。。&nbsp;为了表现我正在努力加速成长，&nbsp;我拿出了3台设备，平板、电脑和手机，&nbsp;开始沉默且眼花缭乱地三管齐下划小红书。。&nbsp;但是突然我觉得很不对劲，&nbsp;好像我越努力，&nbsp;看起来就越猖狂。。。&nbsp;救，到底要怎样才能让我看起来偷感不那么重啊！！！&nbsp;我真在上班！&nbsp;我真在上班。吗？
投递小红书等公司10个岗位 >
点赞 评论 收藏
分享
10-13 17:47
门头沟学院 Java
小公司0-20人的Java开发招聘
我感觉我说的没毛病😂😂😂
wulala.god：图一那个善我面过，老板网上找的题库面的
点赞 评论 收藏
分享
11-27 19:08
已编辑
门头沟学院 嵌入式工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
240554次浏览 2050人参与
# 实习，投递多份简历没人回复怎么办 #
2447299次浏览 34795人参与
# 北方华创开奖 #
67947次浏览 558人参与
# 25届秋招总结 #
424762次浏览 4292人参与
# 虾皮求职进展汇总 #
100359次浏览 809人参与
# 地方国企笔面经互助 #
7360次浏览 18人参与
# 阿里云管培生offer #
65323次浏览 1766人参与
# ai智能作图 #
35306次浏览 434人参与
# 中兴求职进展汇总 #
470961次浏览 2453人参与
# 我在牛爱网找对象 #
75228次浏览 556人参与
# 双非有机会进大厂吗 #
106138次浏览 1333人参与
# 实习想申请秋招offer，能不能argue薪资 #
37946次浏览 313人参与
# 机械求职避坑tips #
24196次浏览 252人参与
# 发工资后，你做的第一件事是什么 #
10523次浏览 52人参与
# 25届机械人为了秋招做了哪些准备？ #
26796次浏览 366人参与
# 投格力的你，拿到offer了吗？ #
47861次浏览 337人参与
# 我的实习求职记录 #
6143990次浏览 84084人参与
# 投递实习岗位前的准备 #
1193561次浏览 18510人参与
# 机械人怎么评价今年的华为 #
158436次浏览 1354人参与
# 在职场上，你最讨厌什么样的同事 #
6474次浏览 96人参与
# 实习与准备秋招该如何平衡 #
725890次浏览 8568人参与
# 华为工作体验 #
112459次浏览 871人参与
牛客网
牛客企业服务