第２ｌ卷第６期 ２００７年１１月 中文信息学报 ＪＯＵＲＮＡＬ ＯＦ ＣＨＩＮＥＳＥ ＩＮＦＯＲＭＡＴＩＯＮ ＰＲＯＣＥＳＳＩＮＧ Ｖｏ１．２ｌ，Ｎｏ．６ ＮＯＶ．，２００７ 文章编号：１００３—００７７（２００７）０６—００５９－０６ 中文信息检索系统的模糊匹配算法研究和实现 王静帆，邬晓钧，夏云庆，郑方 （清华大学计算机系清华信息科学与技术国家实验室 技术创新和开发部语音和语言技术中心，北京１０００８４） 摘要：在现代中文信息检索系统中，用户输入的字符串和实际数据库中的条目往往存在局部偏差，而基于关键词 匹配的检索技术不能很好地解决这一问题。本文参考并改进了Ｔａｒｈｉｏ和Ｕｋｋｏｎｅｎ提出的过滤算法 ］，针对汉字 拼音输入法中常出现的同音字／近音字混用现象，将算法进一步扩展到广义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ上。实验表明，本文提 出的算法能有效提高中文信息检索系统的召回率，在实际应用中可达到“子线性”的效率。 关键词：计算机应用；中文信息处理；模糊匹配；过滤算法；动态规划 中图分类号：ＴＰ３９ｌ 文献标识码：Ａ Ａｎ Ａｐｐｒｏｘｉｍａｔｅ Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｃｈｉｎｅｓｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ Ｓｙｓｔｅｍｓ ＷＡＮＧ Ｊｉｎｇ～ｆａｎ，ＷＵ Ｘｉａｏ—ｊ ｕｎ，ＸＩＡ Ｙｕｎ—ｑｉｎｇ，ＺＨＥＮＧ Ｆａｎｇ （Ｄｅｐｔ．ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉ．＆Ｔｅｃｈ．Ｔｓｉｎｇｈｕａ Ｕｎｉｖｅｒｓｉｔｙ， Ｃｅｎｔｅｒ ｆｏｒ Ｓｐｅｅｃｈ ａｎｄ Ｌａｎｇｕａｇｅ Ｔｅｃｈｎｏｌｏｇｉｅｓ，Ｄｉｖｉｓｉｏｎ ｏｆ Ｔｅｃｈｎｉｃａｌ Ｉｎｎｏｖａｔｉｏｎ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， Ｔｓｉｎｇｈｕａ Ｎａｔｉｏｎａｌ Ｌａｂｏｒａｔｏｒｙ ｆｏｒ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ １０００８４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｅ ｍｏｄｅｒｎ Ｃｈｉｎｅｓｅ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ ｓｙｓｔｅｍｓ，ｃｌａｓｓｉｃａｌ ｋｅｙｗｏｒｄ ｂａｓｅｄ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ ｃａｎ ｎｏｔ ｗｏｒｋ ｗｈｅｎ ｔｈｅ ｉｎｐｕｔ ｓｔｒｉｎｇ ｉｓ ｄｉｆｆｅｒｅｎｔ ｆｒｏｍ ｔｈｅ ｅｎｔｒｉｅｓ ｉｎ
ｔｈｅ ｄａｔａｂａｓｅ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ Ｔａｒｈｉｏ ａｎｄ Ｕｋｋｏｎｅｎ’Ｓ ｆｉｌｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｔＯ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ．Ｂｅｃａｕｓｅ ｔｈｅ Ｃｈｉｎｅｓｅ Ｐｉｎｙｉｎ ｔｙｐｅｗｒｉｔｉｎｇ ｕｓｕａｌｌｙ ｃｏｎ— ｓｉｓｔｓ Ｃｈｉｎｅｓｅ ｃｈａｒａｃｔｅｒｓ ｗｉｔｈ ｔｈｅ ｓａｍｅ ｏｒ ｓｉｍｉｌａｒ ｐｒｏｎｕｎｃｉａｔｉｏｎｓ，ｗｅ ｄｅｆｉｎｅｄ ａ ｓｐｅｃｉａｌ Ｅｄｌｔ Ｄｉｓｔａｎｃｅ ａｎｄ ｅｘｐｅｎｄｅｄ ｏｕｒ ｍｅｔｈｏｄ ａｃｃｏｒｄｉｎｇｌｙ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗｅｄ ｔｈａｔ ｏｕｒ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｒｅｃａｌｌ ｒａｔｅ ｏｆ ｔｈｅ ｒｅ— ｔｒｌｅｖａｌ ｓｙｓｔｅｍｓ ａｎｄ ｏｂｔａｉｎ ｐｒａｃｔｉｃａｌ ｓｕｂ—ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ． Ｋｅｙ ｗｏｒｄｓ：ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎ；Ｃｈｉｎｅｓｅ ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ；ａｐｐｒｏｘｉｍａｔｅ ｍａｔｃｈｉｎｇ；ｆｉｌｔｅｒ ａｌｇｏｒｉｔｈｍ；ｄｙｎａｍｉｃ ｐｒｏｇｒａｍｍｉｎｇ １ 引言 现有的信息检索系统大部分采用基于关键词匹 配的检索技术ｌ＿２］。在实际应用中，用户往往凭借印 象进行检索，有时只能模糊地描述查询目标，输入的 关键词无法和数据集合中保存的数据完全一致；另 一方面，在构建数据集时引入的错误（如ＯＣＲ识别错 误等）也可能造成这些数据无法被用户获取。在上述 情况下，传统的检索系统将难以从数据集中查找到所 需要的信息。本文采用模糊匹配方法查找数据集中 和用户输人相似的项，并根据相似度排序输出结果， 以部分解决上述问题。模糊匹配方法还可以用于其 他领域，如入侵检测、信息过滤、基因检测等＿３“ 中文用户大部分使用拼音输入法。用户输入查 询串时选词错误造成的同音字替换是很典型的一种 现象；方言、发音习惯等造成的音近字替换（如南方 方言中，ｚｈ和ｚ不分）是第二种典型的错误现象。本 文针对这些错误，提出了一种考虑同音字／近音字替 换的距离度量方法，在此基础上建立模糊匹配算法。 收稿Ｅｔ期：２００７－０１—０９定稿Ｅｌ期：
２００７ ０９ １０ 作者简介：王静帆（１９８２一），女，硕士生，研究方向为自然语言处理；邬晓钧（１９７６一），男，博士，助研，研究方向为ＶＩ语对 话系统和自然语言处理；郑方（１９６７一），男，博士，教授，研究方向为语音信号处理。 维普资讯 http://www.cqvip.com
６Ｏ 中文信息学报 ２背景简介 字符串的模式匹配（精确匹配）问题是：给定目 标字符串ｓｔｒ和模式串ｐａｔ，在ｓｔｒ中寻找ｐａｔ的匹配 位置。其经典算法有Ｋｎｕｔｈ—Ｍｏｒｒｉｓ－Ｐｒａｔｔ（ＫＭＰ）Ｅｓ］， Ｂｏｙｅｒ—Ｍｏｏｒｅ（ＢＭ） 等。实际应用中，ＢＭ算法及 其改进型（如ＢＭＨ［７ 等）能达到极高的效率（子线 性），被各种检索系统广泛使用Ｉ＿３ ］。 类似的，字符串的模糊匹配目标是在ｓｔｒ中查 找与ｐａｔ相似的字串位置。普遍采用Ｅｄｉｔ Ｄｉｓｔａｎｃｅ （ＥＤ）来刻画两个字符串的距离Ｉ＿３］。设Ａ，Ｂ为两个 字符串，狭义的ＥＤ（Ａ，Ｂ）定义为：把Ａ转换成Ｂ 需要的最少删除（删除Ａ中一个字符）、插入（在Ａ 中插入一个字符）或替换（把Ａ中的某个字符替换 成另一个字符）次数。直观地；两个串互相转换需要 经过的步骤越多，相差越多。模糊匹配问题转化为 对给定正整数ｋ，找出ｓｔｒ的所有子串ｓ ，使得ＥＤ （ｓ ，ｐａｔ）＜志。 模糊匹配技术的策略主要有以下四种 ］：１．动 态规划 ］，２．自动机口 ，３．位平行策略Ｉ＿ｌ ］，４．过滤 策略口］。将它们结合使用，常常可以获得更高的时 间效率Ｅ１３￣ｌｓ］。 本文基于Ｔａｒｈｉｏ和Ｕｋｋｏｎｅｎ提出的过滤算 法［１］（ＴＵ过滤算法），配合带剪枝的动态规划算 法 ］，在以下两方面进行了改进：１．扩展了原有过 滤算法，使之能处理更一般的情况；２．针对中文中特 有的同音字／近音字替换问题定义了广义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ，并扩展了过滤算法和动态规划算法以解 决该距离度量下的模糊匹配问题。 本文的余下部分安排如下：第３节简单介绍动 态规划及剪枝算法 ］和ＴＵ算法＿１ ；第４节介绍我 们对ＴＵ算法的扩展；第５节针对同音字／近音字问 题定义了广义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ，并提出该距离度量 下解决模式匹配的基于ＴＵ过滤和剪枝动态规划算 法；第６节给出实验结果和分析，最后是结论。 ３ 动态规划和ＴＵ过滤算法 为了更好的说明模糊匹配算法，首先定义可能 用到的符号：字符集∑上，目标
字符串为ｓｔｒ，长度 为 ，模式字符串ｐａｔ，长度为ｍ。两个匹配串之间 的最大Ｅｄｉｔ Ｄｉｓｔａｎｃｅ为ｋ，错误率上界为ａ，ａ—ｋ／ ｍ。用ｓＥ０，…， ］表示字符串ｓ的一个子串，下标由 ０开始。 ｓｔｒ的每个子串可以表示为其前缀子串的后缀 子串，动态规划方法 计算了ｐａｔ的前缀子串ｐａｔ ［０，…，ｉ一１－１和ｓｔｒ的前缀子串ｓｔｒ Ｅｏ，…， 一１］的 后缀子串的最小Ｅｄｉｔ Ｄｉｓｔａｎｃｅ，记入Ｄ（ｉ， ）。 Ｄ（０，Ｊ）一０（ 一０，１，…， ） Ｄ（ｉ，０）一Ｄ（ｉ一１，０）４－１ （ｉ一１，２，…，ｍ） Ｄ（ｉ，Ｊ）一ｍｉｎ｛Ｄ（ｉ～１， 一１），Ｄ（ｉ～１， ）， Ｄ（ｉ，Ｊ一１）｝４－１ ｉｆ ｓｔｒＥＪ一１］≠ｐａｒ２ｉ一１］ 一Ｄ（ｉ一１，ｊ．～１） ｉｆ ｓｔｒＥＪ一１］一ｐａｔＥｉ—１］ （ —ｌ，２，…，ｍ，Ｊ—ｌ，３，…， ） Ｄ（ｉ， ）只和Ｄ（ｉ～１． ），Ｄ（ｉ， ～１），Ｄ（ｉ一 １， —１）有关，分别对应于对ｐａｔ［ｉ一１］的删除、插 入、替换或匹配操作，计算（ ４－１）ｘ（ ４－１）的动态 规划矩阵Ｄ，复杂度为０（ｒａｎ）。 Ｕｋｋｏｎｅｎ［３ ］证明，在狭义ＥＤ定义下，Ｄ沿对 角线从左上到右下，元素值非严格单调递增。对每 列的最后一个元素Ｄ（ ，Ｊ），如果Ｄ（ ，Ｊ）＞ｋ说 明在该位置上不能找到和ｐａｔ匹配的子串。若 Ｄ（ｉ， ）＞志，其具体值不影响后来的计算。记下列 中不大于ｋ的最后一个元素的位置ｌａｓｔ，对 ＋ｌ 列，只需计算Ｄ（０，Ｊ ４－１），Ｄ（１． ＋１），…，Ｄ（１ａｓｔ ＋１， ＋１）。这种方法被称为ｃｕｔ—ｏｆｆ ｈｅｕｒｉｓｔｉｃ剪 枝，把时间复杂度减小到Ｏ（ｋｎ）。配合ｃｕｔ—ｏｆｆ ｈｅｕ— ｒｉｓｔｉｃ剪枝的动态规划是目前为止最快，也是唯一具 有实用价值的基于动态规划的模糊匹配方法。 和动态规划方法不同，过滤算法不能直接计算 得到ＥＤ值，必须配合其他方法使用。分为两个阶 段：①在较少的时间消耗下过滤掉大部分无法匹配 的位置；②对余下可能匹配的位置调用其他方法定 量计算ＥＤ值。过滤算法目标是在快速过滤掉无法 匹配的位置。 ＴＵ算法出发点是用近似方法找到并过滤掉Ｄ 中必然大于ｋ的Ｄ（ｉ， ），实现上借鉴了ＢＭＨ算 法 中从右向左扫描ｓｔｒ串，寻找失败位置，跳跃性 移动ｐａｔ串，以及通过预处理减少查找
时间的思想， 通过查找“坏字符”，滤掉ｓｔｒ中Ｅｄｉｔ Ｄｉｓｔａｎｃｅ必然 大于ｋ的大部分子串位置。 在动态规划矩阵Ｄ中，记录下每个元素Ｄ（ｉ，ｊ．） 的来源（即Ｄ（ 一１， ），Ｄ（ｉ， —１），Ｄ（ｉ一１， —１）之 一），可跟踪每个Ｄ（ｉ， ）的生成路径。Ｄ（ｍ， ）的 生成路径称为ｊ．上的最小化路径，若Ｄ（ ， ）＜志， 该路径称为成功的最小化路径。每条最小化路径对 应于一个成功的匹配。Ｔａｒｈｉｏ和Ｕｋｋｏｎｅｎ证明了： 维普资讯 http://www.cqvip.com
６期 王静帆等：中文信息检索系统的模糊匹配算法研究和实现 ６１ 在Ｄ矩阵中，成功的最小化路径不能跨越多于是条 对角线。在此基础上，定义坏字符如下：对ｐａｔ中 的位置ｉ，若字符ａ ｛ｐａｔ［ 一是］，ｐａｔＥｉ一是＋１］， …，ｐａｔＥｉ＋是］｝，把ａ定义为位置ｉ上的一个“坏字 符”。在成功的匹配中，一个坏字符将造成Ｅｄｉｔ Ｄｉｓｔａｎｃｅ至少增加１。若一条最小化路径经过对角 线ｈ（设Ｄ（ｉ， ）对应对角线为ｈ一 一ｉ），则ｓｔｒＥｈ， …，ｈ＋ 一１］中的“坏字符”数不大于是。若找到是 ＋１个坏字符，该位置的匹配失效，跳跃到下一位 置；否则调用动态规划方法计算该位置附近子串ｓｔｒ ［＾一是，…，ｈ＋ 一１＋是］和ｐａｔ的最小Ｅｄｉｔ Ｄｉｓ— ｔａｎｃｅ。 每种匹配方案对应ｓｔｒ和ｐａｔ的一种对齐方式。 一个成功匹配最多允许是次操作，所以在ｓｔｒ中的 连续是＋１个字符中至少有一个等于ｐａｔ中的某个 字符，也就是说，考察单个字符ａ在ｐａｔ中出现的位 置将可以近似排除ｐａｔ和ｓｔｒ中不可能的匹配位置， 指导ｐａｔ“跳跃”到下一个可能匹配的位置。 Ｔｕ算法过程如下： 预处理阶段，可通过扫描一次ｐａｔ构建最小跳 跃距离表格ｄ和坏字符表格ｂａｄ。ｂａｄＥｉ，ａ］指示在 ｐａｔＥｉ￣和ｓ ｒ［ ］一ａ对齐时，ａ是否为坏字符；ｄ［ ， ａ］指示对应情况下，下次可能匹配成功的最大跳跃 的长度。 ｂａｄＥｉ，ａ］一 ｉｆ（了Ｚ）， 埘一 （１） ａｎｄ Ｚ一是≤ｉ≤Ｚ＋是 ｏｔｈｅｒｗｉｚｅ ［ ，ａ —ｍｉｎ｛ｚ ｌ（ｚ一 ）ｏｒ（０＜ｚ＜ ａｎｄ ｐａｔＥｉ—ｚ］一ａ）｝ （２） ａ Ｅ＞ ， 一是一１≤ｉ＜ 字符串比较过滤阶段，在当前位置ｈ上把ｐａｔ —ｐａｔＥＯ，…， 一１］串和ｓｔｒ的子串ｓ 一ｓｔｒＥｈ，…，ｈ ＋
一１］对齐（＾初始化为０），从ｓｔｒＥｈ＋ 一１］开始 向左扫描ｓｔｒ子串。对ｓｔｒＥｈ＋ ］（ 一 一１， 一２， …，０），查询ｂａｄ表确定是否坏字符。同时对ｉ Ｅ ［ 一１一是， 一１］，查表获得ｎｅｘｔｄ—ｍｉｎ｛ ［ ，ｓｔｒ ［＾＋ ］］｝作为下个可能匹配的最小跳跃距离。若 找到大于是个坏字符，说明经过该对角线的所有的 “最小化路径”的权值之和均大于是，不能满足模糊 匹配的要求，可以跳到下一个位置。Ｕｋｋｏｎｅｎ证明 了，当２是＋１≤ 时，若在ｓｔｒＥｈ＋是，…，ｈ＋ 一１］这 一是个字符中，有多于是个坏字符，可以把ｐａｔ向 右移动至少是＋１个位置，即ｎｅｘｔｄ—ｍａｘ｛ｎｅｘｔｄ，是 ＋１｝。 在ａ较小，Ｉ∑Ｉ较大的情况下，由于第一阶段 快速滤去了大部分不匹配的位置，该方法时间效率 能达到“子线性”。 ４ 改进的ＴＵ过滤算法 文献［１］证明了，在ｓｔｒＥｈ＋，…，ｈ＋ 一１］这 一是个字符中，若有多于是个“坏字符”，可以把 ｐａｔ向右移动至少是＋１个位置。但是，当２是＋１＞ 时，ｓｔｒＥｈ＋是，…，ｈ＋ 一１］中不可能找到多于是 个坏字符，原过滤算法不可用。 在这种情况下，我们证明了：若从后向前扫描 到的第是＋１个“坏字符”为ｓｔｒＥｈ＋“］（０≤“＜是）， 则至少可以移动“＋１个位置，即下一步只需比较 ｐａｔ和ｓ ｒ［＾＋“＋１，…，＾＋“＋ ］。 证明：对坏字符ｓｔｒＥｈ＋ ］（“≤ ＜ 一１），由坏 字符的定义，ｓｔｒＥｈ＋ ］ ｛ｐａｔＥｉ一“］，ｐａｔＥｉ一“＋ １］，…，ｐａｔＥｉ－－１］｝所以对角线ｈ＋１，ｈ＋２，…，ｈ ＋“范围内所有的最小化路径的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ都大 于是。 因此，若在ｓｔｒＥｈ，…，ｈ＋ 一１］中找到是＋１ 个坏字符，则下一步的移动距离为ｎｅｘｔｄ—ｍａｘ ｛ｎｅｘｔｄ，“＋１｝，至少移到对角线ｈ＋“＋１上，从ｓｔｒ ［ ＋ ＋“］开始向左扫描，不会漏解。若在ｓｔｒ［＾， …，ｈ＋ 一１］中找不到是个坏字符，则ｓｔｒＥｈ一是， …，ｈ＋是＋ 一１］的某个子串ｓ 和ｐａｔ可能满足ＥＤ （ｐａｔ，ｓ ）≤是，调用动态规划算法精确计算。这里， 最坏的情况下可能出现只移动１个位置的情况。 综合以上两种情况，改进后的算法可描述为： 令第是＋１个坏字符的下标为ｈ＋“，最小跳跃距离 ｎｅｘｔｄ≥ｍｉｎ｛是＋１，“＋１｝
。 ５基于广义Ｅｄｉｔ Ｄｉｓｔａｎｃｅ的扩展 ５．１ 新的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ定义 给插入、删除、替换以不同的代价，可以得到广 义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅｌ３］。 令对ｐａｔ插入和删除一个字符的代价分别为 ｒ 和ｒ ，替换的代价根据不同的替换字符定义，只 需满足距离的一般定义，即： １．ｃｏｓｔ（ａ－＊ｂ）＞０（当ａ≠６） ２．ｃｏｓｔ（“ ａ）一０ 维普资讯 http://www.cqvip.com
６２ 中文信息学报 ３．ｃｏｓｔ（ｎ一６）≤ｃｏｓｔ（ｎ—ｃ）十ｃｏｓｔ（ｃ一６） 且所有代价均大于０小于正无穷。 我们将过滤算法和扩展的ＴＵ算法进行了扩 展，以处理这种广义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ。 ５．２扩展的动态规划剪枝算法 扩展后的递推公式如下： Ｄ（Ｏ，ｊ：）一０（ｊ：一０，ｌ，…， ） Ｄ（ ，０）一Ｄ（ —ｌ，０）＋ｃ出ｆ （ｉ—ｌ，２，…， ） Ｄ（ｉ， ）一ｍｉｎ｛Ｄ（ —ｌ， 一１） ＋ｃｏｓｔ（ｐａｔ［ｉ－－１］一ｓ ｒ［ 一１］）， Ｄ（ —ｌ，ｊ：）＋ｃ出 ， Ｄ（ｉ，ｊ：一１）＋ｃ ｝ （ —ｌ，２，…，ｍ，Ｊ—ｌ，３，…， ） （３） 我们证明了（详细证明见附录Ａ），在５．１定义 下，动态规划矩阵中的主对角线依旧是非严格单调 递增，可以采用ｃｕｔ—ｏｆｆ ｈｅｕｒｉｓｔｉｃ剪枝算法。 ５．３扩展的改进ＴＵ过滤算法 接下来，再将改进的过滤算法扩展到广义的 Ｅｄｉｔ Ｄｉｓｔａｎｃｅ意义下。 设ｇ—ｋ／ｍｉｎ｛ ，‰｝，与前类似，一条成功的 最小化路径不能跨越多于ｑ条对角线，因为从当前 对角线到达相邻对角线，必然经过水平或者竖直方 向的转移，每一步转移的代价不小于ｍｉｎ｛ｃ如 ，‰｝。 成功的最小化路径 被限制在以 为中心的２ｇ＋ｌ 条对角线范围内。 设 一ｍｉｎ｛ｃ出 ，‰，ｃｏｓｔ（ｎ一６）｝，新的“坏字 符”定义如下： 设ｓｔｒ［ｊ］和ｐａｔ［ｉ１对齐，若ｓｔｒ［ｊ］ ｛ｐａｔＥｉ— ｇ］，ｐａｔ［ｉ—ｇ＋１］，…，ｐａｔ［ｉ＋ｇ］｝，把ｓｔｒ［ｊ］称为 该比较对角线上的一个“坏字符”，“坏字符”必然造 成该匹配位置上ＥＤ值增加至少 。若一条成功 的最小化路径经过对角线 ，则它在 上的“坏字 符”数不大于ｋ／ｃ…。新的算法为：对齐ｐａｔ和ｓｔｒ 的子串Ｓ 一ｓｔｒ［ｈ，…， ＋ 一１］，从右向左扫描Ｓ ， 若找到ｋ／ｃ…＋１个坏字符，该位置的匹配失
效，跳 跃到下一位置，设第ｋ／ｃ 。 ＋１个坏字符的下标为 ＋ ，最小跳跃距离ｎｅｘｔｄ＝ｍｉｎ｛ｇ＋ｌ， ＋ｌ｝；否则 调用动态规划方法计算该位置附近子串ｓｔｒ［ｈ—ｑ， …， ＋ —ｌ＋ｇ］和ｐａｔ的最小ＥＤ。 特定应用中，可能给某些字符替换定义了很高 的相似度，导致 很小，过滤时必须扫描很多字 符，更糟糕的是，无法保证ｋ／ｃ ≤ｍ，即扫描了整个 串都找不到足够的“坏字符”。总之，考虑每个细节 将使过滤算法失掉高效的优点。这时可以略微放宽 限制，只保证不滤掉可能解，及能滤掉大部分不可能 解，把细节的考察放到动态规划评分中。改进思路 是：在过滤阶段只选用其中足够大的插入／删除／替 换代价计算，把很“相似”的当成相等处理： ｆ ｃｏｓｔ（ａ一６）ｉｆ ｃｏｓｔ（ａ一６）＞ｔｃｏｓｔ ｃｏｓｔ２（ａ ６）一ｆ ０ ｅｌｓｅ Ｉ （４） 其中，ａ，ｂ不全为空。ｔｃｏｓｔ是一个阈值，用来 分开“相似”和“不相似”，必须满足ｋ／ｔｃｏｓｔ＜ｍ。 ｔｃｏｓｔ过小可能导致过滤阶段时间效率降低，过大可 能导致第二阶段的计算量增加。我们认为空字符和 任何其他的字符都不相似，在这种假设下，可以令 ｔｃｏｓｔ＝ｍｉｎ ，ｃ如 ｝。这样的替换不会漏掉可能的 匹配位置。 ５．４用于同音字／近音字处理 在中文信息检索的实际应用中，大量用户由于 使用拼音输入法经常产生同音字／近音字的错误。 同音字是现代汉语里语音相同但字形、意义不同的 字。所谓语音相同，一般是指声母、韵母和声调完 全相同．如“江”和“姜”。近音字是在现代汉语里语 音相近，但字形，意义不同的字。在这里我们处理了 几种常出现的近音字混用：１．声韵母相同，但声调 不同，如“江”和“讲”２．声母、韵母存在差异但发音相 近的字，包括前后鼻音混用（ｉｎｇ／ｉｎ，ａｎｇ／ａｎ，ｅｎｇ／ ｅｎ），平舌卷舌混用（ｚ／ｚｈ，ｃ／ｃｈ，ｓ／ｓｈ）。在进行模 糊匹配时，我们给同音字／近音字替换赋予较小的权 重（ｃｏｓｔ为０．５），给其他替换和插入删除操作赋予 较高的权重（ｃｏｓｔ为１），采用以上的过滤算法配合 带剪枝的动态算法计算Ｅｄｉｔ Ｄｉｓｔａｎｃｅ，取得了很好 的效果。 ６ 实验结果 本次实验的数据包括歌曲名称数据库和用户查 询日志，实验环境为Ｗｉｎｄｏｗｓ ＸＰ，记录的时间并非 程序的绝对运行时间，只是开始和结束时间之差，并 未除去系统调度
的时间。所以我们只考虑时间的相 对意义而不考虑其绝对意义。被检索的是一个歌曲 数据集合，包含了６００左右歌手／乐队名和５ ０００左 右的歌曲名称。查询词是一段时间内的用户查询日 维普资讯 http://www.cqvip.com
６期 王静帆等：中文信息检索系统的模糊匹配算法研究和实现 ６３ 志，包含大约２００ ０００个查询串。 在ｍ一６时对三种算法进行对比：精确匹配 ＢＭＨ算法，狭义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ汉字匹配的过滤 算法（ａ＝＝＝０．４，ｍ一６），以及带同音字／近音字广义 Ｅｄｉｔ Ｄｉｓｔａｎｃｅ扩展的过滤算法（ａ一０．４，ｍ一６，取同 音字／近音字替换代价为０．５），后两个算法的第二 阶段均采用带剪枝的动态规划算法。实验结果如图 １所示，对于相同的数据集合，模糊匹配比精确匹配 可以检索到更多的条目，而考虑同音／近音字能进一 步提高召回率。 一 豁 皿 弭 簿 圈精确匹配一狭义ＥＤ图广义ＥＤ 图１不同距离度量下的输出比较 接下来，我们对四种算法（在汉字集合上的动态 规划和过滤算法，带同音字／近音字的扩展Ｅｄｉｔ Ｄｉｓｔａｎｃｅ下的动态规划和过滤算法）的时间效率进 行比较，实验结果如图２所示。 ７０ 譬６０ ５０ 害４０ 嚣３０ ２０ １０ ０ ／ ／ ／ ／ ／ 一／ ． ＝＝： ●—————一 ＋汉字动态规划 一汉字过滤 ＋扩展动态规划 —＊一扩展过滤 ａ＝０．２ ０．４ ０．６ ０．８ 图２各算法时间效率比较 实验证明： １．两种过滤算法的时间效率都优于动态规划， 过滤算法能有效提高时间效率。汉字集合上的过滤 算法时间效率最高，因为汉字字符集合比拼音集合 大（汉字２Ｏ ０００多个，常用的有４ ０００多个，中文音 节数量约４００个），可以滤掉更多字串。因此，在时 间要求较高时，可以在过滤时适当放宽ｋ值，把对拼 音的处理放在第二阶段的动态规划中。 ２．在ａ变大时，动态规划的剪枝效果降低，过 滤算法过滤掉的位置也减少，因此两者的耗时都上 升。 通过理论分析和实验验证，我们得到以下结论： 动态规划可给出精确的输出，但是耗时太多，不 适合直接使用，需要配合过滤算法。我们还把原有 过滤算法的适用范围扩展到ａ＞ｏ．５的情况，过滤算 法可以有效提高时间效率，但是在ａ较大的时候时 间性能下降。 ７总结和展望 本文参考并改进了基于ＢＭＨ算法的ＴＵ模糊 匹配过滤算法，用于解决查询系统中用户输入字
串 和数据库中词条的局部偏差造成的召回率下降；并 针对汉字拼音输入法带来的同音字／近音字混用现 象定义广义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ，将模糊匹配算法推广 到该广义定义上。从理论和实验上证明我们的方法 能在有限的时间代价下有效提高检索的召回率。 由于汉字字符集的规模很大，基于汉字实现过 滤在时间效率上有相当明显的优势，但空间利用效 率不高。使用Ｈａｓｈ Ｔａｂｌｅ可以在一定程度上解决 这一问题。 除了同音字／音近字外，本算法还可以对替换的 代价作不同的定义，用于处理词义类似，字形类似或 错别字混用等检索系统中可能出现的问题。 本文是在线匹配的算法，不能预处理文本建立 索引，对于大规模的语料扫描需要耗费大量时间；在 ａ很大的时候，过滤效果不明显，时间效率较低。我 们将进一步寻找有效的方法解决这些问题。 参考文献： Ｅ ｌ ｉ Ｔａｒｈｉｏ．Ｊ，Ｕｋｋｏｎｅｎ Ｅ．Ａｐｐｒｏｘｉｍａｔｅ Ｂｏｙｅｒ—Ｍｏｏｒｅ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ．［Ｊ］．ＳＩＡＭ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｐｕｔｉｎｇ． １９９３ ２２（２）：２４３—２６０．Ｐｒｅｌｉｍｉｎａｒｙ ｖｅｒｓｉｏｎ ｉｎ ＳＷＡＴ’ ９０（Ｉ ＮＣＳ，ｖｏ１．４４７，１９９Ｏ）． Ｒ Ｂａｅｚａ—Ｙａｔｅｓ．Ｂ Ｒｉｂｅｉｒｏ－Ｎｅｔｏ．．Ｍｏｄｅｒｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖｅ ｒＭ］．ＡＣＭ ｐｒｅｓｓ，１９９９． ＮＡＶＡＲＲ（）Ｇ．Ａ ｇｕｉｄｅｄ ｔｏｕｒ ｔＯ ａｐｐｒｏｘｉｍａｔｅ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ［Ｊ］．ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ，２００１，３３ （１）：３１－８８． 陈儒．面向短信过滤的中文信息模糊匹配技术［Ｄ］．哈 尔滨：哈尔滨工业大学信息检索实验室２００３． Ｋｎｕｔｈ Ｄ Ｅ，Ｍｏｒｒｉｓ Ｊ Ｈ，Ｐｒａｔｔ Ｖ Ｒ．Ｆａｓｔ ｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ ｉｎ ｓｔｒｉｎｇｓ．［Ｊ］．ＳＩＡＭ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｐｕ— ｒｉｎｇ，１９７７．６（２）：３２３—３５０． Ｒ．Ｓ．Ｂｏｙｅｒ，Ｊ．Ｓ．Ｍｏｏｒｅ．Ａ ｆａｓｔ ｓｔｒｉｎｇ ｓｅａｒｃｈｉｎｇ ａｌｇｏ— ｒｉｔｈｍ．Ｉ－Ｊ］．Ｃｏｍｍ．ＡＣＭ １９７７ ２０（１０）：７６２—７７２． Ｈｏｒｓｐｏｏｌ Ｎ．Ｐｒａｃｔｉｃａｌ Ｆａｓｔ Ｓｅａｒｃｈｉｎｇ ｉｎ
Ｓｔｒｉｎｇｓ．［Ｊ］． ］ ］ ］ ］ ］ ］ 维普资讯 http://www.cqvip.com
６４ 中文信息学报 ２００７芷 Ｅ８］ ［９］ Ｅｌｏ］ ［１１］ ［１２］ ［１３］ ［１４］ Ｓｏｆｔｗａｒｅ Ｐｒａｃｔｉｃｅ ａｎｄ Ｅｘｐｅｒｉｅｎｃｅ，１９８０，１０． Ｇ０ＮＮＥＴ．Ｇ，ＢＡＥＺＡ—ＹＡＴＥＳ．Ｒ．Ｈａｎｄｂｏｏｋ ｏｆ Ａ１一 ｇｏｒｉｔｈｍｓ ａｎｄ Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ，２ｎｄ ｅｄ［Ｍ］．Ａｄｄｉｓｏｎ Ｗｅｓｌｅｙ．１９９１．２５１－２８４． Ｕｋｋｏｎｅｎ，Ｅ．Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ａｐｐｒｏｘｉｍａｔｅ ｓｔｒｉｎｇ ｍａｔｃ— ｈｉｎｇ．［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｎｔｒｏ１．１９８５ａ．６４，１００一 ｌ１８．Ｐｒｅｌｉｍｉｎａｒｙ ｖｅｒｓｉｏｎ ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａ ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎ Ｔｈｅｏｒｙ （ＬＮＣＳ，ｖｏ１．１５８，１９８３）． Ｕｋｋｏｎｅｎ， Ｅ． Ｆｉｎｄｉｎｇ ａｐｐｒｏｘｉｍａｔｅ ｐａｔｔｅｒｎｓ ｉｎ ｓｔｒｉｎｇｓ．［Ｊ］．Ａｌｇｏｒ．１９８５ｂ，６ １３２—１３７． Ｗｕ．Ｓ，Ｍａｎｂｅｒ．Ｕ．Ｆａｓｔ ｔｅｘｔ ｓｅａｒｃｈｉｎｇ ａｌｌｏｗｉｎｇ ｅｒ ｒｏｒｓ．［Ｊ］．Ｃｏｍｍｕｎ．ＡＣＭ ３５，１９９２，１０，８３—９１． Ｍｙｅｒｓ，Ｇ．Ａ ｆａｓｔ ｂｉｔ—ｖｅｃｔｏｒ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｐｐｒｏｘｉ— ｍａｔｅ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｐｒｏｇｒａｍ— ｍｉｎｇ．［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ＡＣＭ（ＪＡＣＭ），１９９９，３９５— ４１５． Ｇ Ｎａｖａｒｒｏ，Ｍ Ｒａｆｆｉｎｏｔ．Ｆａｓｔ ａｎｄ ｆｌｅｘｉｂｌｅ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ ｂｙ ｃｏｍｂｉｎｉｎｇ ｂｉｔ——ｐａｒａｌｌｅｌｉｓｍ ａｎｄ ｓｕｆｆｉｘ ａｕ—－ ｔｏｍａｔａ，［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｅｘｐｅｒｉｍｅｎｔａｌ Ａｌｇｏｒｉｔｈｍｉｃｓ （ＪＥＡ），２０００，５（４）． Ｈ Ｈ ｙｙｒｏ，Ｇ Ｎａｖａｒｒｏ．Ｆａｓｔｅｒ ｂｉｔ—ｐａｒａｌｌｅｌ ａｐｐｒｏｘｉｍａｔｅ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ．
［Ａ］．Ｐｒｏｃ．１３ｔｈ Ｃｏｍｂｉｎａｔｏｒｉａｌ Ｐａｔ— ｔｅｒｎ Ｍａｔｃｈｉｎｇ（ＣＰＭ’２００２）［Ｃ］，ＬＮＣＳ，２００２ Ｓｐｒｉｎｇｅｒ，２３ ７３． ［１５］ 陈开渠，赵洁，彭志威．快速中文字符串模糊匹配算 法［Ｊ］．中文信息学报，２００４，１８（１２）：５８—６５． 附录Ａ 证明：定义新的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ如下： 对ｐａｔ插入和删除一个字符的代价分别为 和ｃ出 ，替换的代价满足： １．ｃｏｓｔ（口一６）＞０ （当ａ≠６） ２．ｃｏｓｔ（口 口）＝０ ３．ｃｏｓｔ（ａ－＋ｂ）≤ｃｏｓｔ（ａ－￣ｃ）＋ｃｏｓｔ（ｃ－￣ｂ） 且所有代价均大于０小于正无穷，则动态规划 矩阵中的主对角线依旧是非严格单调递增的。 引理１：令５。，５。，５。，…，５ 为矩阵的一列， 则Ｓ 一５ ｌ∈［一ｃ ，ｃ出ｆ］，ｉ一１，２，…，例。 证明： （１）对于第０列，由定义： Ｄ（０，０）一０ Ｄ（ｉ一１，０）一ｃ ＜Ｄ（ｉ一１，０） ≤Ｄ（ｉ，０）一Ｄ（ｉ一１，０）＋ｃ ｆ （ｉ一１，２。…， ） ．‘． ５ 一５ １∈［一ｃ ，ｃ如ｆｊ （２）对 作归纳，假设对第０，１，…， 一１列引 理１成立（ ≥１），则对第 列，有： Ｄ（ｉ， ）一ｍｉｎ｛Ｄ（ｉ～１， 一１） ＋ｃｏｓｔ（ｐａｔ［ｉ－－１］一ｓ￡ｒ［ 一１］）， Ｄ（ ～１，Ｊ）＋ｆ如ｒ， Ｄ（ｉ，Ｊ一１）＋ｃ ） ≤Ｄ（ｉ一１， ）＋Ｃｄｅｒ （５） Ｄ（ 一１， ）一ｍｉｎ｛Ｄ（ 一２， 一１） ＋ｃｏｓｔ（户口￡［ 一２］一５￡ｒＤ一１］）， Ｄ（ｉ一２， ）＋Ｃｄｅｌ， Ｄ（ｉ一１， 一１）－４－ｃ ） ≤Ｄ（ 一１， 一１）＋ｆ （６） Ｄ（ｉ，ｊ．）一ｍｉｎ｛Ｄ（ ～１，ｊ．一１） －４－ｃｏｓｔ（ｐａｔ［ｉ一１］一 ￡ｒ［ 一１］）， Ｄ（ 一１， ）＋ｃ出￡， Ｄ（ｉ， 一１）＋ｃ ） ≥ｍｉｎ｛Ｄ（ｉ～１， 一１），Ｄ（ｉ一１， ）＋Ｃｄｅ ， Ｄ（ ～１， 一１）一Ｃ ＋Ｃ ） （由归纳假设） ≥ｍｉｎ｛Ｄ（ 一１， ）一ｃ ，Ｄ（ｉ～１， ）＋ｃ出ｒ， Ｄ（ 一１， ）一ｃ ） （由式（６）） 一Ｄ（ 一１， ）一ｃ 引理２：令 ，Ｔ ， ， 的一行，则丁Ｊ一丁Ｊ ∈［一ｃ 证法同引理１ 证明： …，Ｔ 为扩展后矩阵中 ，ｃ ］， 一１，２，…， 。 由引理１，Ｄ（ｉ， ～１）≥Ｄ（ｉ
一１， 一１）一ｃ ； 由引理２，Ｄ（ 一１，Ｙ）≥Ｄ（ｉ一１， 一１）一ｃ出 ； Ｄ（ｉ， ）一ｍｉｎ｛Ｄ（ｉ一１， 一１） ＋ｃｏｓｔ（ｐａｔ［ｉ－－１］一ｓ￡ｒ［ 一１］）， Ｄ（ ～１， ）＋ｃ ｆ， Ｄ（ｉ， 一１）＋ｃ ） ≥ｍｉｎ｛Ｄ（ｉ一１，ｊ．一１），Ｄ（ｉ一１，ｊ．）＋ｃ捌， Ｄ（ｉ， 一１）＋ｃ ） ≥ｍｉｎ｛Ｄ（ 一１， 一１），Ｄ（ 一１， 一１）一Ｃｄｅｆ ＋Ｃ如ｆ，Ｄ（ｉ， 一１）一ｃ ＋ｃ ） 一Ｄ（ｉ一１， ～１） 因此，在我们定义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ意义下，沿 着矩阵对角线从左上到右下，每个元素的值依然是 非严格单调递增的。 维普资讯 http://www.cqvip.com
第２ｌ卷第６期 ２００７年１１月 中文信息学报 ＪＯＵＲＮＡＬ ＯＦ ＣＨＩＮＥＳＥ ＩＮＦＯＲＭＡＴＩＯＮ ＰＲＯＣＥＳＳＩＮＧ Ｖｏ１．２ｌ，Ｎｏ．６ ＮＯＶ．，２００７ 文章编号：１００３—００７７（２００７）０６—００５９－０６ 中文信息检索系统的模糊匹配算法研究和实现 王静帆，邬晓钧，夏云庆，郑方 （清华大学计算机系清华信息科学与技术国家实验室 技术创新和开发部语音和语言技术中心，北京１０００８４） 摘要：在现代中文信息检索系统中，用户输入的字符串和实际数据库中的条目往往存在局部偏差，而基于关键词 匹配的检索技术不能很好地解决这一问题。本文参考并改进了Ｔａｒｈｉｏ和Ｕｋｋｏｎｅｎ提出的过滤算法 ］，针对汉字 拼音输入法中常出现的同音字／近音字混用现象，将算法进一步扩展到广义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ上。实验表明，本文提 出的算法能有效提高中文信息检索系统的召回率，在实际应用中可达到“子线性”的效率。 关键词：计算机应用；中文信息处理；模糊匹配；过滤算法；动态规划 中图分类号：ＴＰ３９ｌ 文献标识码：Ａ Ａｎ Ａｐｐｒｏｘｉｍａｔｅ Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｃｈｉｎｅｓｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ Ｓｙｓｔｅｍｓ ＷＡＮＧ Ｊｉｎｇ～ｆａｎ，ＷＵ Ｘｉａｏ—ｊ ｕｎ，ＸＩＡ Ｙｕｎ—ｑｉｎｇ，ＺＨＥＮＧ Ｆａｎｇ （Ｄｅｐｔ．ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉ．＆Ｔｅｃｈ．Ｔｓｉｎｇｈｕａ Ｕｎｉｖｅｒｓｉｔｙ， Ｃｅｎｔｅｒ ｆｏｒ Ｓｐｅｅｃｈ ａｎｄ Ｌａｎｇｕａｇｅ Ｔｅｃｈｎｏｌｏｇｉｅｓ，Ｄｉｖｉｓｉｏｎ ｏｆ Ｔｅｃｈｎｉｃａｌ Ｉｎｎｏｖａｔｉｏｎ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， Ｔｓｉｎｇｈｕａ Ｎａｔｉｏｎａｌ Ｌａｂｏｒａｔｏｒｙ ｆｏｒ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ １０００８４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｅ ｍｏｄｅｒｎ Ｃｈｉｎｅｓｅ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ ｓｙｓｔｅｍｓ，ｃｌａｓｓｉｃａｌ ｋｅｙｗｏｒｄ ｂａｓｅｄ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ ｃａｎ ｎｏｔ ｗｏｒｋ ｗｈｅｎ ｔｈｅ ｉｎｐｕｔ ｓｔｒｉｎｇ ｉｓ ｄｉｆｆｅｒｅｎｔ ｆｒｏｍ ｔｈｅ ｅｎｔｒｉｅｓ ｉｎ
ｔｈｅ ｄａｔａｂａｓｅ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ Ｔａｒｈｉｏ ａｎｄ Ｕｋｋｏｎｅｎ’Ｓ ｆｉｌｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｔＯ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ．Ｂｅｃａｕｓｅ ｔｈｅ Ｃｈｉｎｅｓｅ Ｐｉｎｙｉｎ ｔｙｐｅｗｒｉｔｉｎｇ ｕｓｕａｌｌｙ ｃｏｎ— ｓｉｓｔｓ Ｃｈｉｎｅｓｅ ｃｈａｒａｃｔｅｒｓ ｗｉｔｈ ｔｈｅ ｓａｍｅ ｏｒ ｓｉｍｉｌａｒ ｐｒｏｎｕｎｃｉａｔｉｏｎｓ，ｗｅ ｄｅｆｉｎｅｄ ａ ｓｐｅｃｉａｌ Ｅｄｌｔ Ｄｉｓｔａｎｃｅ ａｎｄ ｅｘｐｅｎｄｅｄ ｏｕｒ ｍｅｔｈｏｄ ａｃｃｏｒｄｉｎｇｌｙ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗｅｄ ｔｈａｔ ｏｕｒ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｒｅｃａｌｌ ｒａｔｅ ｏｆ ｔｈｅ ｒｅ— ｔｒｌｅｖａｌ ｓｙｓｔｅｍｓ ａｎｄ ｏｂｔａｉｎ ｐｒａｃｔｉｃａｌ ｓｕｂ—ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ． Ｋｅｙ ｗｏｒｄｓ：ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎ；Ｃｈｉｎｅｓｅ ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ；ａｐｐｒｏｘｉｍａｔｅ ｍａｔｃｈｉｎｇ；ｆｉｌｔｅｒ ａｌｇｏｒｉｔｈｍ；ｄｙｎａｍｉｃ ｐｒｏｇｒａｍｍｉｎｇ １ 引言 现有的信息检索系统大部分采用基于关键词匹 配的检索技术ｌ＿２］。在实际应用中，用户往往凭借印 象进行检索，有时只能模糊地描述查询目标，输入的 关键词无法和数据集合中保存的数据完全一致；另 一方面，在构建数据集时引入的错误（如ＯＣＲ识别错 误等）也可能造成这些数据无法被用户获取。在上述 情况下，传统的检索系统将难以从数据集中查找到所 需要的信息。本文采用模糊匹配方法查找数据集中 和用户输人相似的项，并根据相似度排序输出结果， 以部分解决上述问题。模糊匹配方法还可以用于其 他领域，如入侵检测、信息过滤、基因检测等＿３“ 中文用户大部分使用拼音输入法。用户输入查 询串时选词错误造成的同音字替换是很典型的一种 现象；方言、发音习惯等造成的音近字替换（如南方 方言中，ｚｈ和ｚ不分）是第二种典型的错误现象。本 文针对这些错误，提出了一种考虑同音字／近音字替 换的距离度量方法，在此基础上建立模糊匹配算法。 收稿Ｅｔ期：２００７－０１—０９定稿Ｅｌ期：
２００７ ０９ １０ 作者简介：王静帆（１９８２一），女，硕士生，研究方向为自然语言处理；邬晓钧（１９７６一），男，博士，助研，研究方向为ＶＩ语对 话系统和自然语言处理；郑方（１９６７一），男，博士，教授，研究方向为语音信号处理。 维普资讯 http://www.cqvip.com
６Ｏ 中文信息学报 ２背景简介 字符串的模式匹配（精确匹配）问题是：给定目 标字符串ｓｔｒ和模式串ｐａｔ，在ｓｔｒ中寻找ｐａｔ的匹配 位置。其经典算法有Ｋｎｕｔｈ—Ｍｏｒｒｉｓ－Ｐｒａｔｔ（ＫＭＰ）Ｅｓ］， Ｂｏｙｅｒ—Ｍｏｏｒｅ（ＢＭ） 等。实际应用中，ＢＭ算法及 其改进型（如ＢＭＨ［７ 等）能达到极高的效率（子线 性），被各种检索系统广泛使用Ｉ＿３ ］。 类似的，字符串的模糊匹配目标是在ｓｔｒ中查 找与ｐａｔ相似的字串位置。普遍采用Ｅｄｉｔ Ｄｉｓｔａｎｃｅ （ＥＤ）来刻画两个字符串的距离Ｉ＿３］。设Ａ，Ｂ为两个 字符串，狭义的ＥＤ（Ａ，Ｂ）定义为：把Ａ转换成Ｂ 需要的最少删除（删除Ａ中一个字符）、插入（在Ａ 中插入一个字符）或替换（把Ａ中的某个字符替换 成另一个字符）次数。直观地；两个串互相转换需要 经过的步骤越多，相差越多。模糊匹配问题转化为 对给定正整数ｋ，找出ｓｔｒ的所有子串ｓ ，使得ＥＤ （ｓ ，ｐａｔ）＜志。 模糊匹配技术的策略主要有以下四种 ］：１．动 态规划 ］，２．自动机口 ，３．位平行策略Ｉ＿ｌ ］，４．过滤 策略口］。将它们结合使用，常常可以获得更高的时 间效率Ｅ１３￣ｌｓ］。 本文基于Ｔａｒｈｉｏ和Ｕｋｋｏｎｅｎ提出的过滤算 法［１］（ＴＵ过滤算法），配合带剪枝的动态规划算 法 ］，在以下两方面进行了改进：１．扩展了原有过 滤算法，使之能处理更一般的情况；２．针对中文中特 有的同音字／近音字替换问题定义了广义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ，并扩展了过滤算法和动态规划算法以解 决该距离度量下的模糊匹配问题。 本文的余下部分安排如下：第３节简单介绍动 态规划及剪枝算法 ］和ＴＵ算法＿１ ；第４节介绍我 们对ＴＵ算法的扩展；第５节针对同音字／近音字问 题定义了广义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ，并提出该距离度量 下解决模式匹配的基于ＴＵ过滤和剪枝动态规划算 法；第６节给出实验结果和分析，最后是结论。 ３ 动态规划和ＴＵ过滤算法 为了更好的说明模糊匹配算法，首先定义可能 用到的符号：字符集∑上，目标
字符串为ｓｔｒ，长度 为 ，模式字符串ｐａｔ，长度为ｍ。两个匹配串之间 的最大Ｅｄｉｔ Ｄｉｓｔａｎｃｅ为ｋ，错误率上界为ａ，ａ—ｋ／ ｍ。用ｓＥ０，…， ］表示字符串ｓ的一个子串，下标由 ０开始。 ｓｔｒ的每个子串可以表示为其前缀子串的后缀 子串，动态规划方法 计算了ｐａｔ的前缀子串ｐａｔ ［０，…，ｉ一１－１和ｓｔｒ的前缀子串ｓｔｒ Ｅｏ，…， 一１］的 后缀子串的最小Ｅｄｉｔ Ｄｉｓｔａｎｃｅ，记入Ｄ（ｉ， ）。 Ｄ（０，Ｊ）一０（ 一０，１，…， ） Ｄ（ｉ，０）一Ｄ（ｉ一１，０）４－１ （ｉ一１，２，…，ｍ） Ｄ（ｉ，Ｊ）一ｍｉｎ｛Ｄ（ｉ～１， 一１），Ｄ（ｉ～１， ）， Ｄ（ｉ，Ｊ一１）｝４－１ ｉｆ ｓｔｒＥＪ一１］≠ｐａｒ２ｉ一１］ 一Ｄ（ｉ一１，ｊ．～１） ｉｆ ｓｔｒＥＪ一１］一ｐａｔＥｉ—１］ （ —ｌ，２，…，ｍ，Ｊ—ｌ，３，…， ） Ｄ（ｉ， ）只和Ｄ（ｉ～１． ），Ｄ（ｉ， ～１），Ｄ（ｉ一 １， —１）有关，分别对应于对ｐａｔ［ｉ一１］的删除、插 入、替换或匹配操作，计算（ ４－１）ｘ（ ４－１）的动态 规划矩阵Ｄ，复杂度为０（ｒａｎ）。 Ｕｋｋｏｎｅｎ［３ ］证明，在狭义ＥＤ定义下，Ｄ沿对 角线从左上到右下，元素值非严格单调递增。对每 列的最后一个元素Ｄ（ ，Ｊ），如果Ｄ（ ，Ｊ）＞ｋ说 明在该位置上不能找到和ｐａｔ匹配的子串。若 Ｄ（ｉ， ）＞志，其具体值不影响后来的计算。记下列 中不大于ｋ的最后一个元素的位置ｌａｓｔ，对 ＋ｌ 列，只需计算Ｄ（０，Ｊ ４－１），Ｄ（１． ＋１），…，Ｄ（１ａｓｔ ＋１， ＋１）。这种方法被称为ｃｕｔ—ｏｆｆ ｈｅｕｒｉｓｔｉｃ剪 枝，把时间复杂度减小到Ｏ（ｋｎ）。配合ｃｕｔ—ｏｆｆ ｈｅｕ— ｒｉｓｔｉｃ剪枝的动态规划是目前为止最快，也是唯一具 有实用价值的基于动态规划的模糊匹配方法。 和动态规划方法不同，过滤算法不能直接计算 得到ＥＤ值，必须配合其他方法使用。分为两个阶 段：①在较少的时间消耗下过滤掉大部分无法匹配 的位置；②对余下可能匹配的位置调用其他方法定 量计算ＥＤ值。过滤算法目标是在快速过滤掉无法 匹配的位置。 ＴＵ算法出发点是用近似方法找到并过滤掉Ｄ 中必然大于ｋ的Ｄ（ｉ， ），实现上借鉴了ＢＭＨ算 法 中从右向左扫描ｓｔｒ串，寻找失败位置，跳跃性 移动ｐａｔ串，以及通过预处理减少查找
时间的思想， 通过查找“坏字符”，滤掉ｓｔｒ中Ｅｄｉｔ Ｄｉｓｔａｎｃｅ必然 大于ｋ的大部分子串位置。 在动态规划矩阵Ｄ中，记录下每个元素Ｄ（ｉ，ｊ．） 的来源（即Ｄ（ 一１， ），Ｄ（ｉ， —１），Ｄ（ｉ一１， —１）之 一），可跟踪每个Ｄ（ｉ， ）的生成路径。Ｄ（ｍ， ）的 生成路径称为ｊ．上的最小化路径，若Ｄ（ ， ）＜志， 该路径称为成功的最小化路径。每条最小化路径对 应于一个成功的匹配。Ｔａｒｈｉｏ和Ｕｋｋｏｎｅｎ证明了： 维普资讯 http://www.cqvip.com
６期 王静帆等：中文信息检索系统的模糊匹配算法研究和实现 ６１ 在Ｄ矩阵中，成功的最小化路径不能跨越多于是条 对角线。在此基础上，定义坏字符如下：对ｐａｔ中 的位置ｉ，若字符ａ ｛ｐａｔ［ 一是］，ｐａｔＥｉ一是＋１］， …，ｐａｔＥｉ＋是］｝，把ａ定义为位置ｉ上的一个“坏字 符”。在成功的匹配中，一个坏字符将造成Ｅｄｉｔ Ｄｉｓｔａｎｃｅ至少增加１。若一条最小化路径经过对角 线ｈ（设Ｄ（ｉ， ）对应对角线为ｈ一 一ｉ），则ｓｔｒＥｈ， …，ｈ＋ 一１］中的“坏字符”数不大于是。若找到是 ＋１个坏字符，该位置的匹配失效，跳跃到下一位 置；否则调用动态规划方法计算该位置附近子串ｓｔｒ ［＾一是，…，ｈ＋ 一１＋是］和ｐａｔ的最小Ｅｄｉｔ Ｄｉｓ— ｔａｎｃｅ。 每种匹配方案对应ｓｔｒ和ｐａｔ的一种对齐方式。 一个成功匹配最多允许是次操作，所以在ｓｔｒ中的 连续是＋１个字符中至少有一个等于ｐａｔ中的某个 字符，也就是说，考察单个字符ａ在ｐａｔ中出现的位 置将可以近似排除ｐａｔ和ｓｔｒ中不可能的匹配位置， 指导ｐａｔ“跳跃”到下一个可能匹配的位置。 Ｔｕ算法过程如下： 预处理阶段，可通过扫描一次ｐａｔ构建最小跳 跃距离表格ｄ和坏字符表格ｂａｄ。ｂａｄＥｉ，ａ］指示在 ｐａｔＥｉ￣和ｓ ｒ［ ］一ａ对齐时，ａ是否为坏字符；ｄ［ ， ａ］指示对应情况下，下次可能匹配成功的最大跳跃 的长度。 ｂａｄＥｉ，ａ］一 ｉｆ（了Ｚ）， 埘一 （１） ａｎｄ Ｚ一是≤ｉ≤Ｚ＋是 ｏｔｈｅｒｗｉｚｅ ［ ，ａ —ｍｉｎ｛ｚ ｌ（ｚ一 ）ｏｒ（０＜ｚ＜ ａｎｄ ｐａｔＥｉ—ｚ］一ａ）｝ （２） ａ Ｅ＞ ， 一是一１≤ｉ＜ 字符串比较过滤阶段，在当前位置ｈ上把ｐａｔ —ｐａｔＥＯ，…， 一１］串和ｓｔｒ的子串ｓ 一ｓｔｒＥｈ，…，ｈ ＋
一１］对齐（＾初始化为０），从ｓｔｒＥｈ＋ 一１］开始 向左扫描ｓｔｒ子串。对ｓｔｒＥｈ＋ ］（ 一 一１， 一２， …，０），查询ｂａｄ表确定是否坏字符。同时对ｉ Ｅ ［ 一１一是， 一１］，查表获得ｎｅｘｔｄ—ｍｉｎ｛ ［ ，ｓｔｒ ［＾＋ ］］｝作为下个可能匹配的最小跳跃距离。若 找到大于是个坏字符，说明经过该对角线的所有的 “最小化路径”的权值之和均大于是，不能满足模糊 匹配的要求，可以跳到下一个位置。Ｕｋｋｏｎｅｎ证明 了，当２是＋１≤ 时，若在ｓｔｒＥｈ＋是，…，ｈ＋ 一１］这 一是个字符中，有多于是个坏字符，可以把ｐａｔ向 右移动至少是＋１个位置，即ｎｅｘｔｄ—ｍａｘ｛ｎｅｘｔｄ，是 ＋１｝。 在ａ较小，Ｉ∑Ｉ较大的情况下，由于第一阶段 快速滤去了大部分不匹配的位置，该方法时间效率 能达到“子线性”。 ４ 改进的ＴＵ过滤算法 文献［１］证明了，在ｓｔｒＥｈ＋，…，ｈ＋ 一１］这 一是个字符中，若有多于是个“坏字符”，可以把 ｐａｔ向右移动至少是＋１个位置。但是，当２是＋１＞ 时，ｓｔｒＥｈ＋是，…，ｈ＋ 一１］中不可能找到多于是 个坏字符，原过滤算法不可用。 在这种情况下，我们证明了：若从后向前扫描 到的第是＋１个“坏字符”为ｓｔｒＥｈ＋“］（０≤“＜是）， 则至少可以移动“＋１个位置，即下一步只需比较 ｐａｔ和ｓ ｒ［＾＋“＋１，…，＾＋“＋ ］。 证明：对坏字符ｓｔｒＥｈ＋ ］（“≤ ＜ 一１），由坏 字符的定义，ｓｔｒＥｈ＋ ］ ｛ｐａｔＥｉ一“］，ｐａｔＥｉ一“＋ １］，…，ｐａｔＥｉ－－１］｝所以对角线ｈ＋１，ｈ＋２，…，ｈ ＋“范围内所有的最小化路径的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ都大 于是。 因此，若在ｓｔｒＥｈ，…，ｈ＋ 一１］中找到是＋１ 个坏字符，则下一步的移动距离为ｎｅｘｔｄ—ｍａｘ ｛ｎｅｘｔｄ，“＋１｝，至少移到对角线ｈ＋“＋１上，从ｓｔｒ ［ ＋ ＋“］开始向左扫描，不会漏解。若在ｓｔｒ［＾， …，ｈ＋ 一１］中找不到是个坏字符，则ｓｔｒＥｈ一是， …，ｈ＋是＋ 一１］的某个子串ｓ 和ｐａｔ可能满足ＥＤ （ｐａｔ，ｓ ）≤是，调用动态规划算法精确计算。这里， 最坏的情况下可能出现只移动１个位置的情况。 综合以上两种情况，改进后的算法可描述为： 令第是＋１个坏字符的下标为ｈ＋“，最小跳跃距离 ｎｅｘｔｄ≥ｍｉｎ｛是＋１，“＋１｝
。 ５基于广义Ｅｄｉｔ Ｄｉｓｔａｎｃｅ的扩展 ５．１ 新的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ定义 给插入、删除、替换以不同的代价，可以得到广 义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅｌ３］。 令对ｐａｔ插入和删除一个字符的代价分别为 ｒ 和ｒ ，替换的代价根据不同的替换字符定义，只 需满足距离的一般定义，即： １．ｃｏｓｔ（ａ－＊ｂ）＞０（当ａ≠６） ２．ｃｏｓｔ（“ ａ）一０ 维普资讯 http://www.cqvip.com
６２ 中文信息学报 ３．ｃｏｓｔ（ｎ一６）≤ｃｏｓｔ（ｎ—ｃ）十ｃｏｓｔ（ｃ一６） 且所有代价均大于０小于正无穷。 我们将过滤算法和扩展的ＴＵ算法进行了扩 展，以处理这种广义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ。 ５．２扩展的动态规划剪枝算法 扩展后的递推公式如下： Ｄ（Ｏ，ｊ：）一０（ｊ：一０，ｌ，…， ） Ｄ（ ，０）一Ｄ（ —ｌ，０）＋ｃ出ｆ （ｉ—ｌ，２，…， ） Ｄ（ｉ， ）一ｍｉｎ｛Ｄ（ —ｌ， 一１） ＋ｃｏｓｔ（ｐａｔ［ｉ－－１］一ｓ ｒ［ 一１］）， Ｄ（ —ｌ，ｊ：）＋ｃ出 ， Ｄ（ｉ，ｊ：一１）＋ｃ ｝ （ —ｌ，２，…，ｍ，Ｊ—ｌ，３，…， ） （３） 我们证明了（详细证明见附录Ａ），在５．１定义 下，动态规划矩阵中的主对角线依旧是非严格单调 递增，可以采用ｃｕｔ—ｏｆｆ ｈｅｕｒｉｓｔｉｃ剪枝算法。 ５．３扩展的改进ＴＵ过滤算法 接下来，再将改进的过滤算法扩展到广义的 Ｅｄｉｔ Ｄｉｓｔａｎｃｅ意义下。 设ｇ—ｋ／ｍｉｎ｛ ，‰｝，与前类似，一条成功的 最小化路径不能跨越多于ｑ条对角线，因为从当前 对角线到达相邻对角线，必然经过水平或者竖直方 向的转移，每一步转移的代价不小于ｍｉｎ｛ｃ如 ，‰｝。 成功的最小化路径 被限制在以 为中心的２ｇ＋ｌ 条对角线范围内。 设 一ｍｉｎ｛ｃ出 ，‰，ｃｏｓｔ（ｎ一６）｝，新的“坏字 符”定义如下： 设ｓｔｒ［ｊ］和ｐａｔ［ｉ１对齐，若ｓｔｒ［ｊ］ ｛ｐａｔＥｉ— ｇ］，ｐａｔ［ｉ—ｇ＋１］，…，ｐａｔ［ｉ＋ｇ］｝，把ｓｔｒ［ｊ］称为 该比较对角线上的一个“坏字符”，“坏字符”必然造 成该匹配位置上ＥＤ值增加至少 。若一条成功 的最小化路径经过对角线 ，则它在 上的“坏字 符”数不大于ｋ／ｃ…。新的算法为：对齐ｐａｔ和ｓｔｒ 的子串Ｓ 一ｓｔｒ［ｈ，…， ＋ 一１］，从右向左扫描Ｓ ， 若找到ｋ／ｃ…＋１个坏字符，该位置的匹配失
效，跳 跃到下一位置，设第ｋ／ｃ 。 ＋１个坏字符的下标为 ＋ ，最小跳跃距离ｎｅｘｔｄ＝ｍｉｎ｛ｇ＋ｌ， ＋ｌ｝；否则 调用动态规划方法计算该位置附近子串ｓｔｒ［ｈ—ｑ， …， ＋ —ｌ＋ｇ］和ｐａｔ的最小ＥＤ。 特定应用中，可能给某些字符替换定义了很高 的相似度，导致 很小，过滤时必须扫描很多字 符，更糟糕的是，无法保证ｋ／ｃ ≤ｍ，即扫描了整个 串都找不到足够的“坏字符”。总之，考虑每个细节 将使过滤算法失掉高效的优点。这时可以略微放宽 限制，只保证不滤掉可能解，及能滤掉大部分不可能 解，把细节的考察放到动态规划评分中。改进思路 是：在过滤阶段只选用其中足够大的插入／删除／替 换代价计算，把很“相似”的当成相等处理： ｆ ｃｏｓｔ（ａ一６）ｉｆ ｃｏｓｔ（ａ一６）＞ｔｃｏｓｔ ｃｏｓｔ２（ａ ６）一ｆ ０ ｅｌｓｅ Ｉ （４） 其中，ａ，ｂ不全为空。ｔｃｏｓｔ是一个阈值，用来 分开“相似”和“不相似”，必须满足ｋ／ｔｃｏｓｔ＜ｍ。 ｔｃｏｓｔ过小可能导致过滤阶段时间效率降低，过大可 能导致第二阶段的计算量增加。我们认为空字符和 任何其他的字符都不相似，在这种假设下，可以令 ｔｃｏｓｔ＝ｍｉｎ ，ｃ如 ｝。这样的替换不会漏掉可能的 匹配位置。 ５．４用于同音字／近音字处理 在中文信息检索的实际应用中，大量用户由于 使用拼音输入法经常产生同音字／近音字的错误。 同音字是现代汉语里语音相同但字形、意义不同的 字。所谓语音相同，一般是指声母、韵母和声调完 全相同．如“江”和“姜”。近音字是在现代汉语里语 音相近，但字形，意义不同的字。在这里我们处理了 几种常出现的近音字混用：１．声韵母相同，但声调 不同，如“江”和“讲”２．声母、韵母存在差异但发音相 近的字，包括前后鼻音混用（ｉｎｇ／ｉｎ，ａｎｇ／ａｎ，ｅｎｇ／ ｅｎ），平舌卷舌混用（ｚ／ｚｈ，ｃ／ｃｈ，ｓ／ｓｈ）。在进行模 糊匹配时，我们给同音字／近音字替换赋予较小的权 重（ｃｏｓｔ为０．５），给其他替换和插入删除操作赋予 较高的权重（ｃｏｓｔ为１），采用以上的过滤算法配合 带剪枝的动态算法计算Ｅｄｉｔ Ｄｉｓｔａｎｃｅ，取得了很好 的效果。 ６ 实验结果 本次实验的数据包括歌曲名称数据库和用户查 询日志，实验环境为Ｗｉｎｄｏｗｓ ＸＰ，记录的时间并非 程序的绝对运行时间，只是开始和结束时间之差，并 未除去系统调度
的时间。所以我们只考虑时间的相 对意义而不考虑其绝对意义。被检索的是一个歌曲 数据集合，包含了６００左右歌手／乐队名和５ ０００左 右的歌曲名称。查询词是一段时间内的用户查询日 维普资讯 http://www.cqvip.com
６期 王静帆等：中文信息检索系统的模糊匹配算法研究和实现 ６３ 志，包含大约２００ ０００个查询串。 在ｍ一６时对三种算法进行对比：精确匹配 ＢＭＨ算法，狭义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ汉字匹配的过滤 算法（ａ＝＝＝０．４，ｍ一６），以及带同音字／近音字广义 Ｅｄｉｔ Ｄｉｓｔａｎｃｅ扩展的过滤算法（ａ一０．４，ｍ一６，取同 音字／近音字替换代价为０．５），后两个算法的第二 阶段均采用带剪枝的动态规划算法。实验结果如图 １所示，对于相同的数据集合，模糊匹配比精确匹配 可以检索到更多的条目，而考虑同音／近音字能进一 步提高召回率。 一 豁 皿 弭 簿 圈精确匹配一狭义ＥＤ图广义ＥＤ 图１不同距离度量下的输出比较 接下来，我们对四种算法（在汉字集合上的动态 规划和过滤算法，带同音字／近音字的扩展Ｅｄｉｔ Ｄｉｓｔａｎｃｅ下的动态规划和过滤算法）的时间效率进 行比较，实验结果如图２所示。 ７０ 譬６０ ５０ 害４０ 嚣３０ ２０ １０ ０ ／ ／ ／ ／ ／ 一／ ． ＝＝： ●—————一 ＋汉字动态规划 一汉字过滤 ＋扩展动态规划 —＊一扩展过滤 ａ＝０．２ ０．４ ０．６ ０．８ 图２各算法时间效率比较 实验证明： １．两种过滤算法的时间效率都优于动态规划， 过滤算法能有效提高时间效率。汉字集合上的过滤 算法时间效率最高，因为汉字字符集合比拼音集合 大（汉字２Ｏ ０００多个，常用的有４ ０００多个，中文音 节数量约４００个），可以滤掉更多字串。因此，在时 间要求较高时，可以在过滤时适当放宽ｋ值，把对拼 音的处理放在第二阶段的动态规划中。 ２．在ａ变大时，动态规划的剪枝效果降低，过 滤算法过滤掉的位置也减少，因此两者的耗时都上 升。 通过理论分析和实验验证，我们得到以下结论： 动态规划可给出精确的输出，但是耗时太多，不 适合直接使用，需要配合过滤算法。我们还把原有 过滤算法的适用范围扩展到ａ＞ｏ．５的情况，过滤算 法可以有效提高时间效率，但是在ａ较大的时候时 间性能下降。 ７总结和展望 本文参考并改进了基于ＢＭＨ算法的ＴＵ模糊 匹配过滤算法，用于解决查询系统中用户输入字
串 和数据库中词条的局部偏差造成的召回率下降；并 针对汉字拼音输入法带来的同音字／近音字混用现 象定义广义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ，将模糊匹配算法推广 到该广义定义上。从理论和实验上证明我们的方法 能在有限的时间代价下有效提高检索的召回率。 由于汉字字符集的规模很大，基于汉字实现过 滤在时间效率上有相当明显的优势，但空间利用效 率不高。使用Ｈａｓｈ Ｔａｂｌｅ可以在一定程度上解决 这一问题。 除了同音字／音近字外，本算法还可以对替换的 代价作不同的定义，用于处理词义类似，字形类似或 错别字混用等检索系统中可能出现的问题。 本文是在线匹配的算法，不能预处理文本建立 索引，对于大规模的语料扫描需要耗费大量时间；在 ａ很大的时候，过滤效果不明显，时间效率较低。我 们将进一步寻找有效的方法解决这些问题。 参考文献： Ｅ ｌ ｉ Ｔａｒｈｉｏ．Ｊ，Ｕｋｋｏｎｅｎ Ｅ．Ａｐｐｒｏｘｉｍａｔｅ Ｂｏｙｅｒ—Ｍｏｏｒｅ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ．［Ｊ］．ＳＩＡＭ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｐｕｔｉｎｇ． １９９３ ２２（２）：２４３—２６０．Ｐｒｅｌｉｍｉｎａｒｙ ｖｅｒｓｉｏｎ ｉｎ ＳＷＡＴ’ ９０（Ｉ ＮＣＳ，ｖｏ１．４４７，１９９Ｏ）． Ｒ Ｂａｅｚａ—Ｙａｔｅｓ．Ｂ Ｒｉｂｅｉｒｏ－Ｎｅｔｏ．．Ｍｏｄｅｒｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖｅ ｒＭ］．ＡＣＭ ｐｒｅｓｓ，１９９９． ＮＡＶＡＲＲ（）Ｇ．Ａ ｇｕｉｄｅｄ ｔｏｕｒ ｔＯ ａｐｐｒｏｘｉｍａｔｅ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ［Ｊ］．ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ，２００１，３３ （１）：３１－８８． 陈儒．面向短信过滤的中文信息模糊匹配技术［Ｄ］．哈 尔滨：哈尔滨工业大学信息检索实验室２００３． Ｋｎｕｔｈ Ｄ Ｅ，Ｍｏｒｒｉｓ Ｊ Ｈ，Ｐｒａｔｔ Ｖ Ｒ．Ｆａｓｔ ｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ ｉｎ ｓｔｒｉｎｇｓ．［Ｊ］．ＳＩＡＭ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｐｕ— ｒｉｎｇ，１９７７．６（２）：３２３—３５０． Ｒ．Ｓ．Ｂｏｙｅｒ，Ｊ．Ｓ．Ｍｏｏｒｅ．Ａ ｆａｓｔ ｓｔｒｉｎｇ ｓｅａｒｃｈｉｎｇ ａｌｇｏ— ｒｉｔｈｍ．Ｉ－Ｊ］．Ｃｏｍｍ．ＡＣＭ １９７７ ２０（１０）：７６２—７７２． Ｈｏｒｓｐｏｏｌ Ｎ．Ｐｒａｃｔｉｃａｌ Ｆａｓｔ Ｓｅａｒｃｈｉｎｇ ｉｎ
Ｓｔｒｉｎｇｓ．［Ｊ］． ］ ］ ］ ］ ］ ］ 维普资讯 http://www.cqvip.com
６４ 中文信息学报 ２００７芷 Ｅ８］ ［９］ Ｅｌｏ］ ［１１］ ［１２］ ［１３］ ［１４］ Ｓｏｆｔｗａｒｅ Ｐｒａｃｔｉｃｅ ａｎｄ Ｅｘｐｅｒｉｅｎｃｅ，１９８０，１０． Ｇ０ＮＮＥＴ．Ｇ，ＢＡＥＺＡ—ＹＡＴＥＳ．Ｒ．Ｈａｎｄｂｏｏｋ ｏｆ Ａ１一 ｇｏｒｉｔｈｍｓ ａｎｄ Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ，２ｎｄ ｅｄ［Ｍ］．Ａｄｄｉｓｏｎ Ｗｅｓｌｅｙ．１９９１．２５１－２８４． Ｕｋｋｏｎｅｎ，Ｅ．Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ａｐｐｒｏｘｉｍａｔｅ ｓｔｒｉｎｇ ｍａｔｃ— ｈｉｎｇ．［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｎｔｒｏ１．１９８５ａ．６４，１００一 ｌ１８．Ｐｒｅｌｉｍｉｎａｒｙ ｖｅｒｓｉｏｎ ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａ ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎ Ｔｈｅｏｒｙ （ＬＮＣＳ，ｖｏ１．１５８，１９８３）． Ｕｋｋｏｎｅｎ， Ｅ． Ｆｉｎｄｉｎｇ ａｐｐｒｏｘｉｍａｔｅ ｐａｔｔｅｒｎｓ ｉｎ ｓｔｒｉｎｇｓ．［Ｊ］．Ａｌｇｏｒ．１９８５ｂ，６ １３２—１３７． Ｗｕ．Ｓ，Ｍａｎｂｅｒ．Ｕ．Ｆａｓｔ ｔｅｘｔ ｓｅａｒｃｈｉｎｇ ａｌｌｏｗｉｎｇ ｅｒ ｒｏｒｓ．［Ｊ］．Ｃｏｍｍｕｎ．ＡＣＭ ３５，１９９２，１０，８３—９１． Ｍｙｅｒｓ，Ｇ．Ａ ｆａｓｔ ｂｉｔ—ｖｅｃｔｏｒ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｐｐｒｏｘｉ— ｍａｔｅ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｐｒｏｇｒａｍ— ｍｉｎｇ．［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ＡＣＭ（ＪＡＣＭ），１９９９，３９５— ４１５． Ｇ Ｎａｖａｒｒｏ，Ｍ Ｒａｆｆｉｎｏｔ．Ｆａｓｔ ａｎｄ ｆｌｅｘｉｂｌｅ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ ｂｙ ｃｏｍｂｉｎｉｎｇ ｂｉｔ——ｐａｒａｌｌｅｌｉｓｍ ａｎｄ ｓｕｆｆｉｘ ａｕ—－ ｔｏｍａｔａ，［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｅｘｐｅｒｉｍｅｎｔａｌ Ａｌｇｏｒｉｔｈｍｉｃｓ （ＪＥＡ），２０００，５（４）． Ｈ Ｈ ｙｙｒｏ，Ｇ Ｎａｖａｒｒｏ．Ｆａｓｔｅｒ ｂｉｔ—ｐａｒａｌｌｅｌ ａｐｐｒｏｘｉｍａｔｅ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ．
［Ａ］．Ｐｒｏｃ．１３ｔｈ Ｃｏｍｂｉｎａｔｏｒｉａｌ Ｐａｔ— ｔｅｒｎ Ｍａｔｃｈｉｎｇ（ＣＰＭ’２００２）［Ｃ］，ＬＮＣＳ，２００２ Ｓｐｒｉｎｇｅｒ，２３ ７３． ［１５］ 陈开渠，赵洁，彭志威．快速中文字符串模糊匹配算 法［Ｊ］．中文信息学报，２００４，１８（１２）：５８—６５． 附录Ａ 证明：定义新的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ如下： 对ｐａｔ插入和删除一个字符的代价分别为 和ｃ出 ，替换的代价满足： １．ｃｏｓｔ（口一６）＞０ （当ａ≠６） ２．ｃｏｓｔ（口 口）＝０ ３．ｃｏｓｔ（ａ－＋ｂ）≤ｃｏｓｔ（ａ－￣ｃ）＋ｃｏｓｔ（ｃ－￣ｂ） 且所有代价均大于０小于正无穷，则动态规划 矩阵中的主对角线依旧是非严格单调递增的。 引理１：令５。，５。，５。，…，５ 为矩阵的一列， 则Ｓ 一５ ｌ∈［一ｃ ，ｃ出ｆ］，ｉ一１，２，…，例。 证明： （１）对于第０列，由定义： Ｄ（０，０）一０ Ｄ（ｉ一１，０）一ｃ ＜Ｄ（ｉ一１，０） ≤Ｄ（ｉ，０）一Ｄ（ｉ一１，０）＋ｃ ｆ （ｉ一１，２。…， ） ．‘． ５ 一５ １∈［一ｃ ，ｃ如ｆｊ （２）对 作归纳，假设对第０，１，…， 一１列引 理１成立（ ≥１），则对第 列，有： Ｄ（ｉ， ）一ｍｉｎ｛Ｄ（ｉ～１， 一１） ＋ｃｏｓｔ（ｐａｔ［ｉ－－１］一ｓ￡ｒ［ 一１］）， Ｄ（ ～１，Ｊ）＋ｆ如ｒ， Ｄ（ｉ，Ｊ一１）＋ｃ ） ≤Ｄ（ｉ一１， ）＋Ｃｄｅｒ （５） Ｄ（ 一１， ）一ｍｉｎ｛Ｄ（ 一２， 一１） ＋ｃｏｓｔ（户口￡［ 一２］一５￡ｒＤ一１］）， Ｄ（ｉ一２， ）＋Ｃｄｅｌ， Ｄ（ｉ一１， 一１）－４－ｃ ） ≤Ｄ（ 一１， 一１）＋ｆ （６） Ｄ（ｉ，ｊ．）一ｍｉｎ｛Ｄ（ ～１，ｊ．一１） －４－ｃｏｓｔ（ｐａｔ［ｉ一１］一 ￡ｒ［ 一１］）， Ｄ（ 一１， ）＋ｃ出￡， Ｄ（ｉ， 一１）＋ｃ ） ≥ｍｉｎ｛Ｄ（ｉ～１， 一１），Ｄ（ｉ一１， ）＋Ｃｄｅ ， Ｄ（ ～１， 一１）一Ｃ ＋Ｃ ） （由归纳假设） ≥ｍｉｎ｛Ｄ（ 一１， ）一ｃ ，Ｄ（ｉ～１， ）＋ｃ出ｒ， Ｄ（ 一１， ）一ｃ ） （由式（６）） 一Ｄ（ 一１， ）一ｃ 引理２：令 ，Ｔ ， ， 的一行，则丁Ｊ一丁Ｊ ∈［一ｃ 证法同引理１ 证明： …，Ｔ 为扩展后矩阵中 ，ｃ ］， 一１，２，…， 。 由引理１，Ｄ（ｉ， ～１）≥Ｄ（ｉ
一１， 一１）一ｃ ； 由引理２，Ｄ（ 一１，Ｙ）≥Ｄ（ｉ一１， 一１）一ｃ出 ； Ｄ（ｉ， ）一ｍｉｎ｛Ｄ（ｉ一１， 一１） ＋ｃｏｓｔ（ｐａｔ［ｉ－－１］一ｓ￡ｒ［ 一１］）， Ｄ（ ～１， ）＋ｃ ｆ， Ｄ（ｉ， 一１）＋ｃ ） ≥ｍｉｎ｛Ｄ（ｉ一１，ｊ．一１），Ｄ（ｉ一１，ｊ．）＋ｃ捌， Ｄ（ｉ， 一１）＋ｃ ） ≥ｍｉｎ｛Ｄ（ 一１， 一１），Ｄ（ 一１， 一１）一Ｃｄｅｆ ＋Ｃ如ｆ，Ｄ（ｉ， 一１）一ｃ ＋ｃ ） 一Ｄ（ｉ一１， ～１） 因此，在我们定义的Ｅｄｉｔ Ｄｉｓｔａｎｃｅ意义下，沿 着矩阵对角线从左上到右下，每个元素的值依然是 非严格单调递增的。 维普资讯 http://www.cqvip.com