kds:“前驻法大使吴建民指出，应该理**国”,想了一下，原来两个星号是“性爱”两字，生活在一个机械屏蔽时代的中国还真有喜感。——via

想必您也看到了推特上关于“理＊＊国”的笑话了。我正好想学一下中文分词方面的知识，这是第一篇。

分词原理与实现

英语等以空白字符作为分隔符的语言，分词不是问题。中文分词，需要处理的细节太多。单就“真歧义”这一问题（简言之，如果没有上下文，连活生生的人也无法确定如何断句的歧义句）的处理方法而言，前辈们就已写出洋洋洒洒许多文字。不过这属于进阶题目。我想先实现一个最简单的分词程序。

以我的理解，最简单的分词程序，应该是先将中文文本切成最小的单位－－汉字－－再从词典里找词，将这些字按照最左最长原则（与正则精神暗合），合并为以词为单位的集合。这样的应该是最快的，只按照给定的数据划分合并即可，不必考虑语法元素的权重（词性：名动形数量代等等，语法：主谓宾定状补），以及上下文的出现次数。

关于源文本的切分，就参照《统计汉字／英文单词数》一文的思路，使用正则表达式r"(?x) (?: [\w-]+  | [\x80-\xff]{3} )")来匹配即可。

关于词典，我使用的是CC-CEDICT的词典，原因有三：没有版权问题；速度较快；Chrome也在用它（发现了吧：在Chrome上双击中文句子，会自动选择中文词汇而不是单字或整行进行反选高亮）。

接下来是如何分词。经过思考，我发现搜索树的原理可以拿来就用。原理请见此文：Trie in Python。具体方法是，将词库逐字读入内存，建立搜索树；然后对目标文本进行逐字分析，如果该字之后还可搜索，则继续搜索；否则停止，作为一个词汇单位处理。

这样的算法理论上比较快（未进行benchmark），原因有三：使用Trie结构，本质上是哈希表，空间换时间，是O(0)级的搜索；词库只有800K，可以轻易载入，内存空间没占多少；算法最慢的部分是载入Trie的阶段，之后速度就不再受影响。

不过，谈到它的扩充性，目前只能在words.txt中手动添加新词，而不能实现机器学习。

源码

完整的程序（包括我处理过的词库列表）放在github上了。有兴趣的可以把玩一下。这里列出主程序：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#!/usr/bin/python # -*- coding: utf-8 -*- # #author:         rex #blog:           http://iregex.org #filename        nlp.py #created:        2010-09-26 19:15 import re import sys regex=re.compile(r"(?x) (?: [\w-]+  | [\x80-\xff]{3} )") def init_wordslist(fn="./words.txt"):     f=open(fn)     lines=sorted(f.readlines())     f.close()     return lines def words_2_trie(wordslist):     d={}     for word in wordslist:         ref=d         chars=regex.findall(word)         for char in chars:             ref[char]=ref.has_key(char) and ref[char] or {}             ref=ref[char]         ref['']=1     return d def search_in_trie(chars, trie):     ref=trie     index=0     for char in chars:         if ref.has_key(char):             print char,             ref=ref[char]             index+=1         else:             if index==0:                 index=1                 print char,             print '*',             try:                 chars=chars[index:]                 search_in_trie(chars, trie)             except:                 pass             break def main():     #init     words=init_wordslist()     trie=words_2_trie(words)     #read content     fn=sys.argv[1]     string=open(fn).read()     chars=regex.findall(string)         #do the job     search_in_trie(chars, trie) if __name__=='__main__':     main()

本机测试

测试的文本如下：

1 2 3 4 5 6 7 8 9 10 11 12

只听得一个女子低低应了一声。绿竹翁道：“姑姑请看，这部琴谱可有些古怪。”那 女子又嗯了一声，琴音响起，调了调弦，停了一会，似是在将断了的琴弦换去，又调了调 弦，便奏了起来。初时所奏和绿竹翁相同，到后来越转越高，那琴韵竟然履险如夷，举重 若轻，毫不费力的便转了上去。令狐冲又惊又喜，依稀记得便是那天晚上所听到曲洋所奏 的琴韵。这一曲时而慷慨激昂，时而温柔雅致，令狐冲虽不明乐理，但觉这位婆婆所奏， 和曲洋所奏的曲调虽同，意趣却大有差别。这婆婆所奏的曲调平和中正，令人听着只觉音 乐之美，却无曲洋所奏热血如沸的激奋。奏了良久，琴韵渐缓，似乎乐音在不住远去，倒 像奏琴之人走出了数十丈之遥，又走到数里之外，细微几不可再闻。 理性爱国 性爱体验 我爱正则表达式

请留意末尾三行。

再看一下程序处理的结果：（＊表示词汇间的分隔）

1

