문자열 검색 알고리즘

패턴 전처리 방식, 텍스트 전처리 방식, 완전탐색(Brute-Force), KMP(Knuth-Morris-Pratt), 보이어- 무어(Boyer-Moore), 라빈-카프(Rabin-Karp)

 

1. 효과적인 키워드 검색을 위한 문자열 검색알고리즘 개요

가. 문자열 검색 알고리즘(String Matching Algorithm)정의

-. 제시되는 정형적 문자열(Text)내에서 특정 문자열(Pattern)을 빠르고 저비용으로 검색하기 위해 사용되는 절차나

방법

나. 문자열 검색 알고리즘 접근방식

 

패턴 전처리 방식 : 

-. 임의의 텍스트에 대해 해당 패턴을 효율적으로 찾을수 있으므로,텍스트가 자주 바꾸지만 찾는 패턴의 길이가 짧은 에디터(문서 편집기, 문서뷰어, 인터넷 브라우저 등)에 주로 사용

 

텍스트 전처리 방식 : 

-. 임의의 패턴에 대해 해당 텍스트에서 효율적으로 찾을수 있으므로, 텍스트는 고정되어 있지만 다양한 패턴에 대해 검색을 수행하는 DNA 문자열과 같은 경우에 유용하게 사용

 

3. 문자열 검색 알고리즘의 성능

알고리즘 성능

완전탐색(Brute –Force) -. 최악: O(TP), 평균: O(P)

KMP(Knuth-Morris-Pratt) -. 평균 수행 속도: O(T+P)

보이어-무어(Boyer-Moore) -. 검색시 시간복잡도: O(T+P)

라빈-카프(Rabin-Karp) -. 검색과정 예정 시간 복잡도 : O(T+P)