（计算机应用技术专业论文）基于统计语言模型的手机中文输入系统的研究与实现.pdf

基于统计语言模型的手机中文输入系统的研究与实现中文摘要 中文摘要 智能中文输入技术在桌面平台已经得到了广泛的应用，通过研究手 机平台汉字输入的特点，本文将智能输入技术引入到手机平台上，并在 手机平台上实现了以二元概率为基础的整句预测输出。 本文首先描述了对一种较为流行的数码输入法编码规则的改进方 法，介绍了智能输入技术中普遍采用的n 元语法模型以及两种常用的数 据平滑算法，并给出了一个记忆用户输入习惯的自学习模型。然后，详 细描述了上述数码中文输入系统中各类数据文件的存储结构及相关查找 算法，在设计这些数据结构和算法时，充分考虑了手机资源的有限性。 在此基础上，着重说明了实现整句输入的预测算法，该算法利用了正整 数拆分表提高了执行效率。在介绍了s y m b i a n 平台的输入法接口与系统 特性后，本文详细描述了基于该平台实现上述手机中文输入系统的过程， 并就测试情况作了说明。 在系统实现过程中，根据手机上文字输入的特点，本文以电影人物 对白作为二元数据文件的统计来源。测试结果表明，该系统在口语输入 的环境下达到了较好的实用水平。本文将统计语言模型运用到手机输入 系统中，具有较大的实用价值。 关键词：中文输入法：统计语言模型；口语语料；自学习模型；s y m b i a n 作者：韩卓平 导师：杨季文 a b s t r a c tt h ed e s 哳a n d 岫l e r e a to fa 岫i l 蕾0 1 i | 嘲坤ns y s t 锄胁谢ms t a t i s t i c a lt m g u 印y 战i e l t h ed e s i g na n di m p l e m e n to fam o b i l e s c h i n e s e i n p u ts y s t e mb a s e do ns t a t i s t i c a ll a n g u a g em o d e l a b s t r a c t i n t e l l i g e n tc h i n e s ei n p u tt e c h n o l o g y ( i c i t ) h a sb e e nw i d e l yu s e di n d e s k t o pc o m p u t e r s ，b yr e s e a r c h i n gt h ec h a r a c t e r i s t i c so ft h ec h i n e s ei n p u to n m o b i l e s ，t h i sp a p e ri m p o r t st h ei c i tt ot h em o b i l ep l a t f o r m ，a n di m p l e m e n t s t h es e n t e n t i a lf o r e c a s tb yc a l c u l a t i n gt h ed u a l i t yp r o b a b i l i t y f i r s t ，t h i s t h e s i sd e s c r i b e sai m p r o v e dm e t h o dw h i c hd i g i t a l i n p u t m e t h o d ，i n t r o d u c et h en - g r a mm o d e lw h i c hi sw i d e l yu s e di ni n t e l l i g e n ti n p u t t e c h n o l o g ya n dt w oc o m m o ns m o o t h i n gm e t h o d ，a n dp r e s e n t sas e l f - s t u d y m o d e l w h i c hc a nr e n m e m b e ru s e r s i n p u th a b i t t h e n ，t h ep a p e rf u l l y d e s c r i b e st h es t o r a g es t r u c t u r ea n dc o r r e l a t i v es e a r c ha r i t h m e t i co ft h ed a t a f i l e su s e db yt h ec h i n e s ei n p u ts y s t e m w h e nd e s i g n i n gt h e s ed a t as t r u c t u r e a n da r i t h m e t i c ，t h el i m i t a t i o no ft h em o b l i e sw a sf u l l yc o n s i d e r e d b a s eo nt h e a n a l y s i sa b o v e ，t h ep a p e re m p h a s i so nt h ef o r e c a s ta r i t h m e t i co fs e n t e n t i a l i n p u t ，w h i c hu s e st h ep o s i t i v e - i n t e g e rs p l i tt a b l et oi m p r o v et h ep e r f o r m a n c e a f t e ri n t r o d u c e st h ei n p u tm e t h o da n dt h ec h a r a c t e r i s t i c so ft h es y m b i a n p l a t f o r m ，t h ep a p e rd e s c r i b e st h ep r o g r e s so fi m p l e m e n tt h ei n p u ts y s t e m a b o v e ，a n dr e f e r st ot h et e s t sp e r f o r m a n c eo f i t a c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h et e x ti n p u to n t h em o b i l e s ，t h i s p a p e ru s e st h em o v i ed i a l o g a st h es t a t i s t i cs o u r c eo ft h ed a t af i l e t h e e x p e r i m e n t a lr e s u l t ss h o wt h a ti nt h eo r a lc o n d i t i o n ，t h es y s t e mg e t s a p r e f e r a b l ep e r f o r m a n c e t h i sp a p e ra p p l i e st h es t a t i s t i c a ll a n g u a g em o d e lt o t h em o b i l e si n p u ts y s t e m ，w h i c hw i l lb eo f g r e a tp r a c t i c a ls i g n i f m c a n c e k e y w o r d s ：c h i n e s ei n p u tm e t h o d ；s t a t i s t i c a ll a n g u a g em o d e l ；o r a lc o r p u s ； s e l f - s t u d yl a n g u a g em o d e l ；s y m b i a n w r i t t e nb yh a nz h u o p i n g s u p e r v i s e db yy a n gj i w e n 1 1 0； il辐疆疆s，；i列描匍铷，i；7， o x9 5 7 16 3 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：垒望垩日期：宴些：三：! 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 沦文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：堡皇壬 日期：型：妄! 至 导师签名拯日期： 基于统计语言模型的手机中文输入系统的研究与实现 第一章引言 1 1 课题的背景与意义 1 1 1 课题背景 第一章引言 近年来，我国的手机用户数量以惊人的速度增长。回顾历史，从9 0 年代初的数量很少且体型硕大的“大哥大”，到如今各个城市街头随处可 见的各式手机，手机已经完全成为大众化的商品。截至2 0 0 5 年9 月底， 中国的手机用户数已达3 7 7 亿，相当于每i 0 0 个人拥有2 9 部手机，中 国已经成为拥有世界上最大的手机市场的国家( 中国电信产业部统计数 据) o 在手机用户数得到快速增长的同时，而手机终端的功能也从最早的 单一语音通话，逐步发展到手机短信，订阅资讯，手机上网，玩手机游 戏，下载各种软件等各种多样化的服务。 与移动业务的飞速发展相比，手机输入法的研究进程则略显缓慢。 目前手机上使用数字键盘的传统中文输入法如t 9 ，i t a p 及字能输入法等， 还都是以单字的方式进行输入，这极大地限制了中文输入的速度。因此， 研究针对手机的智能中文输入也显得越来越有实际意义。手写汉字输入 已经不容忽视地成了手机输入法的另一发展方向，与其他手机输入法相 比，手写输入在易用性方面具有很大的优势，但手写输入往往需要用户 双手操作，不如单手的数码输入方便，另外，由于用户经常需要在一系 列笔形相似的汉字中进行选择，在输入速度上不能得到有效提高。语音 输入也有其优越的一面，但其缺点也同样明显，它对使用场合有一定的 要求，因此也无法完全代替数字键盘的汉字输入。可见，传统的数码汉 字输入还是目前的主流。 在过去，一般手机都使用封闭的操作系统，不开放编程接口，自然 第一章引言基于统计语言模型的手机中文辅l 入系统的研冗与买现 也不支持第三方的输入法。随着手机终端功能的不断增强，市场上出现 了一种新型手机。与普通手机相比，它们具备更强大的功能，具体表现 在它采用更高频率的c p u ，更高分辨率的显示屏，以及支持各种第三方应 用软件。在市场价格不断下降的情况下，智能手机逐渐得到大众化，特 别是3 g 网络业务的即将商用，必将极大地推进智能手机的普及。 目前，市场上已经出现了一些针对智能手机开发的第三方汉字输入 法，如中文之星手机输入法。这类输入法在手机中实现了词语输入甚至 语句级的中文输入，并提供了简单的自学习功能，大大加快了手机输入 速度。但在策略上，这类输入法还是根据候选字词的一元频率来调整字 词的出现顺序。而目前在桌面p c 中已经广泛使用的智能中文输入技术， 由于其大量的数据需求，还未能在手机中得到有效应用。为了充分挖掘 智能手机的强大处理功能，有必要开发基于手机平台的智能中文输入法。 1 1 2 课题内容 鉴于以上课题背景，本文将研究现有智能中文输入的技术，将其移 植到手机平台上，并以纵横汉字输入法为实例，选择一个手机平台进行 实现。 要实现的输入法主要有以下功能： 1 ) 支持字，词方式的汉字输入； 2 ) 能够以整句输入的方式进行汉字的连续输入； 3 ) 运用二元语法模型，对输入码进行语句级的智能预测输出； 4 ) 有自学习功能，能够对用户的输入习惯进行记忆； 1 1 3 课题意义 课题的实现有如下现实意义； 1 ) 首次将桌面计算机中使用的智能输入技术引入到了手机终端上， 极大地提高了手机汉字输入的速度，从而给手机用户带来全新的 基于统计语言模型的手机中文输入系统的研究与实现第一章引言 输入体验。 2 ) 有利于打破目前国外输入法垄断的局面。当前不管是t 9 ，i t a p ， 还是字能输入法，都是由国外巨头开发，这三大输入法占据了市 场的9 0 以上份额。而国内手机厂商每生产一部使用如上输入法 的手机，就要支付一定数额的使用费。如果能开发出性能更加优 越的国产手机输入法，则可以节省国内手机厂商的不少开销。 3 ) 促进手机应用的进一步普及化。手机正日益走向智能化和综合 化，逐渐地具备了计算机的功能。在保持体积小的优势下，人们 也越来越期望能够通过手机处理w o r d 文件、发送e - m a i l 等。而 传统单字输入的方式在这种需求下显得明显不足。如果能够在手 机上快速高效地输入汉字，则可以迸一步促进这类应用的普及。 4 ) 为日后开发针对手机终端输入法的从业人员提供参考依据，减少 部分工作量。 1 2 本文的工作 1 2 1 改进输入规则 在目前的数码输入法中，各个单字的编码都是由数字组成的，在组 成词语时，这些单字的编码之间没有直接的切分规则。而在拼音编码规 则下，几乎每个汉字的拼音都是由声母和韵母组成，能够自动把输入 编码切分成拼音串。为了能够更好地利用智能输入技术，本系统使用了 定长码的方式，从而使输入码串可以根据长度被切分为各个单字的编码。 1 2 2 建立动态自学习语言模型 为了对用户输入的输入码串能给出一个比较好的预测输出，本文建 立了一种基于统计的动态自学习语言模型来预测用户当前可能要输入的 内容。首先根据二元语法模型从原始语料中得到一个通用二元数据文件， 第一苹引言基于统计语盲模型的手机中文输入系统的研咒与实现 利用文件中保存的各个字词之间的相关度来预测输出。但这单一不变的 数据对于输入习惯各不相同的用户而言是远远不够的。因此，本文利用 用户输入的历史数据对输入法进行训练，在用户使用输入法的过程中， 不断地根据用户输入来调整字词之间的相关度，这包括对通用二元信息 文件中原有二元项的修改，以及对用户二元信息文件中新二元项的添加， 删除与更新等操作，从而达到逐步适应用户的输入习惯的目的。 1 2 3 文件设计与查找 在桌面计算机的输入法中，实现整句输入所使用的数据往往都很庞 大，少则几十兆，多则数百兆，这对于拥有高容量磁盘的桌面计算机来 说可能不是问题，但对于存储空间有限的手机而言，却是完全不能接受 的。另外，过多的数据量在计算预测输出时也会给c p u 造成大量的负担。 因此对于手机平台而言，必须设计紧凑高效的数据文件设计结构，从而 使智能输入技术能够在手机上得到有效应用。 本文将算法与文件结构相结合，对实现智能输入所需要的各类文件 设计，以及所使用的各种算法进行了详细的介绍。 1 2 4 目标平台的实现 最后，利用本文所设计的模型，在s y m b i a n 平台上实现了一个智能 输入法的实例。本文通过分析s y m b i a n 的输入法接口与特点，给出了一 个基于客户端服务器端的设计框架，并对各个功能分别进行了编码实 现。为了使输入法能在目标平台流畅运行，本文在编码时进行了大量的 优化。最终，本文对这个输入法进行了测试。 1 3 本文的组织结构 第一章，介绍了课题的背景与意义以及本文的工作安排。 笫二章，介绍了与设计目标相关的基础工作，包括对编码规则的改 基于统计语宙模型的手机中文输入系统的研究与实现 第一苹引百 进，智能输入技术的介绍，并提出了一个输入法的自学习模型。 第三章，介绍了输入法所使用的文件结构设计以及在此基础上的文 件查找算法。 第四章，简要介绍了s y m b i a n 开发平台的构架，并对输入法的客户 端和服务器端分别进行了设计与实现。 第五章，简单演示了输入法的运行效果并对其性能进行了测试。 第六章，对本文所做的工作进行了简要总结和展望。 第二章相关菇础工作 基于统计语言模型的手机中文输入系统的研究与实现 第二章相关基础工作 2 1 编码方案的改进 在手机设备上，由于手机本身体积的限制，往往只采用了数字键盘， 数字键盘的特点是仅由“0 ”“9 ”以及一些必需的功能键组成，而2 6 个英文字母则被分散到各个数字键上。在这种情况下，使用字母编码的 输入法受到了很大的限制。与之相比，采用数字编码的输入法则拥有了 天然的优势。 本文将以纵横输入码为例，在手机平台上设计一个数字编码的智能 中文输入法。 在拼音码规则中，几乎每一个字的拼音都由声母和韵母组成，根据 这一点，能够把输入码串正确地切分成拼音串。例如“大学”，它的输入 码是“d a x u e ”，根据声母和韵母，可以将它正确地切分成“d a lx u e ”，这 对大部分拼音编码都是适用的，只有少量编码需要通过人为的方式手动 输入分隔，如输入码“x i a n ”，可以被切分为“x il a n ”，如对应词语“西 安”，也可以不进行切分，如对应单字“先”。 但在数码输入法中，字的编码都是由0 9 十个数字组成，字编码之 间没有可遵循的方式进行切分。而整句输入时，用户需要连续输入若干 汉字的编码串，如何切分这个编码串就成了首要的问题。因此，需要对 原有编码方案进行改进。 2 1 1 原有编码规则 这里，本文先简单介绍下原有纵横输入法的编码方案。 1 ) 字编码规则 纵横码把笔形分为1 0 类，分别用“0 ”到“9 ”这1 0 个数字表示。 笔形与数字代码的关系可通过下列口诀表达：一横二竖三点捺，叉四插 基于统计语言模型的手机中文输入系统的研究与实现第二苹相关基础工作 五方块六；七角八八九是小，撇与左钩都是零。 在获取单字的编码时，将该汉字看成一个方块字，取汉字四个角的 笔形为单字编码，取码次序为：左上，右上，左下，右下。在不足四码 的情况下，则补空。 2 ) 词编码规则 词组分为二字词组、三字词组、四字词组及多字词组，每类词组取 码最多为六码，下面详细介绍词组的取码方法。 二字词组取码法是以每个字的纵横码前三码连在一起( 3 + 3 ) 。如 果其中单字只有一码或二码，便全取其编码而不用补上任何编 码。二字词组码长最长为六码，最少为二码。 三字词组，取每一个字纵横码的第一及第二码( 2 + 2 + 2 ) 。如果一 个单字只有一码可取时，就只取一码而不用补上任何编码。 四字词组，先取第一个字纵横码的第一及第二码，再取第二字及 第三字的第一码，最后取第四字第一及第二码( 2 + 1 + 1 + 2 ) 。如果 第一或第四个字只有一码可取时，就只取一码而不用补上任何编 码。 。 五字或五字以上词组，都只是对前五个字取码，第一个字取第一 及第二码，后四个字均取纵横码的第一码( 2 + l + l + 1 + 1o 如果第 一个字只有一码可取时，就只取一码而不用补上任何编码。 2 1 2 改进后的编码规则 观察拼音编码的规则，发现其单字编码可以通过声母加韵母方式获 得，而词编码则由各个单字编码的连接而成。这种方式十分适合整句输 入，因为在这种情况下，一个单字的编码既可以独立对应一个单字，与 前后候选字词进行连接，也可以和前导编码相结合，或者与后置编码相 结合而形成一个词语。但在当前纵横码成词规则下，这是无法实现的。 因此，在对原有编码规则进行改进的时候，要充分考虑到成词规则的修 改。 第二章相关基础工作基于统计语言模型的手机中文输入系统韵研冗与实现 1 ) 字编码规则 为了使数字编码也有单独的切分规则，可以通过如下两种方式来实 现： 添加结束符； 使用定长编码，长度不足时，用不同于“o ”“9 ”固定编码补 满； 显然，使用结束符的方式会导致平均码长加1 ，而在使用定长编码方 式的情况下，设定长码的长度为l ，则平均码长也为l 。 下面是采用不同改进方案下，输入法的平均码长和平均重码率的统 计数据，详细信息见表2 1 。 表2 1 不同方案下的输入码的平均码长和平均重码率 编码方案平均码长平均重码率 原有编码方案 3 72 7 4 添加结束符 4 72 7 4 定长码，l = 2 ，取第l ，2 码 26 2 0 定长码，l = 2 ，取第1 ，3 码 26 1 5 定长码，l = 2 ，取第1 ，4 码 26 2 o 定长码，l = 3 ，取前3 码 3 8 1 定长码，l = 4 42 7 4 从表中可见，当取定长码l ：2 时，平均重码率超过了6 0 ，在输入生 僻字的时候，可能需要用户进行多次翻页，这将极大地影响输入法的整 体表现。当取定长码l = 3 时，尽管重码率还是比较高( 约为8 1 ) ，但在 引入了智能输入技术后，可以预期输入法应该能有更好的表现。而如过 采用添加分隔符的方式，平均码长比定长3 码增加了2 3 3 。 因此，本系统采用了定长码l = 3 的改进方式，即单字编码取原来纵 横编码的前3 码，不足3 码时用键盘上的“术”键补全。 2 ) 词编码规则 参考拼音输入码的方式，本文在改进后的纵横码规则中的词编码设 基于统计语言模型的手机中文输入系统的研究与实现第二章相关基础工作 为各个单字的编码连接，以便整句输入的实现。 在这种方式下，输入码的切分变得非常简便：由于每3 个编码对应 一个单字，只需进行等长切分即可。如用户输入编码2 5 8 6 6 3 5 4 4 5 9 0 ，输 入码被自动切分成2 5 8 f 6 6 3 i5 4 4 f 5 9 0 。 2 2n 元语法模型与数据平滑 2 2 1n 元语法模型 在智能输入法中经常需要根据当前甚至以往输入的词来预测下一个 词，这种预测可以用条件概率p 表示： p ( w 。1w l w n i )( 公式2 1 ) 这种根据前玎一1 个已经出现的词来预测第疗个词的模型称为n 元语法 模型( 也称为一一1 阶马尔可夫模型) ，该模型在智能输入法中有着广泛 的应用，模型中有 。 p ( 1w l w + n - 。) = 兰掣( 公式2 2 ) p t w l 一l j 在智能输入法中，这个公式表示第行项候选字词的出现概率取决于前 行一1 个字词项。 如果用最大似然估计( m l e ) 来估计p 的值，则： p 脚( w l ) = 垡掣 ( 公式2 3 ) 刖w 。lw i 。w n _ i ) = 糕= 爵器( 从式2 4 ， 可以从大规模语料进行统计，用这一项字词项连续出现的次数来近似 估算它们的概率。 理论上，”值越大，计算出来p 的值越贴近实际应用。但这种方式需 要保存大量的数据，且随着一的增加，数据量将以指数级增长。如果输入 法使用的字词库有k 个字词项，则所需的数据量为k 的n 阶幂。由于数据 量过大，在实际应用中，n 的取值往往设为2 或3 。 第二章相关基础工作基于统计语官模型的手机中文输入系统的研究与实现 由于本文的输入法是针对手机平台而设计的，考虑到设备的存储空 间和处理能力，本文选用了二元语法模型，即n = 2 的情况。 在使用了二元语法模型后，对符合输入码串的候选字w t ，w 2 ， 可以通过如下公式计算w l ，w 2 ，连续出现的概率。 p = p ( w 1 ) p ( w 21w 1 ) p ( w 3i ) p ( i 一1 )( 公式2 5 ) 2 2 2 数据平滑处理 在获取概率数据的过程中，本文使用了最大似然估计的方法近似估 算，但这种方法有一个缺点：再大的语料库，其规模也是有限的，它不可 能包含所有事件的出现情况。因此，最大似然估计的方法只统计了在语 料中已出现事件的概率，对于语料中未出现事件的概率则都设为了0 。根 据公式2 5 ，在计算p 的过程中，若有一个二元项p ( k l w k 。) = o ，则无论 其他二元项组合的概率有多大，计算结果p 必然为0 。这样的结果是不合 理的。为了解决这个问题，本文引入了数据平滑技术。 数据平滑的基本思想：调整最大似然估计的概率值，使零概率增值， 使大概率下调，消除零概率，“劫富济贫”，改进模型的整体正确率。 目前，数据平滑有多种方法，哈佛大学的c h e n 和g o o d m a n 对各种 平滑算法进行的研究和比较，发现使用二元语法( b i g r a m ) 模型从大量 语料中统计时使用c h u r c h - g a l e n l 平滑算法效果较好，而k a t z 口1 平滑算法 对于从小的语料中统计的二元语法模型效果较好。 无论是c h u r c h - g a l e 平滑算法还是k a t z 平滑算法，都与 g o o d - t u r i n g h l 估计有着密切关系，所以在介绍它们之前先简单地看一下 g o o d - t u r i n g 估计。 2 2 3g o o d - t u r i n g 估计 最大似然估计( m l e ) 高估了已出现事件的概率，低估了未出现事件 的概率。数据平滑就是重新分配这些事件的概率把已出现事件概率 基于统计语官模型的手机中文输入系统的研究与实现 第二章相关基础工作 的部分值分配给未出现事件。g o o d t u r i n g 估计对于n 元语法模型中出现 ，次的事件使用r + 表示，r + 的计算如公式2 6 所示： 一：( ，+ 1 ) 监 刀， ( 公式2 6 ) ，l ，表示出现r 次事件的个数。对于一个在n - g r a m 中出现，次的事件口 的概率可以使用公式2 7 计算： 尼r o ) 2 吾2 萎n r r * ) 公式2 7 由于 = ，z ，r + = n r ( r + 1 ) 竿= ( r + 1 ) 一川= 埘，( 公式2 8 ) r = or = o，一r = or = l 所以公式2 7 中的和原有统计的事件总次数相同。因为当疗，= 0 时 不能使用g o o d t u r i n g 估计，所以通常需要对n ，本身进行平滑。就是要 调整，z ，使所有的刀，都不为零，g a l e 和s a m p s o n 提出了一种平滑n ，的简单 方法。 2 2 5k a t z 平滑算法 k a t z 平滑是一种在g o o d - t u r i n g 估计的基础上组合低阶n - g r a m 和高 阶n - g r a m 插值的平滑算法。这里只讨论在二元模型上的k a t z 平滑算法。 对于一个出现，：c ( 吨) 次的二元模型w - ，可以使用公式2 9 计算次数。 c 肠。c 以。，= 口。w 一。0 2 。，蓼孑三曷 c 公式2 9 ， 对于所有已出现事件( r 0 ) 使用一个折扣系数d r ( ，+ 是g o o d t u r i n g 估计，参见公式2 6 ) 。从已出现事件折扣下来的计数按着低阶模型( 在 这里是一元模型，u n i g r a m ) 分配给未出现事件( ，= 0 ) 。口( w f 一。) 选择的 标准是保持总的次数不变，有公式 c k a 。( 比) = c ( 以。) ( 公式2 1 0 ) 笫二章相关赫础工作基于统计语言模型的手机中文输入系统的研究与实现 a ( w l _ 。) 的取值如公式2 11 所示。 帆，= 专箸= 簧措 ( 公式2 1 1 ) 这样可以使用公式2 1 2 来计算二元模型的概率。 刖小。2 端 ( 公龃1 2 ) 下面讨论折扣系数d r 的计算方法。出现次数( r ) 多的二元组( w t ) 比较可靠，不需要打折。因此可以设置一个阀值k ( k a t z 建议k = 5 ) ，对 于， k 的二元组，t = 1 ；对于r s k 的二元组，使用g o o d t u r i n g 估计计 算d r 。d ，产生的折扣数量与g o o d t u r i n g 估计预测的折扣数量成正比， 如公式2 1 3 所示。另外，所有的二元组折扣出来的数量总和等于根据 g o o d t u r i n g 估计赋予零概率的数量总和，如公式2 1 4 所示。 l 一4 = ( 1 一二一) i s ，k( 公式2 1 3 ) 喜_ ( 1 - d r ) r = ，l 。胪= 丽n l = 以- ( 公式2 1 4 ) 最后得到折扣系数矾的计算公式如2 1 5 所示， 2 1 3 和2 1 4 的限制。 尘一竺! 独丛 咖2 i r 匾n t 甩l 2 2 6c h u r c h g a l e 平滑算法 这个公式满足公式 ( 公式2 1 5 ) c h u r c h 和g a l e 描述了与k a t z 类似的平滑算法，同样是在 g o o d t u r i n g 估计的基础上组合低阶n - g r a m 和高阶n - g r a m 插值的平滑算 基于统计语言模型的手机中文输入系统的研究与实现第二苹相关基v s n - 作 法。这里同样也只讨论b i g r a m 模型。根据g o o d - t u r i n g 估计，出现次数 为，的二元组使用，+ 来表示( 参见公式2 6 ) 。这样r = o 的所有二元组都 被赋予了相同的次数，不太合理，应该考虑相应的一元频率。插值模型 对出现次数为0 的二元组的赋值方法如公式2 1 6 所示。 p ( w fw f 1 ) 芘p ( w i )( 公式2 1 6 ) 为了把概率转换成出现次数，可以乘上二元组的总数，即： p ( w fw l 1 ) c ( 畦1 ) 芘p ( w f ) c ( 幢1 ) = p ( w f ) c ( w f 一。) 芘p ( w f ) p ( w 一i ) 叶 ( 公式2 1 7 ) 这样对于出现次数为0 的二元组w j 的次数就可以根据p ( ) p ( w f 一。) 来 估计。在c h u r c h g a l e 平滑算法中根据j 口。( w ) p 。( w - ) 的值对咄。进行划 分，属于同一个子段的所有二元组被分配在一个桶内。对于每个这样的 桶使用g o o d - t u r i n g 估计，设n 。，为b 桶上的二元组中出现次数为r 的数 日，则某个桶b 上的一个二元组次数( 使用n 表示) 的修正值为： ：( 屹+ 1 ) 堑 ，z 6 ， 2 3 自学习模型设计 2 3 1 自学习模型的结构 ( 公式2 1 8 ) 、通过对大量文本进行统计，并使用数据平滑技术可以得到一个优秀 的通用语言模型。然而由于不同用户的输入习惯存在着较大的差异，为 了使语言模型更加人性化，需要建立一种能够根据用户输入的历史信息 数据来统计该用户输入习惯的语言模型。 这类个性化信息可以在用户使用输入法的过程中获得。利用用户输 入的历史数据，对数据文件中的二元项进行修改，对于那些原本不存在 的二元信息，则将其保存到一个用户二元信息文件中。因此，在对用户 历史数据的学习过程中，语言模型的任务包括对通用二元信息文件的修 改以及用户二元信息文件中二元项的添加，删除与更新。通过这种方式， 第二章相关基础工作基于统计语言模型的手机中文输入系统的研究与实现 用户的输入习惯可以逐渐被反馈到数据文件中，从而使这个输入模型能 够适应用户的输入习惯。 因此，得出自学习模型如图： 图2 1 输入法自学习模型 说明： 1 ) 在初始状态，通用二元信息文件从对口语语料进行统计获得，而 用户二元信息文件则是一个空文件。 2 ) 在使用过程中，输入法根据通用二元信息文件和用户二元信息文 件中的数据对用户输入的编码进行预测输出。用户的最终选择将被反馈 到数据文件中，包括对通用二元信息文件中数据的修改，用户二元信息 文件中二元项的添加，删除与更新。 2 3 2 概率的动态调整 在二元语法模型中，对于指定词w 有一个基本的约束，即它的所有二 元项的概率之和必须为1 ，即 _ p ( l m ) = 1 卢l ( 公式2 1 9 ) 因此，自学习过程中对概率的调整也必须符合这个约束。现在假设 词w 有s 个二元项，其概率分别为只，尸2 ，p s 。可知 只+ p 2 + + b = 1( 公式2 2 0 ) 如果现在要对概率只进行放大，设放大倍数为k ，则对于w f ，它的全 部二元项的概率和增加了( k 一1 ) 只，为了符合( 公式2 1 9 ) 的约束，需 基于统计语盲模型的手机中文输入系统的研究与实现第二章相关基础工作 要将这( 足一1 ) 只分摊到其余s 1 个二元项概率中去。 在分摊过程中，需要参考原来各个概率的大小来确定分摊比例，因 此，概率p f 分摊到的增量为等三净曰，此时只b 卑一等半异，即 尸百1 - p , k ，此时计算w 的全部二元项概率之和 脚喜只脊邓+ 脊喜纠k + i - 耻 可见，这种方法在提升了p 的同时，仍然保证了( 公式2 2 0 ) 的约 束条件。其中，放大系数k 决定了模型对用户输入习惯的吸收速度。另 外，为了防止p 在提升过程中超过1 ，必须符合如下条件： 1 ) 过程放大系数k 必须小于2 ： 2 ) 如果只= m a x z p ，即只已经是最大概率，则不对只做放大处理； 在这种方式下，对二元概率只的放大会导致其余二元项概率的降低， 随着用户的不断使用，用户经常使用的二元项的概率会逐渐提升，而不 使用或相对很少使用的二元项的概率则会逐渐下降，从而更好地适应用 户的输入习惯。 2 4 本章小结 在本章中，首先对原有的纵横码编码规则进行了改进，使用了定长 编码的方式，为整句输入处理中输入码的切分做好了准备。然后介绍了 智能输入技术中普遍采用的n 元语法模型以及两种常用的数据平滑算法： k a t z 平滑算法和c h u r c h g a l e 平滑算法。随后提出了输入法的一个自学 习模型的结构，接着对这个自学习模型过程中概率的动态调整进行了讨 论，并给出了一个概率调整算法。 第三章文件结构与算法设计基于统计语言模型的手机中文输入系统的研究与实现 第三章文件结构与算法设计 3 1 设计准则：性能与时间、空间的平衡 作为一个智能输入法，首要追求的是它的性能，但与桌面计算机相 比，手机平台的硬件资源极其有限，如果输入法占用了过多的存储空间， 或者运行时占用内存过多，或者计算时间过长，对于用户而言，都是不 可接受的。但因此而放弃对输入法性能的追求，也是不可取的。在输入 法的性能与资源占用之间必须进行平衡，即在保证了一定性能的基础上， 尽量减少输入法对资源的使用。 根据目前主流手机的硬件资源配备情况，大致得出本系统的一个可 接受的资源限制： 1 ) 存储空间要小，最好不超过1 m ； 2 ) 输入法在计算过程中，不能让用户感觉到明显的停滞： 3 2 字词库及语料来源的选择 由于本系统主要是针对手机开发，其使用场合大都为编写短消息， 备忘录，以及收发电子邮件等应用，且使用的词汇基本为日常用语，出 于节省存储空间的考虑，本系统使用了日常用语作为字词库，并在此基 础上进行了词语之间的二元信息采集。 由于手机输入的文本以口语为主，因此应该尽量选择带有口语风格 的语料作为统计来源：常规的人民日报语料最容易获得，格式也比较清 晰，容易被计算机处理，但文本风格以新闻体为主，不够口语化；若采 用网络论坛上的帖子，尽管基本以口语为主，各个帖子之间夹杂着大量 的论坛信息，如论坛用户的昵称，签名档，发帖回帖日期，各类广告等， 这些都属于不需要的垃圾信息，而且文本中也有不少不规范的网络用语， 错别字等，这些都给计算机的处理带来了困难；另外，如使用q q ，m s n 基于统计语言模型的手机中文输入系统的研究与实现第三苹文件结构与算法设计 等通讯工具的聊天记录，尽管它们能够很好地符合本文的要求，但这些 都属于私人记录，大量收集比较困难。 最后，本文发现电影节目中的人物对白比较符合本系统的要求，因 此，可以考虑从电影节目的字幕文件中获得语料来源。如视频播放器的 常用字幕文件格式之一s r t 文件，其内容由一系列文本格式的时间代码 与字幕组成，只要将时间代码去除，就是良好的口语语料。互联网上的 以电影字幕为主题的网站的存在，为大量收集这些语料提供了来源。 本文从电影字幕网站上下载了约5 万部电影的字幕文件，从中选取 了以s r t 格式的简体中文字幕，在经过去除时间代码以及一些无效符号 等预处理操作后，得到了约1 7 9 m 的纯文本格式的电影人物对白。 通过使用海量科技公司提供的海量智能分词研究版对语料进行 分词后，本文根据词语的出现频度，选取了一万多条词汇，其中包括1 0 6 3 7 条二字词，1 1 5 8 条三字词，3 0 3 条四字词，由于超过4 字的词语在日常 用语中使用很少，而且大都可以拆分为几个词的组合，因此本文没有对 它们进行收录。对于单字，本文使用了g b 2 3 1 2 的字符集中的全部6 7 6 3 个汉字，这样本文的字词库一共收录了约一万八千多条字词项。 下一步的工作是对这一万八千多条字词进行二元信息统计，再次使 用海量智能分词研究版对电影对白进行分词，将分词结果中两两相 邻的字词对的出现次数进行统计，得n - 元信息的原始数据。 下面分别对字词库文件以及二元信息文件的设计以及查找算法进行 讨论。 3 3 字词库文件的设计与查找 3 3 1 字词i d 的引入 为了便于处理，本文在输入法的计算过程以及数据文件设计中引入 了字词i d ，每个i d 都是一个整数，对应一个候选字词，这样，在程序中 就可以用一个整数来代替各个长度不一的候选字词。不过这也带来一个 第三章文件结构与算法设计 基于统计语盲模型的手机中文输入系统的研究与实现 要求，字词i d 与候选字词之间应该能够方便的相互转换，且出于存储资 源的考虑，用于转换所使用的辅助数据空间应该控制在一个比较小的范 围之内。 3 3 2 字词库文件设计 一个设计良好的字词库文件应该能够在实现对候选字词的快速查找 的同时尽量减少所占用的空间。 为了实现快速查找候选字词，最通常的做法是采用索引技术。首先 来考察对所有可能的编码建立索引的情况，依据本文的编码规则，每个 单字编码的第一个可能编码为“0 ”“9 ”，第二，三个编码为“0 ” “9 ”或者“木”，因此有1 0 1 1 1 l = 1 2 1 0 种可能。但在本系统的字词 库中，最长候选词的字数为4 ，需要对应1 2 1 0 x1 2 1 0 x1 2 1 0 x1 2 1 0 项索 引，约2 万多亿条。显然，如此大量的索引项是无法让人接受的。 那么如果采用只对候选字词的第一个汉字编码进行索引的话，只需 要1 2 1 0 项索引。在这种方式下j 前3 位输入码( 对应候选字词的第一个 汉字) 相同的候选字词被混合存放在一起。为了将这些候选字词区分开 来，需要在各个候选字词之间添加分隔符。对于二字及以上的候选字词， 还要在合适的位置存放它们的完整编码。这样，需要添加的附加数据至 少包括： 1 ) 存放分隔符的空间，如果用2 个字节存放分隔符，需1 8 8 6 1 2 字节，约3 7 k ； 2 ) 存放多字词编码的空间，在最坏情况下，多字词编码各不相同， 即使用1 个半字节保存单字b c d 编码，需要1 0 6 3 7 1 5 + 1 1 5 8 3 + 3 0 3 4 5 字节，约2 0 k ； 另外，如果对字词库进行扩大，用来存放以上数据所需的空间也将 随之增加。由于本系统针对手机平台开发，对存储空间的大小非常敏感， 最好设计出更加有效的存放方式。 根据本文的编码规则，多字词的编码就是组成该词的各个单字编码 基于统计语言模型的手机中文输入系统的研究与实现第三章文件结构与算法设计 的拼接，而且每个汉字编码的长度又都是相同的，所以只需要根据输入 码的长度就可以确定候选字词的长度，根据这一点，本系统对字词库采 用了如下设计，字词库文件的设计如图3 1 ： c 1c 2 c 3 c 4 单字词 二字词 = 字词 四字词 图3 1 字词库文件结构 其中，c k 占2 字节，表示长度为k 的候选字词的个数，其中k = l ，2 ， 3 ，4 。 对于指定的k 字词存储区域，按照编码的字典顺序连续存放各个候 选字词项，由于各个项候选字词的长度是一致的，因此不需要分隔符就 可以连续存放各个候选项，从而可以节省了不少存储空间，而对于字词 i d ，本文用该字词在字词库文件中出现的顺序来表示。 不同于索引技术，本文采用了对编码进行逆向比较的方法：遍历所 有可能的候选字词，将候选字词的编码与输入码比较，如果两者相同， 则表明该候选字词为输入码对应的候选项，并保存该候选字词的i d 。在 遍历了所有可能的候选字词后，就获得了该输入码对应的所有候选字词。 此时，需要解决如下两个问题：。 1 ) 如何确定某字词的编码；、 2 ) 怎样才能快速获得符合条件的候选字词并转换为i d ； 3 3 3 字词编码文件 根据本文的编码规则，多字词的编码仅仅是各个单字编码的简单组 合，这样，只要知道每个汉字的编码，就能够得到字词库中任何项的编 码。 对于一个g b 2 3 1 2 的汉字z ，通过如下公式可以得到该汉字在g b 2 3 1 2 第三章文件结构与算法设计 基于统计语言模型的手机中文输入系统的研究与实现 字符集中的出现位置： v = ( h i g h ( z ) 一o x b o ) 9 4 + ( l o w ( z ) 一o x a l ) i n d e x = jv ( v = 3 7 5 5 ) ( 公式3 1 ) 说明：在v = 3 7 5 5 时，i n d e x 需要减去5 。这是因为在g b 2 3 1 2 中， 最后一个一级汉字与第一个二级汉字的之间有5 个汉字的空缺，而最后 一个一级汉字通过公式3 1 的计算值为3 7 5 5 。 根据公