문자열 매칭 또는 패턴 매칭은 컴퓨터 과학에서 중요한 문제이다. 노트패드나 워드파일 또는 웹 브라우저 데이터베이스에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다. Show 문자열 매칭 방법의 종류는 아래와 같다. 1. Naive Matching (원시적인 매칭) - $O(mn)$ 2. Automata Algorithm (오토마타를 이용한 매칭) - $\Theta(n + |\sum| m)$ 3. Rabin-Karp Algorithm (라빈-카프 알고리즘) - $\Theta(n)$ 4. Knuth-Morris-Pratt(KMP) Algorithm (KMP알고리즘) - $\Theta(n)$ 5. Boyer-Moore Algorithm (보이어-무어 알고리즘) - $\Theta(n)$ Worst Case: $\Theta(nm)$ 하나씩 알아보자. Naive Matching (원시적인 매칭)txt[0...n-1] text와 pat[0...m-1] pattern이 주어질 때 txt를 하나씩 접근하여 pat와 일치하는지 확인하는 것이다. https://www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/Best Case는 pat의 첫 번째 문자가 txt에 없는 경우이다. 이때 시간 복잡도는 $O(n)$이다. Worst Case는 txt가 'AAAAAAAAAAAAAAAAAAAAAAA' pat이 'AAAAA'일 때 처럼 txt의 모든 문자가 pat가 같을 때 이다. pat이 'AAAAB'처럼 pat의 마지막 글자가 달라도 최악의 경우이다. 아래는 파이썬으로 구현한 Navie Matching 알고리즘이다.
Finite Automata Based Algorithm (오토마타를 이용한 매칭)패턴을 전처리하고 Finite Automata를 나타내는 2차원 배열을 만든다. FA를 구성하는게 까다로운데 일단 FA를 만들고 나면 검색은 간단하게 된다. 검색할 때 txt의 첫 문자와 오토마타의 첫 번째 상태에서 시작한다. 모든 단계에서 텍스트의 다음 글자를 고려해서 만들어진 FA에서 다음 상태를 찾고 새로운 상태로 움직이면 된다. FA의 State의 개수는 M(패턴의 길이) +1이다. FA를 구성할 때 고려해야 할 주요한 부분은 가능한 모든 문자에 대해 현재 state에서 다음 state를 얻는 것이다.
Rabin-Karp Algorithm (라빈-카프 알고리즘)Naive 매칭 방법과 같이 라빈카프 알고리즘도 하나씩 문자를 이동하면서 모든 문자에 대해 패턴과 일치하는지 확인한다. 그러나 Naive 매칭과 다른 점은 패턴의 해시값을 쓴다는 것이다. Rabin-Karp가 제안한 해시 함수는 정수값을 계산한다. 그러나 가능한문자의 수는 10개 보다많고패턴길이는클 수 있다. 심하면 컴퓨터 레지스터의 용량이 초과될 수 있거나 오버플로우가 발생할 수 있다. 이에 대한 해결책은 modulo를 사용하는 것이다.
Knuth-Morris-Pratt(KMP) Algorithm (KMP알고리즘)오토마타를 이용한 매칭과 동기가 유사하지만 준비 작업이 더 단순하다. 패턴의 각 위치에 대해 매칭에 실패했을 때 돌아갈 곳을 준비해 둔다.
Boyer-Moore Algorithm (보이어-무어 알고리즘)보이어 무어 알고리즘도 패턴을 전처리한다. 그러나 이전의 매칭 알고리즘과는 다르게 텍스트 무자를 다 보지 않아도 된다. Bad Character Heuristic최악의 경우 시간이 O(mn) 걸릴 수 있다. 텍스트와패턴의 모든문자가 동일할 때 최악의경우가발생한다. 예를 들어 txt [] = "AAAAAAAAAAAAAAAAA" 및 pat [] = "AAAAA"와 같은 경우이다. 참고자료: http://nlp.jbnu.ac.kr/AL/ch20.pdf https://www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/ |