首頁 >後端開發 >php教程 >Python實作字串匹配演算法實例程式碼

Python實作字串匹配演算法實例程式碼

小云云
小云云原創
2017-12-06 09:55:102463瀏覽

這篇文章主要介紹了Python實現字串匹配演算法程式碼範例,涉及字串匹配存在的問題,蠻力法字串匹配,Horspool演算法,具有一定參考價值,需要的朋友可以了解下。

字串符合存在的問題

Python中在一個長字串中尋找子字串是否存在可以用兩種方法:一是str的find()函數,find()函數只傳回子字串符合的起始位置,若沒有,則傳回-1;二是re模組的findall函數,可以傳回所有符合到的子字串。

但是如果用findall函數時需要注意字串中存在的特殊字元。

蠻力法字串匹配:

將模式對準文字的前m(模式長度)個字符,然後從左到右右匹配每一對對應的字符,直到全部匹配或遇到一個不匹配的字符。後一種情況下,模式向右移一位。

程式碼如下:

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演算法:

Horsepool演算法是Boyer-Moore演算法的簡化版本,這也是一個空間換時間的典型例子。演算法把模式P和文字T的開頭字元對齊,從模式的最後一個字元開始比較,如果嘗試比較失敗了,它把模式向後移。每次嘗試過程中比較是從右到左的。

在蠻力演算法中,模式的每一次移動都是一個字符,Horspool演算法的核心思想是利用空間來換取時間,提升模式匹配視窗的移動幅度。與蠻力演算法不同的是,其模式的匹配是從右到左的,透過預先算出每次移動的距離並存於表中。

程式碼如下:

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

顯然,Horspool演算法的最差效率屬於屬於Θ(nm)。在尋找隨機文字的時候,其屬於線性的效率Θ(n)。雖然效率類型相同,但平均來說,Horspool演算法比蠻力演算法快很多。

以上內容就是Python實作字串比對演算法實例程式碼,希望能幫助大家。

相關推薦:

python實作連接資料庫的方法介紹

Python操作SQL Server資料庫的方法

Python中排列組合計算操作的實作範例

#

以上是Python實作字串匹配演算法實例程式碼的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn