分词（Word Segmentation）-最大匹配算法

淡淡的烟草味﹌ 2022-11-25 11:47 155阅读 0赞

**目录**

1.写在前面

2.常用的分词工具

3.分词算法-最大匹配-前向最大匹配（forword-max matching）

3.1 算法思想

3.2 前向匹配代码实现

4.分词算法-最大匹配-后向最大匹配（backward-max matching）

4.1 算法思想

4.2 后向匹配代码实现

5.最大匹配的缺点

--------------------

# 1.写在前面 #

我们上次总结了一个NLP系统中一般有的几个部分，包括分词、清洗数据、标准化、特征提取、建模、评估模型等。这篇文章我们重点总结分词这个部分的知识点。

# 2.常用的分词工具 #

我们最常使用的是jieba分词工具，我们之前对jieba也有一个详尽的介绍：[jieba分词工具的使用-Python代码][jieba_-Python]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70][]

# 3.分词算法-最大匹配-前向最大匹配（forword-max matching） #

之所以研究这个算法，是因为最近在研究NLP中文的分词，所谓分词就是将一个完整的句子，例如“计算语言学课程有意思”，分解成一些词组单元“计算语言学，课程，有，意思”。 “最大匹配法” 在中文分词中有所应用，因此这里介绍一下。

“最大匹配法” 分为前向匹配（正向匹配）和逆向匹配，这里先看前向匹配。

## 3.1 算法思想 ##

正向最大匹配算法依赖于词典匹配，前提条件是语句已经去掉特殊标点符号，并且需要预先设置一个字典，然后根据字典进行匹配。

首先我们可以规定一个词的最大长度（长度设置需要调整，一般5-10个），每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配，如果没有找到，就缩短长度继续寻找，直到找到或者成为单字。如果最后词典没找到变成了单字，那就把单字单独切分，从头开始重新循环下一个最大长度的词组。如果剩余长度不足为最大长度，那就取剩余长度。从左向右扫描寻找词的最大匹配，和字符串匹配算法类似。下面动图设置了词的最大长度为5。

![20200808173724820.gif][]

## 3.2 前向匹配代码实现 ##

1.  对输入的一个中文语句，首先在程序中判断并确保语句中不包含数字或者字母
2.  在句子中的当前位置开始取与词典中最大匹配长度的词作为一个分词段，如果没有在词典中成功匹配到，就将这个单字作为一个分词段，并将匹配位置向后挪一个位置，同时如果剩余长度小于最大长度，那就取剩余的
3.  重复第2步，直到匹配位置移到句末

// 主体代码 java
    public List<String> seg(String text) {
        List<String> result = new ArrayList<>();
        while(text.length() > 0) {
            int len = MAX_LENGTH;
            if (text.length() < len) {
                len = text.length();               
            }
            // 取指定的最大长度的文本去词典里匹配
            String tryWord = text.substring(0, 0 + len);
            while(!DIC.contains(tryWord)) {
                // 如果长度为1 且在词典中为找到匹配， 则按长度为1切分
                if (text.length() == 1) {
                    break;                 
                }
                 
                // 如果找不到，则按长度减1 继续切分
                tryWord = tryWord.substring(0, tryWord.length() - 1 );
                 
            }
            result.add(tryWord);
             
            // 从待分词文本中去除已经分词的文本
            text = text.substring(tryWord.length());           
        }
        return result;
    }

# 4.分词算法-最大匹配-后向最大匹配（backward-max matching） #

## 4.1 算法思想 ##

待分词句子： sentence\[\]=\{"计算语言学课程有意思"\}

词表： dict\[\]=\{"计算", "计算语言学", "课程", "有", "意思"\}

逆向匹配算法大致思路是从右往左开始切分。首先我们定义一个最大分割长度5，从右往左开始分割：

*  (1) 首先取出来的候选词W是 “课程有意思”。
 *  (2) 查词表，W不在词表中，将W最左边的第一个字去掉，得到W“程有意思”；
 *  (3) 查词表，W也不在词表中，将W最左边的第一个字去掉，得到W“有意思”；
 *  (4) 查词表，W也不在词表中，将W最左边的第一个字再去掉，得到W“意思”；
 *  (5) 查词表，W在词表中，就将W从整个句子中拆分出来，此时原句子为“计算语言学课程有”
 *  (6) 根据分割长度5，截取句子内容，得到候选句W是“语言学课程有”；
 *  (7) 查词表，W不在词表中，将W最左边的第一个字去掉，得到W“言学课程有”；
 *  (8) 查词表，W也不在词表中，将W最左边的第一个字去掉，得到W“学课程有”；
 *  (9) 依次类推，直到W为“有”一个词的时候，这时候将W从整个句子中拆分出来，此时句子为“计算语言学课程”
 *  (10) 根据分割长度5，截取句子内容，得到候选句W是“算语言学课程”；
 *  (11) 查词表，W不在词表中，将W最左边的第一个字去掉，得到W“语言学课程”；
 *  (12) 依次类推，直到W为“课程”的时候，这时候将W从整个句子中拆分出来，此时句子为“计算语言学”
 *  (13) 根据分割长度5，截取句子内容，得到候选句W是“计算语言学”；
 *  (14)  查词表，W在词表，分割结束。

## 4.2 后向匹配代码实现 ##

#include<iostream>
    #include<string>
    using namespace std;
    
    // 宏，计算数组个数
    #define GET_ARRAY_LEN(array,len){len=(sizeof(array)/sizeof(array[0]));}
    
    // 定义最大词长
    #define MAX_WORD_LENGTH 5
    
    string dict[] = {"计算", "计算语言学", "课程", "意思"};
    
    // 是否为词表中的词
    bool inDict(string str)
    {
        bool res = false;
        int i;
        int len = 0;
        
        GET_ARRAY_LEN(dict, len);
    
        for (i = 0; i<len; i++)
        {
            if( str == dict[i]) 
            {
                res = true;
            }
        }
        return res;
    }
    
    
    int main()
    {
        string sentence = "计算语言学课程有意思";
        string word = "一";
        int wordlen = word.length();
        
        int i;
        
        for (i = 0; i<sentence.length(); )
        {
            int dealstrbegin = sentence.length()-wordlen*MAX_WORD_LENGTH-i;
            int dealstrlen = wordlen*MAX_WORD_LENGTH;
            // 截取的要处理的字符串
            string dealstr = sentence.substr(dealstrbegin, dealstrlen);
    
            int j;
            for (j = 0; j<MAX_WORD_LENGTH; j++)
            {
                int fb = j*wordlen;
                int fl = wordlen*(MAX_WORD_LENGTH-j);
                // 去掉签名的j个字
                string tmp = dealstr.substr(fb, fl);
    
                if(inDict(tmp) || j==MAX_WORD_LENGTH-1 )
                {
                    cout<<"分词结果："<<tmp<<endl;
                    i=i+fl;
                    break;
                }
            }
        }
    }

# 5.最大匹配的缺点 #

*  1.不能细分，细分有可能是更好的，
 *  2.局部最优解
 *  3.效率非常低，效率依赖于maxLen
 *  4.歧义，不能考虑语义，只能看到单词这个层面word lever（后面有句子句法分析Syntactic analysis，语义分析semantic analysis等层次）

[jieba_-Python]: https://blog.csdn.net/Suyebiubiu/article/details/80466456
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70]: /images/20221124/d8907436c0be4b058b22b66d6733a1f3.png
[20200808173724820.gif]: /images/20221124/ade227b417384ea2bd90cb503ee82198.png