Implémentation Python d'un exemple de code d'algorithme de correspondance de chaînes

Cet article présente principalement des exemples de code d'algorithme de correspondance de chaînes implémenté en Python, impliquant des problèmes de correspondance de chaînes, de correspondance de chaînes par force brute et de l'algorithme Horspool. Il a une certaine valeur de référence. Les amis qui en ont besoin peuvent en apprendre davantage.

Problèmes de correspondance de chaîne

Il existe deux façons de savoir si une sous-chaîne existe dans une longue chaîne en Python : 1. C'est le Fonction find() de str. La fonction find() renvoie uniquement la position de départ de la sous-chaîne correspondante, sinon elle renvoie -1 ; la seconde est la fonction findall du module re, qui peut renvoyer toutes les sous-chaînes correspondantes.

Mais si vous utilisez la fonction findall, vous devez faire attention aux caractères spéciaux qui existent dans la chaîne.

Correspondance de chaîne par force brute :

Alignez le motif sur les premiers m (longueur du motif) caractères du texte, puis de gauche à droite fait correspondre chaque paire de caractères correspondants jusqu'à ce qu'ils correspondent tous ou qu'un caractère non correspondant soit rencontré. Dans ce dernier cas, le motif est décalé d’une position vers la droite.

Le code est le suivant :

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"))

Dans le pire des cas, cet algorithme appartient à Θ(nm), en fait, la moyenne de cet algorithme est bien meilleure que la pire efficacité. En fait, lors de la recherche de texte aléatoire, son efficacité est linéaire Θ(n).

Algorithme de Horspool :

L'algorithme de Horspool est une version simplifiée de l'algorithme de Boyer-Moore, qui est également un exemple typique d'espace-temps . L'algorithme aligne les premiers caractères du motif P et du texte T, en commençant la comparaison à partir du dernier caractère du motif. Si la tentative de comparaison échoue, il déplace le motif vers l'arrière. La comparaison se fait de droite à gauche lors de chaque essai.

Dans l'algorithme de force brute, chaque mouvement du motif correspond à un caractère. L'idée principale de l'algorithme Horspool est d'utiliser l'espace en échange du temps et d'augmenter la plage de mouvement de la fenêtre de correspondance de motifs. Différent de l'algorithme de force brute, la correspondance de motifs s'effectue de droite à gauche et la distance de chaque mouvement est calculée à l'avance et stockée dans le tableau.

Le code est le suivant :

__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"))

Évidemment, la pire efficacité de l'algorithme Horspool appartient à Θ(nm). Lors de la recherche de texte aléatoire, son efficacité est linéaire Θ(n). Bien que le type d'efficacité soit le même, en moyenne, l'algorithme Horspool est beaucoup plus rapide que l'algorithme de force brute.

Le contenu ci-dessus est un exemple de code d'algorithme de correspondance de chaînes implémenté en Python. J'espère qu'il pourra aider tout le monde.

Recommandations associées :

Introduction à la méthode Python de connexion à la base de données

Méthode Python d'exploitation de la base de données SQL Server

Exemple de mise en œuvre d'opérations de calcul de permutation et de combinaison en Python

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!