只 * 听 得 * 一 个 * 女 子 * 低 低 * 应 * 了 * 一 声 * 。 * 绿 * 竹 * 翁 * 道 * ： * “ * 姑 姑 * 请 看 * ， * 这 * 部 * 琴 * 谱 * 可 有 * 些 * 古 怪 * 。 * ” * 那 * 女 子 * 又 * 嗯 * 了 * 一 声 * ， * 琴 * 音 响 * 起 * ， * 调 * 了 * 调 * 弦 * ， * 停 * 了 * 一 会 * ， * 似 是 * 在 * 将 * 断 * 了 * 的 * 琴 弦 * 换 * 去 * ， * 又 * 调 * 了 * 调 * 弦 * ， * 便 * 奏 * 了 * 起 来 * 。 * 初 * 时 * 所 * 奏 * 和 * 绿 * 竹 * 翁 * 相 同 * ， * 到 * 后 来 * 越 * 转 * 越 * 高 * ， * 那 * 琴 * 韵 * 竟 然 * 履 险 如 夷 * ， * 举 重 * 若 * 轻 * ， * 毫 不 费 力 * 的 * 便 * 转 * 了 * 上 去 * 。 * 令 狐 * 冲 * 又 * 惊 * 又 * 喜 * ， * 依 稀 * 记 得 * 便 是 * 那 天 * 晚 上 * 所 * 听 到 * 曲 * 洋 * 所 * 奏 * 的 * 琴 * 韵 * 。 * 这 一 * 曲 * 时 而 * 慷 慨 * 激 昂 * ， * 时 而 * 温 柔 * 雅 致 * ， * 令 狐 * 冲 * 虽 * 不 明 * 乐 理 * ， * 但 * 觉 * 这 位 * 婆 婆 * 所 * 奏 * ， * 和 * 曲 * 洋 * 所 * 奏 * 的 * 曲 调 * 虽 * 同 * ， * 意 趣 * 却 * 大 有 * 差 别 * 。 * 这 * 婆 婆 * 所 * 奏 * 的 * 曲 调 * 平 和 * 中 正 * ， * 令 人 * 听 * 着 * 只 * 觉 * 音 乐 之 * 美 * ， * 却 * 无 * 曲 * 洋 * 所 * 奏 * 热 血 * 如 * 沸 * 的 * 激 * 奋 * 。 * 奏 * 了 * 良 久 * ， * 琴 * 韵 * 渐 * 缓 * ， * 似 乎 * 乐 音 * 在 * 不 住 * 远 * 去 * ， * 倒 像 * 奏 * 琴 * 之 * 人 * 走 出 * 了 * 数 十 * 丈 * 之 * 遥 * ， * 又 * 走 * 到 * 数 * 里 * 之 外 * ， * 细 微 * 几 * 不 可 再 * 闻 * 。 * 理 性 * 爱 国 * 性 爱 * 体 验 * 我 * 爱 * 正 则 * 表 达 式

更新

2010-10-03更新:发现本程序的一个bug。已改进算法，更精确，更快速。程序详见GitHub，链接如前。

请看新程序的分词结果：

只 * 听 * 得 * 一 * 个 * 女子 * 低 * 低 * 应 * 了 * 一声 * 。 * 绿 * 竹 * 翁 * 道 * ： * “ * 姑姑 * 请看 * ， * 这 * 部 * 琴谱 * 可 * 有些 * 古怪 * 。 * ” * 那 * 女子 * 又 * 嗯 * 了 * 一声 * ， * 琴 * 音响 * 起 * ， * 调 * 了 * 调 * 弦 * ， * 停 * 了 * 一会 * ， * 似 * 是 * 在 * 将 * 断 * 了 * 的 * 琴弦 * 换 * 去 * ， * 又 * 调 * 了 * 调 * 弦 * ， * 便 * 奏 * 了 * 起来 * 。 * 初 * 时 * 所 * 奏 * 和 * 绿 * 竹 * 翁 * 相同 * ， * 到 * 后来 * 越 * 转 * 越 * 高 * ， * 那 * 琴 * 韵 * 竟然 * 履 * 险 * 如 * 夷 * ， * 举重 * 若 * 轻 * ， * 毫不 * 费力 * 的 * 便 * 转 * 了 * 上去 * 。 * 令狐 * 冲 * 又 * 惊 * 又 * 喜 * ， * 依稀 * 记得 * 便是 * 那天 * 晚上 * 所 * 听到 * 曲 * 洋 * 所 * 奏 * 的 * 琴 * 韵 * 。 * 这 * 一 * 曲 * 时而 * 慷慨 * 激昂 * ， * 时而 * 温柔 * 雅致 * ， * 令狐 * 冲 * 虽 * 不明 * 乐理 * ， * 但 * 觉 * 这位 * 婆婆 * 所 * 奏 * ， * 和 * 曲 * 洋 * 所 * 奏 * 的 * 曲调 * 虽 * 同 * ， * 意趣 * 却 * 大有 * 差别 * 。 * 这 * 婆婆 * 所 * 奏 * 的 * 曲调 * 平和 * 中正 * ， * 令人 * 听 * 着 * 只 * 觉 * 音乐 * 之 * 美 * ， * 却 * 无 * 曲 * 洋 * 所 * 奏 * 热血 * 如 * 沸 * 的 * 激 * 奋 * 。 * 奏 * 了 * 良久 * ， * 琴 * 韵 * 渐 * 缓 * ， * 似乎 * 乐音 * 在 * 不住 * 远 * 去 * ， * 倒像 * 奏 * 琴 * 之 * 人 * 走出 * 了 * 数 * 十 * 丈 * 之 * 遥 * ， * 又 * 走 * 到 * 数 * 里 * 之外 * ， * 细微 * 几 * 不可 * 再 * 闻 * 。 *

理性 * 爱国 *

性爱 * 体验 *

我 * 爱 * 正则 * 表达式 *

轻 * 音乐 *

建议继续学习：

1. 漫话中文分词算法    (阅读：3918)
2. 漫话中文自动分词和语义识别（下）：句法结构和语义结构    (阅读：3382)
3. 腾讯php程序员面试题目答案――编程任务    (阅读：3193)
4. 基于trie数据字典的php中文分词    (阅读：2986)
5. Levenshtein distance相似度算法    (阅读：2994)
6. 排头兵PHP中文分词,纯PHP版实现    (阅读：2630)
7. Mysql+sphinx+中文分词简介(ubuntu)    (阅读：2287)
8. Mysql+sphinx+中文分词简介(ubuntu)    (阅读：1916)
9. 利用新词统计特征进行中文分词    (阅读：1508)
10. 用MeCab打造一套实用的中文分词系统    (阅读：1120)