문자열 매칭 알고리즘(string matching algorithm)의 종류

참고 사이트: http://www-igm.univ-mlv.fr/~lecroq/string/
참고 문서 :

문자열 색인기법-김성현.pdf

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 알고리즘