[문자열 탐색] Naive 알고리즘과 Hashing 기법

문자열 처리 알고리즘

 웹 문서, XML, 빅데이터 등 문자열 데이터는 실제로 많이 처리되는 내용

 단어별로 정리하여 처리한다 하더라도, 글자 단위로 처리하는 경우가 많이 발생한다.

 

문자열 찾기 예제

 

 

용어 정의

 

 

Naive 알고리즘

• 가장 기본적인 알고리즘으로 두개의 문자열을 처음부터 한 글자씩 비교하는 방법입니다.
• T[1, n], P[1, m]이 주어졌다면, T의 길이 m인 모든 부분문자열 T[1, m], T[2, m+1], ... , T[n-m+1, n]과 P를 비교
• 최악의 경우 시간복잡도: O(nm)

Naive 알고리즘 비교과정

 

 

 

 

Hashing 기법

• P와 길이 m인 모든 부분문자열 T[1, m], T[2, m+1], ... , T[n-m+1, n]을 직접 비교하는 대신, 두 문자열의 hash값을 구하여 이 둘을 비교
  • 만약 hash값이 다르면? 두 문자열은 100% 서로 다르다.
  • 만약 hash값이 같다면? 두 문자열은 같을 수도 있다.
• 즉, 사용하는 hash 함수 f는 x != y라면 높은 확률로 f(x) != f(y)여야 함
• 문제점: f[T[i, i+m-1]을 계산하기 위해서 m글자를 읽어야 한다.
  • O(m)시간이 걸린다면 Naive 알고리즘과 차이가 없다!

 

 

Rabin-Karp fingerprinting

- Hashing 기법에서 O(m)시간이 걸리는 문제를 해결할 수 있는 방법

 

Rabin-Karp

 

• 여기서 고려할 사항
  • 두 문자열 x != y라면 반드시 f(x) != f(y)가 성럽되어야 한다.
  • 이 경우 f 값이 매우 커지게 되는데 커다란 소수로 나눈 나머지를 hash값으로 취한다면 overflow 문제를 해결할 수 있다. 하지만 hash값이 같아지는 충돌을 염두해야 한다.
• 시간 복잡도
  • T의 모든 hash값을 구하는데 O(n) 시간, P의 hash값을 구하는데 O(m)시간
  • hash값의 비교가 n-m+1번이므로 O(n+m) 시간

 

 

추가) Naive 알고리즘을 개선한다면?

• P를 T의 어떤 위치에 맞추어 비교할 때
  • 실패하면 오른쪽으로 한 칸 이동
  • 이동한 다음, 처음부터 다시 비교를 수행
• 따라서, 속도를 높이기 위해서는
  • 이동할 수 있는 한 최대한 이동힌다.
  • 단, P가 T에서 나올 수 있는 경우를 놓치지 않는다.
  • 일단 이동한 다음에는 비교할 필요가 없는 부분을 피한다.