ホームページ > 記事 > バックエンド開発 > 文字列一致アルゴリズムの Python 実装サンプルコード

文字列一致アルゴリズムの Python 実装サンプルコード

小云云オリジナル: 2017-12-06 09:55:102354ブラウズ

この記事では、主に Python で実装された文字列マッチングアルゴリズムのコード例を紹介します。文字列マッチング、総当たり文字列マッチング、および Horspool アルゴリズムの問題が含まれます。必要な方は、それについて学ぶことができます。

文字列マッチングの問題

Python では、長い文字列の中に部分文字列が存在するかどうかを調べる方法が 2 つあります。1 つは str の find() 関数で、もう 1 つは部分文字列のみを返す find() 関数です。一致しない場合、開始位置は -1 を返します。2 番目は re モジュールの findall 関数で、一致したすべての部分文字列を返すことができます。

ただし、findall 関数を使用する場合は、文字列内に存在する特殊文字に注意する必要があります。

ブルートフォース文字列マッチング:

テキストの最初の m (パターン長) 文字にパターンを配置し、すべてが一致するか 1 つが見つかるまで、対応する文字の各ペアを左から右に照合します。文字。後者の場合、パターンは 1 つ右にシフトされます。

コードは次のとおりです:

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

最悪の場合、このアルゴリズムは Θ(nm) に属します。実際、このアルゴリズムの平均効率は最悪の効率よりもはるかに優れています。実際、ランダムなテキストを検索する場合、その効率は線形 Θ(n) です。

Horspool アルゴリズム:

Horspool アルゴリズムは、Boyer-Moore アルゴリズムの簡略版であり、空間を時間に交換する典型的な例でもあります。アルゴリズムは、パターン P とテキスト T の先頭文字を位置合わせし、パターンの最後の文字から比較を開始します。試行された比較が失敗した場合、パターンは後方に移動します。比較は各試行中に右から左に行われます。

ブルートフォースアルゴリズムでは、パターンのそれぞれの動きがキャラクターです。Horspool アルゴリズムの中心となるアイデアは、時間と引き換えに空間を使用して、パターンマッチングウィンドウの移動範囲を拡大することです。ブルートフォースアルゴリズムとは異なり、パターンマッチングは右から左へ行われ、各移動の距離が事前に計算され、テーブルに保存されます。

コードは次のとおりです:

__author__ = &#39;Wang&#39; 
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"))

明らかに、Horspool アルゴリズムの最悪の効率は Θ(nm) に属します。ランダムなテキストを検索する場合、その効率は線形 Θ(n) です。効率のタイプは同じですが、平均すると、Horspool アルゴリズムはブルートフォースアルゴリズムよりもはるかに高速です。

上記の内容は、Python で文字列マッチングアルゴリズムを実装するためのサンプルコードです。

文字列一致アルゴリズムの Python 実装サンプル コード

関連記事

文字列一致アルゴリズムの Python 実装サンプルコード