基于词典的正向匹配算法

今天教大家写个简单的中文分词器。使用中文分词器，我们能将一段文字拆分成一个一个的关键词。在写出这个中文分词器之前，薯条老师先介绍一个基于词典的正向匹配算法。一步步地理解这个算法，然后将算法用文字进行描述，最后将文字描述通过Python代码进行实现。熟悉的概念分解大法又来了，先将复杂的概念进行分解：

(1) 基于词典

所谓基于词典，是指根据词典里面的关键词来进行分词，即分出来的词只能出现于词典中，笔者举个例子：

# 定义词典集合
dictionary = {"中国", "人"}

在上文代码中定义了词典集合dictionary, 那么分词的时候就是根据词典集合中的关键词来进行分词。比如将"我是中国人"进行分词，由于词典中只有"中国"和"人"，所以文本只能被分成"中国"和"人"。怎么把"我"分出来呢？很简单，把"我"加入dictionary这个集合中即可。

# 定义词典集合
dictionary = {"中国", "人","我"}

(2) 正向匹配

所谓正向是指在文本中按从左到右的顺序，根据最大的分词宽度进行分词，这里的最大分词宽度是词典中长度最长的词语的长度。

匹配是指将上一步分词的结果与词典中的词进行匹配。

若匹配成功，则以词的结束位置作为起始位置，继续进行分词匹配。

若匹配失败，则将分词的最大宽度减一，分词的起始位置不变，继续进行正向匹配，直到分词的长度为0。

分词的最大宽度为0以后，将起始位置向前移动一个位置，重复进行上述的分词步骤。

下图表示对"年仅13岁的天才童星克罗兹"使用正向匹配算法进行分词，最大分词宽度为5：

假设词典中的关键词为{"正义", "天使"}。由于最大分词宽度为5，所以先正向匹配长度为5的字符串"年仅13岁"，匹配失败后再继续正向匹配长度为4的字符串"年仅13"，不断重复这样的过程，直到分词宽度为0。分词宽度为0以后，将分词的起始位置向前移动一个位置，继续以最大分词宽度5来进行匹配。

分词算法实现

现在通过基于词典的正向匹配算法来将描述超杀女的一段话进行分词:

# __filename__ = hit_girl.py
# __author__ = 薯条老师

# 定义CONTENT变量，内容引用自百度百科，在代码中会将这段描述进行分词
CONTENT = '''
在《海扁王》中，年仅13岁的天才童星科洛·莫瑞兹扮演的血腥暴力"超杀女"是个擅长使用各种兵器的11岁小女孩，
从小接受父亲"大老爸"的近身枪击（当然有穿防弹衣）、徒手战斗、刀械枪支等训练，加上"大老爸"带着她四处打击犯罪，
小小年纪便累积不少实战经验，成了杀人不眨眼的顶尖杀手。
她的主要武器是蝴蝶刀与武士刀，以研究各类武器为乐，对枪械更是了若指掌！
'''


# 定义的分词器函数
def cut(text):
    '''
    :param text:待分词的文本
    :return:返回分词列表
    '''
    
    keywords = []
    # 将text变量作为判断条件，如果text为空值，则停止循环
    # 在循环中会不断将text变量进行切片
    while text:
        
        # 执行range函数会生成一个整数序列，
        # 读者可以查阅官方文档，来了解range函数的用法
        # 这里的range函数为生成一个倒排序列，比如6,5,4,3,2,1
        for index in range(THE_MAX_LENGTH_OF_WORD, 0, -1):
            # 对文本按最大宽度进行切片
            keyword = text[:index]
            # 如果切片分出来的词语在词典集合中，就保存到列表words变量中，并且退出for循环
            # 在集合中进行快速查找
            if keyword in DICTIONARY:
                keywords.append(keword)
                text = text[index:]
                break
                
        else:
            """
            (1) 如果匹配失败，则将文本的起始位置向前移动一个位置，重复进行上述的分词步骤
            (2) 不断地对字符串进行分片来实现位置的移动, 更佳的做法是在循环中通过索引来进行控制，这留给读者做课后练习。
            """
            text = text[1:]
 
    return keywords
    
    
 
if __name__ == "__main__":
 
    # 在__main__中定义的变量，在其它函数中可以直接引用
 
    # 定义词典，用来保存分词的词语，读者也可以自行加入其它的词语
    DICTIONARY = {"小女孩","海扁王", "科洛·莫瑞兹",
                  "超杀女", "蝴蝶刀", "武士刀", "枪械",
                  "暴力萝莉","杀人不眨眼"}
                  
    # 词典中最长的词为"科洛·莫瑞兹",长度为6。读者可编写一个函数来计算最大分词宽度
    THE_MAX_LENGTH_OF_WORD = 6
    # 执行cut函数，来对文本进行分词
    keywords = cut(CONTENT)
    print(keywords)

简单搜索引擎

在下节的项目实战中，将使用本节中的中文分词器来实现一个简单的中文搜索引擎。

最具实力的小班培训

(1) Python后端工程师高薪就业班，月薪11K-18K，免费领取课程大纲
(2) Python爬虫工程师高薪就业班，年薪十五万，免费领取课程大纲
(3) Java后端开发工程师高薪就业班，月薪11K-20K, 免费领取课程大纲
(4) Python大数据分析，量化投资就业班，月薪12K-25K,免费领取课程大纲

扫码免费领取学习资料：