[알고리즘] KMP 알고리즘 (문자열 검색 #2)

이번 시간에는 KMP 알고리즘에 대해서 설명하려고 한다.

KMP 알고리즘 .. 이 역시 이전

카프라빈 알고리즘에 이어서 문자열을 검색하는데 있어 빠르게 검색하기 위한 문자열 검색 알고리즘 중 하나이다.
(http://carstart.tistory.com/97)

카프라빈과의 차이점은
 
카프라빈은 매번 한칸식 이동하면서 문자열과 패턴의 비교를 줄여서 속도를 빠르게 하는 작업이라면

KMP와 나중에 나올 보이무어는 문자열의 비교를 하는 작업 보다는

비교할 필요가 없는 부분을 찾아 한칸이 아니라 비교할 필요없는 부분은 빼고 여러 칸씩 이동함에 있어 속도를 빠르게 한다.

자 그럼 KMP 알고리즘에 대해 알아보자.,,



먼저 왜 이름을 KMP 알고리즘이라 지었나요 ?

Knuth Morris Partt 이름을 따서 만들어진 알고리즘이라 한다.

앞자만 따서 KMP 알고리즘이라 한다.



KMP알고리즘은 어떤 원리인가요 ?

KMP알고리즘은 다음에 차차 설명하겠지만 간단히 설명하자면 다음과 같다.

비교 할 필요가 없으면 패스 하고 비교 할 필요가 있으면 비교를 수행한다.

비교할 필요가 없는 부분은 비교하지 않고 지나가니 속도가 빠르다 이거인가..

어랏 !



그럼 비교를 할 필요가 없는지 비교할 필요가 있는지는 어떻게 구분하나요 ?

비교 가 필요없는 부분을 구분하기 위해서는 먼저 접두부 접미부 경계에 대해서 알아야 한다.

문자열은 접두부와 접미부 경계를 지니거나 지니지 않는 경우가 있는데



자 접두부와 접미부가 먼지 알아보자 !

접두부 (Prefix) 라
접미부 (Suffix) 라 하는데

말 그대로 접두부 문자열의 머리부분이라 한다.
    그리고 접미부는 문자열의 꼬리부분이라 한다.

아래 그림을 보자

그림은 접두부 접미부 그리고 경계를 설명하기위해 BAABABAA 라는 문자를 가지고 설명하는 그림이다.

그림에서 파랑색 접두부이다.
말그대로 문자열의 머리부분을 뜻하는데
파랑색 부분은 모두 접두부가 될 수 있다.

그림의 빨간색 부분은 접미부이다.
말그대로 문자열의 꼬리부분을 뜻하는데
빨간색 부분은 모두 접미부가 될 수 있다.

(BAABABAA 문자열의 전체는 접두부 접미부 모두가 될수 있기 때문에 둘다 아니다.)

여기서 접미부를 헤갈리는 경우가 있다. 혼동 하지 말자.
(시작이 뒤에서부터 시작해서 뒤에부터 읽는 경우가 있지만 읽을 때는 앞에서 부터 읽는다. )

접미부 3번째를 구해보면 AAB가 아니라 BAA이다.


그럼 경계는 무엇일가?

자 여기서 3번째 접두부와 접미부를 각각 보자
어랏 접두부와 접미부가 같네

그렇다.
우리가 원하는 것은 접두부와 접미부가 같은것이다.

그림을 보면

BAA     BA     BAA 
접두부와 접미부가 같은 BAA이다.

여기서 가운데 BA를 볼수가 있다. 
이 BA를 접두부와 접미부의 경계라 한다.

자 그럼 우리는 접두부 접미부 경계가 무엇인지 알았다.



그럼 KMP알고리즘의 원리 (비교할 필요가 없는 부분) 에 대해 알아보자 !

원리는 다음과 같다.

1. 비교할 패턴을 문자열의 첫번째에 위치시킨다.

2. 먼저 비교할 패턴을 문자열의 비교할 대상의 위치시키고 비교를 한다.

3. 패턴의 왼쪽에서 오른쪽으로 비교를 하면서 일치하지 않는 부분을 찾는다.
     (일치하면 문자열을 찾는데 성공 종료)
     (일치하지 않으면 4번으로 진행)

4. 일치하지 않는 부분의 왼쪽 부분을 가지고(패턴안의 패턴) 경계를 찾는다.
     (경계를 찾으면 5로 이동)
     (경계를 찾지 못하면 문자열의 패턴의 틀린 부분만큼 이동)

5. 경계를 찾으면 접미부와 접두부가 나올 것이다. 경계가 1개 면 상관이 없지만 2개이상도 나올 수 도 있다.
   여기서 선택하는 경계는 경계가 최대가 되었을 경우를 설정해주는 것이다.
   그리고 최대경계일 경우의 접두부와 접미부가 있다면 그 접두부의 길이의접두부시작 위치에서 접미부 위치로 이동을 시켜준다.

6. 이동을 하면 2번으로 다시 이동하여 지속적으로 수행


흐미 이렇게 설명하면 너무 어렵다..

그렇다. 그럼 쉽게 이해하기 위해서 예를 들어 설명해줘용~~~ ^^



말로 표현하면 어려우니 예를 들어 설명해보자 !

아래 동영상을 보면서 설명하겠다.




BAABAABAB 라는 전체 문자열이 있다고 하자

그런데 여기서 우리는 BAABAB 라는 단어를 찾을려고 한다. (예를 들어 설명하기 위해 짧게 한것이다.)

처음 문자열을 찾기 위해

1번 맨 첫위치에 위치를 시킨다.


2번 적용 각각 패턴과 문자열을 비교를 한다.

BAABAABAB
BAABAB

자 진행함에 있어 찾을려는 패턴의 마지막인 B가 본문과 틀림을 알수 있다.

3번에서 일치하지 않으면 4번으로 가라고 했다.


4번에서 접두부 접미부 경계를 찾으라 했다.

이 틀린 부분의 왼쪽 부분인 BAABA 에서 접두부, 접미부, 경계를 찾는다.

   BA     B     BA
접두부  경계  접미부

이렇게 찾았다. 어랏 5번으로 이동하라고  ?


5번에서 경계의 길이가 최대인 접두부 접미부의 길이를 설정해주어야하는데
접두부와 접미부는 1개 밖에 없으니 BA가 되는 것이다.

그럼 이동을 시켜줘야한다.

BA (접두부)의 시작인 B 에서
BA (접미부)의 시작인 B 까지

0  1 2  3 4  5
B A A B A B
패턴으로 따지면 패턴[0]  -> 패턴 [3] 만큼 즉 3만큼 이동을 시켜주는 것이다.

이동을 완료 하였다.

그리고 다시 2번으로

그리고 다시 처음부터 비교를 한다.

앗 이번엔 모두 일치하니 정답~ ...

그리고 종료

어느정도 이해가 가셨는지 모르겠따.



여기서 생각해보면 일반적인 탐색은 한칸식 이동하면서 비교를 해야하지만

KMP알고리즘에서는 이동하는데 있어 경계를 찾고 접두부에서 접미부로 만큼 이동과

경계가 없으면 문자열 패턴의 길이만큼 이동을 해주니 훨신 빠른 알고리즘임을 알 수 있다.


오오오~~ 굉장한데.... ㅋ

그런데 잠간... 여기서 알고리즘을 한다면 한가지 의문이 생겨



경계를 찾는데 있어 소요되는 비용은 ?
이것도 무시 못할 거 같은데 매번 경계를 찾다보면 한칸 이동하는 것보다 더 들수도 있을거 같은데요 어떻게 하나요?

그래서 하는게

찾으려는 패턴을 가지고 이동경로 테이블을 만들어 주는 것이다.

처음 이동작을 수행하면 그 표를 보고 이동경로만 보고 진행하기 때문에 매번 경계를 찾는 일을 제거할 수 있다.




그럼 어떻게 이동경로 테이블을 만드나요 ?

 테이블 만드는 법에 대해서 알아보자.

예를 들어 BAABABAA 패턴을 가지고 설명해 보겠다.

테이블을 만들기 위해서 기본 틀을 만들어 보자

일치 접두부 길이	0	1	2	3	4	5	6	7	8
8문자열	B	A	A	B	A	B	A	A
최대 경계 너비					1

자 여기서 설명하겠다.

일치 접두부의 길이 : 일치하는 길이라 생각하면 된다.
                             (만약 일치접두부 길이가 4 라면 BAAB 까지만 일치하고 4의 위치한 A에서 틀렷다는 말이다. )

문자열                  : 우리가 찾을려는 패턴이다.

최대 경계 너비       : 위에서 설명 했던 일치하는 부분을 찾고 그 곳에서 접두부와 접미부를 찾았을 때
                              경계가 가장 최대가 되었을 경우 접두부와 접미부의 길이 이다. 
                            
                             예를 들자면 BAAB 에서 나올 수 있는 접두부와 접미부는
                             접두부  경계   접미부
                               B        AA       B
                               BA               AB

                              가 나올 수 있다. 경계가 최대가 될수 있는게 AA 인 경우이다. 이 경우 접두부와 접미부의 길이를 
                              최대 경계 너비에 설정해주니 B 하나 이므로 1이 되겠다.

                            (말이 최대경계너비 지만 실질적으로는 최대경계일 때 접두부 접미부의 길이 표현이 더 맞을것 같다.)

이동하는 공식        : 이동 길이는  = 일치 접두부의 길이 - 최대 경계 너비 길이
                             이를 쉽게 말하자면 만약 일치 접두부 길이가 4 라면 4에 해당하는 경계 너비는 1이다.
                              그러므로 4 - 1 빼면 3만큼 이동만 해주면 되는 것이다.





그럼 본격적으로 위의 테이블을 만들어 보자 !


테이블을 만들고 최대 경계너비만 설정해주면 된다.
                

일치 접두부 길이	0	1	2	3	4	5	6	7	8
8문자열	B	A	A	B	A	B	A	A
최대 경계 너비

1. 일치 접두부의 길이가 0인 경우  (찾을려는 패턴과 문자열이 0번 째 즉 처음부터 틀렸다)
   -  이경우에는 1칸만 이동을 해줘야한다. 
   - 그런데 공식은  (이동경로 =  일치접두부 길이 - 최대 경계 너비) 이다.
   - 이에 맞춰서 1칸 이동은     =        0             -       (-1) 이 되어야   답이 1이 되기 때문에 설정을 -1로 해준다.
   

2 . 일치 접두부의 길이 (1~3) 까지 진행함에 있어 경계가 나오지 않는다. 그러므로 0으로 설정해준다.

일치 접두부 길이	0	1	2	3	4	5	6	7	8
8문자열	B	A	A	B	A	B	A	A
최대 경계 너비	-1	0	0	0

3. 일치 접두부의 길이 4
   - 이 경우 BAAB 에서 경계를 찾아야 한다.
   - 경계는 B   "AA"   B 
                BA  " "   AB 가 나와서 
   - "AA" 와 " "  2개가 나온다.
   - 최대 길이는 AA 이기 때문에 AA일때 접두부와 접미부는  B 이다. 
   - 이 B의 길이인 1을 설정해준다.

일치 접두부 길이	0	1	2	3	4	5	6	7	8
8문자열	B	A	A	B	A	B	A	A
최대 경계 너비	-1	0	0	0	1

4. 일치 접두부의 길이가 5
  - 이 경우 BAABA 에서 경계를 찾아야 한다.
   - 경계는 BA  A   AB 가 나와서 
   - "A"  1개가 나온다.
   - 최대 길이는 A 이기 때문에 A일때 접두부와 접미부는  BA 이다. 
   - 이 BA의 길이인 2를 설정해준다.

일치 접두부 길이	0	1	2	3	4	5	6	7	8
8문자열	B	A	A	B	A	B	A	A
최대 경계 너비	-1	0	0	0	1	2

5. 일치 접두부의 길이 (6 ~ 7)까지 진행함에 있어 경계가 나오지 않는다. 그러므로 0으로 설정해준다.

일치 접두부 길이	0	1	2	3	4	5	6	7	8
8문자열	B	A	A	B	A	B	A	A
최대 경계 너비	-1	0	0	0	1	2	0	0

6. 일치 접두부의 길이 8 경우 (찾을려는 패턴과 문자열이 모두 일치한다.)

   - 다 일치한다고 해서 패턴 만큼 이동하면 안된다. 

   -  BAABABAABABAA 문자열이 있다고 하자.
      BAABABAA            패턴을 찾을 때 다 일치 한다 해서

   -  BAABABAABABAA 
       --------->BAABABAA    패턴의 길이 만큼 이동하면 

   -  BAABABAABABAA 
       ----->BAABABAA    를 중간에 일치하는 경우를 놓칠 수 가 있다.

   -  그렇다 마지막 설정은 
       전체 패턴에서 최대 경계 너비를 설정해주는 것이다.

   - 여기서 경계는 BAA  BA  BAA 가 나와서
   - "BA" 1개가 나온다.
   - 최대 길이는 BA 이기 때문에 접두부와 접미부인  BAA 이다.
   - 이 BAA 의 길이인 3을 설정해준다.
     

일치 접두부 길이	0	1	2	3	4	5	6	7	8
8문자열	B	A	A	B	A	B	A	A
최대 경계 너비	-1	0	0	0	1	2	0	0	3

    

자 그럼 테이블도 완성되었다.



그럼 이 테이블을 가지고 실제로 테이블 공식되로 하면 제대로 탐색이 되는지 확인해보자 !

동영상을 보고 설명해보자




1. 먼저 찾을려는 문자열이 BAABABAA 이다. 우리는 아까 테이블을 만들었다.
    이 테이블을 가지고 공식인 이동경로 = 일치접두부길이 - 최대경계너비를 가지고 진행해보자

2. 첫위치에 설정하고 비교를 한다. 3번째 A가 틀렸네 
  이동경로  = 접두부의 길이  - 최대 경계 너비는
                         2             -           0
      2 칸이동한다.

3. 비교를 한다. 2번째 A가 틀렸네 
  이동경로  = 접두부의 길이  - 최대 경계 너비는
                         1             -           0
      1 칸이동한다.

4. 비교를 한다. 1번째 다 틀렸네 
  이동경로  = 접두부의 길이  - 최대 경계 너비는
                         0             -           (-1)
      1 칸이동한다.

5. 비교를 한다. 1번째 다 틀렸네 
  이동경로  = 접두부의 길이  - 최대 경계 너비는
                         0             -           (-1)
      1 칸이동한다.


6. 비교를 한다. 3번째 A가 틀렸네 
  이동경로  = 접두부의 길이  - 최대 경계 너비는
                         2             -           0
      2 칸이동한다.

7. 어랏 다 일치하네 그럼 정답을 호출하고
   뒤에도 답이 있을 경우도 있으니.
   이동경로  = 접두부의 길이  - 최대 경계 너비는
                         8             -           3
      5 칸이동한다.

이런식으로 하면 오우~~~ 굿~~~~~

KMP알고리즘에 대해 설명을 다 했다.

궁금한 사항은 리플을 남겨주시기 바랍니다.




도움이 되셨다면 리플을 남겨주세요 ^^

항상 리플하나가 힘이 됩니다.