基于规则知识的英语词法分析研究_研究生入学考试_高等.pdf

收稿日期 2003 09 17 修订日期 2003 11 25 作者简介 郭永辉 1967 男 河南兰考人 副教授 博士研究生 主要研究方向 自然语言处理 机器翻译 王炳锡 1945 男 天津人 教授 博士生导师 主要研究方向 语音信号处理 自然语言处理 吴保民 1965 男 河南商丘人 副教授 硕士 主要研究方向 计算语言学 机器翻译 李剑 1980 男 辽宁海城人 硕士研究生 主要研究方向 自然语言处理 机器翻译 文章编号 1001 9081 2004 03 0071 04 基于规则知识的英语词法分析研究 郭永辉1 2 王炳锡1 吴保民3 李 剑1 1 解放军信息工程大学 信息工程学院 河南 郑州 450002 2 解放军信息工程大学 电子技术学院 河南 郑州 450004 3 解放军信息工程大学 理学院 河南 郑州 450001 gyh101 163 com 摘 要 词法分析是自然语言处理系统首要的词汇级语言分析模块 以 MatLink 英汉机器翻译 系统为基础 介绍了词法分析所要求的语言知识及其组织结构 并给出了处理这些语言知识的算法 该词法分析器结构模型不仅具有自学习功能 而且最大限度地从语义角度进行词汇级词语组合 实 验表明 它可以降低句法分析的复杂性 提高语言分析的正确率与分析效率 关键词 自然语言处理 机器翻译 词法分析 中图分类号 TP391 2 文献标识码 A Rule based Research on English Morphological Analysis GUO Yong hui1 2 WANG Bing xi1 WU Bao min3 LI Jian1 1 Institute of Information Engineering PLA Inf ormation Engineering University Zhengzhou Henan 450002 China 2 Institute of Electronic Technology PLA Inf ormation Engineering University Zhengzhou Henan 450004 China 3 Institute of Science PLA Information Engineering University Zhengzhou H enan 450001 China Abstract Morphological analysis is a lexical level functional module which lays in the beginning of natural language processing system Based on MatLink a English Chinese machine translation system the paper describes the linguistic knowledge and its representation for morphological analysis and introduces the algorithm for processing such linguistic knowledge The model of morphological analysis proposed in the paper not only has the ability of self study but also semantically combines words into phrase to the largest extent Experiment results on MatLink indicate that it can reduce the complexity of syntactic analysis and also improve the correct rate and analysis efficiency of nature language processing Key words natural language processing machine translation morphological analysis 1 引言 词法分析是指自然语言处理系统从接收输入词串开始到 对输入词串进行句法分析之前 对输入词串所进行的词汇级 的处理 1 它是各种自然语言处理系统 特别是机器翻译系 统中首要的源语言分析模块 是进行句法分析 语义分析的基 础 不同的翻译任务 由于源语言的词法结构不同 词法分析 的内容也不相同 对于英语这样的屈折语来说 句子中的词 通常要根据其语法意义产生各种形态变化 因此 去除形态 变化噪声 并从机器词典中读取词汇固有的包括词类在内的 有关信息 是以英语为源语言的词法分析的主要任务之一 除此之外 词法分析还根据构词和组词规律识别词典中未收 录的词汇 以及进行必要的词语组合 以便根据语言学知识 确定在当前输入句子的上下文中 各个词汇所应该具有的词 类特征 基于规则知识的词法分析是以语言学规则知识为知识 源 将真实语言文本变换为一个词性序列的过程 我们的英 语词法分析器采用数据驱动策略 包括预处理 形态分析 未 收录词处理和词组分析等几个功能模块 主要利用的知识源 有系统综合词典 派生词表 形态规则 构词规则和组词规则 其中派生词表是词法分析自学习的结果 见图 1 图 1 词法分析器结构模型 2 词典与规则 综合词典 派生词表与三种规则作为独立的数据基 是词 法分析器的主要知识源 在词法分析中具有重要作用 2 1 系统综合词典 为了提高词典的检索效率 降低信息冗余度以及保持词 第 24 卷第 3 期 2004 年 3 月 计算机应用 Computer Applications Vol 24 No 3 Mar 2004 典内容的一致性 在词典的设计中 我们采用一部英汉综合词 典代替传统的多部词典的策略 实验证明 这种做法在消除 词汇歧义 结构歧义和提高译文准确率等方面更具优越性 2 2 1 1 词典的逻辑结构 综合词典集词法 语义和目标生成信息于一体 是贯穿机 器翻译全过程的主要知识源 在设计综合词典过程中 我们 主要把握以下原则 一是区分个别知识与普遍知识 综合词 典只收录个别知识 而普遍知识则由各种规则描述 二是知识 丰富 全面 既包含语言学知识 也包含非语言知识 如领域 信息 和上下文约束知识 如限制规则 三是既面向用户 又 面向机器 我们对词典知识的描述以适合机器处理为主 同 时设计了词典管理模块 为用户管理 使用综合词典提供方 便 四是存储空间小 搜索速度快 实用化的机器翻译系统对 词典容量有一定的规模下限要求 因此 综合词典在存储上要 进行优化考虑 同时 也要采用更好的搜索算法以加快搜索速 度 五是可扩充性要强 增 删 改等操作要方便 综合词典 的逻 辑结构 可用巴 科斯 范式 Backus Naur Form BNF 描述如下 各项含义以及综合词典的存储结构可参见文献 3 2 1 2 词条的检索 综合词典的检索机制采用以词条为关键字的散列搜索 法 在物理结构上以一个词典信息文件为主体 外加一个散 列表和冲突表 此二表存放词条在词典信息文件中的 32 位地 址 考虑到该系统的词典容量只有几万条 因此设计散列地 址空间为 64K 即散列值为一个 16 位的无符号整数 使用的 散列函数为 HashVal word H MakeLower word H key key 0 a 否则 若 Address word 的 最高位 b31 0 说明该哈希码无冲突 Address word 即是 word 这个词条在词典信息文件中的地址 按该地址读取词条 信息即可 若 Address word 的最高位 b31 1 表明发生了 冲突 首先从 Address word 中分离冲突词条数 count 和冲突 词条在冲突表中的开始地址 h addr 然后从冲突表的 h addr 地址开始依次读取冲突词条在词典中的存放地址 w addr 并 根据 w addr 从词典中读出该词条 和 word 进行比较 若匹 配 说明查找成功 若不匹配 则继续读取下一冲突词条的地 址以同样方法处理 若 count 个冲突词条和 word 都不匹配 则查找失败 word 不在词典中 由于综合词典的设计是面向机器的 与用户的接口需要 专门的功能模块来实现 为此 我们设计了综合词典管理与 维护模块 它主要为词典词条及相应的短语和习语的增 删 改以及转换等操作提供用户接口 该模块为用户提供界面交 互和批处理两种操作方式管理和维护综合词典 2 2 形态规则 形态规则是指以规则的形式描述英语实词在句子中的形 态变化规律 这主要包括名词的复数和所有格 动词的第三 人称单数 过去式 分词 和现在分词 形容词 副词的比较级 和最高级 每一条形态规则可被看作一个四元组 Morph tail Original tail Category Morph 其中 Morph tail表示有形词的后缀 Original tail 表示源 词 对应的词典中单词 的后缀 Category 表示源词应具有的 词性 Morph 表示有形词的形态特征 这里 Morph tail 和 Original tail是字符串 Morph tail 的首字符可以为 用以 表示字母双写 Original tail可以为空串 例如 规则 s NOUN plural 表示了名词加 s 变复 数的规律 规则 ied y VERB v ed en 表示了以辅音字 母加 y 结尾的动词 把 y 变 i 加 ed 成为过去式或过去分 词的规律 规则 er ADJ adj er 表示了形容词双写 最后一个辅音字母加 er 变比较级的规律 Matlink 机器翻 译系统中共包含了 37 条形态规则 2 3 构词规则与派生词表 构词规则是指以规则的形式描述英语实词的词缀变化规 律 其规则形式类似于形态规则 每一条构词规则可被看作 一 个 六 元 组 Flag Affix Original affix Original cat Category Translation 其中 Flag 表 示 词 缀 类 型 标 识 可 为 PERFIX 或 SUFFIX Affix 表示派生词的词缀 Original affix 表示对应的 源词的词缀 Original cat 表示源词的词性 Category 表示派生 词的词性 Translation 表示派生词的译文模式 这里 Affix Original tail和 Translation 是字符串 当 Flag PERFIX 时 Affix 为派生词的前缀 其尾字符可以为 用以表示源词 首字母双写 当 Flag SUFFIX 时 Affix 为派生词的后缀 其首字符可以为 用以表示源词尾字母双写 Original tail 可以为空串 Translation 是由汉字与 组成的字符串 其中 表示源词的译文 例如 规则 SUFFIX er VERB NOUN 者 表 示了动词尾加 er 变名词的规律 其派生词对应的译文为 者 规则 PERFIX i ADJ ADJ 不 表示了形 容词加前缀 i 保持词性不变 而意义变为否定的规律 如 regular 规则的 加 ir 后变为 irregular 不规则的 对一个词来说 形态规则总是只使用一次 而构词规则可 多次使 用 如词 semiagricultural 通过使用规则 SUFFIX al e NOUN ADJ 的 和 PERFIX semi ADJ ADJ 半 就可由单词 agriculture NOUN 农业 得到其词 性为 ADJ 译文为 半农业的 派生词表是词法分析器在利用构词规则对未收录词进行 72 计算机应用2004 年 分析过程中所获得的单词列表 每一个派生词表项是如下结 构的四元组 派生词的词性和译文由该表给出 而其他特征 如语义特 征 类同源词 这里源词是词典中收录的单词 派生词表可 以像综合词典一样用于形态分析和未收录词处理 2 4 组词规则 组词规则是指以规则的形式描述英语词组的组合规律 在词法分析中分析英语词组对后续的句法分析和语义分析都 具有重要意义 组词规则可用 BNF 描述如下 由于组词规则是用文本文件存储的 每条规则占用一行 因此 规则中各成分的分隔要统一规定 具体如下 1 中各 或 之间由空格分隔 2 由中括号 括起来 3 由大括号 括起来 4 由尖括号 括起来 5 对于数词 若限制其值在一定范围 则初值与终值间 用逗号分隔 并用圆括号括起来 例如 规则 more ADJ BASE ADJ ER 更 2 表 示 more 与形容词原型构成形容词比较级 其译文是在形容词 第二个词 译文前加 更 字 规则 at NUM 1 59 past NUM 0 23 ADV sem Btime 4 点 2 分 表示由四个 单词组成的时间副词 第二个单词是数词 表示分钟 必须在 1 到 59 之间 第四个单词也是数词 表示小时 必须在 0 到 23 之间 如 at twenty past nine 可由上述组词规则确定为时间 副词 其译文为 9点 20 分 3 词法分析算法 词法分析算法利用上述知识源实现词法分析的功能 包 括形态预处理 形态分析 未收录词处理和词组分析等几个功 能模块的实现算法 3 1 形态预处理 尽管在书面英语中 总以空格作为单词的区分标志 但若 仅以空格为分界区分单词 常常会发生分词错误 因此 有必 要在形态分析前对英语句子进行形态预处理 形态预处理是 指在形态分析前对句中的标点符号 单词的缩写 如 Mr 与 连写 如 I m 等进行的特殊处理 常用的单词缩写与连写是 有限可枚举的 因此我们将其收录到词典中 对于句子中不存在功能歧义的标点符号 空格符及行结 束符 系统认为是单词分隔符 对于句子中存在歧义的标点 符号的处理主要有 1 可用作句号 缩写 小数点和网址 等 缺省情况认为是句号 用作缩写时 必须与其前面的字 符串构成词典中存在的缩写词 并且下一个字符是单词分隔 符 用作小数点时 必须其前后字符至少有一个是数字 另一 个可为数字或单词分隔符 用作网址时 通常其前后的分隔符 间有不止一个这样的 2 可用作逗号和数字分隔符 缺省情况认为是逗 号 用作数字分隔符时 必须后续的三个字符均为数字 3 可用作冒号 时分间隔符 缺省情况认为是冒号 用作时分间隔符时 必须与其前后两个字符构成 hh mm 的 形式 其中 hh 和 mm 都是 00至 59 的数字 4 可用作单引号 所有格和连写符 缺省情况认为 是单引号 用作连写符时 必须与其前后的字符串构成词典 中存在的连写词 用作所有格时 其后续字符必须是 s 或单 词分隔符 前接的字符串是词典中存在的名词 3 2 形态分析 形态分析就是将输入的英语句子中的每一个带有形态变 化的单词还原为其基本形式 并提取形态信息传递给句法层 次的分析 英语单词的形态变化分为规则和不规则两种形 式 不规则形式的单词集合是一个有限的闭集 因此可收录到 词典中 而规则形式的单词集合是一个无限的开集 无法而且 也不必要收录到词典中 英语单词的形态变化只改变其形态 特征 而不改变单词本身的词性 语义等性质 因此 对需要 进行形态还原的单词 只需读取其在词典中源词的所有特征 后 改变形态特征即可 为快速检索相应的规则 我们按照 Morph tail 的长度和 字母顺序为规则库建立索引 形态分析时对输入句子中的每 一个单词 做如下工作 1 查综合词典 若已收录 从词典中读取该词的有关信 息 转 4 2 查派生词表 若已收录 从词典中读取该词源词的有 关信息 并标注其词性和译文 转 4 3 对该词应用每一条形态规则 进行形态还原 a 判断该词后缀与规则的 Morph tail 是否匹配 若不匹 配 转 g b 去后缀 Morph tail 补后缀 Original tail 得到其源词 c 判断源词在综合词典是否收录 若已收录 转 e d 判断源词在派生词表中是否收录 若未收录 转 g e 判断源词的词性与 Category 是否匹配 若不匹配 转 g f 从词典中读取源词的有关信息 标识形态特征 Morph 转 4 g 若当前规则为最后一条形态规则 标志该词为未收录 词 转 4 h 试用下一条形态规则 转 a 4 若当前词为最后一个单词 算法结束 5 处理下一个单词 转 1 3 3 未收录词处理 一般来说 比较实用的机器翻译系统的词典收词量都非 常大 但面对真实文本 总会遇到词典中未收录的词 在机器 翻译的词法分析中 主要任务是确定句中单词的词性 以便为 句法分析打好基础 另外 目标生成阶段需要得到输入句子中 各单词的译文信息 因此 对于一个未收录词来说 如果能确 认其是已知的某一单词的派生词 我们就可以依据构词规则 得到其词性和译文 并将其收入派生词表 以便以后可直接利 用 对于非派生词的未收录词 我们认为其译文就是单词本 身 在句中其词性应是名词 动词 形容词和副词中的一个 对于人名 地名及其他专有名词总是具有名词特征 标为名 词 如果不具有这些名词特征 可认为它是兼有上述四种词 73第 3期郭永辉等 基于规则知识的英语词法分析研究 性的词 再由后续的词性标注模块采用规则及统计方法对其 词性进行削歧处理 对输入句子中的每一个单词 如果它是未收录词 做如下 工作 1 派生词检查 对该词应用每一条构词规则 a 根据词缀标志 Flag 判断该词的前缀或后缀与规则的 Affix 是否匹配 若不匹配 转 h b 去词缀 Affix 补源词缀 Original affix 得到其源词 c 判断源词在综合词典是否收录 若已收录 转 e d 判断源词在派生词表中是否收录 若未收 录 对源词应用每条构词规则递归调用本模块 e 判断源词 的词性与 Original cat 是否匹配 若不匹配 转 h f 从词典中 或通过 派生词表得到该源词 的有关信息 标识 其词性为 Category 并根据 Translation 和其源词的译文得到该派生词译 文 g 标志该词为派生词 并将其记入派生词表 返回 h 若 当前规则为最后一条构词规则 标志该词为非派生词 转 2 i 试用下一条构词规则 转 a 2 如果当前词为派生词 转 4 3 当前词为非派生词 若其首字母大写或所有字母大 写 则标识其为专有名词 否则 标识其为兼性词 置其译文 为单词自身 4 若当前词为最后一个单词 算法结束 5 处理下一个单词 转 1 3 4 词组分析 词组分析是指将单词序列组合成词组的过程 词组分析 包括依据词典信息进行的短语和习语识别 以及依据组词规 则所进行的词组识别 词组分析是词法分析器的重要组成部 分 它最大限度地从语义角度进行词汇级词语组合 以减轻句 法分析的负担 提高语言分析的正确率与分析效率 短语和习语是存储在综合词典中的个别语言知识 它们 都附着在其中心词条目下 短语更像某个单词 具有词性 形 态 语义等特征 有时它还与上下文单词具有某种搭配关系 短语可分为四种类型 即独立型 如 human being 搭配型 be interested in something 必插型 take somebody or something to somewhere 和可插型 break up 短语识别是以中心词为基 础向前和向后跳过可变成分 搜索需匹配的单词 习语相对 短语要简单一些 它可独立构成句子或句子成分 是固定型 的 习语识别也是以中心词为基础向前和向后搜索需匹配的 单词 短语和习语匹配成功后 需将这些单词组合在一起 根 据词典信息标识其各种特征和属性 词组分析的另外一个任务是依据组词规则进行词组识 别 词组识别时对输入句子中的每一个单词和每一条组词规 则 做如下工作 1 匹配 将词序列中每一个词与以当前词 为首的词序列匹配 匹配是指二者单词原型 词类 形态特 征 语义特征 子词类以及数值范围等完全一致 若不匹配 转 4 2 组合词序列 依据 标识其词性 形态特 征及其他属性 缺省的特征与属性同 标识的词 3 依据 生成该词组的译文 其中的 由该 标识的词的译文代替 转 6 4 若当前规则为最后一条组词规则 转 6 5 试用下一条组词规则 转 1 6 若当前词为最后一个单词 算法结束 7 处理下一个单词 转 1 4 散列函数选择实验 散列法是一种高效的搜索方法 但它依赖于选择合理的 散列函数 选择散列函数的目标是在散列空间一定的情况下 使 Hash 值随机性好 散列均匀 冲突少 从而使平均查找次数 少 散列函数以待查找的英语单词为自变量 因而可利用的 信息有构成单词的各个英文字母和单词长度 我们以前三个 字母 分别称为 A B C 尾字母 T 各字母叠加值 X 和长 度 L 为基础 在散列空间为 64KB 的情况下 设计了三种不 同组合的 16 位散列码计算方案 A L X T 3 A C L X T 3 脊线跟踪 细节点检测 中图分类号 TP391 41 文献标识码 A Fingerprint Minutiae Extraction by Following Its Ridge YANG Xiao dong NING Xin bao TAN Tai zhe Department of Electronic Science ridge following minutiae detection 1 引言 近年来 以指纹为代表的生物识别技术引起了人们的广 泛关注 由于具有唯一性和终身不变性 指纹日益成为当今应 用最为广泛的生物特征 1 自动指纹识别系统 AFIS 大多 是依靠细节特征 minutiae 来实现指纹识别的 准确 可靠地 提取细节特征是自动指纹识别的前提和基础 但噪声 对比 度失衡 几何形变 不正确的采集方法 以及对于干 湿 脏 老 化和磨损严重的指头 往往难以采集到清晰的指纹图像 会产 生大量的伪特征信息 丢失许多真正的特征信息 这就为特征 点检测的可信度带来一定困难 因此 细节点检测是指纹匹 配过程中一个非常关键的环节 一般的指纹细节特征提取算法大多由图像与背景分离 指纹增强 图像二值化 图像细化和细节特征检测等步骤组 成 这些步骤前后相关 如果前一步处理不好会影响到下一 步处理结果 因此 计算复杂度增加 运算速度减慢 另外 由 于处理步骤较多 在处理过程中还会产生许多伪细节点 丢失 一些真正的细节特征点 D Maio 与 D Maltoni 2 提出了一种 基于脊线跟踪的直接从灰度级指纹图像提取细节特征点的新 颖算法 而不必经过二值化和细化过程 X jiang 3 等在此基 础上作了一些自适应步长和细节点后处理方面的改进 它在 沿纹线方向和与纹线垂直