一、搜索一个模式在文本中的所有近似出现
输入:模式p=p1p2..pn,文本t=t1t2...tm以及参数(它是最大错配数)。
输出:所有位置1<=i<=m-n+1,使得titi+1....ti+n-1与p1p2...pn至多有k个错配(即:dH(ti,p)<=k)
二、查询匹配问题
找到所有与文本近似匹配的查询的子字符串
输入:查询序列q=q1...qp,文本t=t1...tm,以及整数n和k
输出:所有配对位置(i,j),其中1<=i<=p-n+1,1<=j<=m-n+1,使得q中第i个位置起的长为n的子字符串与文本t中从第j个位置起的长为n的子字符串匹配,其中最多有k个错配。
当p=n时,查询匹配问题成为一个允许k个错配的近似字符串匹配问题。
三、l-元组过滤技术
如果一个查询的n字符子字符串与文本中长为n的子字符串近似匹配,对足够大的l来说,2个子字符口中 至少共享一个l元组。
如果字符串x1x2...xn和y1y2...yn相匹配,其最大错配数为k那么它们共享一个l-元组,其中l=|n/(k+1)|即:xi+1..xi+l=Yi+1..Yi+l,其中1<=i<=n-l+1
l元组过滤算法如下:
1)潜在匹配检测。找到查询和文本中所有的l元组匹配,其中l=|n/(k+1)|
2)潜在匹配验证。通过向左向右延伸检验每个潜在的匹配,直到第一次发现k+1个错配(或者到达查询或文本的2端)
潜在匹配的检测可利用哈希表方法或者后缀树方法来实现
分享到:
相关推荐
一种快速近似模式匹配算法.doc
高效,安全的外包近似模式匹配协议
串匹配问题实际上就是一种模式匹配问题,即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配(Keyword Matching)。所谓关键词匹配,是指给定一个长为n的文本串T[1,n]和长为m的...
为解决实际中不同制造模式的实现之间存在大量相似但又不完全相同的模块的自重构问题,提出基于近似匹配的知识化制造系统自重构的理论和算法.首先讨论知识化制造系统自重构中知识点的匹配度定义和性质;然后给出基于...
搜索-近似模式匹配 描述: 「“ abcde”に近い文字列」のように,距离表现で指定しにくい暧昧検索を実行します。 概要: a = Asearch.new('abcde') a.match('abcde') # => true a.match('abXcde') # => false a....
模糊匹配库提供了OmniMark模式函数,该函数试图将输入前缀与任何给定的目标字符串近似匹配。 距离每个目标字符串的允许的Damerau–Levenshtein距离是用户指定的。 此距离等于将目标字符串转换为输入所需的最小字符...
针对此问题,已有工作分析了在不同的模式特征下,匹配数Ω随文本长度增加呈指数级增长。同时考虑文本分布特征和模式特征,建立了期望模型E(Ω)=nDπ(P),其中n为文本长度,D为模式中各通配符跨度的乘积,π(P...
Landau-Vishkin 89 是一种近似的字符串匹配算法,它提供了一种动态编程解决方案,用于查找最多 k 差异的模式文本对齐的所有出现。 该算法在接近线性的时间内运行,特别是 O(nk),其中 n 是文本的长度,k 是最大编辑...
第三章 近似串匹配算法 27 第一节 引言 27 第二节 动态规划算法 28 第三节 基于自动机的串匹配算法 35 第四节 位并行串匹配算法 37 第五节 过滤算法 与 index 41 小结 42 参考文献 43 附录A 算法源码 45 1 BM算法 45...
NETASPNO:非重叠条件下的近似严格模式匹配
函数 fzsearch(r,p,n,case) 查找字符串 r(参考)和字符串 p(模式)的子字符串之间的最佳或预定近似匹配。 Levenshtein 距离用作匹配的度量。 Levenshtein 距离是将字符串 A 转换为字符串 B 所需的最小单字符替换、...
Dio或“ Dive Into Objects”(Dive Into Objects)是用于Ruby对象的包装器,这些对象没有定义模式匹配接口,但是具有使它们能够实现其近似的方法: Dio [ 1 ] in { succ : { succ : { succ : 4 } } }# => true ...
主要功能和特点如下: 支持简单字符串搜索、韩文音节近似匹配、辅音匹配可以在一个字符串中搜索多个模式您可以使用正则表达式锚点^和$将模式的位置限制在搜索目标字符串的开头和结尾。 支持 Unicode Hangul Jamo 和...
为解决实际中不同制造模式的实现之间存在大量相似但又不完全相同的模块的自重构问题,提出基于近似匹配的知识化制造系统自重构的理论和算法.首先讨论知识化制造系统自重构中知识点的匹配度定义和性质;然后给出基于...
Clojure 的近似模式匹配库,可用于基于 Levenshtein 距离查找相似词。 基于 Vladimir Levenshtein 的。 用法 ( require '[fuzzy-matcher.core :as fuzzy]) ; ; Let's search for a list of similar words for a ...
融合的封闭模式匹配是一种基于封闭的模式匹配的近似匹配,可用于鉴定肿瘤基因组中的融合肽。 在本文中,我们提出了一种新的融合块模式匹配算法。 我们将Julio解决方案与我们的解决方案进行了比较,这表明我们的算法...
MTIMESX 是一个快速的通用矩阵和标量乘法例程,具有以下特点: - 直接支持多维(nD,n>2)数组- 支持转置、共轭转置和共轭预...即使它与 MATLAB 不完全匹配- SPEEDOMP:最快的 BLAS、LOOPS 或 LOOPOMP 方法,即使它与
按照功能,串匹配算法主要分为三类:精确串匹配算法、近似串匹配算法和正则表达式算法。其中,最有影响的是KMP算法、BM算法、RK随机算法和SUANDAY算法以及由此而产生的一些改进算法。在实际应用中,这些算法都...