基于词典的汉语自动分词算法的改进

发布于:2021-11-27 12:51:58

情报杂志 2006 年第 1 期 · 情报方法·

1 概 述

计算机语言学界和情报检索界的热门 课题 ,前者主要将切分结果用于自然语 和自然语言接口等 ; 后者则侧重于将其 结果应用于标引研究
[1 ]

言理解 , 自动翻译 , 语音自动识别输入

词是中文信息处理的基础 ,在中文信息 些年 ,情报检索领域内的专家学者们在

处理系统中具有广泛的应用前景 .前 汉语词的切分标引研究中显得十分活

跃 ,提出了 10 余种算法 .但是*几年 来 ,情报学界研究的步伐逐步减缓 , 这 主要是由于随着计算机存储能力和运 算能力的飞速提高 , 原来认为 "几乎不 可能" 实现的全文检索系统已经全面投 入使用 ,并且在速度和查全率方面均取

得了令人满意的效果 [ 2 ] ; 而情报学界的 自动分词是为标引服务的 ,标引又是为 检索服务的 ; 既然可以利用计算机能力 的提升来绕过 "自动分词" 这一难关达 到检索目的 ,人们自然不会再去为自动

分词投入更多的精力 .同时还有人提 出 ,即便是需要进行自动标引 , 也可以 从主题词表出发 , 到文献中进行 "逆向 匹配" ,这一过程也不需要自动分词 ,
[3 ]

该方法唯一的*羌扑慊脑诵兴

度 ,但是根据摩尔定律 , 这一瓶颈也将 很快被突破 .但是 ,以机器翻译为目的 的汉语语词自动切分仍然是语言学专
基金项目 : 受湖南省图工委基金项目资助 .

作者简介 : 傅立云 ,女 ,1975 年生 ,馆员 ; 刘 ,男 ,1975 年生 ,硕士 ,研究方向为计算机算法 . 新

40

基于词典的汉语自动分词算法的改进 3
傅立云 刘 新
( 湘潭大学图书馆 湘潭 411105) ( 湘潭大学信息工程学院 湘潭 411105)

摘 要 综合分析了目前在计算机自动分词领域取得的进展和面临的困难 ,针对词典法提出了一种新的词典构筑方 法以及相应的匹配算法 . 关键词 自动分词 词典法 自然语言处理

家们不得不面对的难题 .目前虽有中 科院 , 微软等研究机构推出的一些实验 果仍不尽如人意 .

无论用哪一种匹配算法 ,都必须对

待切分的字符串进行扫描 ,逐字与词典 中的字进行匹配 .常用的扫描算法有 三种 : 前向扫描 , 逆向扫描和二者结合 的多趟扫描 .其中 ,前向扫描更符合人 们的思维*惯 , 发展得也最为成熟 , 是 自动分词的主攻方向 ; 后两者都是为了 解决词语的歧义问题提出的辅助方法 . 如果我们能构筑一个合适的语义库 ,在 绝大多数情况下可以只需要前向扫描 . 2 2. 词典构筑 词典法的核心就在 词典的构筑上 , 通常认为有两个难点 : 一是词典的完备性 , 二是匹配速度 , 二 者互相制约 [ 6 ] .关于词的严格定义 ,已 经有了公论 ,但由于汉语的语素和单字 词 ,合成词和短语之间没有清晰的界 限 ,导致在分词中对于词的标准难于把 握 .一种意见认为应严格按照中国国 家标准 GB13715 信息处理用现代汉语 《 分词规范》 公布的为准 ; 一种认为应该 按约定俗成 ,以人们通常的对 "词" 的理 解为准 ,合成词和短语都应算做词 , 本 文采用第二种意见 .这样 ,一个完备的 词典 ,必须囊括所有日常用语 , 词组 , 熟 语, , 成语 人名 , 地名 , 机构名称和专业 词 ,这使得它的规模十分庞大 , 匹配时 的效率很低 .所以人们常常将词典分 为常用词典和专业词典两种 ,匹配时只 需要查找常用词典和对应的专业词典 , 这就缩小了查找范围 .据 《现代汉语词 典》 统计 , 汉语常用词只有 56 000 条 ,

