机器辅助翻译中模糊查词典和快速录入单词.pdf

中文信息学报 第 l 1 卷第4 期J 0 u R N A L O F C H I N E S E I N F O R M A T I O N P R O C E S S I N G v o l 1 1 N o 4 机 H 辅 助 翻 译 中 模 糊 查 词 典 和 快 速 录 入 单 词 驴一 一 李 生 吴 葳 哈尔 滨工业大学计算机系3 2 1 信箱 e m i l L x h am血b h i t e d u 摘要 本文介绍在单词记 己 不准 确的情况下 如何查找词典以 及如何只 键入单词中 的几个字母快速录入单词的算法 在辅助翻译和写作系统中 词汇级的帮助是最基本的 主 要指词典查询 但很多情况下 用户单词记忆不艰准确 只记住了几个字母 本文解决这种 情况下的模糊查询问题 这种模糊技术的核心是全文检 索 依辅于词典的特殊索引 在解决 j模糊查询之后 利用全文检索技求以及模糊二分查找技求进一步开发了写作系统中的快速 录入功能 关键词 机器辅助翻译 模糊查词典 查词典是机器翻译系统中最基本的功能 二分查找法是最广泛采用的查找方法 p 3 l 2 查找速度和准确率已经满足了翻译的需要 本文主要解决下面两个方面的问题 一 在辅助翻译和写作系统中 有些情况 下 用户单词记忆不很准确 只记住了几个 字母 例如对单词 s c ie n t i s t 用户可能没有记全 只记住 s c fi a t 仅利用此信息 系统 如何查出单词 s c ie n t i s t 叉如 用户知道 名 的译文为 n a e 但忘记了 姓 如何 翻译 可以推测该词可能含有 n a m e 用户即可用 n a m e 来查词典 这就是模糊查 找词典的问题 二 英文写作系统中 有些单词很长 如单词 a n t ie s t a b l is h me n t a li s t 有 2 2个字母 完整输入需击键 2 2 次 实际上只需输入 a n t i t a li s t 1 1 个字母即可 减少 5 0 的击键次 数 用户也可以输入其他的省略形式 如 e s t a t a l ls t a n ta t a 等等 主要取 0本渫疆受国裳8 6 3 计划 8 6 3 3 0 6 0 3 0 6 3 资助 奉文初稿干 1 9 9 6 车7月4日 收到修订稿于 1 9 9 7 年3月1 8日 收到 6 0 言 维普资讯 决于用户记住的关键字母 这就是快速录入的问题 解决这两个问题 对用户提供了很大的方便 本文将利用全文检索解决这两个问题 采 用全文检索模糊查询词典不仅未见报道 而且用于辅助翻译系统中尚 属首次 快速录入单词 即使在非常常用的编辑软件wO R D中也没有此功能 模糊查询词典和快速录入单词的核心问题是如何根据用户提供的不完整的信息检索出符 合要求的单词 采用传统的 词典索引方法不能解决问题 因为要查的词中含有通配符 表示任意多个任意字母 表示一个字母 这种待查的词不能作为关键词在 索引中二分查找 本文采用全文检索技术 f 3 3 对词典中单词的每一个字母进行索引 使得 模糊壹询的检索式非常灵活 检索速度快 索引空间较小 本文说明的算法以用于达雅信使 中英文写作系统 i 6 J 该系统是一个汉英双向辅助翻译系统 具有短语级双向翻译功能 还 将用于正在研制的B T 8 6 3 项目 汉英双向机器翻译系统 本文第2 节介绍用于全文检索的词典索引结构 第 3 节描述模糊查词典的算法 第4 节 说明 快速录入的实现 最后提出该方法进一步改进方法 并指出在中文中应用的可能 二 词典的索引结构 假设英文词典的结构为记录 单词 E W 解释 分隔符 的集合 传统方法以单词E W 为关键词进行索引 词典按E W排序 查找过程可以在索引中二分进行 本文采用的全文检索只对词典中单词E W 中的所有字母及连字符共 2 7 个关键字索引 而不是词典中的每一个字符 用户输入的检索式不再局限于完整的单诃 而是单词中的部分 字母 索引结构如图 1 所示 倒排文件分为2 7 块 分别记录2 6 个字母和连字符出现在哪些单词中 词典中每个单词 对应一个 I D值 即该词在词典中的序号 倒排索引文件中每个字母 X 指向的倒排文件记录 着所有单词中含有字母x的单词的I D值 如词典中第 i 个单词为 lo o k 倒排文件中 字 母 l k 对应的倒排文件中 分别记录 1 o o k 的I D值 i 表示字母 l O k 在词典中第i 个词中出现 根据上述索引 对任意给定的字母 由倒排索引在倒排文件中找到对应的记录块 该记 录块记录了所有出现了该字母的单词集合 三 模糊查词典算法 3 1 检索式 检索式是字母 连字符和通配符的任意组合 通配符包括 表示任意 多个拄意字母 7 表示一个字母 例如对单词 o p e n h e a r t 可用检索式 o p a r t h e a r t o e n t o p e n h t 等等 通常 通配符用来代替记忆不清楚的部分 6 l 维普资讯 3 2模糊查找算法 a k l 词典 倒排索引 倒排文件 图l词典索引 3 2 1检索式规范化 检索式规范化主要是去掉冗余的 以及多余的空格 大写字母改为小写 如对 I k 可以简化为 l k 大写字母改为小写 因为索引统一按小写进行的 按照小写 检索 最后的大小写由第4 步判断 3 2 2解释检索式 包括检索式的正误判断 若检索式不合规范 返回 正确的检索式 需要记录查询的字 母集合A l p h a S e t 字母的位置关系 距离信息 如对检索式 l k 集合A l p h a S e t 包古两 个字母 I k 字母的位置关系 l 在 k 之前 距离信息 如对检索式 1 k 集合 A 1 p h a s e t 包含两个字母 l k i 字母的位置关系 I 和k 之间可以有任意多个字母 3 2 3按字母查找 1 i 检索式中字母个数 r e s u l t 一包古字母 A I p h a S e t 0 的单词标号集合 2 f o r j 1 j i j 3 n e w s e t 一 包含字母 A l p h a S e t j 的单词标号集合 4 r e s u l t 一r e s u l t 交 n e ws e t 5 if r e s u l t 为空 返回0 没有检索到 维普资讯 6 J r e s u l t 的元素个数 结果存在数组r e s u l t 中 3 3算法的复杂性 3 3 1 索引空间的大小 这里主要说明为实现模糊查询算法所要建立的索引空间的大小 设词典中所有单词占用 的存储空间为 S 个字节 则倒排文件占用的空间为2 S 个字节 证明很简单 因为单词中 字母的一次出现占用一个字节 在倒排文件中为记录该字母在第 i 个单词中出现 需占用两 个字节 因为词典中有 1 3 0 1 3 0个词条 所以将词典分成两部分 每一部分的词条步于 6 5 5 3 6 可用两个字节表示 这个索引空间很小 对 l 3 个单词的词典 倒排文件所占用的空 间不足2 M 3 3 2查询的时间复杂性 3 l 设查询检索式中有M个字母 词典中字母出现的次数最多为 N 参看 3 2 3 即 i 等 于M 集合A l p h a S e t 的元数最大为N 第 4 步求集合的交 由于两个集合的元素是有序 的 可用二分法求交集 时间复杂性为O N N 2 的循环次数为 M 因而总体时 间复杂性为O M N ig N 当M增大时 步 4 中集合r e s u l t 的元数不断减小 求交集的比较次数减少 所以实 际上总体时间不会由于 M的增大而线性增长 3 4 举例说明 对单词 a p p r o x ima t e 若只记得其中古有字母 a p m a t e 检索式可写戚 a p r oar e 解释检索式意义为 a p 在 m a t e 之前 中间可以有任意个字母 古有 p 的 单词 有 4 3 9个 集 合 r esul t 的值为 a p A P a p a c e a p a c h e a p a r a l y t i c a p a r a p h y s t e a p a r t a p p r o x i m a t e 含有 m a t e 的单词共有 8 2 个 集合A l p h a S e t 1 的值为 a c c l i ma t e a c h r o ma t e b i c h mma t e c a r b a ma t e d e c i ma t e e s t i ma t e f o r ma t e g l u t a r r Ia t e h e l p m a t e i l le g i t ima t e 集合 r e s ul t 与 A l p h S e t 求交集 得到结果 r e s u l t 为 a p p r o x i m a t e 达到了查询的目的 四 快速录人 4 1 模糊输入 利用第 3 节的模糊检索技术 可以实现单词的快速录入 该功能作为写作系统中编辑器 的功能之一 当用户记忆单词不准确时 或者想减少输入次数时 快速录入功能给用户提供 了有益的帮助 如单词 a n t ie s t a b l is h m e n t a li s t 有2 2 个字母 完整输入需击键2 2 次 实际 上只需输入 a n t i Mis t 1 1 个字母即可 当用户输入含有通配符的单词时 键入空格键表 示单词输入完毕 系统自 动进行模糊检索 列出满足要求的单词集合 若集合是一元的 直 接用该唯一的候选单词替换检索式 4 2词头输入 我们对具有 1 3 0 1 3 0 个单词的英文词典进行丁下面的统计工作 统计表明当输入单词 6 3 维普资讯 的前7 个字母之后 候选的单词个数平均不超过两个 如表 l 所示 这就说明当用户输入了 单词前 7 个字母时 系统就可以以这7 个字母作为一个单词在词典中模糊二分查找 4 l 文 4 详细证明了 r 用模糊二分查找方法 能够找到与输入词在词典中距离最近的词 例如 尽 管 g u a r d a g 不是单词 但是可以以 g u a r d a g 在词典中二分查找 能够找到与之词典序 最相邻的单词 g u a r d a g a i n s t 词头长 词头个数 词头相同的词个数 平均词头重复次数 H e a d NO R e p e a t N o R e p e a t No H e a d N c 5 2 8 0 6 2 9 8 5 2 4 3 5 1 6 4 3 8 3 7 7 8 7 5 2 1 8 0 7 5 7 0 8 4 5 9 2 5 6 1 0 4 8 6 5 2 4 2 4 2 6 7 4 0 6 5 9 6 8 6 8 2 2 9 1 8 9 0 2 4 1 0 6 7 6 0 9 1 1 8 8 9 7 0 2 8 表 l 词头重复的情况统计 表一说明 只输入5 个字母 平均有 5 个候选词 1 3 5 1 输入 6 个字母 候选词 3 个 输入7 个字母 候选词只有2 个 1 l 0 4 这就是为什么选择前 7 个字母在词典 中二分查找的原因 当只输入7个字母时 候选词仍很多时 用户可继续输入第 8 个乃至第 9 个字母 直到待输入的诃排在候选列表的前面 五 结论 本文介绍利用全文检索技术实现的词典的模糊查询和单词的快速录入 详细说明了用于 全文检索的特殊索引结构 词典的模糊查询解决了单词记忆不准确的情况下查找词典的困 难 快速录入提高了英文单词的录入速度 而且用户记忆模糊时 仍然能够正确快速的输 入 可以说 这种方法使编辑器具有一定的智能 因为它只利用部分信息 能够 知道 用 户想要输入的单词 目前 算法要求用户决定哪些确定信息需要用户给出 在快速录入时 影响了录入速度 的进一步提高 对单词 a n t ie s t a b l i s h m e n t a l is t 输入 a n t i t is t 还是 e s t a t a li s t 或 a r l t a g t a 用户当然希望选择的检索式使得候选的单词最少 这要求用户在多种检 索式之间作出选择 如果捡索速度极快 每当用户击键一次 候选的单词集合实时更新 当 候选集合中出现了用户想输入的单词时 用户只需选择单词 不必继续输入该词的检索式新 的确定信息 6 4 维普资讯 这种方法能针对汉语 索引的美键字是汉字 而不是英文字母 我们曾做过类似的实验 I 3 J 用于检索倒旬 用户能够以任意关键词 汉语或英语 检索双语倒句 参考文献 1 李生 赵铁军 机器词典的信息表示厦在设英机器翻译中的实现 中文信息学报 V o l 8 N o 1 2 赵铁军 高文 李生 机器翻译通用电子词典的实现构想 情报学报V O1 1 4 N o 6 3 刘小虎 李生等 在机助人译系统中参照双语例旬的策略 P r o e o f I n t e r n a t i o n a l C o n f e r e n c e o f O h i n e e C o mpu t i n ff一9 6 4 H M a r u y a m a B a c k t r a c k i n g F r e e D i c t i o n a r y A c c e s s Me t h o d f o r J a p a n e s e M o r p h o l o g i c a l A n a l i s T h e T h i r d Na t u M La n g u a g e P r o e o a s i n g P a c i i c Ri m S y mp o 6 i u m S o u l Ko r e a 1 9 9 5 5 G S e r a s s e t I n t e fl i n g u a l L e x i e M O r g a n i s h t i o n f o r Mu t i l i n g u a l L e x l c a l D a t a b a s e s i n N A D I A T h e F i ft e e n t h L t I n a t i o n a l C o n f e r e n c e o n C o mp u t a t io n a l L i n g u i s t i c s K y o m J a p a n A u g t m t 1 9 9 4 6 Z h o u M i n g D E A R A T r a n s l a t o r s Wo r k s t a t i o n T h e T h i r d N a t u a l L a n a a g e P r e c e d i n g P a c f i c R i m S y m p o s i u m S e n d Ko r e a 1 9 9 5 F u z z y d i c t i o n a r y l o o k一叩 a n d f a s t i n p u t wo r d i n ma c h i n e a i d e d t r a ns l a t i o n L i l i i a o h u L i S h e n g Wu We i B o x 3 2 1 De p a r t me n t o f Co mp u t e r S c i e n c e a n d En g i n e e r i n g Ha r b i n n i t u t e of Te e h n o l o g yo A t r a c t T h j s p a p e r p r e s e n t s a me t h o d o n d i c t i o n a r y l o o k u p a n d s l i n p u t w o r d b y s u b s e t l e t t e I 8 i n a w o r d L e x i c a l a i d i s v e ry i mp o r t a n t i e d i c t i o n a r y 1 o k u p i n a MA T m a c h i n e ai d e d t r a n s l a t i o n s y s t e m B u t i n ma n y c a a e t h e s p e l l