中文分词的算法分析

前言

起因是一次电话面试，面一个技术比较好的公司，我认为自己玩Elasticsearch还是比较久了，还是能交锋几个回合吧，结果人家一问，中文分词的算法，你有了解吗？

纳尼？中文分词，不就是调一下中文分词器做index嘛，我说了调用IK分词器，人家让我说一下中文分词的算法，或者你有没有了解过，我只有老实的说，我没。

后来当然是有点凉，我觉得我需要去详细看一下这方面的东西。所以这两天除了看房子，我也具体看了一下Elasticsearch和其他的，例如tika，fscrawler之类的分词逻辑，加上网上的一些资料，还是有一些收获，这里做个记录，也是未来的博客文章从基础转向高级的一个转折点吧。

分词是什么？什么是分词？它能干嘛？

首先三连，这个我认为比较基础，简单的说，在我们搭建检索引擎或者设计搜索的时候，为了方便能更加简便的搜索出我们想要的东西，首先听一个术语，叫做分词粒度，例如，我们搜索 “我是吴彦祖”，下面是不同的粒度的分析划分。

1. 我，是，吴彦祖 最细粒度
2. 我是，吴彦祖 正常粒度
3. 我，我是，我是吴，吴彦祖，是吴彦祖 混合粒度

你可以看见，不同的分词效果，带来的分词结果不同，举个例子，我们如果根据正常粒度，搜索 “我”，这时就搜索不出来，但是根据混合粒度，我们搜索 “我”，就能得到 “我是吴彦祖” 的搜索结果，所以，良好的分词，是增加搜索效率和搜索结果的重要因素，同理，分词也是一个搜索引擎的老大部分，这次咱们不说屁股的事儿，咱们光说中文，中文的分词算法组成到底有哪些，您往下看。

中文分词的几个算法解析

根据我查询的一些资料，和阅读一些技术文档，我总结出了如下几个搜索算法

词典类分词法

这个大类其实比较好理解，现在大部分的搜索引擎都是根据中文字典作为分词的方法，它首先是基于中文字典，然后根据算法做分词，具体的算法如下

最大匹配算法（Maximum Matching）

这里分为两种，一种是正向最大匹配，一种是逆向最大匹配，这里我主要说一下正向最大匹配方法，下面我都用MM来代替算法名，后面也都一样。

正向最大匹配算法

MM正向算法的原理，其实就是将等待分词的文本和字典进行匹配，遵循的是从左往右匹配的原则，如果匹配上了，切分出一个词汇，举个简单的例子

# 等待分词的列表
wait_seg_word = ["我","是","吴","彦","祖"]
# 词典
word_dicts ={"我是", "吴彦祖", "我", "是吴彦祖", "彦祖"}

首先从wait_seg_word开始扫描

wait_seg_word[0] = “我”

wait_seg_word[1] = “是”

这时候发现了 “我是” 已经在word_dicts中了，可以做切分了，但是我们需要做到最大匹配，所以继续切分

wait_seg_word[2] = “吴”，发觉 “我是吴” 不能够组成词组，继续往下

wait_seg_word[3] = “彦”, 不能组成任何词组

wait_seg_word[4] = “祖”, “是吴彦祖” 匹配了词典，所以最大匹配为 “是吴彦祖”

这就是基础的正向最大匹配算法

逆向最大匹配算法

MM逆向算法其实就是MM正向算法的逆袭思维，我们简单说一下吧。

# 等待分词的列表
wait_seg_word = ["我是吴彦祖"]
# 词典
word_dicts ={"我是", "吴彦祖", "我", "是吴彦祖", "彦祖"}

定义一个做大分割值为 4，从右往左切分等待分词的列表

取得到 “是吴彦祖”， 发觉它已经在词典中了

去掉最左边第一个字，得到 “吴彦祖”

以此类推，一直到无法被减去为止。

然后再做一次切分，取得到 “我是吴彦”

再次切分，对比。重复上述步骤。

双向最大匹配算法

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

这个做个比较就好了，我简单说下它是干嘛的吧。

双向切分算法就是使用正向切分一次、逆向切分一次。如果两次切分结果一样的话就好说了，随便选一个结果就可以。

但是如果切分不一样的话使用那一次的切分结果呢？这就涉及到了结果的选取原则问题。切分词应该遵守以下原则：

1：最大匹配原则：上面一直在说这个，使用这个原则的原因是词的字数越多，表示的含义越丰富、对于一条语句分出来的词也就越少，相对的，准确性也就会越高。

2：词库中没有的单字词越少越好。这个原则有点依赖于词库了，至少词库中应该有一些常用的单字成词的字吧，比如：“你”、“我”、“他”、“和”、“的”、“了”等。使用这个原则的原因可以从上面提到的“我是吴彦祖”这个例子看出来：

正向结果：我是、是、吴彦祖

逆向结果：我是、我、是吴彦祖

虽然分出来的结果单字词都是一个，但是，逆向的单字词”和“在词库中存在，所以我们选择返回逆向切分结果。

