Python中模式搜索的博耶摩尔Boyer Moore算法

博耶-摩尔（Boyer Moore）算法是最有效的模式匹配算法。在记事本/word 文件、网络浏览器或数据库中查看字符串时，模式搜索方法会显示搜索结果。博耶-摩尔字符串搜索技术是一种常见的模式搜索技术，并有实际应用。

博耶-摩尔要求对所搜索的模式进行预处理，快于 O(n) 的字符串搜索方法，后者通常需要对文本进行一些预处理，如果频繁进行预处理，计算成本会很高，如果文本内容较多，则会占用大量内存。

这种算法首先要对我们要搜索的字符串进行预处理。我们从预处理中获得的信息将用于搜索算法的进一步步骤。这种算法的主要特性是匹配序列的尾部而不是头部，并以多字符跳转的方式向下跳过文本，而不是检查文本中的每个字母。

问题陈述
字符串指定为str[0….s - 1]，模式字符串指定为ptn[0….p-1]，其中s 是字符串长度， p是模式长度；我们需要创建一个函数来打印文本字符串中所有出现的模式字符串。我们可以假设文本字符串的长度大于模式字符串的长度。

让我们通过几个例子来理解问题陈述。

示例1：

输入：   

str[ ]:  "
HELLO TESTING THE TEST TEXT
"  
ptn[]：  “
TEST
”  

  
输出：  
模式 “TEST”位于 索引 6 处。   
模式 “TEST”位于 索引 18 处。   

示例2：
Input:   

str[ ]: "ABCDABBACACABBAD"  
ptn[ ]: "ABBA"  

  
Output:  
The Pattern "ABBA" is found at index 4.  
The Pattern "ABBA" is found at index 11.  

用于存储字符和多个序列的不可变数据类型称为字符串。

  • 从示例1中可以看出，我们是从索引开始搜索模式的。在第一个示例中，我们从索引 0 开始搜索模式 "TEST"，然后在索引 6 和 18 处找到了模式。
  • 同样，在第二个示例中，我们试图查找 "ABBA "模式，并从第一个位置开始搜索。我们首先在第 4 个索引处，然后在第 11 个索引处找到了该模式。

我们将使用 Boyer Moore 算法来搜索字符串中的模式，即分配两个指针来搜索字符串中的模式。指针分配在字符串和字符串的第 0 个索引处。该算法从最后一个字符开始搜索模式。然后，从最右边的字符开始，将模式与其当前位置的文本字符串进行比较。

当字符无法匹配时，Boyer-Moore 算法会以两种方式同时移动字符：

  1. 不良字符启发法
  2. 良好的后缀启发法

不良字符启发法
当算法无法找到字符串中的模式时，它会给出两种不同的情况：

  • 模式中存在输入的一些不匹配字符

在这些情况下，不匹配的字符称为坏字符。当发现不匹配的字符时，我们移动模式直到它与字符串的字符匹配。

例如，我们正在字符串 ABPRPXCPREDFT中搜索模式 PCERST。当我们将模式字符串与文本字符串进行比较时，我们发现字符串的字符 P（坏字符）和模式的字符 E之间不匹配。然后，我们将移动模式字符串，直到模式字符串的字符 P 与文本字符串的字符 P 匹配。

解释：
我们从索引0开始在文本字符串中搜索模式，发现第一个字符与模式字符不匹配。然后，我们移动模式以匹配字符串文本。

  • 当文本字符串与模式字符串中不存在任何不匹配的字符时 

total_chars = 256  
  
def badCharacterHeuristic(char, size):  
  
    badChar = [-1]*total_chars  
  
# 填充坏字符列表（数组）中最后出现的字符的实际值。  
    for i in range(size):  
        badChar[ord(char[i])] = i  
  
    return badChar  
  
def boyerMooreAlgorithm(txt, ptn):  
    # 获取模式和字符串的大小。  
    m = len(ptn)  
    s = len(txt)  
  
    badCharacter = badCharacterHeuristic(ptn, m)  
  
    # Initially, there is no shift  
    shift = 0  
  
    # Defining the boundaries of the searching  
    while(shift <= s-m):  
        j = m-1  
  
        # 检查当前的移位位置；如果在当前移位位置，则 j 将变为 -1
        while j >= 0 and ptn[j] == txt[shift+j]:  
            j -= 1  
  
