（计算机软件与理论专业论文）拼写校正技术在信息检索和文本处理领域的应用.pdf

中文摘要 拼写校正是自然语言处理领域研究的一个热点。随着信息检索和文本处理系 统的大规模应用，人工输入的文档中不可避免地包含拼写错误。对用户输入到搜 索引擎中的查询或包含错误拼写的文档的处理会带来计算机资源和用户时间的 极大浪费。 在针对拼写校正技术的广泛和深入调查的基础上，我们比较了拼写校正技术 在辅助信息检索和文本处理应用更正拼写错误的异同，分别为这两个领域设计并 实现了系统。在信息检索领域，在对海量网页查询日志分析的基础上，我们发现 错误拼写词与其正确拼写建议往往在相同或者类似的上下文中出现，而与其他拼 写相近的候选建议极少出现甚至不出现。我们使用分布式相似度指标对这种上下 文相似性进行度量。基于这个发现，我们首先采用了噪音信道模型，用分布式相 似度对其错误模型进行了改进；我们还将分布式相似度作为一个特征用于最大熵 判别模型中，结合编辑距离、发音相似度、语言模型等基本特征。在实验中我们 比较了噪音信道和最大熵模型的性能。 为更正文本处理应用中的拼写错误，我们提出了一种新的基于判别式重排序 拼写校正方法，第一次将拼写校正问题归结为一个排序问题，比较了传统上归结 为分类问题的优劣。该方法针对已有拼写校正系统( g n ua s p e u ) 的输出进行重排 序，使用判别式模型r a n k i n gs v m 来改进它的性能。它将现今较为成熟的拼写 校正技术以特征的形式整合到这个模型中来，显著地提高了基准系统a s p e l l 的初 始排序质量，同时也超过了一些商用系统( 如m i c r o s o f tw o r d2 0 0 3 ) 的拼写校正模 块。此外，针对模型学习标注训练对往往需要耗费大量人力物力的情况，我们还 提出了一种在搜索引擎查询日志链中自动抽取拼写校正训练对的新方法。采用这 种训练对的模型获得了基于人工标注数据模型所得结果相近的性能。 最后本文给出了拼写校正评测中的一些建议，对今后的研究工作进行了展 望，提出了若干值得研究的问题。 关键词：拼写校正机器学习分布式相似度排序式支持向量机查询日志链 a b s t r a c t s p e l l i n gc o r r e c t i o ni so d eo ft h eh o ts p o t si nr e c e n tn a t u r a ll a n g u a g ep r o c e s s i n g r e s e a r c h a st h ep e r v a s i v ea p p l i c a t i o n so fi n f o r m a t i o nr e t r i e v a la n dt e x tp r o c e s s i n g ， t h es p e l l i n ge r r o r sa 他u n a v o i d a b l ei nt h eh n m a n - t y p e dd o c u m e n t s t h ep r o c e s so f m i s s p e l l i n g si saw a s t eo ft i m ea n dm o n e y a f t e rc o n d u c t i n gat h o r o u g hs u r v e yo ns t a t e - o f - t h e - a r t s p e l l i n g c o r r e c t i o n t e c h n i q u e s ，w ec o m p a r e dt h ed i f f e r e n c e so fi t sa p p l i c a t i o n si nw e bs e a r c ha n dt e x t p r o c e s s i n g ，i m p l e m e n t i n gs y s t e m sf o rt h e s et w of i e l d s ，r e s p e c t i v e l y b a s e do nt h e a n a l y s i so fl a r g ev o l u m eq u e r yl o gd a t a , w ef o u n dt h em i s s p e l l i n g ss h a r et h em o s t s i m i l a rc o n t e x tw i t hi t sm o s ti n t e n d e dc o r r e c t i o nw o r d ；w h e r e a si t sc o n t e x ti sl e s s s i m i l a rw i t ho t h e rc a n d i d a t e s w ef i r s te m p l o y e dt h en o i s yc h a n n e lm o d e l ，w i t h i m p r o v e m e n ti ni t sc o m p o n e n te r r o rm o d e lu s i n gd i s t r i b u t i o n a ls i m i l a r i t yb a s e do n t h i sf i n d i n g n e x tw eu s e dd i s t r i b u t i o n a ls i m i l a r i t ya saf e a t u r ei nt h ed i s c r i m i n a t i v e m a x i m u me n t r o p ym o d e l ，、) l ，i t l le d i td i s t a n c e ，p h o n e t i cs i m i l a r i t y , a n dl a n g u a g em o d e l 嬲o t h e rf e a t u r e s i nt h ee x p e r i m e n t a lr e s u l t sp a r tw ee v a l u a t e dt h e s et w om o d e l s 。 t oc o r r e c tt h em i s s p e l l i n g si nt e x tp r o c e s s i n ga p p l i c a t i o n s ，w ep r o p o s e dan o v e l m e t h o dw h i c hi sb a s e do nd i s c r i m i n a t i v er e r a n k i n gf r a m e w o r k f o rt h ef i r s tt i m ew e d e d u c e dt h es p e l l i n gc o r r e c t i o na sar a n k i n gp r o b l e m , r a t h e rt h a nt h et r a d i t i o n a l c l a s s i f i c a t i o no n e t h i sm e t h o dr e r a n k st h eo u t p u to fe x i s t i n gs p e l l i n gc o r r e c t o ra s p e l l ， u s i n gr a n k i n gs v m i te m p l o y sc u t t i n g e d g es p e l l i n gc o r r e c t i o nt e c h n i q u e sa s f e a t u r e s ，g r e a t l yi m p r o v e di t sp e r f o r m a n c e i ta l s oo u t p e r f o r m e ds e v e r a lo f f - t h e - s e l f s p e l l i n gc o r r e c t o r s ，s u c ha st h eo n eu s e di nm i c r o s o f tw o r d2 0 0 3 t ol e v e r a g et h e g r e a tc o s to nh u m a na n n o t a t i o no ft r a i n i n gp a i ra c q u i s i t i o n ，w ea l s op r e s e n t e da f l e w m e t h o dt o a u t o m a t i c a l l ye x 仃a c tt r a i n i n gp a i r sf r o mw e bq u e r yl o gc h a i n t h e p e r f o r m a n c eo fm o d e lt r a i n e db yq u e r yc h a i np a i r si sc o m p a r a b l et ot h a to ft r a i n e do n h u m a n a n n o t a t e d p a i r s i nt h el a s ts e c t i o nw eg a v es o m es u g g e s t i o n so ns p e l l i n gc o r r e c t i o nt e s t i n g a c t i v i t i e s w ea l s or a i s e ds o m ep r o b l e mn e e d e df o rf u r t h e rr e s e a r c h k e y w o r d s ：s p e l l i n gc o r r e c t i o n ，m a c h i n el e a r n i n g ，d i s t r i b u t i o n a ls i m i l a r i t y , r a n k i n g s v m ，q u e r yl o gc h a i n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫童盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文版权使用授权书 山f 日 f 本学位论文作者完全了解苤壅盘堂有关保留、使用学位论文的规定。 特授权岙鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：歌面 签字日期：等山 新躲) 斤璃 签字日期：口1 年乙月f 日签字日期：口f 年乙月f 日 第一章绪论 1 1 选题背景 第一章绪论 拼写校正是自然语言处理领域研究的一个热点。早在上个世纪6 0 年代，人 们就开始了对文本拼写校正的研究工作，但现有的学术或商用拼写校正器在适用 范围和准确度上还不是很理想。随着计算机计算能力和存储容量的不断提升， i n t e m e t 的飞速发展，网上的可用信息不断增加，使得现有的文本、代码和数据 项还存在着大量的拼写错误亟待更正。而眼下w e b2 0 应用( 博客、维基、自定 义标签) 的不断涌现，互联网的用户也逐渐成为信息的主体发布者，拼写错误数 量呈上升趋势。搜索引擎查询和文本处理系统作为两种重要而常见的用户文字录 入接口，不可避免地大量接受包含拼写错误的输入。对这些包含错误拼写的信息 的处理，势必会带来人力和计算机资源的巨大浪费，甚至造成灾难性事件，例如 1 9 9 1 年夏天贝尔大西洋太平洋电话网络瘫痪就是由于其软件补丁包里的一个小 小的拼写错误 2 9 】。此外，很大一部分拼写错误都是计算机在接受终端用户的文 字输入时产生的，比如文字编辑、搜索引擎查询、数据库查询、语音识别等应用， 拼写校正对人机交互提供辅助。完善的拼写校正功能可以很好地增进用户体验。 为迎接这样的挑战，拼写校正还有一些问题尚待解决。举个例子来说，假设 英语单词的平均长度是5 ，如果一个文本识别设备正确地识别出了1 0 0 个字母中 的9 9 个( 9 9 的精度，已是很高了) 。但相邻的的5 个字母组成一个单词，2 0 个 单词错了一个，这时单词的识别精度降到9 5 。这就对一些文本、语音识别设备 的精度提出了更高的要求。只有拼写校正准确度的进一步提高，才能使这些设备 的应用更为广泛。此外，在诸如文本源代码编辑、计算机辅助教学、机器翻译、 数据库交互和一些语音应用中都需要有强大的拼写校正器辅助。 1 2 拼写校正研究现状 1 2 1 国际研究概况 国际上不少科研机构开展了对拼写校正理论和技术的研究工作，如微软雷德 第一章绪论 蒙德研究院、微软亚洲研究院、英国约克大学等等。拼写校正领域( 主要是英文 拼写校正) 比较好的综述文章主要有 2 7 1 和 2 9 1 。而这两篇文章都发表在上个世纪 末期。 国际拼写校正研究，尤其是英文文本拼写校正研究，可以分为三个依次深入 的基本问题：1 、非词错误识别；2 、单个词拼写校正；3 、上下文相关拼写校正。 对第一个问题的研究集中在上个世纪7 0 年代初到上个世纪8 0 年代初。解决思路 集中在使用模式匹配，字符串比较技术判断某个字符串是否在预定义的词典里 面。代表应用有u n i x 平台下的s p e l l 程序。对第二个问题的研究从2 0 世纪6 0 年代就已开始，至今仍有进一步的研讨。一些通用或专用的拼写校正、文本校对 技术得以开发出来。u n i x 下g r o p e 工具就是针对单个词拼写校正的。对上下文 相关拼写校正的研究开始于二十世纪8 0 年代。由于涉及上下文信息，这部分工 作与传统的自然语言处理理解技术关联比较紧密。上下文相关拼写校正最近的 研究热点是统计方法的应用。u n i x 平台下的w r i t e r sw o r k b e n c h 是解决上下文拼 写校正的一个尝试。我们可以把上下文相关拼写校正看作是单个词相关拼写校正 的扩展，因为它考虑了更多因素。 拼写校正模型方面，现阶段国际的研究工作主要放在改进噪音信道模型中的 错误模型上【1 】 5 】 8 】【1 1 】【2 8 】【3 6 】 4 2 1 【4 3 1 。这种改进错误模型的趋势主要基于 对字符串的编辑操作：如何衡量从一个字符串变换为另一个字符串的代价。从简 单的d a m e r a u l e v e n s h t e i n 距离( 即朴素编辑距离) ，到基于语料统计的字符串编辑 操作概率，都是从这个方面进行考虑的。噪音信道模型具有原理简单，参数估计 方便等特点，但在性能上仍有瓶颈。 1 2 2 国内研究概况 国内在拼写校正方面的研究主要是针对汉语文本处理展开。由于语言语系上 的巨大差别，某些适用于英文拼写校正的技术和方法对汉语并不太适用。中文拼 写校正基于汉语自然语言理解技术的研究，在进行查错纠错分析时，通过上下 文依存关系进行评判，而这恰恰是现今自然语言理解技术的瓶颈所在。 现阶段国内有不少单位开展了中文文本拼写校正理论和技术的研究，除了微 软亚洲研究院、m m 中国研究院、哈尔滨工业大学、清华大学、东北大学、北 第一章绪论 京师范大学、北京工业大学、山西大学等科研院所外，一些有实力的高新技术公 司，如北京黑马电子新技术公司、北大方正公司、金山公司等都开展了中文拼写 校正软件的研究和开发。 随着中文搜索引擎( 百度、雅虎中国、搜狗等) 访问量的不断增大，网页查询 也需要中文拼写校正技术的支持。同英文中的情况一样，中文网页查询与中文文 本在单词长度、单词分布上有所不同，不能直接照搬用于中文普通文本的拼写校 正技术。目前针对中文网页查询的科研文章在国内鲜有发表，其实现细节只是由 几家搜索引擎公司自主研发，未对外公布。 1 3 本文贡献 本文的贡献主要有以下几点： 1 、对国内外拼写校正历史尤其是近几年的热点和动向作出了细致的分析和 评价。从拼写校正工作流程、错误来源和类型、成型算法和模型、评测指标和评 测集合，以及中英文拼写校正的差异比较方面做了广泛而深入的调查。 2 、针对搜索引擎网页查询的拼写校正任务，我们首先采用了噪音信道模型， 用分布式相似度对其错误模型进行了改进；我们还将分布式相似度作为一个特征 用于最大熵判别模型中，结合编辑距离、发音相似度、语言模型等基本特征。获 得了良好的性能。 3 、为更正文本处理应用中的拼写错误，我们提出了一种新的基于判别式重 排序拼写校正方法，第一次将拼写校正问题归结为一个排序问题。该方法针对已 有拼写校正系统( g n ua s p e l l ) 的输出进行重排序，使用判别式模型r a n k i n gs v m 来改进它的性能。 4 、针对模型学习标注训练对往往需要耗费大量人力物力的情况，我们还提 出了一种在搜索引擎查询日志链中自动抽取拼写校正训练对的新方法。采用这种 训练对的模型获得了基于人工标注数据模型所得结果相近的性能。 5 、最后本文给出了拼写校正评测中的一些建议，对今后的研究工作进行了 展望，提出了若干值得研究的问题。 第一章绪论 1 4 本文的组织结构 第一章为绪论，介绍拼写校正课题的研究背景、研究价值以及拼写校正课题 的研究现状，然后列出本文的核心研究工作。 第二章综述拼写校正技术现状，包括问题描述、系统流程、拼写错误来源及 类型、成型算法、学习模型、结果评价方法等，并对中英文拼写校正技术的差异 进行比较。 第三章针对搜索引擎网页查询的拼写校正任务，我们提出了一种基于分布式 相似度的拼写校正方法。这种方法应用到两个学习模型中都取得了较好的性能。 第四章我们将介绍如何将用于文本处理领域的拼写校正归结为一个排序问 题而不是传统的分类问题，随后我们给出实验结果分析以证明这种思路的正确 性。此外，我们还提出了一种基于查询日志挖掘的机器学习训练对抽取方法，由 这种方法自动抽取的训练对获得了与人工标注训练对接近的性能。 第五章将总结本文的研究工作，对今后的研究工作进行了展望，提出了若干 值得研究的问题。 第二章拼写校正技术综述 2 1 拼写校正定义 第二章拼写校正技术综述 拼写校 e ( s p e l l i n gc o r r e c t i o n ) ：毛指针对由拼写检查器( s p e nc h e c k e r ) 检测出存 在于文本中的每个拼写错误，做出一个或多个更正建议的过程。在传统文献中人 们通常喜欢用拼写检查( s p e l lc h e c k i n g ) 指代拼写错误的检查及校正过程，实际上 这样做是不准确的。我们认为将整个过程称作拼写校正更为恰当一些。拼写校正 的具体过程可细分为四步，流程如图2 - 1 所示。 1 识别错误拼写 弋 7 i2 生成拼写建议的候选集合 旷 3 候选评分 u 4 对候选重新打分进行重排序 图2 1 拼写校正系统流程 首先由拼写检查器检测出用户输入中的错误拼写，然后拼写校正器针对错误 拼写按照一定规则在预定义的词典中进行搜索，找出满足规则的所有候选建议， 可能同时返回有词频等统计信息，生成候选集合。接下来拼写校正器的评分模块 会对这个候选集合中的每一个候选进行评分，按照应用的不同需要将一个或多个 建议返回。评分的方式可以是规则、概率、基于特征的加权得分等。评分考虑的 因素可以是编辑距离、发音相似度、词频，或这些因素的综合。上述三步是一个 完整的拼写校正系统所必须具备的。 第二章拼写校正技术综述 如果使用已有的拼写校正器而它的输出建议不尽如人意的话，可以进行第四 步：针对已有拼写校正器的候选集合进行重新评分以获得更高的准确度。这就相 当于在已有拼写校正系统前端加了一个适配器( a d a p t e r ) ，以满足特定的需要。重 新评分往往会考虑更多的影响因素作为判断依据，包括已有系统在第三步提供的 一些信息，比如为每个候选给出的具体分数，排名等等。本文第四章所做的工作 就是针对已有系统( g n ua s p e l l ) 在某些指标精度不理想的情况，使用一种判别式 模型对候选进行重排序以提高系统性能。 这几步工作流程是一个串行的过程，前一步的错误会给下一步工作带来很大 的影响，这就是在自然语言处理任务中常常出现的错误传递( e r r o rp r o p a g a t i o n ) i h l 题：如果拼写检查器漏判了某个错误拼写，那个接下来的几步工作都变得没有意 义；而如果拼写校正器为某个错误拼写生成的候选集合里不包含它的正确形式， 那么接下来的评分过程无论如何评判也无法输出正确建议。以此类推。如果只是 简单地放宽条件，可以使召回率等指标提高，但往往会带来响应速度等系统性能 的较大影响，所以有必要根据具体应用做出折中( t r a d e - o f f ) ，找到最佳方案。 接下来给出拼写校正的正规定义。针对每个错误拼写，一般做法是在给定词 典里找出所有编辑距离小于设定阈值的所有候选。这里m 表示错误拼写，c 代表 候选，g e n ( m ) 是m 的候选集合，下同。 g e n ( m ) = ( c ie d i t d i s t ( m ，c ) 0 b ，f ，p ，v 一 1 c ，g ，j ，k ，q ，s ，x ，z 一 2 d ，t 一 3 l 一 4 m ，n 一 5 $ 一 6 图2 4s o u n d e x 映射规则 s o u n d e x 2 9 首次提出了从发音上考虑单词相似度的思路，它使用7 条规则( 如 图2 4 所示) 将英文单词映射到一个保留首字母，接下来跟几个连续数字的字符 串。如果拼写错误的单词和某些正确单词具有相同的s o u n d e x 串，我们就可以把 这些正确单词作为拼写建议的候选集合。s o u n d e x 它主要考虑辅音的情况，对于 元音只是简单的滤去。举例来说，b u s h 专b 0 2 0 专b 2 ，b u s c h - yb 0 2 2 0 专b 2 ， 这是理想的情况。而对于q u a y l e - - q 0 0 0 4 0 - - q 4 ，或者k w a i l - - k 0 0 0 4 第二章拼写校正技术综述 k 4 来说，这就不是我们所想要的结果了。 总的来说s o u n d e x 提供了一种粒度较粗的单词发音映射规则。下面的 m e m p h o n e 、d o u b l em c t a p h o n e 对发音规则进行了细化，可以看作是对s o u n d e x 的改进。他们的基本思想一样，都是将每个字符串与一个发音键相对应，使那些 拼写相似的字符串具有相同或相似的键。当计算出某个误拼字符串的键值后，可 以在特定的字典里找出所有与该误拼字符串相似的单词，并将它们作为误拼字符 串的纠错建议。这为以往仅通过编辑距离生成候选的方法提供了一种新的思路。 5 、m e t a p h o n e 【3 9 】 m e t a p h o n e 是由l a w r e n c ep h i l i p s 发表在1 9 9 0 年的c “+ u s e r s j o u r n a l 上。 与s o u n d e x 相比，m e t a p h o n e 加入了一些基本的英语发音规则，因而精度较高。 6 、d o u b l em e t a p h o n e 【4 0 d o u b l em e t a p h o n e 作为m e t a p h o n e 的后续版本，由l a w r e n c ep h i l i p s 发表在 2 0 0 0 年的c c + + u s e r s j o u r n a l 上。之所以称为“d o u b l e ”是因为它在为字符串 返回主码( p m n a r yk e y ) 的同时还会返回一个从码( s e c o n d a