总第２５５期 ２０１１年第１期 计算机与数字工程 Ｃｏｍｐｕｔｅｒ＆Ｄｉｇｉｔａｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏｌ＿３９ Ｎｏ．１ １４ 一种改进的基于二元统计的ＨＭＭ分词算法 田思虑Ｄ 李德华 潘 莹＂ ’ ４３００７４）（广西大学信息网络中心 南宁５３０００４） （华中科技大学图像识别与人工智能研究所” 武汉摘要中文分词是中文信息处理的基础。基于二元统计的ＨＭＭ中文分词算法表现良好，但也存在易将包含常用 介、副词的词进行误拆分的问题。改进的分词算法运用逆向最大匹配的思想，在计算粗分集权重的过程中，考虑了分词的词 长及词序对正确切分的有利影响。该算法首先计算出二元统计粗分模型有向边的权值，然后根据词长修定权值，最后运用 最短路径法求出分词结果。实验结果表明，该算法有效的解决了过分拆分的问题，分词效果良好。 关键词中文分词；逆向最大匹配；二元统计模型；ＨＭＭ模型 ＴＰ３１１ 中图分类号Ｉｍｐｒｏｖｅｄ ２一Ｇｒａｍ ＨＭＭ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｃｈｉｎｅｓｅ Ｗｏｒｄ Ｓｅｇｍｅｎｔａｔｉｏｎ Ｔｉａｎ Ｓｉｌｖ Ｌｉ Ｄｅｈｕａ Ｐａｎ Ｙｉｎｇ ’。 （Ｉｎｓｔｉｔｕｔｅ ｆｏｒ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ＆Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ．Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ”．Ｗｕｈａｎ ４３００７４） （Ｉｎｆｏｒｍａｔｉｏｎ Ｎｅｔｗｏｒｋ Ｃｅｎｔｅｒ，Ｇｕａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ２ ，Ｎａｎｎｉｎｇ ５３０００４） Ａｂｓｔｒａｃｔ Ｃｈｉｎｅｓｅ ｗｏｒｄ ｓｅｇｍｅｎｔａｔｉｏｎ ｉｓ ａ ｂａｓｉｃ ｗｏｒｋ ｆｏｒ Ｃｈｉｎｅｓｅ ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ．２－Ｇｒａｍ ＨＭＭ ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｃｈｉｎｅｓｅ ｗｏｒｄ ｓｅｇｍｅｎｔａｔｉｏｎ ｉｓ ｗｉｄｅｌｙ ｕｓｅｄ，ｂｕｔ ｅａｓｙ ｔｏ ｂｒｉｎｇ ｏｎ ｗｒｏｎｇ ａｄｖｅｒｂ ｗｏｒｄ ｓｅｇｍｅｎｔａｔｉｏｎ．Ｕｓｉｎｇ ｒｅｖｅｒｓｅ ｄｉｒｅｃｔｉｏｎａｌ ｍａｘｉｍｕｍ ｍａｔｃｈ ｍｅｔｈｏｄ（ＲＤＭ）ｃａｎ ｌｅｓｓｅｎ ｔｈｅ ｅｒｒｏｒ ｒａｔｅ．Ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｃａｌｃｕｌａｔｉｎｇ ｒｏｕｇｈ ｓｅｇｍｅｎｔａｔｉｏｎ ｓｅｔ，ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ａｄｊｕｓｔｓ ｔｈｅ ｗｅｉｇｈｔｓ ｂｙ ｔｈｅ ｗｏｒｄ ｌｅｎｇｔｈ ａｎｄ ｗｏｒｄｓ ｏｒｄｅｒ ａｎｄ ｏｂｔａｉｎｓ ｔｈｅ ｗｏｒｄ ｓｅｇｍｅｎｔａｔｉｏｎ ｒｅｓｕｌｔ ｗｉｔｈ ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｍｅｔｈｏｄ．Ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｅｒｒｏｒ ｒａｔｅ ｏｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈ ｉｓ ｄｅｃｒｅａｓｅｄ，ａｎｄ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｐｅｒｆｏｒｍｓ ｂｅｔｔｅｒ ｔｈａｎ ｔｈｅ ｏｒｉｇｉｎａ１． Ｋｅｙ Ｗａ￣ｆｌｓ Ｃｈｉｎｅｓｅ ｗｏｒｄ ｓｅｇｍｅｎｔａｔｉｏｎ。ＲＭＭ，２－ｇｒａｍ ｍｏｄｅｌ，ＨＭＭ ｍｏｄｅｌ Ｃｌａｓｓ Ｎｕ｜Ｔ－，ｅｒ ＴＰ３１ １ ｌ 引言 词是最小的能够活动的有意义的语言成 分，是自然语言处理系统中重要的知识载体与基本 计的分词方法；３）基于理解的分词方法。实际使 用的分词系统，都是把机械分词作为一种初分手 段，然后还需通过利用各种其他的语言信息来进一 步提高切分的准确率。 国内最早中文开源分词项目之一的ＩＣＴＣＬＡＳ 开源版系统，它采用的五层隐马尔柯夫模型。此系 操作单元口］。中文分词就是由计算机自动识别文 本中的词边界的过程，它是自然语言理解及中文信 息处理中的一个基础性的工作，是诸如自动翻译、 统在中文分词中取得了良好效果，切分正确率达到 ９７．９６ ［４］。文本检索、语音识别、文本校对以及搜索技术中的 重要组成部分。分词就是将连续的字符串或序列 按照一定的规范重新组合成词序列的过程＿＿２］。中 文分词技术主要分为三类＿３］：１）基于字符串匹配 的分词方法，此方法又称机械分词方法；２）基于统 但是，它也存在一些问题，例如，对由 “上”、“的”等常用介词或副词组成的词如“登上”、 “的确”，有时会将一个词拆分为二。在此背景下， 本文研究了基于二元统计的ＨＭＭ中语言分词模 型，并结合逆向最大匹配的思想提出了一种有效改 收稿日期：２０１０年７月２１日，修回日期：２０１０年８月３０日 作者简介：田思虑，女，硕士，研究方向：人工智能、数据挖掘。 ２０１１年第１期 计算机与数字工程 进算法，取得了更好的分词效果。 率密度分布的状态序列产生。 ２ Ｎ一元统计模型 自然语言可以理解成由一个信源产生的信号 中文分词的～元统计模型中，将信号源抽象 为隐马信号源，也就是采用了二元统计模型。而这 时的Ｍａｒｋｏｖ模型中的状态是我们观察不到的。 而对应正确的切分词的序列就是此隐马模型的真 实序列，而被分词的文本则是此隐马尔柯夫链的观 测值。则在二元统计模型中，中文分词的过程就转 序列，该信源发出的信号就是语言的最小单位一 词。 假设Ｃ 是文本中的一个词，如果已知它在该 词前面的词的序列Ｃ …Ｃ ，便可以用条件概率Ｐ （Ｃ Ｉ Ｃ …ＣＨ）来预测Ｃ 出现的概率。这就是统 化已知隐马模型观测值（文本）求解其真实序列的 值（分词结果）。 计语言模型的概念 。一般来说，如果用变量Ｃ 表示信源产生的词序列，它由顺序排列的 个词组 成，即ｃ—ｃ Ｃｚ… ，则统计语言模型就是该词序 列（、在文本中出现的概率Ｐ（Ｃ）。利用条件概率 的乘积公式，Ｐ（Ｃ）可展开为： Ｐ（０一Ｐ（ ）Ｐ（Ｃ２ ｌＧ）Ｐ（Ｇ ｌ Ｃｌ ）…Ｐ（ ＧＧ…Ｇ） （１） Ｎ元统计语言模型的思想是：一个单词的出现 与其上下文环境中出现的单词序列密切相关，第 个词的出现只与前面７２—１个词相关，而与其它任 何词都不相关，即：Ｐ（Ｃ ｌ ｃ …Ｃ ）＝＝＝Ｐ（Ｃ Ｊ Ｃｒ． …Ｃ ）所以式（１）变为： Ｐ（Ｃ）＝＝＝Ｐ（Ｃ１）Ｐ（Ｃ２ ＩＣ１）…Ｐ（（＝＝， ｌ —Ｎ＋１… １）（２） 不难看出，词序Ｃ出现的概率在于计算Ｐ（ Ｉ Ｇ ・・ 一 ）的值，而它的精确值是未知的，所以 我们利用统计估计，用频率近似逼近： Ｐ（Ｃ ＩＣ 一卅１…Ｃ 一１）≈＿厂（ Ｎ＋１… 一１ ） ／ｆ（Ｃｎ Ｎ＋１…Ｃ｝ｌ一１） （３） 其中厂（ —Ｎ＋ … ）和．厂（ —Ｎ＋ … 一 ）分别 是词 —Ｎ＋ … 和Ｃ 一Ｎ＋ … 一 训练语言模 型时出现在训练语料库中的次数。假定大数定理 成立，只要训练语料库的容量足够大，频率便趋近 概率。 ３基于二元统计的ＨＭＭ分词模型 定义ｌ设随机过程｛Ｘｅ，ｎ∈Ｔ｝，若对任意的 整数 ∈Ｔ和任意的ｉ。，ｉ 一，ｉ ＋ ∈ｊ，条件概率满 足 Ｐ｛Ｘ 一ｉ 『Ｘ０＝ｉｏ，Ｘ１一ｉ１，…，Ｘ １＝ｉ一１｝一 Ｐ｛Ｘ 一ｉ Ｉ 一ｉ ）则称｛Ｘ ， ∈Ｔ｝为马尔可 夫链，简称马氏链ｌ７］。 隐马尔可夫模型是马尔可夫链的一种，它的状 态不能直接观察到，但能通过观测向量序列观察 到，每个观测向量都是通过某些概率密度分布表现 为各种状态，每一个观测向量是由一个具有响应概 记录Ｍａｒｋｏｖ信源产生的词的序列Ｃ的某个 可能分词结果为ｗ一（叫 ，…， ），Ｗ对应的词的 隐状态序列Ｃ一（ｆ ”， ）。我们选择最优的隐状 态序列作为我们的分词结果ｗ ： Ｗ 一ｍａｘＰ（Ｗ） （４） 运用贝叶斯条件公式展开得： Ｗ 一ｍａｘＰ（Ｗ Ｃ）Ｐ（Ｃ） （５） ＨＭＭ模型中，向量值序列对应的观测值序列 的一阶响应： Ｐ（ｗ ｃ）一ｌＪ Ｐ（叫 ） （６） 一１ 运用二元统计模型，将式（６）代入式（５）得到： Ｗ ｍｅｔｘ Ｕ （叫 ）户（ｃ １） （７） ｉ一１ 对式（６）取负对数简化运算： ｌｎｗ ＝ｒａｉｎ∑［一ｔｎｐ（ｗ ｃ ）－－ｌｎｐ（ｃ １）］ 一１ （８） 对ｗ 求解的问题则转化为求此问题的最小值。 对于已收入核心词典的词，Ｐ（叫 Ｉ Ｃ ）一１分词 过程中只考虑未录登词的ｐ（ｗ ｉ Ｃ ）值＿４Ｊ。 ４ 结合逆向最大匹配思想的改进算法 ４．１ ＨＭＭ模型分词结果的不足 使用ＨＭＭ模型进行中文分词的假设是二元 统计模型。它将自然语言简化为一个词Ｃ 只与前 面的一个词ＣＨ相关，并且在语料库中出现词组 ＣＨＣ 的条件概率越高，则赋予取此词的权重越 大。然而在自然语言中，如“的”、“在”、“上”等介词 或副词作为单独一个词的频率较高，因此基于 ＨＭＭ模型的分词方法会有将包含此字的词拆分 的倾向。例如“他说的确实在理”会被拆分为“他／ 说／的／确实／在／理”。其中“在理”就被拆分了。因 此考虑结合逆向最大匹配的方法，保护长词，使同 等条件下，长词更具优势，并且侧重重心在后的词。 田思虑等：一种改进的基于二元统计的ＨＭＭ分词算法 第３９卷 ４．２结合逆向最大匹配方法的改进原理 定义２逆向最大匹配（ＭＭ）对于文本中的字 串ＡＢＣ，Ｃ∈Ｗ，ＢＣ∈Ｗ，ＡＢＣ Ｗ，Ｗ为字典，那 么就取切分Ａ／ＢＣＬ 。 逆向最大匹配的主要思想就是从后前面匹配， 且词长越长，越具优势。 对于文本中的字串ＡＢＣ，在前一个词为Ａ的情 况下，字串分词结果为Ａ／ Ｂ或Ａ／ＢＣ，不仅需要考虑 语料库中Ｐ（ＢＩＡ）和Ｐ（ＢＣｌＡ）的条件概率，还应考虑 后面接的词Ｂ和ＢＣ的词长和位置的因素。多数隋况 下，拆分为Ａ／ＢＣ比Ａ／Ｂ／Ｃ更合适。因此赋予后接 词长的词更小的权值（１ｍ的标记“末＃末”不算）： ，型 一１ｎｗ ＝ｍｉｎ｛∑［、 ｉ＝１ －－ｌｎｐ（ｗｉ Ｊ ｃｉ）－－ｌｎｐ（ｃｉ Ｊ ｃｉ ）］ １ ／ｌｅｎｇ￣（ｗｉ）一ｌ （ ｛ ）一１ （ ｆＣｎ一１）｝ （９） 但若ＢＣ、ＣＤ都为一个词，字串ＡＢＣＤ拆分为 Ａ／Ｂ／ＣｌＤ比Ａ／ＢＣ／Ｄ的确准率更高。因为中文语 言特性，重心在后面，所以逆向匹配的效果较好。 因此，赋予实际分词结果中最后一个词与词长成反 比的权值： ， 一ｌｎｗ ＝ｍｉｎ｛∑［、 ｉ＝１ －－ｌｎｐ（ｗｉ ｌＣｉ）一ｌ （ ｌ 一１）］ ￣ｌｅｎｇｔｈ（ｗｉ）一［１ （ ＩＣｎ）一ｌ （ ｆ 一１）］ １ ／ｌｎｅｇｔｈ（ｗ．一１）｝ （１０） 结合以上两点分析，因此式（１０）即为结合逆向 匹配思想修证后的公值。 ４．３改进后的分词过程 以文本“他说的确实在理”为例，说明改进后的 中文分词过程： １）文本首尾分别加“始＃始”及“末＃末”。则 分词文本修改为“始＃始他说的确实在理末＃末”。 这样二元统计时，连接“始＃始”及其后面一个词的 有向边（即二元词组）的权值表现“始＃始”后面的 词为句首的条件概率，同理连接“末＃末”前面一个 词和“末＃末”的有向边的权值表现“末＃末）前面 一个词为句尾的条件概率。 ２）依据词典全切分修改过的分词文本。切分 结果：始蒜始ｆ他／说／鹋／的确／确／确实／实／实在， 在／在理／理／末＃末。 ３）构造基于二元统计的词法树，如图１所示， 此树的结点为全切分结果的每个词，每个边为二元 逻辑的权值即式（１Ｏ）平滑后的值。 图１二元逻辑的词法树 图２改进后的词法树 此树有向边的意义：如节点“确实”和节点“在” 之间的有向边，用“确实＠在”表示，此边权值的意 义是在前一个词为“确实”的条件下，后一个词是 “在”的权值（由Ｐ（确实ｌ在）转化而来）。 ４）依据词长修正边的权值。对于一条边连结 的两词，考虑后一个词的词长影响，对于实际结尾 的词，即“末＃末”前面一个词，考虑此词词长影响， 修正权值。修正后的词法树如图２所示。 ５）求得此树的最短路径作为粗分集［９３。示例文 本被切分为“始＃始／他／说／的／确实／在理／末＃末”。 ６）末登录词识别。 ７）最终结果。示例文本被切分为“始＃始／他 ／说／的／确实／在理／末＃末”。 ５实验结果分析 表１ 改进算法前后实验结果 测试用例 ＩＣＴＣＬＡＳ开源版系结合逆向最大匹配 统 思想的系统 他说的确实在他／说／的／确实／在／他／说／的／确实／在 理 理 理 这人的确实在这／人／的／确实／在这／人／的确／实在 是哪只手推动是／哪／只／手／推动／是／哪／只／手／推动／ 绿豆价格大跌绿豆／价格／大跌／呢绿豆／价格／大跌／呢 呢？正如当初／？／正／如／当初／有／？／正如／当初／有 有人将绿豆售人／将／绿豆／售价／人／将／绿豆／售价／ 价猛涨归咎于猛涨／归咎／于／故弄猛涨／归咎／于／故弄 故弄玄虚的张玄虚／的／张／悟本／玄虚／的／张／悟本／ 悟本和他那本和／他／那／本／畅销／和／他／那／本／畅销／ 畅销的《把吃出的／《／把／吃／出来／的／《／把／吃／出来／ 来的病再吃回的／病／再／吃／回去的／病／ｉ￣ｉ／吃／回去 去》一样，如今／》／一样／，／如今／也／》／一样／，／如今／也 也南入将绿豆／有人ｆ将７绿豆ｆ大ｆ ７奄人／将７绿豆７大／ 大跌价归功于跌价／归功／于／“／张跌价／归功／于／“／张 “张悟本神话”／Ｎ／本／神话／”／的／／悟／本／神话／”／的／ 的破灭。 破灭／。 破灭／。 （下转第２Ｏ页） 曾琳等：基于ＲＢＦ神经网络的智能ＰＩＤ控制算法 第３９卷 自整定后的仿真结果。 保证其它工艺条件的情况下，提高了产品的质量， 降低了能耗，具有一定的经济技术效益。 参考文献 Ｅ１］王耀南．智能控制系统ＥＭ］．长沙：湖南大学出版社， ２００６，７：１８０～２０５ Ｅ２３何克忠，李伟．计算机控制系统［Ｍ］．北京：清华大学出 版社，２００４，１：２６３￣２６５ （ｂ） Ｅ３］刘金琨．先进ＰＩＤ控制及ＭＡＴＬＡＢ仿真［Ｍ］．北京：电 子工业出版社，２００３，１：１０４－－１１１ 图６仿真结果 Ｅ４］王学雷，邵惠鹤，李亚芬．一种径向基函数神经网络在 ６ 结语 从仿真结果图６中可以看出，图６（ａ）有超调且 在８０ｓ之前都有振荡现象存在；而图６（ｂ）在３５ｓ左 线训练算法及其在非线性控制中的应用ＥＪ］．信息与控 制，２００１（６）：２４９￣２５３ Ｅｓ３余丽平．基于虚拟仪器的电阻炉智能温度控制系统的 研究［Ｄ］．西安：西安建筑科技大学硕士学位论文，２００７ 右就可以无偏差的跟踪设定值，这说明本文使用的 控制方法可以给出很好的辩识结果，既消除了系统 Ｅ６３王春民，刘兴明，嵇艳鞠．连续与离散控制系统ＥＭ３．北 京：科学出版社，２００８：４９１￣－４９４ 由于大时滞引起的超调振荡现象，得到了很好的动 态特性曲线，而且控制效果稳定、快速。此控制算 法已投放入到温度控制系统的研发中，实验表明， Ｅ７］王中杰，柴天佑，邵诚．基于ＲＢＦ神经网络的加热炉钢 温预报模型ＥＪ］．系统仿真学报，１９９９（６）：１８１￣１８４ Ｅ８］葛哲学，孙志强．神经网络理论与ＭＡＴＬＡＢ２００７实现 ［Ｍ］．北京：电子工业出版社，２００７，９：１１７￣１２６ 本系统有较好的控制和跟踪性能，控制精度高，在 ４ ｋ ｄ０ ｋ ‘ 、’ Ｅ ｌ Ⅳ （上接第１６页） 为了考查改进算法的效果，选取了两常用示例 及从网上任意找的新闻中的一段语句运用基于 参考文献 ＨＭＭ模型分词算法和运用逆向最大匹配改进后 算法进行分词。实验结果如表１所示。比较两算 法的实验结果，原算法对常用副词、介词有错分、错 拆情况。改进后的算法有效改善了情况，取得到了 更好的分词效果。如上面三例中：“在理”、“实在”、 Ｅ１］徐飞，孙劲光．中文分词切分技术研究［Ｊ］．计算机工程 与科学，２００８，３０（５）：１２６￣１２８ Ｅｚ］朱巧明，李培峰．中文信息处理技术教程ＥＭ３．北京：清 华大学出版社，２００５ Ｅ３］赵泉．信息检索ＥＭ］．北京：机械工业出版社，２００８ Ｅ４］刘群，张华平，俞鸿魁，等．基于层叠隐马模型的汉语词 法分析ＥＪ］．计算机研究与发展，２００４，４１（８）：１４２１￣１４２９ “正如”这三词，原算法误分或误拆，而改进后的算 法则得到了正确的切分结果。 Ｅ５３徐望，王炳锡．Ｎ－ｇｒａｍ语言模型中的插值平滑技术研 究［Ｊ］．信息工程大学学报，２００２，３（４）：１３￣１５ ［６３高山，张艳，徐波，等．基于三元统计模型的汉语分词及 标注一体化研究Ｅｃ］／／自然语言理解与机器翻译一全 国第六届计算语言合学术会议论文集，２００１ Ｅ７］刘次华．随机过程ＥＭ］．武汉：华中科技大学出版社， ２００５ ６ 结语 中文分词是自然语言处理的基础性工作，本文 在保留ＨＭＭ中文分词模型的二元逻辑优势的基 础上，提出了一种结合逆向最大匹配方法的中文分 词改进算法，该算法考虑了词长及词序对分词效果 的影响，有效的解决了ＨＭＭ分词模型中的拆分过 分问题。随机选取的文本分词实验结果表明，算法 取得了良好的分词效果，这为下一步进行文本检索 以及文本聚类的工作奠定了基础。 Ｅ８３翟凤文，赫枫龄，左万利．字典与统计相结合的中文分 词方法ＥＪ］．小型微型计算机工系统，２００６，２７（９）：１７６６ ～１７７１ Ｅｇ］张华平，刘群．Ｎ‘最短路径方法的中文词语粗分模型 ［Ｊ］．中文信息学报，２００２，１６（５）：１～７