汉语自动分词研究多年来一直是

系统 ( 如 CSW , WB2000 等 ) , 但分词效 目前常用的分词方法有三大类 : 词

典法 , 基于规则切分标记法和人工智能

法 [ 4 ] .后两种要求程序的智能程度高 , 高, 歧义处理困难以及无法囊括所有词 高 ,所以大多数的系统是以该方法为主 改进 .

.因而 ,汉语分

目前尚不 实 用 ; 词典虽然存在效率不 等等不足 , 但它实现简单 ,分词效率很

来实现的 .本文着重讨论对词典法的

2 词典法的基本要素

一个完善的词典法必须包含两部

分 : 一是词典 ,二是相应的匹配算法 ,二 者相互依存 .

1 2. 匹配算法 目前常用的匹配算
[5 ]

法有 "长词优先法" "短词优先法" . 和 例如对于 "有机化学合成法" 长词优 " , 先法" 得到的结果是 "有机化学" 合成 , " 法" 两个词 , 而用 "短词优先法" 得到的

结果是 "有机" 化学" 合成" 法" , " , " , 四 " 个词 .显然 "长词优先法" , 的优势在于

专指程度 高 , 可以消除大多数的歧义 词 ,更适合于标引和机器翻译 ; 它的劣 程序的实现比较复杂 .不过 ,只要我们 在构筑词典时多下一番功夫 ,完全可以 消除此劣势 . 势在于匹配时需要多趟扫描 , 效率低 ,

情报杂志 2006 年第 1 期

· 情报方法·
为词尾 . 3 2. 基于字符树的长词优先匹配算 法 对于这样的字符树 ,长词优先法匹 配算法需要考虑两个问题 : 一是如何让 匹配的词尽量地长 ? 这需要逐字前向 匹配一直到不能匹配为止 .二是可能 存在这样的情况 : 某字符串 a1 ,a2 , …, "
a n" 在字符树中匹配成功 , 且 a1 ,a2 , … " an ,an + 1 " 匹配不成功 ,但 an 处并不是词

常用的地名和人名 4 000 余条 ; 而通常 某一专业的专业词语不过 4 000 条 , 设 词的*均长度为 3 ,总计约为 : ( 56000 +
4000 + 4000 ) ×3 ×2 = 384000 字节 , 还

需一趟前向扫描 ,假定每棵树的深度为
H ,每个结点拥有的孩子数目为 M , *

均词长为 L , 在最坏情况下 , 查找次数 也小于 N · ,而*均查找次数约为 N/ M
L · ( H ,M ) .相比传统的匹配算法 , min

不到现在普通微机的存储能力 ( 128M ) 的 0. 3 % ,即便再加上其它辅助控制信 息 ,计算机的内存也绰绰有余 , 所以完 备性不再是一个难点 . 再来看匹配速度的问题 ,为提高匹 配速度 , 有人主张将词典按词频排序 , 有人主张先按词的长度分类再按词频 排序 [ 6 ] ,但实际上这都不能从根本上解 决问题 .现在考虑最坏情况 : 某词在词 典中未收录 , 则无论采用哪种排序 , 查 找次 数 均 为 64 000 次 ( 以 常 用 词 , 人 名, 地名和某一专业词库组成的词典为 例) ; 如果匹配算法采用 "长词优先法" , 则每个未成词的单字的查找次数均为
64 000 次 ,这几乎是不可忍受的 .为提

效率有了明显的提高 .
3 歧义处理

无论哪种分词算法 ,都无法回避汉 语中的歧义问题 .长词优先算法只能 在一定程度上减少歧义发生的次数 ,不 能处理歧义问题 .目前通用的方法是 加入语法规则 ,这不仅要求程序有较高 的人工智能 ,而且显著降低了自动分词 的处理速度 .为解决这一弊端 ,笔者在 文献 7 中提出了一种基于词频统计的
[ 歧义处理方法 —— —"易断点分离法"7 ] ,

尾 ,词尾在 ak ( k < n ) 处 , 如何尽快找到 这个 a k 呢 ? 这就需要逐级回溯 , 找到 距离 a n 最 *的词尾进行切分 就 可 以 了 .具体算法如下 :
Proc segment (Astr : string) ;

