ASP.net基于内容的音乐检索方法研究(8)
AC-BM算法描述：
设模式树中最短模式串的长度为L，第一次比较是从待匹配的文本字符串的末端向前取L个字符与模式树的根字符对齐，然后从树的根字符开始比较，当出现不匹配的字符时：
(1)若目标字符不在任何模式串中，则模式树偏移量为L位；
(2)移动到另一模式串前缀的下一位置；
(3)将模式树移动到作为树中另一个模式后缀能够正确匹配目标串的某个前缀的下一个位置。要注意的是：AC-BM算法在移动过程中，模式树移动的偏移量不能超过最短模式串的长度L。们设模式字符串集合中，字符串最小长度为minlen，最大长度为maxlen，待匹配文本长度为n，则在最优情况下，时间复杂度为O(n／minlen)，在最坏情况下，时间复杂度为O(n*maxlen)。
AC-BM算法结合多模式匹配AC和单模式匹配BM两种算法的优点，既可以同时匹配多个模式又可以跳过不必要的字符，因此相比其它模式匹配算法具有较高的性能和效率。
3.2.7 KMP算法的优点
虽然歌词搜索的算法有很多，但是相比较其他算法而言，KMP算法有很多其他算法不具有的优点：
(1) KMP算法作为无回溯匹配的模式匹配中的代表，本身就是一种改进算法，相较于回溯模式匹配算法而言，他节约了大量的时间，使算法更效率。
(2)相比较于朴素算法，KMP算法仅仅只在其原本基础上修改了一条语句，这却使算法的时间复杂度变成了0（m+n）,大大节省了程序的运算时间，提高了工作效率。
(3) KMP算法程序简洁，凝练，充分体现了算法的易读性原则。并且KMP算法可以变换成多种形式，实现深度搜索，广度搜索，以及双向广度搜索的功能。除了这些，KMP算法还能与正态分布等这些实际的应用问题结合一起，从而实现更加快速，简便的搜索。
因此基于上述优点，决定选用KMP算法来实现歌词搜索功能。
3.3 KMP算法介绍
目前，串匹配算法一般是以模式串的长度为扫描窗口大小，在窗口中使用不同的扫描策略来进行匹配。假设模式串长为m，主串长为n，串匹配算法根据策略的不同，大致可以分为以下3类：从前往后匹配模式前缀的KMP算法，从后往前匹配模式后缀的BM算法及其各种变形，以及从后往前匹配模式前缀的RF算法等等。
KMP算法是从前往后进行扫描，使用自动机记住己匹配模式前缀的正文内容，并依据这些内容来确定是否已经匹配成功。换句话说，就是先对模式串进行预计算，然后再与主串匹配，而且主串不需要回溯，它的时间复杂度比较好，一般是O(m+n)。BM算法及其变形是在扫描窗口中从后往前进行扫描，记住已匹配模式后缀的正文内容，并依据这些内容来进行窗口移动，这种方法虽然简单易行，但是时间复杂度比较差，最坏情况下为0(m+n)，所以当串比较长时，效率就会很低。
RF算法等是在从后往前进行扫描时，反向使用模式逆串的后缀自动机来匹配模式的前缀，这样可以增大窗口移动的距离，从而获得更好的平均时间复杂度，达到理论最优结果。该方法效率较高，但是比较复杂，硬件实现难度大。
综合考虑现有的比较成熟的模式匹配算法，认为在硬件实现方面，KMP算法具有其他算法没有的优势。
KMP算法是Knuth等人在BF算法的基础上提出来的。从本质上讲，KMP算法就是出现不匹配情况下带有智能指针初始化的BF算法。为了在不匹配时重新定位指针，KMP算法需要进行预处理算出一个Shift表来。
基本思想：KMP算法利用已匹配成功部分的信息，即前缀(模式字符串中存在的相同子串)，可以使模式字符串向前推进若干个字符位置，而不只是一个字符，避免了重复比较，同时也实现了文本字符串指针的无回溯。要点是：们能够通过预先对模式的分析获得知识，即如果在模式的位置l或2匹配失败则移动1个位置，如果在模式的位置3匹配失败则移动2个位置，如果在模式的位置4匹配失败则移动3个位置，以此类推。
上一篇：云计算在校园网中的应用与研究