문자열을 덜 찾으며 다 찾기 : KMP, 보이어 무어

최초 작성 4월 15일 23시

최근 수정 4월 16일 수요일 17시, 오후 11시 40분

 

https://trash-in-trashcan.tistory.com/76

문자열 매칭(KMP, 보이어 무어 ), 파이썬 구현

이 글에서 설명하는 내용을 바탕으로 한번 예시를 수행해보자.

keyword : RETREETRETRRT
내가 찾고자 하는것 : RETRR

전체 문자열에서 특정한 문자열을 찾고자 할 때 시도한다.
이것을 시도하려면 접미사와 접두사의 매칭 관계를 사전에 알아야한다.

그래서 꽤 큰 크기의 문자열 시도는 메모리 소모가 좀 더 있을 수 있지만, 그걸 보통은 감안 할 수 있을 것이다.

i	word	pi[i]
0	R	0
1	RE	0
2	RET	0
3	RETR	1
4	RETRR	1

접미사와 접두사 비교가 일어나서 pi[i]는 그대로 유지된다.

pi는 뭘 말합니까?

KMP는 문자열 일치 여부를 확인하는데 완전 대조인 Brute Force보다 나은 방법을 제공한다. 근데 이게 큰 틀에 있어서 한 글자 씩 비교하는건 다르지 않다. 하지만 중요한것은 틀렸을 때 새로운 위치에서 다시 탐색하는데 있어, 있을만한 경우를 더 선택해서 탐색하는 것이다.

그래서 우선은 text가 주어지고 pattern 이라고 부르지만 나는 target이라고 하겠다.

1.  text 와 target을 비교하며 일치하는 횟수를 i라고 하자. 이 i가 증가하면 당연히 순차적으로 일치하고 있는 것이고, 멈춘다면 불일치가 일어난 것이다. 만약 i가 target 글자 수 만큼 도달하지 못하고 멈출 때를 보자.
2. 비교 결과가 틀린 상황이 일어난 경우 i 값을 우선 본다. 첫 글자만 일치했거나 한 글자도 일치 하지 못한경우 한 글자만 이동하지만 그 보다 일치한 글자가 많으면 그 만큼 이동한다. 동시에 pi[i] 내용을 확인한다.
   • 이 경우를 좀 주의깊게 예외로 두면 좋은 것이, 오른쪽으로 더 넘길 글자 수는 얼마나 일차하냐에 따라 영향을 받는다. 하지만, 일치 글자 0일때는 뒤에 무슨 일이 있는지 모르니 당연히 한 글자 단위로 넘겨야 하고, 일치 글자 1일때는 또 한 글자만 일치해서는 뭔가 알 수 있는게 없으니 한 글자만 넘기게 된다. 일치 수가 2 이상은 되어야 그 수치만큼 우측으로 넘길 수 있다는 점을 알아두자.
3. i 만큼 우측으로 target을 밀어서 확인해야하지만, pi[i]는 다시 왼쪽으로 당기는 정도를 정한다. 왜냐하면, pi[i]는 이정도만큼 사전에 일치한다! 라는 것을 수치로 정리한 배열이기 때문이다. 그래서 좀 더 명확하게 정리하면,  i - pi[i] 만큼 이동되어서 다시 문자열 비교가 진행된다. 뭘 시도하든  i - pi[i]는 자연수이다. 
   • pi[] 배열은 접두사와 접미사에 대한 비교 결과를 저장하는데 의의가 있다. 어쨌든 동일해야 한다는 것은 비교 선상에 전체 대상에서 일부만 똑 떼어서 보자는 것이니, 그것은 접두사 접미사라는 이름에서 볼 수 있듯 전체 문자열 길이의 2분의 1이 최대 비교 할 수 있는 길이가 된다. 이 말을 조금 더 3번의 식과 연결 시키면, i는 전체 문자열에서 i 만큼 진행되었는데, pi[i]가 i/2보다 많다면, 맥락상 그게 접두사와 접미사를 비교한게 아니게 된다. 그래서, 다소 흐름이 어색 할 수 있지만 i - pi[i]는 자연수이다.

접두사와 접미사의 매칭 관계를 나타내야하는 pi 배열을 구성하는 것부터 시작해야한다. 그리고 실질적인 비교가 이루어진다.

