技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 一个简单的中文分词程序

一个简单的中文分词程序

浏览:4553次  出处信息

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. 漫话中文分词算法    (阅读:4005)
  2. 漫话中文自动分词和语义识别(下):句法结构和语义结构    (阅读:3461)
  3. 腾讯php程序员面试题目答案――编程任务    (阅读:3244)
  4. Levenshtein distance相似度算法    (阅读:3189)
  5. 基于trie数据字典的php中文分词    (阅读:3048)
  6. 排头兵PHP中文分词,纯PHP版实现    (阅读:2708)
  7. Mysql+sphinx+中文分词简介(ubuntu)    (阅读:2352)
  8. Mysql+sphinx+中文分词简介(ubuntu)    (阅读:1969)
  9. 利用新词统计特征进行中文分词    (阅读:1678)
  10. 用MeCab打造一套实用的中文分词系统    (阅读:1304)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1