ASP.net基于内容的音乐检索方法研究(6)
时间:2017-04-13 10:38 来源:毕业论文 作者:毕业论文 点击:次
BF算法就是把模式串和文本串的所有窗口逐一进行比较。如果当前字符相同而且模式串结束则匹配成功．如果字符相同而模式串未结束就比较下一个字符：如果字符不相同，则窗口向后移动一个字符位置，模式串和新窗口从开始字符重新比较。 对于文本字符串Tl…Tk…Tj…Tm-k-1…Tn 模式字符串Pl…Pi…Pm 算法描述： (1)P和T从左端对齐，使得Pl与T1对齐； (2)从左到右匹配P与T的字符，直到出现不匹配的情况或是P已被完全匹配： (3)如果出现不匹配的情况，则将P右移一个字符，重新开始匹配； (4)重复上述过程，直到P被完全匹配，或P移到T的右端。 每次模式串和某个窗口比较次数应该是0(m)，而窗口的个数是0（n—m)个。因此算法最坏情况的时问复杂度是O(mn)。最坏情况的例子之一是文本串是某一相同字符的字符串．而模式串也是这一字符的字符串。这种算法的缺陷是匹配过程中带有回溯，准确地说是当匹配不成功的时候，之前进行的匹配完全变为无效的,所有的比较需要从模式串首字符重新开始。 BF算法的优点是不需要预处理。辅助的空间是常量，即只需要几个变量的临时存储区域。模式串和某个窗口内匹配的顺序是任意的，向左或者向右都是可以的。 3.2.2 KMP算法 一种由Knuth(D.E.Knuth)、Morris(J.H.Morris）和Pratt(V.R.Pratt）三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ，匹配时间为Θ（n），只用到辅助函数π[1，m]，它是在Θ（m）时间内，根据模式预先计算出来的。数组π使得们可以按需要，“现场”有效的计算（在平摊意义上来说）变迁函数δ。粗略地说，对任意状态q=0，1，…，m和任意字符a∈Σ，π[q]的值包含了与a无关但在计算δ（q，a）时需要的信息。由于数组π只有m个元素，而δ有Θ（m∣Σ∣）个值，所以通过预先计算π而不是δ，使得时间减少了一个Σ因子。 KMP算法是通过分析子串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后在上面的算法中使用。 3.2.3 BM算法 BM算法是由Boyer和Moore于1977年提出，该算法是目前应用最为广泛的单模式匹配算法。BM算法的一个最主要的特点是，在对字符串的匹配过程中，可以跳过很多无用的字符，即不对无用的字符进行匹配。通过这种跳跃式的匹配，获得了较高的执行效率。有实验数据表明，BM算法的匹配速度大约是KMP算法的3～5倍。 BM算法描述[15]： 第一步：预处理，算法根据预先计算好的两个数组将模式字符串向右移动尽可能远的距离。计算Skip[]数组和Shift[]数组，分别代表BC规则和GS规则。 第二步：从右向左逐个字符比较文本字符串和模式字符串，单个字符匹配则继续比较。如果到达模式字符串的最左边，则成功发生了匹配，输出；如果发生字符失配，则转第三步。 第三步：取失配字符相应的Skip[]数组和Shift[]数组中的数值最大的一个， 作为移动距离，将模式字符串右移。如果己到达文本字符串的末尾，则退出算法；否则转回到第二步执行。 BM算法被设计成为在文本中搜索单一模式字符串的算法，在单一模式的字符串匹配算法中，BM算法一般被认为是性能最佳的。而在内容过滤和检测中有很多种关键词模式需要匹配，因此BM算法需要对每一种模式分别进行匹配。BM算法的预处理阶段的时间空间复杂性是O(m+n)，查找阶段的时间复杂性是O(mn)，查找非周期性模式时的最坏情况下比较次数是3n。BM算法最坏时间复杂度是O(mn)，最好时间复杂度是O(n)。对多模式字符串进行匹配，直接采用BM算法的复杂度是O(kn)。 (责任编辑：qin) |