# 检查当前的移位位置；如果在当前移位位置，则 j 将变为 -1
        if j < 0:  
            print(" The Pattern found at index: ", shift)  
  
            shift += (m-badCharacter[ord(txt[shift+m])]  
                       if shift+m < s else 1)  
        else:  
            shift += max(1, j-badCharacter[ord(txt[shift+j])])  
  
txt = "SWERTAPABCAAPPLOC"  
ptn = "ABCAAPPLO"  
boyerMooreAlgorithm(txt, ptn)  


不良字符启发法的复杂性分析
在这种方法中，我们遍历了文本字符串的每个部分的模式。

  • 时间复杂度：这种方法的时间复杂度为O ( nxm)，其中 n 是文本的长度，m 是模式的长度。
  • 空间复杂度：没有额外的空间用于数组的预处理。因此，空间复杂度为 (O (1))。

良好的后缀启发法
使用 Boyer-Moore 算法搜索模式的另一种方法是首先发现好的后缀，然后对其进行分析。基本思想是将模式和文本字符串的重叠区域对齐在一起，以便在发生不匹配时更有效地移动。

让我们通过一个例子来理解这种情况。采取一个模式并从右侧开始搜索。假设找到了模式字符串的一部分。我们将进行搜索，直到发现不匹配的地方。匹配的模式或模式中与文本字符串匹配的部分称为良好字符串。文本中的任何不匹配都意味着当前位置不是模式字符串的起始位置。现在，我们将模式转移到下一个位置进行搜索。好的后缀可用于转换模式。

有两种情况我们使用好的后缀：
1、好后缀在模式中的位置不同：
例如，文本字符串为AABBCAABBGCAABBAA，模式字符串为AABBAA；我们可以看到好的字符串（模式字符串的一部分与文本字符串匹配）出现在不同的位置。我们将移动好的后缀，使其与文本对齐，并且模式文本与文本字符串匹配。

2. 好的后缀的某些部分是模式的前缀：
在搜索时，我们发现模式不匹配，但与好的字符串不完全匹配。如果找到好的后缀作为模式的前缀，我们可以移动后缀以使模式与文本字符串对齐。

# suffix preprocessing  
def suffix_processing(shift, borderPos, ptn, n):  
    i = n  
    j = n + 1  
    borderPos[i] = j  
      
    while i > 0:  
        while j <= n and ptn[i - 1] != ptn[j - 1]:  
            if shift[j] == 0:  
                shift[j] = j - i  
  
            j = borderPos[j]  
  
        i -= 1  
        j -= 1  
        borderPos[i] = j  
  
# prefix preprocessing  
def prefix_processing(shift, borderPos, ptn, n):  
    j = borderPos[0]  
    for i in range(n + 1):  
        if shift[i] == 0:  
            shift[i] = j  
  
        if i == j:  
            j = borderPos[j]  
  
# searching string   
  
def boyerMooreAlgorithm(txt, ptn):  
    s = 0  
    n = len(ptn)  
    m = len(txt)  
  
    shift = [0] * (n + 1)  
    borderPos = [0] * (n + 1)  
  
    # First, performing the preprocessing  
    suffix_processing(shift, borderPos, ptn, n)  
    prefix_processing(shift, borderPos, ptn, n)  
  
    while s <= m - n:  
        j = n - 1  
  
        while j >= 0 and ptn[j] == txt[s + j]:  
            j -= 1  
  
        if j < 0:  
            print("The Pattern is found at index:", s)  
            s += shift[0]  
        else:  
            s += shift[j + 1]  
  
txt = "ABCDAABBEEPYPAABBEE"  
ptn = "AABBEE"  
boyerMooreAlgorithm(txt, ptn)  

输出：
The Pattern is found at index: 4
The Pattern is found at index: 13

优秀字符启发式的复杂性分析

在这种方法中，我们遍历了模式字符串，并对字符串的后缀和前缀进行了预处理。

  • 时间复杂性：这种方法的时间复杂度为 O (m x n)，其中 m 是文本的长度，n 是模式的长度。
  • 空间复杂度：这种方法的空间复杂度为 [O (n) + O (n)]，等于 O (m)，其中 m = n + n。