第
39
卷第
2
期
2010
年
3
月
内蒙古师范大学学报(自然科学汉文版)
Journal
of
Inner Mongolia
Normal
University
(Natural
Sc
ience Edition)
基于动态规划算法单字
估价值的中文自动分词研究
李艳秋,李成城
(内蒙古师范大学计算机与信息工程学院,内蒙古呼和浩特
010022)
Vol.
39
No.2
Mar. 2010
摘
要=提出一种基于动态规划算法单字估价值的中文自动分词的研究方法.使用该方法对大量语料进行
统计,通过分析四字词及四字词以下词单字的出现位置和出现次数.把出现概率转换为估价值.根据单字的出现
位置和该位置的估价值,将分词问题转换为决策树求最优解问题,采用动态规划选取最优路径,从而确保切分结
果的整体估价值最优.
关键诩
s
自然语言处理
z
自动分词
z
动态规划
z
估价值
中图分类号:
TP
301
文献标识码
A
文章编号:
1001-8735(2010)02-0202-04
中文自动分词是信息检索、文本校对、机器翻译、语音识别、文本挖掘等研究的前提和基础.由于汉语句
子构成的复杂性和多变性,中文自动分词已成为目前中文信息自动处理的"瓶颈"与西文相比,中文词与词
之间没有明显的分隔标记.因此中文信息处理的首要问题就是将句子中的一个个词分离出来,也就是中文分
词问题
[1-2J
目前,国内外对于中文分词方法的主要研究成果有正向最大匹配法、反向最大匹配方法、分词与词性标
注一体化方法、最佳匹配法等[叫,但对于歧义和未登录词识别两个基本问题仍有待进一步解决
[5-6J
本文提
出一种机器学习的单字在词中的位置的估价值的构词方法,根据词位特性的学习,获得一个概率模型,即把
分词过程视为字在字串中的构词位置问题,运用动态规划思想正向估价词的最优切分点,最后逆向切分.这
样做的一个重要优势在于,它能够平衡地看待词表词和未登录词的识别问题,从而能更好地解决未登录词和
大部分歧义问题.
气
1
动态规划模型
依据动态规划最优化准则[问],"作为整个过程的最优策略具有这样的性质
z
无论过去的状态和决策如
何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略"也就是说,不论前面的状态和策略
如何,以后的最优策略只取决于由最初策略所决定的当前状态,最优决策序列中的任何子序列都是最优的.
假设为了解决某一优化问题,需要依次作出
n
个决策矶
,
D2
,
队,…
,
D.
,
若这个决策序列是最优的,对于任
何一个正数
k
(1
<k<
时,不论前面
h
个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前
状态,即以后的决策
Dk+1
,
DH2'
…
,
D.
也是最优的.
假设给定一个汉字字符串
S
屿,由
n
个汉字组成,
Str.
=W
1
W
2
W
3
......W.(n
注1),将
D
i
(l
ζtζ
n)
定义
为判定仅字
W
i
是一个词末尾投字〈即在
i
处判定一个词结束〉的决策点.根据本文研究四字词及四字词以下
词的范围可知,在字符串
Str.
中每相邻的
4
个汉字必有一个是词末尾字,即相邻的
4
个
Di
(1
~i
运的节点有
一个是必经节点,每一个节点的父节点代表前一个判定词结尾的节点.由于在本文的研究范围内,一个词可
以包含一个字、双字、三字和四字,那么一个节点的父节点的位置应该是在该节点前
1
个字、
2
个字、
3
个字和
收稿日期
I
2009-09-06
基金项目
a
国家自然科学基金资助项目
(2002AAl17010-07)
I
教育部、国家语委民族语言文字规范标准建设及信息化科研项目
(MZl15-022)
作者简介,李艳秋<1
981-)
,女,黑龙江佳木斯人,内蒙古师范大学硕士研究生
通信作者
g
李成城<1
971-}
,男,内蒙古扎兰屯人,内蒙古师范大学副教授,博士,主要从事自然语言理解、自动文摘研究,
E-mail ,
cieclcc@
imnu.
edu.
cn.