アルゴリズム-KMP文字列マッチングとそのPython実装

KMPモードマッチングアルゴリズム

1.考え方分析

参照先:https://blog.csdn.net/lemon_tree12138/article/details/48488813

1.1知識の補充

マッチングモードでは、各最適接頭辞(最適接頭辞については「アルゴリズム導論」32章の内容を参照することができる)Sにおいて、Sの自己の最長ではない1つが最適接尾辞(最適接尾辞については「アルゴリズム導論」32章の内容を参照することができる)に等しい最適接頭辞SSである.この言葉にはいくつかの早口が聞こえるかもしれませんが、次の例で説明します.
マッチングモードP:ababaca
Pの最適プレフィックスS=ababaを選択すると,SS=abaとなる.SSはSの最適接頭辞であり、Sの最適接尾辞であり、最も長いからである.

1.2例の説明

KMPアルゴリズムの鍵は、主文字列のマッチング位置「ポインタ」を使用して遡及する必要がない重複マッチングを排除することです.ここでは小さな例を挙げてみましょう.
主文字列T:fababadaaswababababacaマッチングモードP:ababaca
もしこのときTの7位(fababa[d]aaswababababababa)とPの6位(ababa[c]a)をマッチングしていて,マッチングに失敗していたら.素朴なマッチングパターンに対してはTの「ポインタ」が(fa[b]abadaaswabababacaに遡り,Pの「ポインタ」が([a]bababababababacaに遡る)である.Tの「針」の遡及は、多くの時間を浪費したに違いない.
P(ababaca)を再確認し、6位のマッチングを開始すると、前の5位のマッチングが完了しました.また,［aba］ba＝ab［aba］である.では,Tに対してfab[aba]daaswababacaの3ビットは既にマッチングされており,マッチングはP(aba)caであり,[aba]ba=ab[aba]である.ここで選択された最適なサブストリングは、現在の一致文字列Tの一部(aba)全体を表すことができ、一致時に接頭辞が失効すると、接尾辞から直接一致することが理解される.このとき,T「ポインタ」を直接fab[aba]の後ろの要素(すなわちi=6,P「ポインタ」は[aba]の後ろの要素(すなわちi=3)を指すことができる.

2コード実装

import time
import numpy as np


class SimpleMatching():

    def getIndexOfPinT(self, t, p):
        if t is None or p is None:
            return None

        indexes = []

        for i in range(len(t) - len(p) + 1):
            for j in range(len(p)):
                if t[i + j] == p[j]:
                    if j == len(p) - 1:
                        indexes.append(i)
                    continue
                break

        return indexes


class KmpMatching():

    def getNext(self, text):
        if text is None:
            return None

        lengths = np.zeros(len(text), dtype=int)
        for i in range(len(text)):
            sub = text[0: i+1]
            maxlen = 0
            for j in range(len(sub)-1):
                subChild = sub[0: j+1]
                if sub.endswith(subChild) and len(subChild)>maxlen:
                    maxlen = len(subChild)

            lengths[i] = maxlen

        return lengths

    def getIndexOfPinT(self, t, p):
        if t is None or p is None:
            return None
        indexes = []
        next = self.getNext(p)

        indexT = 0
        indexP = 0
        while indexT < len(t):
            if t[indexT] == p[indexP]:
                indexP += 1
                indexT += 1
            elif indexP == 0:
                indexT += 1
            else:
                indexP = next[indexP - 1]

            if indexP == len(p):
                indexes.append(indexT - indexP)
                indexP = 0

        return indexes


if __name__ == "__main__":
	
	t = "fababadaaswababaca"*100000
    p = "ababaca"
    
    start_SimpleMatch = time.time()
    simple_match = SimpleMatching()
    indexes1 = simple_match.getIndexOfPinT(t, p)
    print(indexes1)
    end_SimpleMatch = time.time()
    print("The time of SimpleMatching is: ", end_SimpleMatch-start_SimpleMatch)

    start_KMPMatch = time.time()
    KMP_match = KmpMatching()
    indexes2 = KMP_match.getIndexOfPinT(t, p)
    print(indexes2)
    end_KMPMatch = time.time()
    print("The time of KMP-Matching is: ", end_KMPMatch - start_KMPMatch)


>>> The time of SimpleMatching is:  1.203505516052246
	The time of KMP-Matching is:  1.116056203842163

結果から,KMPアルゴリズムは素朴なマッチングよりも高速であることが分かった.