ブールモルアルゴリズム


Boyer Moore


右から左へ比較
  • ほとんどの商用ソフトウェアで採用されているアルゴリズム
  • 表示
  • −ムーアアルゴリズムは、文字がパターンの右端で一致せず、その文字がパターン内に存在しない場合、移動距離がパターンの長さ、すなわち
  • に相当することを示す.
  • の最初の2つのマッチングアルゴリズムの共通点テキスト文字列の文字は、少なくとも1回遍歴される.
  • ブールモールアルゴリズムは、すべてのテキスト文字
  • を表示する必要はありません.
  • 最悪の場合の実行時間O(MN)
  • 入力とは異なるが、通常はO(n)よりも
  • 時間がかかる.
    # T : target / P : pattern
    
    
    def pre_process(P):
        from collections import defaultdict
    
        M = len(P)    
    
        # skip 배열 대신 딕셔너리
        PI = defaultdict(int)
    
        # 실 사용은 M - value로 할 예정.
        for i in range(M-1):
            PI[P[i]] = 1 + i
        return PI
    
    
    def boyer_moore(T, P, PI):
    
        N = len(T)
        M = len(P)
    
        i = 0
        # 실패할 경우 -1 return
        pos = -1
    
        while i <= N - M:
            # skip 잘 되고있나 확인
            print(i)
    
            # 
            # M번째 인덱스
            j = M - 1
            k = i + M - 1
    
            # 비교할 j가 남아있고, text와 pattern이 같으면 1씩 줄여 왼쪽 비교
            while j >= 0 and P[j] == T[k]:
                j -= 1
                k -= 1
            # 비교 성공
            if j == -1:
                pos = i
                break
            # i를 M - value만큼 스킵
            i = i + M - PI[T[i + M - 1]]
    
        return pos
    
    
    
    
    # Target 문자
    T = "a pattern matching algorithm"
    
    # Pattern 문자
    P = "rithm"
    
    # skip 배열을 만들어줌
    PI = pre_process(P)
    print(PI)
    
    # target, pattern, skip배열을 인자로 넘김
    pos = boyer_moore(T, P, PI)
    print(pos)
    #BoyerMooer algorithm
    #불필요한 탐색 스킵
    def skip(pattern, char):
        for i in range(len(pattern)-2, -1, -1):
            if pattern[i] == char:
                return len(pattern)-i-1
        return len(pattern)
    #BM 본 함수
    #text안에 pattern과 일치하는 문자열 있으면 1반환 바로 종료
    #끝까지 탐색했는데 pattern과 일치하는 문자열이 없으면 0반환
    def boyer(pattern, text):
        cnt = 0
        patternlen = len(pattern)
        textlen = len(text)
        i = 0
        while i <= textlen - patternlen:
            j = patternlen - 1
            while j >= 0:
                if pattern[j] != text[i+j]:
                    move = skip(pattern, text[i + patternlen - 1])
                    break
                j = j - 1
            if j == -1:
                cnt += 1
                return 1
            else:
                i += move
        return 0