整合營(yíng)銷服務(wù)商
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
在經(jīng)典的模式匹配問(wèn)題中，我們給出了長(zhǎng)度為n的文本字符串T和長(zhǎng)度為m的模式字符P，并希望明確是否P是T的一個(gè)字串。如果是，則希望找到P在T中開(kāi)始位置的最低索引j，比如T[j:j+m]和P匹配，或者從T中找到所有的P的開(kāi)始位置索引。
在本文中，我們介紹三種匹配算法，難度依次遞增。
1.暴力窮舉法
窮舉法是極其常用的一種算法，不止在匹配算法上，還在優(yōu)化某些功能上也有涉及。
窮舉法即為列舉出所有的可能情況，并加以逐一判斷。
def find_brute(T, P):
"""Return the lowest index of T at which substring P begins (or else -1)"""
n, m = len(T), len(P) # Get length of T and P's
for i in range(n-m+1): # Because it can't be P after T[n-m+1:]
k = 0 # Record the index of P
while k < m and T[i + k] == P[k]: # The match was incomplete and successful
k += 1
if k == m: # Match successful
return i
return -1這是一個(gè)簡(jiǎn)單的暴力枚舉的匹配算法，判斷P是否是T的一個(gè)子串，是則返回第一次出現(xiàn)的索引，否則返回-1，算法優(yōu)化在不改變代碼結(jié)構(gòu)的基礎(chǔ)上，就是這里扣一點(diǎn)，那里扣一點(diǎn)。例如range函數(shù)的范圍我們給出了n-m+1，因此對(duì)于P長(zhǎng)度越大，則性能優(yōu)化最大。
我們可以看到外層for循環(huán)至多執(zhí)行了n-m+1次，內(nèi)存while循環(huán)至多執(zhí)行了m次，因此，該算法在最壞的情況下的運(yùn)行時(shí)間是
測(cè)試一下：
T = "abcafgasdfwefacasdfe"
P = "asd"
print(find_brute(T, P))運(yùn)行結(jié)果：
2.Boyer-Moore算法
Boyer-Moore算法的主要思想是通過(guò)增加兩個(gè)可能省時(shí)的啟發(fā)式算法來(lái)提升窮舉法的運(yùn)行時(shí)間：
1.鏡像啟發(fā)式（Looking-glass )：當(dāng)測(cè)試P相對(duì)于T可能的位置時(shí)，可以從P的尾部開(kāi)始比較，然后從后向前移動(dòng)直到P的頭部。
2.字幕跳躍啟發(fā)式(-jump )：在測(cè)試P在T中可能的位置時(shí)，有著相應(yīng)模式字符P[k]的文本字符T[i] = c的不匹配情況按如下方法處理：如果P中任何位置都不包含c，則將P完全移動(dòng)到T[i]之后，(因?yàn)樗荒芷ヅ銹中任何一個(gè)字符）；否則，直到P中出現(xiàn)字符c并與T[i]一致才移動(dòng)P。
def find_boyer_moore(T, P):
"""Return the lowest index of T at which substring P begins (or else -1)"""
n, m = len(T), len(P) # get length of T and P's
if m == 0: return 0 # Return 0 if m's length is 0
last = {} # Create a dictionary for P
for k in range(m): # Add each character position of P to the dictionary
last[P[k]] = k
# align end of pattern at index m-1 of text
i = m-1 # This is a pointer to T
k = m-1 # This is a pointer to P
while i < n: # Use the while loop to iterate over T
if T[i] == P[k]: # If the match is successful and all matches
if k == 0:
return i
else: # If the match is successful but no all matches
i -= 1 # Pointer forward
k -= 1
else:
j = last.get(T[i], -1)
# If the current character appears in the mode character,Return index ,else -1
i += m - min(k, j+1)
# Returns the starting pointer position by adding up the number of matched characters
k = m-1
# Restore k
return -1
這段代碼的一個(gè)核心在于以下三條：
j = last.get(T[i], -1)
i += m - min(k, j+1)
k = m-1
通過(guò)字典last.get返回值判斷是否匹配成功過(guò)，如果字符在P中出現(xiàn)過(guò)，則返回索引（即還有多少個(gè)字符沒(méi)有匹配，然后通過(guò)m減去得到已經(jīng)匹配的數(shù)量，在累加到i上，即可使i指針回到最初的位置，正常向后推進(jìn)），否則返回-1，而在第二行中，使用了min函數(shù)判斷k和j+1的大小（如果沒(méi)有匹配到，則j+1得到0，m-0就會(huì)使指針i直接向后推進(jìn)m個(gè)位置，極大程度上減少了運(yùn)行速度。如果匹配成功過(guò)，則也可以通過(guò)min函數(shù)判斷k和j+1的大小使得m-min(k, j+1)能取得最大值）。 最后呢，將k還原為最開(kāi)始的m-1. 如果使用傳統(tǒng)的查找表，在最壞的情況下BM算法的運(yùn)行時(shí)間是o(nm) 測(cè)試一下
print(find_boyer_moore("abedef", "ede"))運(yùn)行結(jié)果：
3.Knuth-Morris-Pratt算法
KMP算法對(duì)于模式有一個(gè)確定的調(diào)整，如果發(fā)現(xiàn)一些匹配的字符但后來(lái)又發(fā)現(xiàn)不匹配，在模式下一次重新匹配時(shí)，我們忽略所有由成功的比較而獲得的信息。這樣避免了信息的浪費(fèi)，并且它能達(dá)到的運(yùn)行時(shí)間為
, 這是漸近最優(yōu)運(yùn)行時(shí)間。即在最壞的情況下，任何模式匹配算法將會(huì)對(duì)文本的所有字符和模式的所有字符檢查至少一次。KMP算法的主要思想是預(yù)先計(jì)算模式部分之間的自重疊，從而當(dāng)不匹配發(fā)生在一個(gè)位置時(shí)，我們?cè)诶^續(xù)搜尋之前就能立刻知道移動(dòng)模式的最大數(shù)目。
失敗函數(shù)
為了實(shí)現(xiàn)KMP算法，我們需要預(yù)先計(jì)算失敗函數(shù)
，該函數(shù)用于表示匹配失敗時(shí)P對(duì)應(yīng)的位移。具體地，失敗函數(shù)f(k)定義為P的最長(zhǎng)前綴的長(zhǎng)度，它是P[1:K+1]的后綴（這里沒(méi)有包含P[0]，因?yàn)橹辽贂?huì)移動(dòng)一個(gè)單元）。如果在字符P[k+1]中找不到匹配，函數(shù)f(k)會(huì)告訴我們多少緊接著的字符可以用來(lái)重啟模式
def compute_kmp_fail(P):
"""Utility that computes and returns KMP 'fail' list."""
m = len(P)
fail = [0] * m # by default. presume overlap of 0 everywhere
j = 1
k = 0
while j < m: # compute f(j) during this pass, if nonzero
if P[j] == P[k]: # k + 1 characters match thus fat
fail[j] = k + 1
j += 1
k += 1
elif k > 0: # k follows a matching prefix
k = fail[k-1]
else: # no match found starting at j
j += 1
return fail這是一個(gè)失敗函數(shù)，通過(guò)雙指針來(lái)匹配最大的重復(fù)前綴，它將模式與KMP中的模式進(jìn)行比較。每次有兩個(gè)匹配的字符，我們?cè)O(shè)置f(j0 = k + 1。因?yàn)樵谡麄€(gè)算法中已經(jīng)有j > k，當(dāng)使用它時(shí)，f(k - 1)總是被定義好的。
def find_kmp(T, P):
"""Return the lowest index of T at which substring P begins (or else -1)"""
n, m = len(T), len(P) # Get length of T and P's
if m == 0: return 0 # Return 0 if P's length is 0
fail = compute_kmp_fail(P) # Call the compute_kmp_fail function to get the return list
j = 0
k = 0
while j < n:
if T[j] == P[k]:
if k == m - 1: # Complete match
return j - m + 1 # Return the index of the first matched character
j += 1 # Match successful but no all, pointer forward
k += 1
elif k > 0: # Match failure but succeeded
k = fail[k - 1] # Prefix rebound
else:
j += 1
return -1這是一個(gè)KMP算法的實(shí)現(xiàn)，其中 k = fail[k-1]實(shí)現(xiàn)了不完全匹配時(shí)觸發(fā)的前綴回跳，以此來(lái)減少匹配次數(shù)，實(shí)現(xiàn)算法優(yōu)化。不太理解的可以打個(gè)斷點(diǎn)觀察一下k的變化。
測(cè)試一下：
print(find_kmp("ababababef", "ababef"))運(yùn)行結(jié)果：
*請(qǐng)認(rèn)真填寫(xiě)需求信息，我們會(huì)在24小時(shí)內(nèi)與您取得聯(lián)系。
