一个简单的中文分词程序
September 26th, 2010 Categories: 应用
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:
#filename nlp.py
#created: 2010-09-26 19:15
import re
import sys
regexr"(?x) (?: [\w-]+ | [\x80-\xff]{3} )")
:
ffn)
linesf.
f.
return lines
def words_2_trie(wordslist):
d
for word in wordslist:
ref=d
chars=regex.findall(word)
for char in chars:
refchar
ref=ref[char]
ref
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,
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
fn
chars
#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，链接如前。
请看新程序的分词结果：
只 * 听 * 得 * 一 * 个 * 女子 * 低 * 低 * 应 * 了 * 一声 * 。 * 绿 * 竹 * 翁 * 道 * ： * “ * 姑姑 * 请看 * ， * 这 * 部 * 琴谱 * 可 * 有些 * 古怪 * 。 * ” * 那 * 女子 * 又 * 嗯 * 了 * 一声 * ， * 琴 * 音响 * 起 * ， * 调 * 了 * 调 * 弦 * ， * 停 * 了 * 一会 * ， * 似 * 是 * 在 * 将 * 断 * 了 * 的 * 琴弦 * 换 * 去 * ， * 又 * 调 * 了 * 调 * 弦 * ， * 便 * 奏 * 了 * 起来 * 。 * 初 * 时 * 所 * 奏 * 和 * 绿 * 竹 * 翁 * 相同 * ， * 到 * 后来 * 越 * 转 * 越 * 高 * ， * 那 * 琴 * 韵 * 竟然 * 履 * 险 * 如 * 夷 * ， * 举重 * 若 * 轻 * ， * 毫不 * 费力 * 的 * 便 * 转 * 了 * 上去 * 。 * 令狐 * 冲 * 又 * 惊 * 又 * 喜 * ， * 依稀 * 记得 * 便是 * 那天 * 晚上 * 所 * 听到 * 曲 * 洋 * 所 * 奏 * 的 * 琴 * 韵 * 。 * 这 * 一 * 曲 * 时而 * 慷慨 * 激昂 * ， * 时而 * 温柔 * 雅致 * ， * 令狐 * 冲 * 虽 * 不明 * 乐理 * ， * 但 * 觉 * 这位 * 婆婆 * 所 * 奏 * ， * 和 * 曲 * 洋 * 所 * 奏 * 的 * 曲调 * 虽 * 同 * ， * 意趣 * 却 * 大有 * 差别 * 。 * 这 * 婆婆 * 所 * 奏 * 的 * 曲调 * 平和 * 中正 * ， * 令人 * 听 * 着 * 只 * 觉 * 音乐 * 之 * 美 * ， * 却 * 无 * 曲 * 洋 * 所 * 奏 * 热血 * 如 * 沸 * 的 * 激 * 奋 * 。 * 奏 * 了 * 良久 * ， * 琴 * 韵 * 渐 * 缓 * ， * 似乎 * 乐音 * 在 * 不住 * 远 * 去 * ， * 倒像 * 奏 * 琴 * 之 * 人 * 走出 * 了 * 数 * 十 * 丈 * 之 * 遥 * ， * 又 * 走 * 到 * 数 * 里 * 之外 * ， * 细微 * 几 * 不可 * 再 * 闻 * 。 *
理性 * 爱国 *
** * 体验 *
我 * 爱 * 正则 * 表达式 *
轻 * 音乐 *
Tags: chinese, nlp, python, utf8| Trackback
16 Responses to “一个简单的中文分词程序”
xingzhong
September 27th, 2010 at 06:01
1
订阅你的博客很长时间了，受益匪浅
目前我是学生，研究方向是 信号处理的语义学表达 ，所以你的正则内容在我的code预处理方面有很大帮助。 希望能和博主多交流。
目前我有一个想法，希望能建立一个以概率为基础的正则表达式引擎而不是进行确定性匹配，由于我本身是无线通信和数字信号处理的背景，在我们的方向上进行信号的匹配与检测，我们一般不采用CS常用的方法，即正则表达式。所以我希望能够将两方面结合，将匹配和检测提升一个高度，将 machine learning 和 feature space 的理论引入。
由于我本身的学识所限，这个想法是否可行，还有待论证，所以希望和你这种CS背景的人多交流。如有兴趣，直接邮件联系，中英文均可。
[]
rex Reply:
September 27th, 2010 at 6:54 am
发邮件了。多交流！
[]
Justice
September 29th, 2010 at 16:31
2
其实这已经不是新的想法了，现代的自然语言处理方法都不再使用机械匹配，几乎都采取了概率模型。语音识别、中文输入法等等问题均可以看成信号处理的过程，隐马尔可夫模型什么的都可以应用在这上面。这样的课题应该已经有了很多年的历史了。
[]
xingzhong Reply:
September 30th, 2010 at 3:36 am
这个确实不是新的想法，HMM确实在很多上下文相关的匹配上有了20-30年的历史。用概率去建模并进行匹配确实不是新想法。
我的想法是提出一个工具，这个工具类似于正则表达式，能够用概率模型去匹配目标。这正如正则与有限状态机的关系一般。 人人都认可与明白使用状态机去进行确定性匹配，但是直到正则的出现，才有更加严谨和可扩展的语言去描述他。
使用概率模型去匹配，使用马尔可夫链去做LL匹配，都很常见，但是如今却应该没有比较完善的使用克莱尼代数进行封装与扩展。
[]
Justice
September 29th, 2010 at 16:32
3
晕..想回复沙发的…原来右下角这个Reply不能嵌套…
[]
rex Reply:
September 29th, 2010 at 10:00 pm
每个comment的左下角有回复链接的，点[Reply]就是。
[]
zhiqiang
October 9th, 2010 at 20:25
4
感觉分得太细了点
[]
rex Reply:
October 10th, 2010 at 9:12 am
确实分得太细，原因是词库中没有这样的词，只好以单字来对待。
原理：从字串的当前位置找字典中存在的最长的词条作为分词依据。因此，目前只能通过手动添加词条的方法来扩充词库，让看起来明显是一个词的汉字归并到一起，以便看起来分得不那么细。
[]
[]
rex Reply:
October 16th, 2010 at 9:04 am
基于概率的中文分词，是个很好的方向。
[]
black he
December 13th, 2010 at 17:52
5
我以前也用java写了一个分词查询 原理和你一样 我有45万天词语的词库 不过分词速度比较慢，1.6的cpu速度只有2万词每秒，你的速度是多少
[]
rex Reply:
July 21st, 2011 at 9:04 am
比我的快多了。
[]
nuota
July 20th, 2011 at 15:27
6
博主，为什么我运行都是乱码呢？请问编码该如何设置？
[]
rex Reply:
July 21st, 2011 at 9:03 am
我的环境是utf8. 莫非你在win环境？
[]
nupta Reply:
July 21st, 2011 at 2:29 pm
嗯，我的是win7，已经搞定了，我环境的编码默认不是UTF-8，而且每个IDE的默认编码都不一样，崩溃啊。
我在前面加了句str_type = sys.getfilesystemencoding() 然后在输出的时候解码。
另外对这个稍微改进了下，效果如下：
只听得 * 一个 * 女子 * 低 * 低 * 应 * 了 * 一声 * 。 * 绿竹翁 * 道 * ： * “ * 姑姑 * 请看 * ， * 这部 * 琴谱 * 可有 * 些 * 古怪 * 。 * ” * 那 * 女子 * 又* 嗯 * 了 * 一声 * ， * 琴音 * 响起 * ， * 调了 * 调弦 * ， * 停了 * 一会 * ， * 似是 * 在 * 将 * 断了 * 的 * 琴弦 * 换去 * ， * 又 * 调了 * 调弦 * ， * 便 * 奏了 * 起来 * 。 * 初时 * 所 * 奏 * 和 * 绿竹翁 * 相同 * ， * 到 * 后来 * 越 * 转* 越高 * ， * 那 * 琴韵 * 竟然 * 履 * 险 * 如 * 夷 * ， * 举重 * 若 * 轻 * ， *毫不 * 费力 * 的 * 便 * 转了 * 上去 * 。 * 令狐冲 * 又 * 惊 * 又 * 喜 * ， * 依稀 * 记得 * 便是 * 那天 * 晚上 * 所 * 听到 * 曲洋 * 所 * 奏 * 的 * 琴韵 * 。 *这一 * 曲 * 时而 * 慷慨 * 激昂 * ， * 时而 * 温柔 * 雅致 * ， * 令狐冲 * 虽不 *明 * 乐理 * ， * 但 * 觉 * 这位 * 婆婆 * 所 * 奏 * ， * 和曲 * 洋 * 所 * 奏 * 的 * 曲调 * 虽 * 同 * ， * 意趣 * 却 * 大有 * 差别 * 。 * 这 * 婆婆 * 所 * 奏 * 的
* 曲调 * 平和 * 中正 * ， * 令人 * 听着 * 只 * 觉 * 音乐 * 之 * 美 * ， * 却 *无 * 曲洋 * 所 * 奏 * 热血 * 如 * 沸 * 的 * 激奋 * 。 * 奏了 * 良久 * ， * 琴韵* 渐 * 缓 * ， * 似乎 * 乐音 * 在 * 不住 * 远去 * ， * 倒像 * 奏琴 * 之人 * 走出 * 了 * 数十 * 丈 * 之遥 * ， * 又走 * 到 * 数 * 里 * 之外 * ， * 细微 * 几 * 不可 * 再 * 闻 * 。 *
[]
rex Reply:
July 21st, 2011 at 3:26 pm
cool!
[]
Leave a Comment
