문자열 검색 알고리즘 종류
- 트라이 (trie, 접두사 트리)
- 보이어-무어 문자열 검색
- 커누스-모리스-플랫 문자열 검색 (KMP 알고리즘)
- 라빈-카프 검색
트라이 (trie, 접두사 트리)
트라이란?
트라이는 트리구조이다. 저장된 문자열 중 현재 검색한 문자열과 일치하는 문자열이 있는지 확인할 때 사용된다.
트라이의 특징
- 각 단계에서 노드는 단어를 완성하기 위해 가지를 친다. (?)
- 각 마지막 노드에는 endOfWord라는 boolean flag를 두어, 어떤 단어가 해당 경로에서 종료되는지 여부를 나타낸다.
- 중첩 객체를 사용해 구현된다. 이때 각 노드는 자신과 직접 연결된 자식들을 지니는데 이 자식들은 키 역할을 한다.
- 트라이에 새로운 문자 (신규 노드)를 삽입할 때, 해당 노드를 루트의 자식으로 생성한다. (이미 있다면 이 과정은 건너뛴다.)
복잡도
삽입, 검색, 삭제 등 모든 연산의 시간 복잡도는 O(W)이다. (W는 검색하려는 문자열의 길이. 문자열의 각 문자를 확인하기 때문이다.)
공간 복잡도는 O(N*M)이다. (N은 트라이에 삽입된 단어의 개수, M은 가장 긴 단어의 길이)
- 공통 접두어를 지닌 다수의 문자열이 있는 경우, 트라이는 효율적인 자료 구조다.
- 반면, 하나의 특정 문자열에서 하나의 특정 문자열 패턴을 검색하는 경우, 트라이는 비효율적이다. (트리와 같은 구조에 문자열 저장을 위한 추가 메모리가 필요하기 때문)
- 이 때는 [보이어-무어 알고리즘]과 [커누스-모리스-프랫 알고리즘]이 유용하다.
보이어-무어 문자열 검색
이 알고리즘은 텍스트 편집기 애플리케이션과 웹 브라우저의 '찾기' 기능에 사용된다.
어떤 문자열 내에서 패턴을 검색할 때 이 알고리즘을 사용하면, 인덱스를 건너뜀으로써 선형 시간에 검색이 가능하다.
인덱스를 건너뛴다는 말을 풀어 설명하면 다음과 같다. 인덱스의 문자열을 돌면서 각각 검색할 때, 문자열이 패턴에 있으면 그 패턴의 첫째 문자와 문자열의 문자가 동일하게끔 인덱스를 증가시켜 (필요하지 않은) 반복을 건너뛴다. 또한 문자열의 끝부분이 일치하지 않으면, 첫 부분을 비교해보지 않아도 된다는 가정 아래 패턴의 마지막 문자를 비교한다.
텍스트 양이 많은 경우 효율적으로 사용할 수 있다.
커누스-모리스-플랫 문자열 검색 (KMP 알고리즘)
이 알고리즘은 접두사와 접미사 개념을 통해 반복되는 연산을 최소화하여 매칭할 문자열을 빠르게 찾는다. (불필요한 문자간 비교를 없애기 위해 실패함수를 사용한다.)
검색하는 동안 중복되는 확인을 건너뛰는 데 최적화된 것이 특징이다.
문자열이 일치하지 않을 때 다음 패턴 비교를 어디에서 해야할 지 결정하는 데 충분한 정보를 지닌다는 관찰을 바탕으로, 문자열 내에 패턴의 등장 횟수를 검색한다. 텍스트 양이 작은 경우 효율적이다.
라빈-카프 검색
이 알고리즘은 텍스트에서 특정 패턴을 찾기 위해 해싱을 활용한다.
해시 함수를 통해 부분 문자열이 패턴과 동일한지 비교하는 과정의 속도를 높이는 것이 특징이다.
라빈-카프 알고리즘은 A 문서의 구문 및 단어가 B 문서에서 얼마나 등장하는지 알아내는 방식으로 표절을 잡아내는 데 사용될 수 있다. 또한 대규모 DNA 자료에서 특정 시퀀스를 찾는 것 같은 문자열 일치 비교 애플리케이션에서도 사용될 수 있다.
