搜索引擎的自然语言分词
前言:计算机就像小孩子一样,虽然什么都不懂,什么都不会,但只要耐心教导,他可以做
的很出色。
上一节我们分享了单词的识别,这一节要分享的就是更加有趣也更加复杂的自然语言分词。
顾名思义,分词就是将一句句子分成一个一个的单词。但是各国的语言都不一样,比如在英
语中,单词一般是用空格或者其他标点符号隔开,这种语种的分词相对比较简单,只需要用
空格来分割字符串。但是像中文,日文等等类似的语种,单词之间是没有任何分割的标记,
因此在分词的过程中就有点难度。
下面就以中文为例子,其他语言也类似。
比如有一句句子:我们都喜欢玩全文搜索引擎。
那么分词的模式就有多种了,这里笔者只介绍最常用的两种
一.智能模式
分词后:[我们] [都] [喜欢] [玩] [全文搜索引擎] [。]
二.最细颗粒模式
分词后:[我] [我们] [都] [喜欢] [玩] [全文] [搜索] [全文搜索] [引擎] [搜索引擎] [全文搜
索引擎] [。]
但是分词后我们发现,有很多没有意思的单词,比如上句中的“都”,“玩”等等副词或者
动词等等,当然还有标点符号。
因此智能模式下我们期望是分成[我们] [喜欢] [全文搜索引擎]这三个词,而不需要那么多无
用的单词。
经过上面的分词,相信读者很容易就能够发现,智能模式是以最长单词为分割限度,而且不
回退的分割模式。而相反最细颗粒模式就是以最小单词为限度,并逐一递增的分割模式。
比如“全文搜索引擎”在智能模式下,就是一个单词 [全文搜索引擎],而在最细颗粒模式
下可以分割成 [全文] [搜索] [全文搜索] [引擎] [搜索引擎] [全文搜索引擎] 这么多个单词。
经验告诉笔者,智能模式的使用范围更广,因为搜索的精度可以更加准确。需要说明的是,
这两个模式在笔者通过程序实现后,它们的分割时间基本持平,智能模式略快。
OK,下面开始介绍整个分词的算法与数据结构。
同样的,开发环境还是 Linux + C + Ecipse CDT
首先先介绍算法,由于要兼容智能模式与最细颗粒模式,在算法上,笔者采用的是著名的
AC 算法,全称叫 Aho-Corasick,也称有穷自动机。
类似上一节分享的 Trie 算法,AC 算法也是在内存中建立单词库,不同的是,它不仅仅可以
做到单词的识别,还可以做到字符串的多模式匹配,也就是笔者说的分词。AC 算法在 Trie
算法的基础上,添加了失败转换的特性。下面通过图来了解 AC 算法的奥妙之处。