NLP-基础任务-中文分词算法(1)-基于词典：机械分词（词典字符串匹配）：前向最大匹配、后向最大匹配、双向最大匹配【OOV：基于现有词典，不能进行新词发现处理】

墨蓝 2023-10-01 16:42 48阅读 0赞

分词与NLP关系：分词是中文自然语言处理的基础，没有中文分词，我们对语言很难量化，进而很能运用数学的知识去解决问题。对于拉丁语系是不需要分词的。

拉丁语系与亚系语言区别

*  拉丁语言系不需要分词，因为他们的词语之间有空格分割，可以根据空格就可以把单词分开。比如英语、法语等。
 *  亚系语言中间没有空格，比如中文、韩文及日文等。因此需要  
    分词。

什么是中文分词：中文分词(Chinese Word Segmentation) 指的是将一个汉字序 列切分成一个一个单独的词。分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。

**任何分词算法都是基于已有词典库来对一句话进行分词。**

## 一、前向最大匹配算法 ##

正向最大匹配法，对于输入的一段文本从左至右、以贪心的方式切分出当前位置上长度最大的词。正向最大匹配法是基于词典的分词方法，其分词原理是：单词的颗粒度越大，所能表示的含义越确切。

该算法主要分两个步骤：

1.  一般从一个字符串的开始位置，选择一个最大长度的词长的片段，如果序列不足最大词长，则选择全部序列。
2.  首先看该片段是否在词典中，如果是，则算为一个分出来的词，如果不是，则从右边开始，减少一个字符，然后看短一点的这个片段是否在词典中，依次循环，逐到只剩下一个字。
3.  序列变为第2步骤截取分词后，剩下的部分序列

例子：“南京市长江大桥”  
词典：\[“南京”,“市长”,“大桥”,“长江”,“江”,“市”\]

前向最大匹配的前向意思是说，从前往后匹配。最大意思是说，我们匹配的词的长度越大越好，也就是这句话中分出来的词的数量越少越好。

这里，我们假设这个最大长度max\_len = 5:

第一轮搜索：  
①"`南京市长江`大桥" ，词典中没有`南京市长江`这个词，匹配失败  
②"`南京市长`江大桥" ， 词典中没有`南京市长`这个词，匹配失败  
③"`南京市`长江大桥" ， 词典中没有`南京市`这个词，匹配失败  
④"`南京`市长江大桥" ， 词典中有`南京`这个词，匹配成功，去除  
句子变为：“市长江大桥”

第二轮搜索：  
①"`市长江大桥`" ，词典中没有`市长江大桥`这个词，匹配失败  
②"`市长江大`桥" ，词典中没有`市长江大`这个词，匹配失败  
③"`市长江`大桥" ， 词典中没有`市长江`这个词，匹配失败  
④"`市长`江大桥" ，词典中有`市长`这个词，匹配成功，去除  
句子变为：“江大桥”

第三轮搜索（句子长度已不足5，将max\_len改为3）：  
①"`江大桥`" ，词典中没有`江大桥`这个词，匹配失败  
②"`江大`桥" ，词典中没有`江大`这个词，匹配失败  
③"`江`大桥" ，词典中有`江`这个词，匹配成功，去除  
句子变为：“大桥”

第四轮搜索：  
①"大桥" ，词典中有`大桥`这个词，匹配成功，去除  
句子变为：""，说明已经处理完毕

最终结果：“南京 / 市长 / 江 / 大桥”

这个结果虽然勉强可以接受，可以认为它说的意思是，南京的市长名字叫江大桥，但是明显跟我们想要表达的或者想要理解的意思不一样，这就有了分词的歧义问题。

如果我们的词典里有南京市这个词，那么结果就是"南京市/长江/大桥"。

dictionaries = ["南京", "市长", "大桥", "长江", "江", "市"]
    
    
    # 前向最大匹配
    def forward_max_matching(text, max_len=5):
        result = []
        text_ = text
        index = max_len
        while len(text_) > 0:
            if index == 0:
                print("分词失败，词典中没有这个词")
                return []
            if text_[:index] in dictionaries:
                result.append(text_[:index])
                text_ = text_[index:]
                index = 5
            else:
                index = index - 1
        return "".join(word + "/" for word in result)

