Python-Implementierung des Beispielcodes für den String-Matching-Algorithmus

In diesem Artikel werden hauptsächlich Codebeispiele für den in Python implementierten String-Matching-Algorithmus vorgestellt, der Probleme beim String-Matching, beim Brute-Force-String-Matching und beim Horspool-Algorithmus beinhaltet. Freunde, die ihn benötigen, können davon erfahren.

Probleme beim String-Matching

Es gibt zwei Möglichkeiten herauszufinden, ob ein Teilstring in einem langen String in Python vorhanden ist: 1. Es ist der find()-Funktion von str. Die find()-Funktion gibt nur die Startposition der übereinstimmenden Teilzeichenfolge zurück. Wenn nicht, gibt sie -1 zurück. Die zweite Funktion ist die Findall-Funktion des re-Moduls, die alle übereinstimmenden Teilzeichenfolgen zurückgeben kann.

Aber wenn Sie die Funktion findall verwenden, müssen Sie auf die Sonderzeichen achten, die in der Zeichenfolge vorhanden sind.

Brute-Force-String-Matching:

Richten Sie das Muster an den ersten m (Musterlänge) Zeichen des Textes aus, dann von links nach rechts stimmt mit jedem Paar entsprechender Zeichen überein, bis alle übereinstimmen oder ein nicht übereinstimmendes Zeichen gefunden wird. Im letzteren Fall wird das Muster um eine Position nach rechts verschoben.

Der Code lautet wie folgt:

def string_match(string, sub_str): 
 # 蛮力法字符串匹配 
 for i in range(len(string)-len(sub_str)+1): 
  index = i  # index指向下一个待比较的字符 
  for j in range(len(sub_str)): 
   if string[index] == sub_str[j]: 
    index += 1 
   else: 
    break 
   if index-i == len(sub_str): 
    return i 
 return -1 

if __name__ == "__main__": 
 print(string_match("adbcbdc", "dc"))

Im schlimmsten Fall gehört dieser Algorithmus tatsächlich zu Θ(nm) Die durchschnittliche Effizienz dieses Algorithmus ist viel besser als die schlechteste Effizienz. Tatsächlich ist seine Effizienz bei der Suche nach Zufallstext linear Θ(n).

Horspool-Algorithmus:

Horspool-Algorithmus ist eine vereinfachte Version des Boyer-Moore-Algorithmus, der auch ein typisches Beispiel für Raum für Zeit ist . Der Algorithmus richtet die Anfangszeichen von Muster P und Text T aus und beginnt den Vergleich ab dem letzten Zeichen des Musters. Wenn der Vergleichsversuch fehlschlägt, wird das Muster rückwärts verschoben. Der Vergleich erfolgt bei jedem Versuch von rechts nach links.

Im Brute-Force-Algorithmus ist jede Bewegung des Musters ein Zeichen. Die Kernidee des Horspool-Algorithmus besteht darin, Raum im Austausch gegen Zeit zu nutzen und den Bewegungsbereich des Mustervergleichsfensters zu vergrößern. Anders als beim Brute-Force-Algorithmus erfolgt der Mustervergleich von rechts nach links, und die Entfernung jeder Bewegung wird im Voraus berechnet und in der Tabelle gespeichert.

Der Code lautet wie folgt:

__author__ = 'Wang' 
from collections import defaultdict 
def shift_table(pattern): 
 # 生成 Horspool 算法的移动表 
 # 当前检测字符为c，模式长度为m 
 # 如果当前c不包含在模式的前m-1个字符中，移动模式的长度m 
 # 其他情况下移动最右边的的c到模式最后一个字符的距离 
 table = defaultdict(lambda: len(pattern)) 
 for index in range(0, len(pattern)-1): 
  table[pattern[index]] = len(pattern) - 1 - index 
 return table 
def horspool_match(pattern, text): 
 # 实现 horspool 字符串匹配算法 
 # 匹配成功，返回模式在text中的开始部分；否则返回 -1 
 table = shift_table(pattern) 
 index = len(pattern) - 1 
 while index <= len(text) - 1: 
  print("start matching at", index) 
  match_count = 0 
  while match_count < len(pattern) and pattern[len(pattern)-1-match_count] == text[index-match_count]: 
   match_count += 1 
  if match_count == len(pattern): 
   return index-match_count+1 
  else: 
   index += table[text[index]] 
 return -1 

if __name__ == "__main__": 
 print(horspool_match("barber", "jim_saw_me_in_a_barbershopp"))

Offensichtlich liegt die schlechteste Effizienz des Horspool-Algorithmus bei Θ(nm). Bei der Suche nach Zufallstext ist seine Effizienz linear Θ(n). Obwohl der Effizienztyp derselbe ist, ist der Horspool-Algorithmus im Durchschnitt viel schneller als der Brute-Force-Algorithmus.

Der obige Inhalt ist der Beispielcode eines in Python implementierten String-Matching-Algorithmus. Ich hoffe, er kann allen helfen.

Verwandte Empfehlungen:

Einführung in Pythons Methode zum Herstellen einer Verbindung mit der Datenbank

Pythons Methode zum Betreiben der SQL Server-Datenbank

Beispiel für die Implementierung von Permutations- und Kombinationsberechnungsoperationen in Python

Das obige ist der detaillierte Inhalt vonPython-Implementierung des Beispielcodes für den String-Matching-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!