基于后缀WM匹配算法的改进算法.docx

基于后缀WM匹配算法的改进算法
后缀WM算法是一种高效的字符串匹配算法，它利用了字符串的后缀和前缀的性质，避免了多余的比较和回溯操作，进而实现快速的匹配。然而，这种算法在处理长字符串时，会出现空间使用和时间复杂度上的问题，因此需要进行改进。本文将介绍基于后缀WM匹配算法的改进算法，并探讨其优化之处。
一、后缀WM匹配算法的基本原理
后缀WM匹配算法是基于前缀和后缀的概念实现的一种模式匹配算法。具体的，该算法的主要思想是：对于待匹配的文本串T，首先对T进行预处理，找出其中所有的后缀子串，并将其和模式串P进行匹配，计算出每个后缀的匹配值（matchvalue），并将其存储在一个数组M中。然后，从T的第一个字符开始，逐一比较模式串P和T的后缀子串，如果发现后缀子串的匹配值等于P的长度，则表示匹配成功；否则，将T向右移动一位，继续匹配。
具体步骤如下：
1.预处理文本串T
一个串的后缀子串是指从串的某一个位置起始，一直到串末尾的所有子串。例如，字符串“abcd”的后缀子串为“abcd”，“bcd”，“cd”和“d”。对于任意的字符串T，它的后缀子串可以通过对T的每个位置i从后向前遍历，并在每个位置上取出从i到T末尾的子串，从而得到。
2.计算匹配值
对于一个后缀子串和模式串，可以计算出它们的匹配值（matchvalue），表示两者在第一个不匹配的字符之前的相同前缀的长度。因此，对于任意的模式串P和文本串T的后缀子串S，可以利用如下公式计算出它们的匹配值：
match_value(P,S)=k(0<=k<|P|)，其中|P|表示P的长度。
例如，对于模式串P=“ababc”，和后缀子串S=“bcababc”，它们的匹配值为“abab”的长度，即4。
3.匹配过程
从文本串T的第一个字符开始，逐一比较后缀子串和模式串。每次比较时，我们都将后缀子串与模式串的第一个字符进行比较，如果相同，则继续比较后续字符；否则，将T向右移动一位，继续匹配。当匹配成功时，记录下此时的T所在位置，即为模式串在文本串中的起始位置。如果一直匹配到达T末尾也没有匹配成功，则匹配失败。
二、后缀WM匹配算法的问题
虽然后缀WM匹配算法是一种高效的字符串匹配算法，但它并不适合用于处理大规模数据，原因如下：
1.空间复杂度高
后缀WM匹配算法需要为每个后缀子串计算出匹配值，并将其存储在一个数组M中，再进行匹配。如果T的长度为n，算法的空间复杂度为O(n^2)，当n很大时，其空间开销非常高。
2.时间复杂度高
后缀WM匹配算法在预处理T和计算匹配值时，需要遍历每个字符，并且每个字符都要和后缀子串进行匹配。因此，该算法的时间复杂度为O(n^2)，其中n表示文本串T的长度，这在处理大规模数据时，耗时较长。
三、基于后缀WM匹配算法的改进算法
针对后缀WM匹配算法的上述问题，可以采取如下措施进行改进：
1.使用后缀数组
后缀数组是一种将串的后缀按字典序排列的数组，它可以快速定位任意一个子串在原串中的位置。因此，可以通过使用后缀数组来替代后缀WM匹配算法中的M数组，从而减少算法的空间复杂度。
具体的，对于文本串T，首先利用后缀数组suffix_array将T的所有后缀子串按字典序排列，并将排列后的位置存储在数组P中。例如，对于字符串T=“ababc”，其后缀数组suffix_array为{5,4,2,3,1}，其中5表示T的末尾，4表示“c”的下标，以此类推。然后，对于每个位置i(0<=i<n)，都可以通过查找P数组中i后面的后缀子串所在位置（即P[i]）来计算T的后缀子串和模式串P的匹配值。由于后缀数组已经将所有的后缀子串按字典序排列，因此可以利用相邻后缀子串间的公共前缀来快速计算它们的匹配值。
2.使用最长公共前缀(LCP)数组
最长公共前缀数组（LCP）是后缀数组的一个重要概念，它记录了相邻两个后缀子串间的公共前缀的长度。因此，在后缀数组(suffix_array)的基础上，可以使用LCP数组减少匹配时的比较次数，从而减少算法的时间复杂度。
具体的，对于后缀数组suffix_array和对应的LCP数组L，可以通过以下公式计算出T的任意两个后缀子串的匹配值：
match_value(P,S)=LCP(suffix_array[i],suffix_array[j])，其中i和j表示P在suffix_array数组中的位置以及S在suffix_array数组中的位置。
例如，对于模式串P=“ababc”和位置i=1，j=2的两个后缀子串S1=“abc”和S2=“ababc”，它们的匹配值为LCP(suffix_array[1],suffix_array[2])=1。
3.使用二分查找法
在使用LCP数组计算匹配值时，可以引入二分查找法来提高匹配速度。具体的，对于任意的模式串P和文