: =0; i while (i < N) i : = i + 1 ; 【 rt : = search (ai ,Dictionary) ; / / 在字典中查 找以 ai 为根的树 ,返回这棵树的根 reapt i : = i + 1 ; 【 : = find (rt ,ai) ; / / 查找 rt 的所有孩子节 p 点 ,看是否有等于 ai 的节点 / 如果存在这样的节点 ,则 p 指向该 / 节点 ,否则 p 等于 N IL (p = N IL) then loop : = False if 【loop : = True ; rt : = p ; 】/ / 进入 rt 的 else 孩子 ,继续向前匹配 until not loop ; 】 repeat if (ai 是词尾) then 【 【切分词 ; loop : = False ; 】 / / ai 不是词尾 ,需要回溯 else i : = i - 1 ; 【 : = rt^. parent ; / / 退回到父节点 rt loop : = True ; 】 until not loop ; 】 】
ENDP.

该方法不仅对程序的智能要求很低 ( 完 全是机械处理) ,实现起来比较容易 ,而 且效率很高 ( 算法复杂度为线性) ,适合 与上述的匹配算法配合使用 .限于篇 幅 ,不再详细介绍 , 读者可自行参考文 献 7.
4 结束语

高 "长词优先法" 的匹配速度 ,笔者参照 键树 ,提出了 "字符树" 存储法 , 具体方 法如下 : 整个字典为一个森林 ; 每个单 字为一棵树的根结点 ; 以该字为起始的 所有二字词的第二个字均是该根结点 的孩子 ; 其余多字词以此类推 . 例如 "中" 字可以组词 : 中国 , 中国 话, 中国画 , 中国字 , 中国人 , 中国人民 , 中国人民解放军 , 中华 , 中华民族 , 中华 人民共和国 ……,则它构成的 "字符树" 如图 1 所示 .

一个实用的自动分词系统必须在 现行的技术条件下实现 ,囿于目前人工 智能的发展水* ,采用词典法是一条可 行的路径 .笔者采用前述的词典和相 应的匹配算法 , 再辅以易断点分离法 , 实现了一个小型的自动分词实验系统 , 其处理效率和准确率均比较令人满意 .
参 考 文 献
1 苏新宁 . 汉语词切分标引算法的改进 . 情报学

报 ,1996 ; (6)
2 石国华 . 科技文献主题词的自动标引法 . 杭州大

例如 ,句子 "中国人民解放了" 对 , 应的就是上面提到的特殊情形 ,应用上 述算法可以轻易切分为 "中国人民" : , "解放" 了" , " 三个词 , 同仁们可以自行 验证 .
图1

学学报 ,1998 ; (3)
3 . 汉语自动分词研究的现状与新思维 . 现 尹 锋

代图书情报技术 ,1998 ; (4)
4 闫引堂 , 周晓强 . 交集型歧义字段切分方法研

究 . 情报学报 ,2000 ; (6)
5 文庭孝 . 情报检索中汉语语词自动切分研究 . 图

需要指出 "中华" : 是词 "中华人民 , 共和国" 是词 , 但 "中华人" 中华人民 , " 共" 并不是词 ,为了区分这一点 ,需要在 "华" 国" , " 等词的结尾处均加上标志 , 表明它是某个词的末尾 ,也即可作为分 词单位 .显然 ,所有的根节点都可以作

还需要指出的是 ,所有根结点均可 以用哈希杂凑法存储到长度为 20902
( GB K 字 符 集 中 汉 字 的 数 目 ) 的 数 组

书与情报 ,2001 ; (2)
6 黄河燕 ,李渝生 . 上下文相关汉语自动分词及词

中 ,只要哈希函数构造得当 , 那么查找 根结点的时间几乎可以忽略不计 .对 于长度为 N 的字符串 , 采用此方法 , 只

法预处理算法 . 应用科学学报 ,1999 ; (6)
7 ,周经野 . 汉语词汇中的 刘 新 "易断点" 及其黏

结度 . 湘潭大学自然科学学报 ,2002 ; (2)
(责编 :京加勃)

41


相关推荐

最新更新

猜你喜欢