双向最大匹配算法思想详解，分词器及全文检索工具及Lucene框架简介_双向匹配

一、中文分词理论描述

前言
这篇将使用Java实现基于规则的中文分词算法，一个中文词典将实现准确率高达85%的分词结果。使用经典算法：正向最大匹配和反向最大匹配算法，然后双剑合璧，双向最大匹配。

根据相关资料，中文分词概念的理论描述，我总结如下：

中文分词是将一个汉字序列切分成一个一个单独的词，将连续的字序列按照一定的规范重新组合成词序列的过程，把字与字连在一起的汉语句子分成若干个相互独立、完整、正确的单词，词是最小的、能独立活动的、有意义的语言成分。

中文分词应用广泛，是文本挖掘的基础，在中文文本处理中意义重大，对于输入的一段中文，成功的进行中文分词，可以达到电脑自动识别语句含义的效果。目前，常用流行的以及分次效果好的工具库包括：jieba、HanLP、LTP、FudanNLP等。

二、算法描述

1、正向最大匹配算法

所谓正向，就是从文本串左边正向扫描，取出子串与词典进行匹配。

算法思想描述：

• 假设初始化取最大匹配长度为MaxLen，当前位置startPosition=0，处理结果result，每次取词subStr，取词长度len，待处理串srcStr。

• len = MaxLen，取字符串0到len的子串，查找词典，若匹配到则赋值加到result，在保证 pos + len <= segstr.length() 情况下，pos = pos + len，向后匹配，直到字符串扫描完成，结束算法。

• 若词典未找到 且 len>1，减小匹配长度len -= 1【减小匹配长度的步长可以根据实际场景进行设置】，继续进行匹配，否则，取出剩余子串，执行匹配流程。

正向最大匹配算法代码如下：

	public static void main(String[] args){
        
        String result = MM("我爱自然语言处理", MaxLen, 0);
        System.out.println("分词结果：" + result);
    }

    private static final int MaxLen = 5; // 最大词长度
    private static StringBuffer result = new StringBuffer(); // 分词结果
    private static Map<String, String> dict = new HashMap<>(); // 词典
	
	// 模拟词典数据
    static{
        dict.put("我", "");
        dict.put("爱", "");
        dict.put("自然", "");
        dict.put("语言", "");
        dict.put("处理", "");
    }

    public static String MM(String srcStr, int len, int startPosition) {
        // 越界判断
        if (startPosition + 1 > srcStr.length()) {
            return result.toString();
        }
        if (startPosition < 0) {
            return result.toString();
        }
        String subStr = "";
        //此处可以设置断点
        int llen = srcStr.length() - startPosition;
        if (llen <= len) {//句末边界处理
            subStr = srcStr.substring(startPosition, startPosition + llen);
        } else {
            subStr = srcStr.substring(startPosition, startPosition + len);
        }

        if (dict.containsKey(subStr)) {
            result.append(subStr).append("/ ");
            len = MaxLen;
            MM(srcStr, len, startPosition + subStr.length());
        } else {
            if (len > 1) {
                len -= 1;
            } else {
                result.append(srcStr).append("/ ");
                startPosition = startPosition + 1;
                len = MaxLen;
            }
            MM(srcStr, len, startPosition);
        }

        return result.toString();
    }
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

从算法代码看出，很容易理解，细节部分在于边界处理。

运行结果：

2、反向最大匹配算法

反向，则与正向相反，从文本串末向左进行扫描。

算法思想描述：

• 假设初始化取最大匹配长度为MaxLen，当前位置pos为字符串尾部，处理结果result，每次取词subStr，取词长度len，待处理串srcStr。

• len=MaxLen，取字符串pos-len到pos的子串，查找词典，若匹配到则赋值加到result，同时pos=pos-len，保证pos-len>=0，向前移动匹配，直到字符串扫描完成，结束算法。

• 若词典未找到，若len>1，减小匹配长度，执行分词匹配，否则，取出剩余子串,执行步分词匹配。
  算法逻辑与正向最大匹配算法类似，取相反方向处理。

代码实现

private static final int MaxLen = 5; // 最大词长度
    private static StringBuffer result = new StringBuffer(); // 分词结果
    private static Map<String, String> dict = new HashMap<>(); // 词典

    static {
        dict.put("我", "");
        dict.put("爱", "");
        dict.put("自然", "");
        dict.put("语言", "");
        dict.put("处理", "");
    }

    public static void main(String[] args){
        String rres = RMM("我爱自然语言处理", MaxLen, 7);
        System.out.println("反向分词结果：" + rres);
    }

    public static String RMM(String srcStr, int len, int startPosition) {
        if (startPosition < 0)
            return result.toString();
        if (startPosition > srcStr.length() + 1) {
            return result.toString();
        }
        String subStr = "";
        //此处可以设置断点
        if (startPosition - len + 1 >= 0)//句末边界处理
            subStr = srcStr.substring(startPosition - len + 1, startPosition + 1);//substring获取的子串是下标frompos~frompos+llen-1
        else
            subStr = srcStr.substring(0, startPosition + 1);//到达句首

        if (dict.containsKey(subStr)) {
            result.insert(0, subStr + "/ ");
            len = MaxLen;
            RMM(srcStr, len, startPosition - subStr.length());
        } else {
            if (len > 1) {
                len = len - 1;
            } else {
                result.insert(0, srcStr + "/ ");
                startPosition = startPosition - 1;
                len = MaxLen;
            }
            RMM(srcStr, len, startPosition);
        }

        return result.toString();
    }
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

执行结果：

3、双向匹配分词算法

