알고리즘은 일을 진행하는 스탭, 절차 등이라고 생각하면 이해하기가 쉽다.
완전 탐색 알고리즘
1.텍스트의 맨 앞부터 패턴을 비교 조회합니다.
2.만약 문자와 패턴이 일치하지 않으면, 패턴을 오른쪽으로 1칸씩옮긴다.
3.패턴이 배열을 벗어날 때 까지 이 처리를 반복한다
시간복잡도 : 최선일 경우 O(n)
function searchString(text, pattern) {
let i = 0;
while (i <= text.length - pattern.length) { //패턴이 텍스트의 길이를 넘지 않는 동안
let p = 0; //p가 패턴의 맨 앞 위치를 가리키도록 한다
while (p < pattern.length) { //패턴의 길이를 넘지 않는 동안
if (text[i + p] != pattern[p]) { //텍스트와 패턴 문자가 일치하지 않으면
break; //반복을 종료한다
}
p = p + 1; //패턴의 비교 위치를 오른쪽으로 1칸 옮긴다
}
if (p === pattern.length) { //패턴의 모든 문자가 텍스트와 일치하면
return i; //텍스트와 일치한 시작 위치를 결과로 반환하고 종료한다
}
i = i + 1; //텍스트의 위치를 오른쪾으로 1칸 옮긴다
}
return -1; //-1을 결과로 반환하고 종료한다
}이동테이블을 활용하는 kmp 알고리즘
- 커누스 모리스 프랫 알고리즘
완전 탐색 알고리즘은 텍스트와 패턴이 일치하지 않으면, 텍스트를 기준으로 패턴의 위치를 오른쪽으로 1칸 옮긴 다음에 패턴의 첫 번째 문자부터 다시 검색합니다. 즉 완전 탐색 알고리즘은 비교하는 도중에 얻은 정보를 버린다는 뜻.
kmp 알고리즘은 패턴을 오른쪽으로 한칸씩 옮기지 않습니다. 비교하는 도중에 얻은 정보를 활용해 패턴의 문자까지 텍스트와 일치했는지 확인한 후 텍스트를 기준으로 패턴의 위치를 몇칸 옮길지 정합니다.
패턴에 포함된 각 문자와 텍스트가 일치하지 않을때 패턴을 몇 칸 옮기는 것이 최선인지 조사하고 그 결과를 테이블로 만듭니다. 이 테이블을 이동 테이블이라고 부름, 검색할때는 이동테이블을 바탕으로 패턴을 몇칸 옮겨야 할지 정합니다.
- 시간 복잡도 : On이지만 실질적으로 이동테이블을 만들기위한 전처리가 시간이 걸려 완전 탐색 알고리즘이 더 효율적일 수도 있다.
std::size_t KMP::FindString(std::string pattern, std::size_t startIndex)
{
if (false == CheckString(pattern, startIndex))
return std::string::npos;
std::string haystack = this->haystack.substr(startIndex);
std::vector<std::size_t> skipInfo(pattern.size(), 0);
std::size_t index = 0;
for (int i = 0; i < pattern.size(); ++i) // i : incorrect index when haystack and pattern are compared
{
for (int j = 0; j < i - 1; ++j) // j : index for finding the longest border in equivalent prefix of haystack and pattern
{
for (index = 0; index <= j; ++index)
if (pattern[index] != pattern[(std::size_t)i - 1 - j + index])
break;
if (index > j)
skipInfo[i] = (std::size_t)i - (j + 1);
}
if (0 == skipInfo[i])
skipInfo[i] = 2 > i ? 1 : i;
}
std::size_t i = 0; // i : beginning index of comparison
while (i <= haystack.size() - pattern.size())
{
for (index = 0; index < pattern.size(); ++index)
if (haystack[i + index] != pattern[index])
break;
if (pattern.size() == index)
return startIndex + i;
i += skipInfo[index];
}
return std::string::npos;
}보이어 무어 알고리즘
완전 탐색 알고리즘 및 kmp 알고리즘은 패턴의 첫번째 문자부터 비교. 그러나 보이어 무어 알고리즘은 패턴의 마지막 문자부터 비교. 일치하지 않을 경우에는 일지하지 않은 문자를 기준으로 패턴을 몇칸 옮길지 결정한다.
- 패턴의 마지막 문자부터 비교
- 패턴의 마지막 문자가 일치하지 않으면 전체 패턴이 일치하지 않는다는 뜻
- 패턴의 위치를 패턴의 길이 만큼 오른쪽으로 옮긴다.
하지만 무작정 패턴 길이 만큼 오른쪽으로 옮기면 중간부터 시작되는 패턴을 빠뜨릴 수 있으므로, 보이어 무어 알고리즘 이동테이블을 이용해서 패턴에 있는문자가 패턴의 마지막 문자를 기준으로 했을때 몇번째 위치에 있는지를 기록
패턴에 있는 문자가 패턴의 마지막 문자를 기준으로 몇번째 위치에 있는지기록. 그 외의 문자는 패턴속 문자의 갯수만큼 이동하도록 테이블에 기록한다.
시간복잡도 : 최악일때 O(n)
평균 : O(n/m)
ex)
function doSearch() {
var inputForm = document.forms.inputForm;
var text = inputForm.text.value;
var pattern = inputForm.pattern.value;
var i;
i = searchString(text, pattern);
if (i >= 0) {
alert(i + " 번째 문자에서 찾았습니다.");
} else {
alert("찾을 수 없습니다.");
}
}
// 함수 searchString(text, pattern)
// 입력: text 검색 대상 문자열, pattern 검색 문자열(키워드)
// 출력: 0 이상 찾은 위치, -1 찾지 못했을 때
function searchString(text, pattern) {
var i;
i = text.indexOf(pattern);
return i;
}Rabin Karp
Rabin Karp 방식은 문자의 아스키코드 값을 이용한 해시를 사용한다.
본문에서 차례대로 패턴 크기만큼 문자열의 해시값을 구하고 미리 구해놓은 패턴의 해시값을 비교해 본다. 이 알고리즘의 핵심은 문자들의 아스키코드 값을 가지고 어떻게 해시값을 만들어내느냐가 관건.