#!/usr/bin/python
    # -*- coding: UTF-8 -*-
    
    #实现正向匹配算法中的切词方法
    def cut_words(raw_sentence,words_dic):
        #统计词典中最长的词
        max_length = max(len(word) for word in words_dic)
        sentence = raw_sentence.strip()
        #统计序列长度
        words_length = len(sentence)
        #存储切分好的词语
        cut_word_list = []
        while words_length > 0:
            max_cut_length = min(max_length, words_length)
            subSentence = sentence[0 : max_cut_length]
            while max_cut_length > 0:
                if subSentence in words_dic:
                    cut_word_list.append(subSentence)
                    break
                elif max_cut_length == 1:
                    cut_word_list.append(subSentence)
                    break
                else:
                    max_cut_length = max_cut_length -1
                    subSentence = subSentence[0:max_cut_length]
            sentence = sentence[max_cut_length:]
            words_length = words_length - max_cut_length
        #words = "/".join(cut_word_list)
        return cut_word_list

## 二、后向最大匹配算法 ##

后向最大匹配的后向意思是说，从后往前匹配。最大意思同样是说，我们匹配的词的长度越大越好。

例子：“南京市长江大桥”  
词典：\[“南京”,“市长”,“大桥”,“长江”,“江”,“市”\]

这里，我们同样假设这个最大长度max\_len = 5:

第一轮搜索：  
①"南京`市长江大桥` " 词典中没有`市长江大桥`这个词，匹配失败  
②"南京市`长江大桥` " 词典中没有`长江大桥`这个词，匹配失败  
③"南京市长`江大桥` " 词典中没有`江大桥`这个词，匹配失败  
④"南京市长江`大桥` " 词典中有`大桥`这个词，匹配成功，去除  
句子变为：“南京市长江”

第二轮搜索：  
①"`南京市长江` " 词典中没有`南京市长江`这个词，匹配失败  
②"南`京市长江` " 词典中没有`京市长江`这个词，匹配失败  
③"南京`市长江` " 词典中没有`市长江`这个词，匹配失败  
④"南京市`长江` " 词典中有`长江`这个词，匹配成功，去除  
句子变为：“南京市”

第三轮搜索（句子长度已不足5，将max\_len改为3）：  
①"`南京市` " 词典中没有`南京市`这个词，匹配失败  
②"南`京市` " 词典中没有`京市`这个词，匹配失败  
③"南京`市` " 词典中有`市`这个词，匹配成功，去除  
句子变为：“南京”

第四轮搜索：  
①"`南京` " 词典中有`南京`这个词，匹配成功，去除  
句子变为：""，说明已经处理完毕

最终结果：“南京 / 市 / 长江 / 大桥”

相同的话，相同的词典，分出来的效果却不一样，导致了歧义问题。

*  前向最大匹配与后向最大匹配 90%的几率分出来的结果一样。
 *  统计结果表明，单纯使用后向最大匹配算法的错误率略低于正向最大匹配算法。

#!/usr/bin/python
    # -*- coding: UTF-8 -*-
    #Author bruce
    
    #实现逆向最大匹配算法中的切词方法
    def cut_words(raw_sentence,words_dic):
        #统计词典中词的最长长度
        max_length = max(len(word) for word in words_dic)
        sentence = raw_sentence.strip()
        #统计序列长度
        words_length = len(sentence)
        #存储切分出来的词语
        cut_word_list = []
        #判断是否需要继续切词
        while words_length > 0:
            max_cut_length = min(max_length, words_length)
            subSentence = sentence[-max_cut_length:]
            while max_cut_length > 0:
                if subSentence in words_dic:
                    cut_word_list.append(subSentence)
                    break
                elif max_cut_length == 1:
                    cut_word_list.append(subSentence)
                    break
                else:
                    max_cut_length = max_cut_length -1
                    subSentence = subSentence[-max_cut_length:]
            sentence = sentence[0:-max_cut_length]
            words_length = words_length -max_cut_length
        cut_word_list.reverse()
        #words = "/".join(cut_word_list)
        return  cut_word_list