#s가 아니라 p의 getpi를 합니다.
def getPi(p):
    m=len(p)
    j=0

    pi=[0 for _ in range(m) ]

    for i in range(1, m): #i는 1부터
        while j > 0 and p[i]!=p[j]:
            j=pi[j-1]
        if p[i]==p[j]: #prefix(p[i])와 surffix(p[j])가 동일하다면
            j+=1
            pi[i]=j 

    return pi

def kmp(s, p):
    ans=[]
    pi= getPi(p)

    n=len(s)
    m=len(p)
    j=0 #P의 포인터

    for i in range(n): #i는 s의 포인터. 0부터 
        while j>0 and s[i]!=p[j]:
            j=pi[j-1]
        if(s[i]==p[j]):
            if(j==m-1): #패턴을 찾았음
                ans.append(i-m+1)
                j=pi[j] 
            else:
                j+=1
    
    return ans


if __name__=='__main__':
    s=input()
    p=input()

    matched=kmp(s,p)
    print(len(matched))
    
    for item in matched:
        print(item+1)

 

보이어 무어 알고리즘 

이론도 실제 효율면에서도 KMP보다 뛰어난 경우이다.

찾고자 하는 타겟 문자열의 끝 문자에서 시작해 앞을 향해 검사를 수행하게 된다.
이 과정에서 일치하지 않는 문자를 발견하면, 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정한다.

전체 word가 ABCXDEZCA 이고, 찾고자 하는 타겟은 ABAC 라고 하자.

비교는 끝부터 시작한다면서 왜 텍스트[0]에 맞추냐?
처음부터 결과가 나올 수 있으니까 당연히 그렇지.. 물론, 배치 자체는 타겟의 끝부터 이루어져야하기 때문에 문자열 길이를 고려해야한다.
핀트는 텍스트[0]과 패턴[0]을 맞춘다.

FULL MISMATCH 케이스만 보고 있기 때문에 3번의 전체 비교 후 끝나는 코드가 나와버렸다.

여기서 알 수 있는 것은 일치하는게 없는경우 아예 문자열의 길이만큼 넘어가야 한다는 것.

그럼 넘어가야 할, 즉 점프 해야 할 길이가 결정되는 과정은?

Bad Character Rule

• 비교 중 틀린 문자가 발생하면, 그 문자가 패턴 안에 마지막으로 등장한 위치를 기준으로 패턴을 이동시켜야 한다.
• 텍스트가 ABCD, 패턴이 AXCD 라고 하면 역순 비교로 D.. C.. 맞겠지만 B != X 이다.
  • 패턴에 B가 있지 않은 상태이다. 이 경우, 패턴을 B 다음 문자로 한 칸 넘겨버리도록 하자.
  • 만약!!! 패턴 안에 B가 있다면, 해당 위치까지 패턴을 점프한 다음 다시 비교한다.
• 요약하면, 비교에서 틀린 문자가 패턴에 있다면, 그 위치까지 맞추고, 없으면 패턴을 건너뛰게 해준다.

Good Suffix Rule

• 이미 일치한 문자열(접미사)에 대한 활용처를 마련하고자 구성된 것이다.
  • 왜 하필 접미사이냐하면, 그야 처음 비교를 끝에서 하기 때문이다. 값어치 있는 정보를 재활용하고자 하는 것이 주 핀트 인 것이다.
• 실제 비교에서 일부라도 일치 하는 경우, 맞았던 접미사를 패턴 내에서 다시 쓸 수 있는 위치를 찾아 점프한다.
• 텍스트가 ABAAABCABB 가 있다고 하고, Pattern이 AABCAB가 주어진다.
• ABAAABCABB
• AABCAB
• 둘은 처음 두 글자가 일치한다. 하지만 더 진행 할 수가 없다.
  • 하지만 우리는 AAB라는 내용을 Pattern에 가지고 있다는 것을 안다. 이 부분을 매칭 시켜서 다시 시도한다. 
  • ABAAABCABB
  • 000AABCAB // (000)은 공백 채우기이니 신경쓰지 말것
• 이게 대표적인 예제이고, 일부만 해당하는경우, 아예 해당이 없는 경우(보통 이러면 Bad Char Rule) 도 있다.

두 경우 모두 탐색 효율을 높이기 위한 전략이며, 보이어 무이는 두 규칙을 동시에 고려하고 더 먼 거리를 움직인다.