平均情况下的最优多模式近似匹配

1、平均情况下的最优多模式近似匹配 Average-Optimal Multiple Approximate String Matching 在目标文本中同时搜索r个模式P1P2.Pr，找到目标文本中和这r个模式中的某一个模式最多只有k个字符不同的所有匹配结果。 最原始的多模式近似匹配算法是对r个模式分别进行单模式近似匹配 平均情况下的最优多模式近似匹配 基于散列方法的算法，只允许进行k=1的近似搜索，但对模式个数r有很强的容忍能力 分块精确搜索算法，基于这样一个事实：如果将P分成k+1块，那么目标文本中的匹配结果中至少精确包含这k+1块中的一块。这个算法将所有的模式都切成k+1块，然后使用多模式

2、精确匹配算法在目标文本中搜索这r(k+1)个模式块。 平均情况下的最优多模式近似匹配 本文介绍的算法是从单模式近似匹配最优算法Chang-Marr算法扩展而来 Chang-Marr算法的基本思想： 每个匹配结果长度至少为 m-k，如果将目标文本切成长度为b=(m-k)/2的块，目标文本中的任何一个匹配结果都至少包含其中的某一整块。 判断一个文本块不是一个匹配结果，要比判断它是一个匹配结果容易。(因此，目标文本中所包含的匹配结果越多，算法处理得越慢)平均情况下的最优多模式近似匹配 怎样判断一个长度为(m-k)/2的文本块不是一个匹配结果？首先选择一个数 ，满足1 = 建立一个表D ，其中保存了任

3、何一个长度为 的串(称为 -gram)在模式中匹配的最小错误数。因此D的大小为 在文本块中只要找到若干个互不交叠的 -gram，它们的D表元素值之和大于k，则可以肯定这个文本块不会和模式匹配k)/2-(m平均情况下的最优多模式近似匹配 本文介绍的算法基本思想是：给定待搜索的r个模式P1.Pr，我们建立和Chang- Marr算法一样的表D，D中保存了任何一个 -gram与任何一个模式的子串匹配的最小错误数。扫描目标文本的每一块，如果在某一个块以内错误数就超过了k，我们就能够确信不可能存在包含本块的匹配结果 平均情况下的最优多模式近似匹配 -gram的最优选择 最简单的办法：依次计算块中前部 -

4、gram的错误数之和。但不是最优其实只要是块内互不交叠的 -gram组成的集合，它们的错误数之和超过了k，而不管这些元素出现的位置，都可以确信本块不构成匹配结果最优选择：扫描当前块，总是选择错误数之和最大的互不相交的 -gram集合平均情况下的最优多模式近似匹配 对于不能跳过的文本块，怎样验证它确实是一个匹配结果呢？ 简单的用动态规划算法逐个验证每个模式，平均情况下效率低下 层次验证平均情况下的最优多模式近似匹配 层次验证 (Hierarchical Verification) 构造一棵层次验证树，每个内部结点代表一个模式集的子集，祖先结点所代表的模式子集包含了后代结点所代表的模式子集，叶结点

5、代表单个模式，而根结点代表了整个模式集 每个结点建造一个D表，叶结点的D表构造方法同Chang-Marr算法；而内部结点的D表，每个元素取子结点D表中对应元素最小的那个值 验证的时候从根结点开始，用它的D表扫描文本块，如果验证没通过，跳过本块；否则用它的子结点依次验证。迭代这个过程直到层次验证树的叶结点，叶结点采用经典的动态规划算法验证平均情况下的最优多模式近似匹配 层次验证 (Hierarchical Verification) 如果层次验证树的各个子树所代表的模式子集存在聚类特征(即子集内的模式之间的编辑距离小于各子集间的模式的编辑距离)，那么将会加速层次验证过程 作者建议，在建立层次验证树之前，采用层次聚类算法对模式进行排序，然后按聚类结果建立子树平均情况下的最优多模式近似匹配 优化措施 为了减少预处理时间，采用带标记的根树(trie)来建造叶结点的D表 为了减少算法所需