# -*- coding: utf-8 -*-
    dictionaries = ["南京", "市长", "大桥", "长江", "江", "市"]
    
    
    # 前向最大匹配
    def forward_max_matching(text, max_len=5):
        result = []
        text_ = text
        index = max_len
        while len(text_) > 0:
            if index == 0:
                print("分词失败，词典中没有这个词")
                return []
            if text_[:index] in dictionaries:
                result.append(text_[:index])
                text_ = text_[index:]
                index = 5
            else:
                index = index - 1
        return "".join(word + "/" for word in result)
    
    
    # 后向最大匹配
    def backward_max_matching(text, max_len=5):
        result = []
        text_ = text
        index = max_len
        while len(text_) > 0:
            if index == 0:
                print("分词失败，词典中没有这个词")
                return []
            # print(text_[-index:])
            if text_[-index:] in dictionaries:
                result.insert(0, text_[-index:])
                # result.append(text_[-index:])
                text_ = text_[:-index]
                index = 5
            else:
                index = index - 1
        return "".join(word + "/" for word in result)
    
    
    if __name__ == '__main__':
        content = "南京市长江大桥"
        forward_result = forward_max_matching(content)
        print("forward_result:", forward_result)
        backward_result = backward_max_matching(content)
        print("backward_result:", backward_result)

打印结果：

forward_result: 南京/市长/江/大桥/
    backward_result: 南京/市/长江/大桥/

## 三、双向最大匹配算法 ##

双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，从而决定正确的分词方法。

据SunM.S. 和 Benjamin K.T.（1995）的研究表明：

*  中文中90.0％左右的句子， 正向最大匹配法和逆向最大匹配法完全重合且正确，
 *  只有大概9.0％的句子两种切分方法得到的结果不一样，但其中必有一个是正确的（歧义检测成功），
 *  只有不到1.0％的句子，或者正向最大匹配法和逆向最大匹配法的切分虽重合却是错的，或者正向最大匹配法和逆向最大匹配法切分不同但两个都不对（歧义检测失败）。

**这正是双向最大匹配法在实用中文信息处理系统中得以广泛使用的原因所在。**

启发式规则：

*  如果正反向分词结果词数不同，则取分词数量较少的那个。
 *  如果分词结果词数相同：
    
     *  分词结果相同，就说明没有歧义，可返回任意一个。
     *  分词结果不同，返回其中单字较少的那个。

#!/usr/bin/python
    # -*- coding: UTF-8 -*-
    
    import FMM
    import BMM
    
    #使用双向最大匹配算法实现中文分词
    words_dic = []
    
    def init():
        """
        读取词典文件
        载入词典
        :return:
        """
        with open("dic/dic.txt","r", encoding="utf8") as dic_input:
            for word in dic_input:
                words_dic.append(word.strip())
    
    #实现双向匹配算法中的切词方法
    def cut_words(raw_sentence,words_dic):
        bmm_word_list = BMM.cut_words(raw_sentence,words_dic)
        fmm_word_list = FMM.cut_words(raw_sentence,words_dic)
        bmm_word_list_size = len(bmm_word_list)
        fmm_word_list_size = len(fmm_word_list)
        if bmm_word_list_size != fmm_word_list_size:
            if bmm_word_list_size < fmm_word_list_size:
                return bmm_word_list
            else:
                return fmm_word_list
        else:
            FSingle = 0
            BSingle = 0
            isSame = True
            for i in range(len(fmm_word_list)):
                if fmm_word_list[i] not in bmm_word_list:
                    isSame = False
                if len(fmm_word_list[i])  == 1:
                    FSingle = FSingle + 1
                if len(bmm_word_list[i]) == 1:
                    BSingle = BSingle + 1
            if isSame:
                return fmm_word_list
            elif BSingle > FSingle:
                return fmm_word_list
            else:
                return bmm_word_list
    
    
    def main():
        """
        于用户交互接口
        :return:
        """
        init()
        while True:
            print("请输入您要分词的序列")
            input_str = input()
            if not input_str:
                break
            result = cut_words(input_str,words_dic)
            print("分词结果")
            print(result)
    
    if __name__ == "__main__":
        main()

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

参考资料：