Python 中的朴素文本搜索算法

作者

在本教程中，我们将研究识别文本中的模式。除了主要内容之外还会有一个子字符串。目的是确定子字符串在文本中出现的次数以及出现的位置。

当文本很大并且我们需要定位特定关键字或术语的出现时，这种模式查找方法非常有用。

在本节中，我们将讨论最基本的“Python 中的朴素字符串匹配算法”以及如何通过更好、更短的代码来改进它。

朴素算法简介

顾名思义，朴素算法是非常基本且易于实现的算法。这些算法使用最基本、最明显的策略来像孩子一样完成任务。

对于初学者来说，在转向更高效、更复杂的算法之前，这些方法是一个很好的起点。其中之一是基本的字符串搜索算法。在字符串匹配/模式查找算法中，它是最基本的。

该过程从逐个字母匹配字符串开始。它搜索主文本和子字符串中的第一个字符。如果匹配，则继续到两个字符串中的下一个字符。

如果字符在循环中的任何位置都不匹配，则循环被中断，并且从主文本字符串中的下一个字符重新开始循环。

实现简单的字符串搜索

1
2
3
4
5
6
7
8
9
10
11
12
def naive(txt,wrd):
    lt=len(txt)#length of the string
    lw=len(wrd)/3length of the substring(pattern)
    for i in range(lt-lw+1):
        j=0
        while(j<lw):
            if txt[i+j]==wrd[j]:
                j+=1
            else:
                break
        else:
            print('found at position',i)

上面代码中的“naive”方法采用两个参数：txt（要从中查找模式的主字符串）和 ward（要搜索的模式）。

由于至少要保留子串的长度来匹配末尾，因此从 0 到（字符串长度-子串长度+1）进行循环。‘for’ 循环从字符串 (text[I]) 中提取每个字符。

然后有一个内部 while 循环，将该字符与子字符串中的下一个字符进行比较，直到整个子字符串匹配。如果没有发现，循环就会中断，并且接下来的迭代（如下一个字符）将从过程中删除。

当发现完整的子字符串时，while 条件被破坏，否则运行部分，并显示位置。另一种是在循环内，仅当 if 条件为 false 时才运行，而另一种则在 while 循环条件为 false 时执行。

让我们看看以下输入的输出：

naive("AABAACAADAABAABA","AABA")

输出结果如下：

found at position 0
found at position 9
found at position 12

结论

恭喜！您刚刚学习了如何实现朴素字符串搜索算法。希望你喜欢它！😇

喜欢该教程吗？无论如何，我建议您查看下面提到的教程：

  1. 查找没有连续 1 的可能字符串的数量
  2. 如何在Python中将字典转换为字符串？
  3. 在 Python 中将元组转换为字符串 [分步]

感谢您抽出宝贵时间！希望你学到新东西！😄