使用 Python 进行 Boyer Moore 算法模式搜索

2025年3月17日 | 阅读 7 分钟

Boyer Moore 算法是模式匹配算法中最有效的一种。模式搜索方法在笔记本/文字文件、网页浏览器或数据库中查找字符串时显示搜索结果。一种常见的模式搜索技术是 Boyer Moore 字符串搜索技术，具有实际应用价值。

比 O(n) 更快的字符串搜索方法通常需要对文本进行一些预处理，如果频繁进行，这可能是计算密集型的，如果文本量很大，这可能是内存密集型的。Boyer Moore 要求要搜索的模式被预处理。

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

问题陈述

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

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

示例 1

Input: 
str[ ]: "HELLO TESTING THE TEST TEXT"
ptn[ ]: "TEST"

Output:
The Pattern "TEST" is found at index 6.
The Pattern "TEST" is found at index 18.

示例 2

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

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

Boyer Moore Algorithm for Pattern Searching using Python

说明

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

如果我们看例子，我们从索引开始搜索模式。在第一个例子中，我们从索引 0 开始搜索模式“TEST”，并在索引 6 和 18 处找到模式。类似地，我们尝试在第二个例子中查找模式“ABBA”，并从第一个位置开始搜索。我们在第 4^个索引和第 11^个索引处找到了模式。

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

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

坏字符启发式
好后缀启发式

坏字符启发式

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

输入中的某些不匹配字符存在于模式中

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

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

说明

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

当文本字符串在模式字符串中没有不匹配的字符时

为了理解这种情况，让我们举个例子：我们需要在字符串 ABPRPXCPREDFT 中搜索模式字符串 PCERST。我们将从右到左比较模式。

坏字符启发式的实现

代码

total_chars = 256

def badCharacterHeuristic(char, size):

    badChar = [-1]*total_chars

# Filling the actual value of the last occurrence of a character in the bad character list (array).
    for i in range(size):
        badChar[ord(char[i])] = i

    return badChar

def boyerMooreAlgorithm(txt, ptn):
    # Getting the size of the pattern and the string.
    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

        # If the pattern and text match, keep reducing the j variable.
        while j >= 0 and ptn[j] == txt[shift+j]:
            j -= 1

# Checking for the current location of the shift; if it is at the current shift, then j will become -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)

输出

The Pattern found at index:  7

坏字符启发式的复杂度分析

在此方法中，我们遍历了文本字符串的每个部分。

时间复杂度

此方法的时间复杂度为O (n x m)，其中 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。

下一主题Python 函数的清理技巧

使用 Python 进行 Boyer Moore 算法模式搜索

问题陈述

坏字符启发式

坏字符启发式的实现

好后缀启发式

好字符启发式的实现

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

使用 Python 进行 Boyer Moore 算法模式搜索

问题陈述

坏字符启发式

坏字符启发式的实现

好后缀启发式

好字符启发式的实现

相关帖子

Python 中的 Box-Cox 变换

Django vs. Node JS

使用 Python 抓取最受欢迎的新闻和推文

如何在 Python 字符串中移除单引号

Python 中的摩尔斯电码翻译器

解析时间戳 Python

Python 列表大小

Python 是脚本语言吗

PyQt5 QDoubleSpinBox - 设置最大可能值

是否应该更新 Python 的最新版本错误修复

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器