这里所说的是正向与反向结合，实现双向最大匹配。
双向最大匹配算法，基于正向、反向最大匹配，对分词结果进一步处理，比较两个结果，做的工作就是遵循某些原则和经验，筛选出两者中更确切地分词结果。

原则如下：

1. 多数情况下，反向最大匹配效果更好，若分词结果相同，则返回RMM结果；
2. 遵循切分最少词原则，更大匹配词为更好地分词结果，比较之后返回最少词的切分结果；
3. 根据切分后词长度的大小，选择词长度大者为最终结果。

具体也需要看开始给定的最大匹配长度为多少。以下代码只实现了原则1、2。

代码示例：

// 这里只是示例代码，思路比较简单
public String BMM() {
        String Mr = MM("我爱自然语言处理", MaxLen, 0);
        String RMr = RMM("我爱自然语言处理", MaxLen, 7);
        if (Mr.equals(RMr)) {
            return "双向匹配相同，结果为：" + Mr;
        } else {
            List<String> MStr;
            List<String> RStr;
            MStr = Arrays.asList(Mr.trim().split("/"));
            RStr = Arrays.asList(RMr.trim().split("/"));

            if (MStr.size() >= RStr.size()) {//多数情况下，反向匹配正确率更高
                return "双向匹配不同，最佳结果为：" + RMr;
            } else
                return "双向匹配不同，最佳结果为：" + Mr;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、示例总结

下面举例，以便更好的理解算法执行过程。

• 正向最大匹配算法：

取MaxLen=3，SegStr=”对外经济技术合作与交流不断扩大”,maxNum=3,len=3,result=””,pos=0,curstr=””.

• 第一次，curstr=”对外经”，查找词典，未找到，将len-1，得到curstr=”对外”，此时匹配到词典，将结果加入result=”对外/”.pos=pos+len.

• 第二次，curstr=”经济技”，查找词典，未找到，将len-1，得到curstr=”经济”，此时匹配到词典，将结果加入result=”对外/ 经济/ ”.pos=pos+len.

• 以此类推…

• 最后一次，边界，pos=13，因为只剩下”扩大”两个字，所以取出全部，查找词典并匹配到，将结果加入result=”对外/ 经济/ 技术/合作/ 与/ 交流/ 不断/ 扩大/ ”.此时pos+1>SegStr.length(),结束算法。

• 反向最大匹配算法：

取MaxLen=3，SegStr=”对外经济技术合作与交流不断扩大”,maxNum=3,len=3,result=””,pos=14,curstr=””.

• 第一次，curstr=”断扩大”，查找词典，未找到，将len-1，得到curstr=”扩大”，此时匹配到词典，将结果加入result=”扩大/
  ”.pos=pos-len.

• 第二次，MaxLen=3，curstr=”流不断”，查找词典，未找到，将len-1，得到curstr=”不断”，此时匹配到词典，将结果加入result=”不断/ 扩大/ ”.pos=pos-len.

• 以此类推…

• 最后一次，边界，pos=1，因为只剩下”对外”两个字，所以取出全部，查找词典并匹配到，将结果加入result=”对外/ 经济/ 技术/ 合作/ 与/ 交流/ 不断/ 扩大/ ”.此时pos-1<0,结束算法。

四、市面上的分词器及字典

首先，分词的算法大致分为两种：

1.基于词典的分词算法

正向最大匹配算法

逆向最大匹配算法

双向匹配分词法

2.基于统计的机器学习算法

HMM、CRF、SVM、LSTM+CRF

这里列出一些开源的分词系统【分词器】：

• 语义分析系统 NLPchina/ansj_segHIT-SCIR/ltp清华大学

• The Stanford Natural Language Processing GroupHanlp分词器

• yanyiwu/cppjiebakoth/kcws

• frcchang/zpar

• wks/ik-analyzer

• 盘古分词、结巴分词、海量分词、Lucene、Solr等等

分词算法实现，不可缺少的就是词典，这里给大家推荐几个词典源。

• 清华大学开放中文词库
• 搜狗标准词库
• 百度中文分词词库
• 海量分词

我个人对Lucene 框架还是比较喜欢的，开源软件DocFetcher也是基于此框架实现的全文检索工具。值得推荐。只是目前DocFetcher使用的还是Lucene6，目前Lucene已经是版本8了，所以就将DocFetcher升级了一下，由于DocFetcher的开源协议是EPL，所以就不方便给大家提供修改后的源码和编译出的工具了。见谅。
不过倒是可以给大家一些修改建议：

• 使用Lucene8，项目中需要使用 lucene-backward-codecs.jar；以支持低版本的索引文件的使用和更新。
• DocFetcher的默认分词器及分词器的使用及分词器的停止词设置还不够完善，需要大家自己添加和设置。比如：DocFetcher代码中提供的几种分词器并没有通过UI的方式展示出来供大家选择，所以，如果有想法的同学可以试试看，对比一下不同分词器的实现方式和原理，及其可扩展情况。
• 由于中英文分词的区别比较大，及中文情况下的模糊匹配相对比较复杂，建议大家可以在创建索引和使用索引【搜索】时，使用不同的分词器来实现分词功能。这样会比较复合大家的预期。比如：对‘苹果手机’这个词语，如果默认使用DocFetcher的分词（中文没有分词效果，按字创建的索引，不是按词），所以在模糊搜索的时候，其实是没有什么技术可言的。而当我们期望实现搜索‘苹果’这个词的时候，‘苹果手机’也需要成为高亮的匹配项，就需要我们使用不同的分词器来实现创建索引和搜索。

到此结束，谢谢观看~

注：双向匹配部分借鉴了目前别的博主写的内容，本人就是简单整理了一下，让代码可以真正的运行起来。方便大家直接运行调试，分析总结。