（计算机应用技术专业论文）一种智能型数码输入技术的研究与设计.pdf

= 登塑墼型墼堡塑垒垫查塑堡壅兰堡生 缝至 摘要 为了在数码输入法中更好地利用智畿输入技术，本文提出了一种智能 型数码输入技术。该技术通过在输入串中增加分隔符，从而改进了数码 输入法的输入规则，使之能够与智能输入技术紧密地结合在一起。这种 输入技术不但降低了输入法的平均码长，而且显著地提高了首字命中率。 本文首先讨论了如何在不改变编码方案的情况下改进数码输入法的 输入规则。然后讨论了怎样设计字词码本结构，使之能够满足灵活多样 的输入方式，着重分析了字词索引文件的设计。继而利用二元语法模型 结合通用语言模型和用户语言模型设计了一种动态自学习语言模型，重 点分析了数据平滑算法在这些语言模型中的应用与改进，并讨论了如何 利用语言模型来提高数码输入法的性能。最后设计了一个输入法示例程 序，该程序采用了改进输入规则的纵横汉字编码方案。并通过该示例程 序对本文提出的智能型数码输入技术进行了测试，对比了改进前后不同 情况下的输入效果。 关键词：数码输入：智能输入；通用模型；用户模型；动态自学习模型 作者：顾平 导师：钱培德 垒! 墅! ：! 塑坠矍型! 型望竺! 婴! ! 竺垫堡! 塑! 曼! 堕竺2 鎏熊! ! ! 蹬挫坐鲤 t h er e s e a r c ha n d d e s i g no fa ni n t e l l i g e n tc h i n e s e d i g i t a li n p u tm e t h o d a b s t r a c t t h i sp a p e ra p p l i e sak i n do fi n t e l l i g e n tt e c h n o l o g yt ot h ec d i m ( c h i n e s e d i g i t a li n p u tm e t h o d ) i no r d e rt oi m p r o v ei t sp e r f o r m a n c ea n de f f i c i e n c y t h i st e c h n o l o g yo p t i m i z e st h ei n p u tr o l e so fc d i mb ya d d i n gt h es e p a r a t i n g c h a r a c t e r st ot h ei n p u ts t r e a m i n t e g r a t i n gt h ei n t e l l i g e n tt e c h n o l o g ya n d s e p a r a t i n gi n p u ts t r e a mi n t ot h ec d i m ，t h i si n t e l l i g e n tc h i n e s ed i g i t a li n p u t m e t h o dn o to n l yc a nr e d u c et h ea v e r a g ec o d el e n g t h , b u ta l s oc a ni m p r o v et h e h i tp r o b a b i l i t yo ff i r s tc h a r a c t e r f i r s t ，t h i sp a p e rd i s c u s s e sh o wt oi m p r o v et h ei n p u tr u l e w i t h o u t m o d i f y i n gt h eo r i g i n a lc o d i n gr u l e s s e c o n d ，i td i s c u s s e sh o wt od e s i g nt h e w o r d c o d ef i l e s ，w h i c hu s e dt oa d a p tt os o m ed i f f e r e n tw a y so fi n p u t t i n g s t r e a m t h ed e s i g no f i n d e xf i l e sa l s oh a sb e e na n a l y z e di nt h i s p a r t s u b s e q u e n t l yi td e s i g n sad y n a m i cs e l f - s t u d yl a n g u a g em o d e lb yu n i f y i n gt h e g e n e r a l - p u r p o s e dl a n g u a g em o d e la n dt h es p e c i a l - u s e rl a n g u a g em o d e l t h e d a t as m o o t h i n ga l g o r i t h mw h i c hi su s e di nt h e s el a n g u a g em o d e l so fc d i m a l s oh a sb e e na n a l y z e di nt h i sp a r t f i n a l l y i td e s i g n sa ni l l u s t r a t e di n p u t m e t h o dw h i c hi sb a s e do nt h ei n t e l l i g e n tc d i mm o d e lp r o p o s e db yt h i sp a p e r i tc o m p o s e st h ep e r f o r m a n c eo fn e wi n p u tm e t h o dw i t t lt h eo r i g i n a li n p u t s y s t e m , a n dt h e ng i v e ss o m ed a t at oa n a l y z et h er e s u l t k e y w o r d s ：c h i n e s ed i g i t a li n p u t ；i n t e l l i g e n ti n p u t ：g e n e r a l - p u r p o s e d l a n g u a g em o d e l ：s p e c i a l u s e rl a n g u a g em o d e l ；d y n a m i cs e l f - s t u d y l a n g u a g em o d e l w r i t t e nb yg up i n g s u p e r v i s e db yq i a np e i d e 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：# 埤日 期：呈业箩 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 导师签名： 日期：a ! 些! 竺! 猡 日期：! ! 些：丝：兰 军竿 熟牲丝啦 一种智能型数码输入技术的研究与设计第一章引言 第一章引言 1 1 研究数码输入技术的背景与意义 随着手机、p d a 和其它手持数码设备( 简称手持设备) 的普及，在这 样的设备上输入中文电话簿、发送中文短消息、用中文记事、上飚是很 普遍的现象。由于手持设备本身体积的限制，一般这类设备只有数字键 盘( 由“0 ”到“9 ”十个数字及一些必须的功能键组成) ，所以在输入中 文时只能使用这些数字键。随着c p u 处理速度的提高、存储设备容量的 增大、显示设备分辨率的提高等，手持设备功能将越来越强大，需要输 入中文的场合也越来越多。但是手持设备体积的增大是很有限的，几乎 不可能再容纳二十六个字母键，也就是说仍然需要依靠数字键盘来输入 中文。这样，手持设备上的拼音输入法很难发挥自身的优势，而数码输 入法却有着天然的优势，是手持设备上十分理想的输入方案。当然，手 写识别输入、语音输入等可能是以后的发展方向，但我们认为数字键盘 输入仍然是主流技术。 这样，如何用数字键简便、高效地输入汉字成为了大众的急需。使用 数字对字词进行编码已成为众多汉字编码研究者关心的课题，其结果是 涌现出了许多数字编码方案。主要有五笔数码、纵横码、笔顺码、数字 五笔、统一码、左右数码、汉易码、四角柳码、九方和十易码等多种数 字编码方案，这些编码方案目前主要使用在p c 机上。由于数字编码方案 很适合在手持设备上使用，所以它们正在被人们移植到各种手持设备上。 这些数字编码方案有一个共同的特点：都是基于汉字笔形的数字编码方 案，而且使用这样的编码需要用户掌握拆分笔形的方法。本文只讨论基 于笔形的数码输入技术，像t 9 拼音那样的拼音数码方案不在本文讨论范 围之内。 智能输入技术一般是指借助语言自身的规律性来提高输入法性能的 技术。最早该技术被拼音输入法用来解决由于同音字引起的重码问题， 接着又被用来简化用户输入( 比如只输入汉字的声母，而省去韵母，此 时重码率更高了) ，后来又被用于适应不同用户的输入习惯。目前在拼音 第一章引言 一种智能型数码输入技术的研究与设计 输入法中常常使用智能输入技术来实现拼音流到汉字流的转换，从而实 现语句级输入“m 朝阳1 。但是语句级拼音输入法在手持设备上很难实现，主 要是由于数字键盘的限制。而数码输入法，尤其是基于笔形的数码方案， 很少有人研究其与智能输入技术之间的关系h ”，对其规律了解不深，这 也是本文的一个特色。 如果能够把智能输入技术和数码输入技术很好地结合起来旧儿”，那么 这样的输入法在手持设备上将大有用武之地。本文在不改变数码输入法 的笔画拆分规则的前提下，通过改进字词输入规则，从而把它们两者有 机地结合在一起设计了一种智能型数码输入技术。 1 2 本文的工作 1 2 1 改进输入规则以实现智能输入 目前的数码输入法只能输入词库已经有的字词，但是用户在常常需要 输入很多词库中没有的词组，例如：人名、地名、专有名词、习惯用法、 专业词汇、简称、新出现的词汇等等。这些词组的使用因人而异，变化 性很大，几乎不可能把它们一一加入词库。采用自定义词库( 也称用户 词库) 是一种解决办法，但是要求用户自己添加这些词组往往比较麻烦。 因为在一般情况下即使用户多次输入了某个词组，也不一定会想到把该 词组添加到自定义词库中。如果能够在用户输入过程中自动记录这些词 组，那么将极大地方便用户再次输入它们。拼音输入法往往比较容易做 到这一点，因为几乎每一个字的拼音都由声母和韵母组成，这样就能够 自动把输入串切分成拼音串。此时如果用户输入了一个词库中没有词与 之对应的拼音串，也能让用户通过选择键来输入一个新词，同时把这个 新词添加到自定义词库中。例如用户需要输入“苏州大学”的简称“苏 大”，他可以输入这样的输入串“s u d a ”，根据声母和韵母能够切分成 拼音串“s u * d a ”。即使用户只输入声母“s d ”也能识别出用户需要输入 的是一个二字词，而且这个二字词的声母依次为s 、d 。当然也有一些时 候存在二义性，这时需要用户在拼音之间使用分隔符( 例如：f a n * g a n 、 f a n g * a n ) 。而数字编码方案几乎不可能自动把输入串切分成每个字的输 一种智能型数码输入技术的研究与设计 第一章引言 入码，这样需要输入词组的时候就不能直接输入每个汉字的编码。一般 采用的解决方法是对词组进行专门编码，这样就不需切分输入串。相应 地也就无法输入词库中没有的词组，例如同样要输入“苏大”，假设词 库中没有这个词，只能分别输入“苏”和“大”两个字。本文对输入规 则进行了修改，对词组不再使用专门编码而是由词组中的每个单字的输 入码组成，同时在字和字的输入码之间使用分隔符( 丰) 。以纵横码为例： “苏”的输入码是“4 3 3 ”、“大”的输入码是“4 8 ”，对于“苏大”就 可以输入“4 3 3 * 4 8 ”，此时输入法就能准确地区分出“4 3 3 ”是第一个字 的输入码，4 8 是第二个字的输入码。同时也可以允许用户使用简化的输 入方法，也就是说不必输入每个汉字的完整编码，只要输入前面几位编 码即可。即可以使用下面的任何一种方法来输入“苏大”：“4 3 3 * 4 8 ”、 “4 3 3 * 4 ”、“4 3 * 4 8 ”、“4 3 * 4 ”、“4 * 4 8 ”和“4 * 4 ”。这样就给用户 提供了一种非常灵活的输入选择：对于经常使用的词组可以采用短一些 的编码；对于不太常用的词组可以采用长一些的编码。 改进数码输入法的输入规则是为了能够更好地利用智能输入技术，把 它们两者很好地结合起来。但是这样的改进却对输入法的设计提出了更 高的要求：一方面用户的输入形式灵活多样，使从输入码到相应字词的 检索变得特别复杂；另一方面用户使用简短的编码输入时，会产生大量 的重码字词。本文设计了一种能满足相应检索要求的字词码本结构很好 地解决了第一个问题。解决第二个问题的方法是使用智能输入技术对所 有重码字词进行排序。第二章的相关基础中介绍了改进输入规则的具体 方法，并对相关问题进行了分析。另外需要注意：改进后的输入规则也 能实现语句级输入，但是本文并不讨论语句级输入闯题，而是利用改进 的规则更好地实现基于词组的数码输入技术。 1 2 2 设计宇词码本结构及索引 纵观五笔数码、纵横码、笔顺码、数字五笔、统一码、左右数码、汉 易码、四角柳码、九方和十易码等数字编码方案，对于单字编码一般采 用4 位、5 位或者6 位数字进行编码。本文对单字编码的前4 位建立了哈 第一章引言 一种智能型数码输入技术的研究与设计 希索引，并且提出了一种按照字典序计算哈希值的算法，使索引表节省 了大约2 0 的空间。对于码长为5 位或者6 位的字码本设计出了一种哈 希索引和稠密索引相结合方案，并且提出选择哪种索引的标准。对于词 码本按照词组的长度分为二字词、三字词、四字词和多字词( 长度大予 四的词组) 。因为可以根据输入串中的分隔符确定需要输入词条的长度， 把不同长度的词条分开来存储能够提高检索效率( 因为长度大于四的词 组数量比较少，所以统一作为多字词处理) 。为了提高检索词组的效率分 别为二字词、三字词、四字词和多字词的部分编码建立了哈希索引( 具 体请参见表3 2 ) 。同时设计了一个字属性结构存储所有单字( g b k 中规 定的2 1 0 0 3 个汉字) 的编码、频度等信息。图1 1 给出了字词码本结构 及根据输入串检索字词的示意图。 图1 1 字词码本结构及检索过程 有关字词码本结构及相应索引的设计，将在第三章详细阐述。本文设 计的字词码本是为改进以后的数码输入规则特别设计的，主要的特点是 能很好地满足灵活多样的输入方法，同时能配合智能输入技术提高检索 效率。 一种智能型数码输入技术的研究与设计 第一章引言 1 2 3 建立动态自学习语言模型 为了对从众多的重码字词给出一个比较好的排序，即把用户需要的字 词排在前面，本文建立了一种基于统计的动态自学习语言模型来预测用 户当前需要输入的字词。首先利用二元语法模型( b i g r a mm o d e l ) 从大 规模( 7 5 亿字) 语料中得出一个通用语言模型( 简称通用模型) ，然后 还是利用二元语法模型从用户输入的历史信息( 小规模语料) 中得出一 个用户语言模型( 随着用户的输入而不断变化的语言模型，简称用户模 型) 。通用模型提供了一种平均情况下的语言模型，但是不能反映某个具 体用户的特点；用户模型提供一种能不断适应某个具体用户的语言模型。 由于用户输入的数据量非常有限，用户模型的可信度往往比较差( 当然 可信度随着用户历史信息的增加而不断提高) 。本文采用的解决方案是结 合通用模型和用户模型，优势互补，形成一种新的语言模型。这种新的 模型既有比较稳定的基础( 通用模型) ，又能根据用户输入的历史信息不 断适应某个用户，称之为动态自学习语言模型( 简称动态自学习模型) 。 图1 2 给出了构建动态自学习模型的示意图。 图1 2 动态自学习模型 通用语言模型的数据量往往特别大，相应的存储空间也很大。本文提 出了一种根据用户给定的存储空间裁剪通用模型的方法，并且改进了 c h u r c h g a l e 吲平滑技术，将其用在裁剪后通用模型的数据平滑上。同时 本文还讨论了在数码输入法中使用这些语言模型的时间代价问题。第四 章的智能输入技术研究就是讨论如何构造语言模型以及怎样把语言模型 应用在数码输入法中。 第一章引言 一种智能型数码输入技术的研究与设计 1 2 4 测试并分析智能型数码输入技术 为了测试本文提出的智能型数码输入技术的优劣，本文基于纵横码实 现了一个智能型数码输入法示例程序。该示例程序在p c 机上运行，采用 了改进的输入规则，利用了前面设计的字词码本结构和动态自学习模型。 测试表明这种透过增加分隔符改进输入规则的方法，不但没有增加平均 码长，而且显著地提高了输入法的首字命中率。第五章给出了测试结果， 并进行了具体分析。可以认为本文提出的智能型数码输入技术是一种成 功的方案，值得在手持设备上推广应用。 一种智能型数码输入技术的研究与设计 第二章相关基础 第二章相关基础 2 1 数字编码方案分析 2 1 1 笔形与代码 本文讨论的数字编码方案全部是基于笔形的编码方案。因为在我们的 研究中主要使用了纵横汉字编码方案( 简称纵横码) ，所以下面关于编码 方案的讨论默认都是基于纵横码的。纵横码把笔形分为1 0 类，分别用 “0 ”到“9 ”这1 0 个数字表示。笔形与数字代码的关系可通过下列口诀 表达：一横二竖三点捺，叉四插五方块六；七角j k a 九是小，撇与左钩 都是零。在取笔形代码时，应注意：当复杂笔形与简单笔形都可取时， 取笔划复杂的笔形，也即“取大不取小”。 其他数字编码方案基本上也把笔形分为1 0 类或者9 类，也有分成更 少类的( 比如五笔数码中的“6 键6 码”方案只把笔形分为6 类) 。也就 是说数码输入技术的码元集合大小一般为1 0 或者9 ，也有更小的。码元 集合大小对字词码本及索引的设计都有一定的影响，但是没有本质差别， 所以本文只讨论了码元集合大小等于1 0 的情况。 2 1 2 单字编码规则 纵横码将汉字看成一个方块字，取汉字四个角的笔形为单字编码，取 码次序为： 先取左上角的笔形为第一码； 再取右上角的笔形为第二码； 再取左下角的笔形为第三码； 再取右下角的笔形为第四码。 一个汉字不足四码( 例如右上角所取之笔形与左上角所取之笔形重 复，合起来取一码) 则有几码取几码。汉字的左上角或右上角星角形笔 形，取较高的笔形。如前所述，取笔形时一般不断开取，但是从不同的 角取的笔形不一样时，该笔形应该断开分别取码。 第一二章相关基础一种智能型数码输入技术的研究与设计 为了使输入更容易更快捷，在g b k 简体字符集中，纵横码对8 2 个常 用字设计了一键简码，取简码的方法为每个字纵横码的第一码；对8 3 0 个常用字设计了二键简码，取简码的方法为每个字纵横码的第一码和第 二码。 其他数字编码方案都有各自的单字取码规则，本文所要关注的是使用 编码的位数，即最大码长( 简称码长) 。纵横码的码长为4 ，五笔数码的 码长为6 ，也有码长为5 的。码长在很大程度上影响字码本及索引的设计， 第三章有详细的讨论。 2 1 3 词组编码规则 词组分为二字词组、三字词组、四字词组及多字词组，每类词组取码 最多为六码，下面详细贪绍词组的取码方法。 二字词组取码法是以每个字的纵横码前三码连在一起( 3 + 3 ) 。如果其 中单字只有一码或二码，便全取其编码而不用补上任何编码。二字词 组码长最长为六码，最少为二码。 三字词组，取每个字纵横码的第一及第二码( 2 十2 + 2 ) 。如果一个单 字只有一码可取时，就只取一码而不用补上任何编码。 四字词组，先取第一个字纵横码的第一及第二码，再取第二字及第三 字的第一码，最后取第四字第一及第二码( 2 + l + l + 2 ) 。，如果第一或 第四个字只有一码可取时，就只取一码而不用补上任何编码。 五字或五字以上词组，都只是对前五个字取码，第一个字取第一及第 二码，后四个字均取纵横码的第一码( 2 + l + 1 + l + 1 ) 。如果第一个字只 有一码可取时，就只取一码而不用补上任何编码。 为了使词组的输入更快捷，对大约一千个常用简体词组( 以二字词组 为主) 定义了简码，用户只需使用一码或两码，即可输入常用词组。对 有一键简码的词组，词组的简码为该词组纵横码的第一码；对有两键简 码的词组，词组的筒码为该词组纵横码的前二码。 其他数字编码方案也都有各自的词组编码规则，但是有一个共同点就 是都对词组进行了专门编码，往往有最大长度限制。这样的编码方法没 一种智能型数码输入技术的研究与设计 第二章相关基础 有连续输入特征，不能自动记录用户输入的新词，也很难提供灵活的输 入选择。 2 2 数字编码方案的输入规则改进 2 2 1 单字编码的输入规则改进 先保持单字的编码规则不变，并去掉所有简码，再对这些编码自动生 成简码。最大码长为4 的编码方案的输入规则改进如表2 1 所示，对于 最大码长为5 或者6 的编码方案依此类推。 表2 1 单字简码规则 汉字编码( a b c d )自动生成的简爵备注 a不需要生成简码 长度为l 的编码 a ba 长度为2 的编码 a b ca 、a b 长度为3 的编码 a b c da 、a b 、a b c 长度为4 的编码 例如汉字“横”原先的纵横码为4 4 9 8 ，加入自动简码规则之后用户输 入4 、4 4 、4 4 9 或者4 4 9 8 都能输出“横”字，但是在单字码本中只存储 一个纵横编码( 4 4 9 8 ) 。有些汉字的笔形按照个人理解不同有着不同的编 码方法，这样几乎所有的数字编码方案都给这部分汉字增加了容错码， 因此需要考虑如何在单字码本中存储容错码。 2 2 2 词组编码的输入规则改进 对于词组不再采用专门编码，而是由词组中的每个字的输入码组合而 成，字与字的输入码之间需要使用分隔符。例如词组“纵横”原先的纵 横码为2 8 1 4 4 9 ( 其中“纵”字的纵横码为2 8 1 ，“横”字的纵横码为 4 4 9 8 ) ，修改以后的输入规则为“2 8 1 4 4 9 8 ”，实际上可以允许用户使 用表2 2 所示的1 2 种方法中的任何一种进行输入。 第二章相关基础 一种智能型数码输入技术的研究与设计 表2 2 词组“纵横”的输入方法枚举 纵横 、横( 4 4 9 8 )横( 4 4 9 )横( 4 4 )横( 4 ) 纵( 2 8 1 )2 8 1 4 4 9 82 8 1 4 4 92 8 1 4 42 8 1 4 纵( 2 8 ) 2 8 * 4 4 9 82 8 * 4 4 92 8 * 4 42 8 * 4 纵( 2 ) 2 * 4 4 9 82 * 4 4 92 * 4 42 * 4 这样修改的主要目的是为了使数码输入法具有连续输入的特征，从而 可以更好地利用智能输入技术。同时词组的输入方式也变得灵活多样， 以适应不同用户在不同情况下的输入需求。 2 2 3 改进后的优点 具有连续输入特征 现在绝大部分数码输入法只能输入词库中已经定义的词组，用户无法 连续输入词库中没有定义的词组。虽然大部分数码输入法支持用户自定 义词组，却不能自动自定义词组。而连续输入使得用户可以输入系统词 库未定义的词组。前殛对词组编码输入规则的改进使得数码输入法也具 有了连续输入的特征，从而使输入法能够自动记录用户输入的新词，方 便用户再次输入该词组。同时用户在输入词组时不必非常在意词库中有 没有该词组，给用户提供了方便。这样就能够更好地利用用户语言模型， 使输入法能够不断适应具体用户的使用习惯或专业领域。 支持灵活多样的输入方式 、二 改进后的输入规则使用了分隔符，并且允许用户只输入词组中每个字 的前面部分编码。这样用户可以在性能和速度上按照自己的使用习惯自 行选择。当采用较长的编码时，熏码率降低，需要通过选择键来确认的 字词数量也相应降低；当采用较短的编码时，重码率上升，需要通过选 择键来确认的字词数量也相应上升。这样，对于用户经常使用的词组可 以采用较短的编码，因为输入法能将重码字词中用户常用的词组排在前 面；同样对于不常用的词可以采用较长的编码，相应的重码字词也就减 少。这种灵活性使得数码输入法必须利用智能输入技术来提高首字命中 率，同时降低平均码长。 = 登要堑型墼塑塑楚查堕堑塞兰望盐篓三童塑叁薹型 降低学习数码输入法的难度 这里讨论的数码输入法都是基于笔形编码的，而对于绝大多数用户来 讲学习笔形输入法要比拼音输入法困难得多。这些数码输入法总有一些 笔形的处理比较特别，用户很难在短时间内掌握好。改进后的输入规则 使得用户即使不知道对某些笔形如何编码，仍然能输入字词，因为现在 有多种灵活的输入方法。这样就降低了学习的难度，有利于数码输入技 术的推广应用。 2 2 4 改进后的缺点及相应的处理方法 灵活多样的输入方式增加了检索字词的难度 改进以后的输入规则对于用户的每个输入串都需要检索更多的字词 码本才能找出所有满足条件字词。这就对字词码本和检索方法的设计提 出了新的要求。这样，如何设计满足灵活多样输入方式的字词码本成了 本文的一个重要主题。 字词重码率可能很高 很明显在极端情况下字词重码率将非常高，这是用户不希望的结果。 需要使用前面提到的动态自学习语言模型来预测用户当前需要输入的字 词，也就是要把所有满足条件的字词按照语言模型计算出来的概率( 在 这里是条件概率) 由大到小进行排序。注意到建立和使用语言模型也将 花费很大的时间和空间代价，所以除了要建立一个优秀的语言模型还要 考虑以怎样的时空代价来使用该语言模型。 分隔符本身也增加了用户的输入负担 使用分隔符增加了用户的输入负担，这一点只能通过允许用户输入更 短的编码来进行弥补。只有使得用户能在使用较短的编码( 平均码长较 小) 输入时得到较高的首字命中率，付出这样的代价才是合理的。这也 要求使用智能输入技术来在总体上降低用户的输入负担，同时保证一定 的首字命中率。 篁兰里壁基础 一种智能型数码输入技术的研究与设计 2 3 稠密索引与哈希索引 在字词码本的设计中使用了稠密索引和哈希索引，有必要在此先介绍 这两种索引的结构及各自的优缺点。这里还给出了一种选择哪种索引的 判断标准，在下一章会给出更详细的公式。 稠密索弓l 的结构如图2 1 所示。 f 索引码指针输入码对应的汉字或词组 索引表码本表 图2 1 稠密索引结构 稠密索引的每个索引项对应一个码本项，而且是一对一的关系，有多 少个索引项就有多少个码本项。一般而言，索引表中的每一个表项是等 长的，而码本表中的每一个表项是不等长的。稠密索引的检索原理是首 先查索引表，找到此输入码对应的汉字或词组集合在码本表中的位置， 再从码本表中读出汉字或词组。查索引表常用的是二分法检索算法，假 设所有的索引码等概率出现，索引项的大小为n ：检索成功的情况下，最 大的比较次数为 1 0 9 ：n ，最小的比较次数为l ，平均约为 1 0 9 a n ；检索 失败的情况下，最大、最小和平均的比较次数都为 1 0 9 小1 。当n 比较小 时常常使用稠密索引。 哈希索引的结构如图2 2 所示。 一种智能型数码输入技术的研究与设计 第二章相关基础 指针 索引表 输入码对应的汉字或词组 码本表 图2 2 哈希索引结构 哈希索引结构省略了索引表中的索引码部分，这是因为索引表的表 项对应于整个编码空间。也就是即使某个输入码没有对应的字词，仍作 为一个表项存在于索引表中，但是码本表中不需要有这一项。假设某个 输入法的码元集合为1 0 个数字，最大码长为4 则应该有1 0 1 i 1 i i 1 = 1 3 3 1 0 个索引项( 通常使用这种方法计算索引项的大小，但是并不精确， 第三章给出了一种精确的计算方法) 。设输入码为a b c d ，如果某一位为空 用使用一l 表示，这样可以使用公式2 i 计算索引项，从而找到此输入码 对应的汉字或词组集合在码本表中的位置。 i n d e x = a x l l x l l x l l + 陋+ 1 ) x l l x l l + ( c + 1 ) x l l + ( d + 1 ) ( 2 1 ) 最大码长大于4 的时候，索引项的总数会比较大。此时往往不能使用 所有的输入码作为哈希索引的索引码，而是仅从输入码中选择几位编码 作为索引码。对于最大码长为5 或者6 的编码方案，本文采用的方法是 取前面的四位输入码作为索引码，对于剩下的一位或者两位采用二级索 引。对于二级索引往往需要判断使用哈希索引还是稠密索引。表2 3 总 结了稠密索引和哈希索引在存储空间和检索时间上的对比。 第一二章相关基础 一种智能型数码输入技术的研究与设计 表2 3 稠密索引与哈希索引性能对比 l 索引 稠密索引 哈希索引 l 时空 d e n s ei n d e xb a s hi n d e x l 存储空问需要存储索引码和指针没只需要存储指针，但是可能会产 有空索引项生大量的空索引项 i 检索时闻平均情况下需要进行需要执行一次计算索引项的公 1 0 9 加次比较 式 通常情况下稠密索引几乎不浪费存储空间，但是检索时间要比晗希索 引大得多，啥希索引往往因为大量的空索引项而浪费较多存储空间。那 么如何衡量时间代价和空间开销哪个更重要呢? 本文采用时间的倍数关 系与空间的倍数关系相比较，使得时间代价和空间开销之间有一个相对 意义上的衡量。如果以稠密索引为基础来考察是否应该使用哈希索引， 可以得到公式2 2 。哈希索引存储开销哈希索引时间代价，。 “一丽酾虱稻丽鬲。丽萌西丽丽 “ 可以为时间与空间的相对重要程度设置一个系数k ( k 一时问的重要程 度空问的重要程度) 。工大予k 则应该使用稠密索引，2 小于k 则应该使 用哈希索引，a 等于k 任选一种都可以。这里的k 是时间空间而不是空 间时间，是因为考察的对象( 哈希索引) 相对与其基础( 稠密索引) 是 一种浪费空间、节省时间的方案。在第三章细化了公式2 2 ，并且讨论了 在具有时问代价和空间开销限定的情况下，如何使用该公式。 2 4 智能输入技术概述 2 4 1 智能型的含义 输入法有两个基本目标：一、简化用户输入，减少平均码长；二、降 低重码字词键选率( 重码字词键选率：在输入给定测试样本过程中，通 过重码选择键确认的汉字字数与测试样本总字数的百分比) 。这两个目 标往往是相互制约的，简化了用户的输入必然会在一定程度上增加重码 率，从而使键选率升高。本文使用的首字命中率在数值上等于1 一重码字 一种智能型数码输入技术的研究与设计 第二章相关基础 词键选率。智能输入技术通过利用语言本身的规律性把最有可能的字词 排列在前面从而提高首字命中率，可以通过建立语言模型( 1 a n g u a g e m o d e l ) 来表达语言的规律性。通常有两种建立语言模型的方法：一、使 用概率统计的方法得到语言之间的规律( 简称统计方法) ；二、使用语法 规则表达语言的规律( 简称规则方法) 。统计的方法适应性比较好，几乎 所有的智能输入法都使用了统计的方法( 包括：智能a b c ，微软拼音，紫 光拼音等一系列优秀的拼音输入法) ；规则的方法一般不单独使用而是和 统计的方法相结合( 微软拼音是一个典型的统计和规则相结合的智能输 入法) 。本文仅使用统计的方法建立语言模型。 数码输入法( 这里指的是基于笔形编码的数码输入法) 一般很少使用 智能输入技术，主要有两个原因：一、根据笔形编码的数码输入法字词 重码率比较低，不需要使用智能输入技术；二、数字编码一般不具有连 续输入特征，限制了智能输入技术的应用。本文改进了数码输入法的输 入规则使得其具有连续输入的特征，同时字词重码率在用户使用较短编 码时升高。这样在数码输入法中使用智能输入技术就很有必要了。基于 统计最简单的方法就是统计字词的频度，把符合条件的字词按照它们的 频度由大到小进行排序。n 元语法模型( 4 1 节有详细的讨论) 能够根据 用户刚刚输入的字词来预测下一个将要输入的字词从而能更好地对重码 字词进行排序( 也就是降低了重码字词键选率，提高了首字命中率) 。考 虑到手持设备的存储空间和c p u 处理能力，本文使用了二元语法模型。 本文所讲的智能型数码输入技术的“智能型”主要包括四个方面，下 面分别介绍。 对于所有的重码字词自动输出最佳排序结果，这里的“最佳”是相对 于该用户的最佳排序。衡量这一特性的一个常用标准是重码字词键选 率，键选率越低相应的首字命中率就越高，用户输入就越方便。这是 “智能型”的一个综合表现，也是绝大多数智能输入法不懈追求的一 个目标。 具有连续输入的特征，用户不仅能够输入词库中的词，还能输入用户 自己的特殊词语或者短语。输入法能够自动记录用户输入的新词，从 第二章相关基础 一种智能型数码输入技术的研究与设计 而方便用户再次输入该词。这一特性能在很大程度上提高首字命中 率，本文对输入规则改进的初衷就是要使数码输入法能够具有连续输 入的特性。 提供了一种灵活的输入方式，有的用户倾向于输入比较完整的输入 码，有的用户则相反。一个智能的输入方案应该能够满足这些不同用 户的需求，当然输入比较完整的输入码时会得到更高的首字命中率。 从表2 2 可以看出，我们几乎在最大程度上为用户提供了这种灵活性。 需要注意的是用户需要为这种灵活性和刚刚提到的连续输入特征付 出一定的代价，那就是需要在每个字的输入码之间加入分隔符。而这 种代价也是通过在使用较低的平均码长时保证一定的首字命中率来 进行弥补的。 随着用户对这种输入法的使用，能够不断适应该用户。本文采用的解 决方案是构造一个动态自学习语言模型，根据用户输入的历史信息来 使输入法不断适应该用户。该特性的最终效果体现在提高首字命中率 上，就是能够对重码字词给出符合该用户的最佳排序。 2 4 2 动态自学习语言模型 可以通过对大量文本进行统计，并使用数据平滑技术解决数据稀疏问 题得到一个优秀的通用语言模型。然而这样的语言模型对于像输入法这 样的个性化比较强的应用显得过于死板，因此器要建立种能够从用户 输入的历史信息中统计该用户使用语言规律的用户语言模型。已经有很 多拼音输入法能够根据用户输入的历史信息调整词频，自动记录用户输 入的新词( 系统词库中没有的词) 。哈尔滨工业大学的刘秉权、王晓龙两 位教授在2 0 0 4 年2 月发表了一篇名为一种面向用户的语言模型及其机 器学习方法“町的文章，其中提出了面向用户的语言模型的概念。这种 语言模型也是结合了通用( 语言) 模型和用户( 语言) 模型，具体如图 2 3 所示。 一种智能型数码输入技术的研究与设计 第二章相关基础 图2 3 面向用户的语言模型结构 文章中给出了一种构造用户模型的机器学习算法，但是并没有提及如 何具体地把通用模型和用户模型结合起来。本文讨论了如何根据通用模 型和用户模型构造一种动态自学习语言模型，并采用了二元语法模型构 造这里的各种语言模型。下面概要地说明通用模型、用户模型和动态自 学习模型的构造。 通用模型的构造：使用人民日报系列的十二大报纸约7 4 万篇文章 ( 1 9 9 5 年到2 0 0 3 年，7 5 亿字，3 亿词条) 作为构造通用模型的数据源。 先对这些文章进行自动分词，再统计出频率最高的6 5 3 8 4 个字词的二元 组1 6 9 7 万条。根据c h e n 和g o o d m a n m 儿”1 对各种平滑算法的研究结论“在 大训练集上的二元语法模型c h u r c h - g a l e 阳1 平滑算法有最好的性能”，本 文使用该平滑算法来构造通用模型。由于通过模型需要的存储空间特别 大，本文利用t 检验提出了一种裁剪二元语法模型的方法，并改进了 c h u r c h - g a l e 平滑算法使其适用于裁剪后的二元语法模型。 用户模型的构造：用户模型的数据源是用户输入的历史数据。这个数 据模型是在用户输入过程中逐步构造的，总的来讲这个数据源很小。c h e n 和g o o d m a n “”“2 1 的研究中得出的另一个结论是“在，m j i i 练集上的二元语 法模型使用k a t z n 3 3 平滑算法最好”，所以在这里我们使用了k a t z 平滑算 法。用户语言模型的一个重要特征是，随着输入过程而不断变化，本文 讨论了如何把k a t z 平滑算法运用在这种不断变化的语言模型中。 动态自学习模型的构造：构造该模型的主要问题就是如何衡量通用模 型和用户模型的相对可信度。用户模型随着用户历史数据的增长而不断 完善，但不是用户模型中的每一项都具有同样的可信度。本文给出了一 第一二章相关基础一种智能型数码输入技术的研究与设计 种根据通用模型和用户模型的线性组合构造动态自学习模型的方法。 二登塑壁型墼塑塑叁垫术的研究与设计第三章码本结构的研究与设计 第三章码本结构的研究与设计 3 1 单字码本结构 3 1 1 字索引 字索引是输入码到汉字的索引，能从索引项中得到符合某一输入码的 汉字在字码本中的位置。我们发现不同数字编码方案的最大码长虽然不 一样，但总是4 位、5 位或者6 位。没有最大码长小于4 位的编码方案， 因为那样字词重码太多：也几乎没有最大码长大于6 位的编码方案，因 为码位太多用户输入的负担就比较重。本文取输入码的前四位编码( 称 之为索引码) 组成字索引表。注意到绝大部分数字编码方案都是不等长 编码，汉字的码长可以是一位、两位、三位等等。对于四位索引码的取 值情况可以这样归纳：第一位不能为空，其它的三位都有可能为空。设 码元集合的大小为1 0 ，每一位索引码的取值情况如表3 1 所示。对于码 元集合小于l o 的情况依此类推，码元集大于1 0 的编码方案( 如拼音输 入法在数字键上的实现) 不在本文的讨论范围之内。 表3 1 四位索引码取值范围 位数取值范围备注 第一位 o 一9 用a 表示 第二位 a 0 9 用b 表示 第三位1 0 0 9 j用c 表示 第四位 0 0 9 用d 表示 约束条件：当某一索引码为空 a 的时候，后 面的码位必须为空。 枚举所有可能的索引码，并按照字典序排列得到“0 0 0 0 、0 0 0 0 、0 0 0 0 、 0 0 0 0 ，0 0 0 1 ，、0 0 0 9 、0 0 1 0 ，0 0 1 0 ，、0 0 1 9 ，0 0 2 0 ，0 0 2 0 ，、0 0 9 9 ， 0 1 0 0 、0 1 0 0 、0 1 0 0 、0 1 0 、，0 1 9 9 、0 2 0 0 ，0 2 0 0 ，0 2 0 0 、，0 9 9 9 、 1 0 0 0 、1 0 0 0 、1 0 0 0 、1 0 0 0 、9 9 9 9 ”。这样有1 0 0 0 0 个四位索引码、 1 0 0 0 个三位索引码、1 0 0 个两位索引码、1 0 个一位索引码，共1 1 1 1 0 个 1 9 箜三童堕查缔构的研究与设计 一种智能型数码输入技术的研究与设计 索引码。采用哈希索引按照字典序对于每一个索引码建立一个索引项， 得到的字索引表结构如图3 1 所示，共1 1 1 1 0 个索引项。 索引项l 索引项2 索引项3 索引项n 图3 1 字索引表结构 每个索引项由两个字节组成，存储的是该索引项对应的汉字在字码本 中的开始偏移( 对应指针图2 2 中的指针) 。索引项中没有存储索引码， 是因为索引码和索引项一一对应，而且可以从索引码( a b c d ) 计算出相应 索引项( i n d e x ) ，下面就来分析这个计算公式。 3 1 2 索引项计算公式 先不考虑约束条件，a 有1 0 种取值，b 、c 、d 各有1 1 种取值，使用 一1 表示0 ( 因为在字典序中0 排在o 的前面，所以使用一l 表示0 ) 。这样 得到的就是在2 3 节给出的公式2 1 。因为没有考虑到约柬条件所以索引 表的空间有些浪费。对于索引码为四位的索引表使用公式2 1 就有1 3 3 1 0 ( i o x i i i i 1 1 ) 个索引项，比这里设计的1 1 1 1 0 个索引项多出约2 0 ( ( 1 3 3 1 0 - - 1 1 1 i 0 ) 1 1 1 1 0 ) 的索引项。 再考虑约束条件( 当某一索引码为空 o 的时候，后面的码位必须为 空) 对公式2 1 的影响，可以从下面的四个方面分析这种影响。 d 为空时对公式2 1 没有影响。 c 为空时公式2 1 中d 有1 1 种取值，而实际上此时d 只能为空。因此 每出现一次c 为空就要把i 删e x 减去1 0 。 b 为空时公式2 1 中c 、d 都有1 1 种取值，共1 2 1 ( 1 1 i i ) 种取值， 而实际上此时c 、d 都只能为空。考虑到c 为空时已经减去1 0 ，因此 每出现一次b 为空就要把i n d e x 减去1 1 0 ( 1 2 1 一卜l o ) 。 a 不可能为空，所以没有影响。 一种智能型数码输入技术的研究与设计第三章码本结构的研究与设计 从以上分析得知，只有b 为空和c 为空对公式2 1 有影响，而且影响 的数值也已经分析出来了。下面的问题就是需要知道对于某个索引码 a b c d ，在不考虑约束条件时，按照字典序排列