中文分词的效果是任何一个中文搜索引擎搜索质量的基础。本文谈谈对于一个中文搜索引擎,分词要解决的各种问题。

由于中文句子中词语之间没有空格(跟英文不一样),而中文语义的最小单位是词语,为了根据关键词能够准确检索到有意义的结果。索引、搜索的时候需要用到中文分词,自动把句子中的词一个个断开。

#1.基本问题 首先要解决的是分词的基本问题,能够把句子中的词语切分出来。

比如这一句话:“根据用户心情和行为投放不同的广告”,可以切分成"根据/用户/心情/和/行为/投放/不同/的/广告 “。“杭州西湖是世界文化遗产”,可以切分为"杭州/西湖/是/世界/文化遗产/” (例子a)

如果不按照词语进行索引、搜索,那么搜索“西湖”的时候出来的结果中会包含“西”出现在商品名,“湖”出现在商品描述中的情况。

通常使用机械分词方法,即基于词典的分词方法。

可以从左到右正向切分,也可以从右到左逆向切分。

#2.歧义 正向分词与逆向分词的结果可能不一样,比如“服装和服饰”。(例子b1)

正向结果:服装/和服/饰

逆向结果:服装/和/服饰

汉语语义的最小单位是词语,我们不希望在搜索“和服”出现“服装和服饰”的结果,“和服”不是这个短语中的词。这个例子中,逆向分词的结果好于正向分词的结果。

根据统计的经验,逆向分词的准确率比正向分词的准确率略高一点(这个结果是跟汉语语言的特性有关)。

歧义需要识别出来,然后消除歧义。

识别歧义可以用正向,逆向分两次来比对。 也可以用正向分词,中间过程进行回溯来找到可能的歧义。

歧义消除的方法简单来说可以用词频概率的方法,同时可以结合词性概率,词语前后关联概率,词性前后关联概率/HMM来找出概率上更可能准确的结果。也可使用条件随机场(conditional random fields, CRF)的算法来消除歧义。

“日月光”因能找到“近日月光”(例子b2)

分词中的常用算法

贪婪算法(属机械分词算法,有最大正向匹配/最大逆向匹配)
最小正向/最小逆向匹配 (属机械分词)
回溯算法(属机械分词,可以最快的速度找出各种可能的分词结果)
隐马尔科夫模型HMM (ICTCLAS使用的HMM)
条件随机场CRF (CRF是2001年提出来的机器学习模型,是目前最准确的一种分词算法)
NGram(常用的有bi-gram, 3-gram)

#3.召回率 要保证召回率,那么用户随便输入一个词语中的任何一部分,都能找到词语。

比如搜索“崇明”,能够找到“崇明岛”。 搜索“火车”能够找到“火车站”,“火车票”。(例子C1)

搜索“重庆/火锅”,应能找到“重庆/麻辣火锅”。(例子C2)

搜索“动物园”,应该能找到“动物园内”。(例子C3)

搜索“西藏路”,应该能找到“西藏路口”。(例子C4)

搜索“浦东机场”,应该能找到“浦东国际机场”。(例子C5)

搜索“索芙特酒店”,应该能找到“索芙特大酒店”。(例子C6)

搜索“日本料理”,应该能找到“日本料理铁板烧”(例子C7)

#4.准确率

在保证召回率的同时,也要保证准确率。

搜索“京东”,不应该出来“南京东路” (例子D)

搜索“安西路”不应该出来“延安西路“,因为安西路是一条路。(例子E1)

但搜索“羊肉”应该能找到“涮羊肉”,类似的“牛排”要能找到“牛排馆”。(例子E2)

搜“自助餐”,应该找到“中西自助餐厅”。(例子E3)

搜“70后”,应该能找到“70后饭吧”。当“后翻吧”被当作一个词时,“70后饭吧”会被分成“70/后饭吧“,搜索“70后”就找不到了。

#5.名词实体识别 搜索“德站琪”,应只出现“德站琪”,搜索“德站”,应该也能出现“德站琪”。(例子F1)

如“鑫花溪”,应该能够识别成一个词语。(例子F2)

有一家商户名叫“新寺洞新”,输入“新寺洞”应该能找到这个商户名。(例子F3)

#6.同义词 “烤鱼”应该能搜索到“烤全鱼”。(例子G1)

“工行”应该能够搜索到“工商银行”。(例子G2)

#6.英文与数字 Laker’s

7-eleven, 7eleven

1979Cheesecake, 1979 Cheesecake, 1979 Cheese cake

#7.日韩文 要谨防日文,韩文搜索不到的问题出现:번지없는주막

#8.词典

词典词库:词库中的词语不能多,不能少,一个恰到好处的词库对于分词的效果非常关键。

词典是分词算法中最重要的数据结构。

常用的词典数据结构有:

Sorted Array/List: 最基本的词典,使用二分查找方法快速查找
Hashtable: 最容易使用的词典,消耗内存大
Trie: 非常快的词典,适合英文词典,中文由于字过多,trie消耗内存非常大
Double Array Trie:适合做中文词典,内存占用小,速度快;其实就是一个状态机,也可认为是一种哈希算法,有开源的实现;
Finite State Transducers (FST):一种有限状态转移机,Lucene 4中有开源的实现;
Ternary Search Tree:三叉树,每一个node有3个节点(equal kid,low kid,hi kid),Trie树中的一个变种,也成为前缀树,常用作spell check, 搜索下拉提示中;
Skip List:跳跃表,排序好的多层级列表,可快速查找词语,在lucene,redis, leveldb中有实现

#9.开源的分词产品

ICTCLAS (中科院,早期版本开源,后来商业化,开源版本中有多个bug)
IKAnalyzer
ansj_seg (中科院ICTCLAS的一个Java版本实现, Javaeye出品的开源分词)
CRF++ (coreseek实现的改进版本)
paoding
mmseg
结巴分词
nlpbamboo