[박혜웅] 문자열 매칭 알고리즘(string matching algorithm)의 종류

• 참고 사이트: http://www-igm.univ-mlv.fr/~lecroq/string/
• 참고 자료: 
  [추천] 색인기법-김성현.pdf

 

• 문자열

  • 유한한 길이의 기호들. 가장 간단한 텍스트 모델

  • w=xyz에 대하여 (x,y,z,w 모두 문자열)

    • x는 w의 접두어(prefix)
    • y는 w의 접미어(suffix)
    • xy는 w의 부문자열(substring) = 연속된 부분 문자열
    • xz는 w의 부분열(subsequence) = 비연속된 부분 문자열

  • 문자열 사이의 유사성

    • 해밍거리(hamming distance)

      • 같은 문자길이의 두 문자열사이에 다른 문자의 수
      • (예) d(text, that) = 2

    • 편집거리(edit distance)

      • 한 문자열을 다른 문자열로 변환하기 위해 필요한 작업(입력/삭제/치환)의 최소 수
      • (예) d(text, tax) = 2  (설명) text에서 ○1e를 a로 치환 ○2t를 삭제
        

• 유한 오토마타

• 문자열 탐색에 사용

   

• string matching algorithm(문자열 검색 알고리즘)의 특징

  • 문자열검색: 텍스트내의 하나의 유형(검색어, 패턴)에 대한 실직적인 모든예를 검색

  • 색인되지 않은 텍스트에서의 검색

    • 예: 검색기의 출력과정에서 필터링(하이라이팅)

  • 윈도우: 텍스트를 패턴의 길이단위로 나눈 것

    • 예: 텍스트 abcde, 패턴 ab 일 때, 윈도우는  ab, bc, cd, de

  • 문자열 검색의 성능

    • 최악의 경우 복잡도 O(n)이 목표

    • 알파벳수=C, 텍스트의 길이=n, 검색어(패턴)의 길이=m (n>m)

      • 텍스트에서 검사해야할 회수: n-m+1

      • 텍스트에서 검색어와 일치한 것을 찾을 확률: 1/C^m

        • 두문자가 문자가 같을 확률: 1/C
      • 텍스트에서 검색어와 일치할 최대 회수: (n-m+1)/C^m

 

 

• 문자열 검색 알고리즘의 종류

  • Brute Force(Naive) 알고리즘
  • Knuth-Morris-Pratt 알고리즘

  • Boyer-Moore 알고리즘

    • Boyer-Moore-Horspool 알고리즘
  • Shift-Or 알고리즘
  • Karp-Rabin 알고리즘

 

 

• 문자열 검색 알고리즘 성능 비교