• 문자열

    • 유한한 길이의 기호들. 가장 간단한 텍스트 모델
    • 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/Cm

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

 

 

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

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

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

 

 

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

 

 

Posted by 바게 BAGE