其实说白了就是很依赖词库，如果没词库就是一个哑巴教一个不会说话的孩子念绕口令，纯属烧脑。。。。

统计类分词法

统计分词是什么？其实说白了，通过相邻的字同时出现的次数越多，就越可能构成一个词，也就是出现的频率。同样的词组出现多次，被统计的概率越大，组成合理词组也就越精准，可信。因此字与字相邻出现的概率或频率能较好的反映词的可信度。

根据我查询的资料和实践所得，具体有这么几种算法

N-gram模型算法

这个主要运用在tika当中，tika你不会不知道吧？你不知道？后面我写个文章你瞅瞅去吧。。。。

tika是我做全文检索插件的时候接触的，它的核心分词算法就是N-gram算法，这个比较重要，我会详细的说一下这个算法。

首先，N-gram是一种基于统计语言模型的算法。它的基本思想是将文本里面的内容按照字节进行大小为N的滑动窗口操作，形成了长度是N的字节片段序列。（这段出自知乎）

一个N-gram就是一个长度为N的词语组成的序列。

简单的流程

N-Gram 算法具体过程：

1. 过滤掉文本数据中的标点符号和其他特殊字符；

2. 对所有单词执行小写转换，并删除单词之间的空格、换行符等标志位；

3. 使用长度为 N 的窗口对文本内容执行字符级滑动取词，将结果存入有序列表。

这里直接借鉴了别人的代码，看的懂就行

def text_filter(text: str) -> str:
    """
    文本过滤器：过滤掉文本数据中的标点符号和其他特殊字符
    """
    result = str()
    for t in text:
        if t.isalnum():
            if t.isalpha():
                t = t.lower()
            result += str(t)
    return result

def slide_word(text: str, l: int = 5) -> list:
    """
    滑动取词器
    Input: text='abcd',l=2
    Output: ['ab','bc','cd']
    :param text: 过滤后的文本 （只包含小写数字/字母）
    :param l: 滑动窗口长度，默认为 5
    :return:
    """
    tf = text_filter(text)
    result = list()
    if len(tf) <= l:
        result.append(tf)
        return result
    for i in range(len(tf)):
        word = tf[i:i + l]
        if len(word) < l:
            break
        result.append(word)
    return result


if __name__ == '__main__':
    banner = 'abcdefghigkLMN*^%$*   \r\n)021'
    print(slide_word(banner))

返回

['abcde', 'bcdef', 'cdefg', 'defgh', 'efghi', 'fghig', 'ghigk', 'higkl', 'igklm', 'gklmn', 'klmn0', 'lmn02', 'mn021']

隐马尔科夫模型算法 (HMM)

通过模拟人对句子的理解，达到识别词的效果，基本思想是语义分析，句法分析，利用句法信息和语义信息对文本进行分词。自动推理，并完成对未登录词的补充是其优点。不成熟.

具体概念:有限状态机\语法约束矩阵\特征词库

以往的分词方法，无论是基于规则的还是基于统计的，一般都依赖于一个事先编制的词表(词典)。

自动分词过程就是通过词表和相关信息来做出词语切分的决策。

与此相反，基于字标注的分词方法实际上是构词方法。

即把分词过程视为字在字串中的标注问题。

由于每个字在构造一个特定的词语时都占据着一个确定的构词位置(即词位)，假如规定每个字最多只有四个构词位置：即B(词首)，M (词中)，E(词尾)和S(单独成词)，那么下面句子(甲)的分词结果就可以直接表示成如(乙)所示的逐字标注形式：

(甲)分词结果：／上海／计划／N／本／世纪／末／实现／人均／国内／生产／总值／五千美元／

(乙)字标注形式：上／B海／E计／B划／E N／S 本／s世／B 纪／E 末／S 实／B 现／E 人／B 均／E 国／B 内／E生／B产／E总／B值／E 五／B千／M 美／M 元／E 。／S

首先需要说明，这里说到的“字”不只限于汉字。

考虑到中文真实文本中不可避免地会包含一定数量的非汉字字符，本文所说的“字”，也包括外文字母、阿拉伯数字和标点符号等字符。所有这些字符都是构词的基本单元。当然，汉字依然是这个单元集合中数量最多的一类字符。

把分词过程视为字的标注问题的一个重要优势在于，它能够平衡地看待词表词和未登录词的识别问题。

在这种分词技术中，文本中的词表词和未登录词都是用统一的字标注过程来实现的。

在学习架构上，既可以不必专门强调词表词信息，也不用专门设计特定的未登录词(如人名、地名、机构名)识别模块。这使得分词系统的设计大大简化。

在字标注过程中，所有的字根据预定义的特征进行词位特性的学习，获得一个概率模型。然后，在待分字串上，根据字与字之间的结合紧密程度，得到一个词位的标注结果。

最后，根据词位定义直接获得最终的分词结果。总而言之，在这样一个分词过程中，分词成为字重组的简单过程。然而这一简单处理带来的分词结果却是令人满意的。

总结

我估摸着我还是要好好把这些算法过一遍，未来还有很长的路要走，算法也太难了。。。