문자열 탐색 성능 개선 중 KMP알고리즘을 사용하면 기존의 브루트포스 알고리즘보다 더 좋은 성능이 나온다는 이야기를 들었다.
정확히 어떻게 성능을 더 빠르게 하는지가 궁금하여 자세한 내용을 정리해보고자 한다.
이 글은 아래 글을 참고하여 작성하였다.
https://bowbowbow.tistory.com/6
KMP : 문자열 검색 알고리즘
문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했을
bowbowbow.tistory.com
KMP 알고리즘이란?
문자열 비교 시 효율적인 인덱스 조정을 통해 이미 비교했던 문자열을 최대한 다시 비교하지 않도록 하여 성능을 개선한 문자열 탐색 알고리즘이다.
더 자세한 설명을 위해 아래 예시를 통해 알아보자
우리는 ABAABAABAABAB라는 텍스트에서 ABAABAB 패턴을 찾는 작업을 진행할 것이다.
패턴(찾을 문자) : ABAABAB
텍스트(탐색 대상) : ABAABAABAABAB
브루트 포스 알고리즘(단순 문자열 탐색)을 활용한 문자열 탐색
KMP가 얼마나 효율적으로 동작하는지 확인하기에 위해 우선 브루트 포스 방식으로 문자열 탐색 진행 과정을 확인해보자
처음 비교를 시작하면 텍스트의 0번째 인덱스부터 순서대로 비교하다 아래와 같이 6번째 인덱스에서 불일치가 발생한다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 텍스트 | A | B | A | A | B | A | A | B | A | A | B | A | B |
| 패턴 | A | B | A | A | B | A | B |
그 다음번에는 비교 시작 인덱스 +1한 텍스트의 1번째 인덱스부터 비교를 진행한다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 텍스트 | A | B | A | A | B | A | A | B | A | A | B | A | B |
| 패턴 | A | B | A | A | B | A | B |
허나 시작하자마자 불일치가 발생해 바로 비교 시작 인덱스 +1 하여 텍스트의 2번 인덱스에 대한 비교를 진행할 것이다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 텍스트 | A | B | A | A | B | A | A | B | A | A | B | A | B |
| 패턴 | A | B | A | A | B | A | B |
위와 같이 계속 비교 시작 인덱스를 1씩 증가시키면서 진행하다 6번째 검사 진행 시 텍스트의 일치하는 부분을 찾게 된다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 텍스트 | A | B | A | A | B | A | A | B | A | A | B | A | B |
| 패턴 | A | B | A | A | B | A | B |
즉 텍스트에 패턴 존재여부를 확인하기 위해 6번의 문자열 비교가 발생한 것이다.
뿐만 아니라 텍스트가 길어질 경우 비교 작업이 배로 많아지며 시간복잡도는 O(n*m) [n: 텍스트의 길이, m : 패턴의 길이]이다.
KMP 알고리즘을 활용한 문자열 탐색
KMP 알고리즘을 활용하여 문자열 탐색을 진행할 경우 두 단계로 나누어 진행한다.
1. 패턴에 대한 접두사 접미사 최대 길이 배열(Longest Prefix Suffix 이하 lps) 배열을 생성
lps배열은 패턴의 0~i까지의 부분 문자열에서 서로 일치하는 prefix, suffix 중 가장 긴 것의 길이이다.
(단 prefix와 suffix는 부분 문자열의 전체가 되면 안된다)
현재 패턴에서 i = 5일 경우를 확인해 보자, 부분 문자열은 ABAABA이고 prefix와 suffix 집합은 아래와 같다.
prefix : {A, AB, ABA, ABAA, ABAAB}
suffix : {A, BA, ABA, AABA, BAABA}
prefix와 suffix가 일치하는 값은 A, ABA이고 이 중 가장 긴 것은 ABA이다. 따라서 lps[5] = 3이 된다.
lps 배열의 전체는 아래와 같다.
| i | 부분 문자열 | lps[i] |
| 0 | A | 0 |
| 1 | AB | 0 |
| 2 | ABA | 1 |
| 3 | ABAA | 1 |
| 4 | ABAAB | 2 |
| 5 | ABAABA | 3 |
| 6 | ABAABAB | 2 |
이제 생성한 배열을 활용하여 문자열 탐색을 해보자
2. lps 배열을 활용한 문자열 탐색
우선 처음은 브루트 포스와 동일하게 텍스트의 0번째 인덱스부터 비교를 진행한다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 텍스트 | A | B | A | A | B | A | A | B | A | A | B | A | B |
| 패턴 | A | B | A | A | B | A | B |
첫 번째 매칭을 하는 과정에서 6번째에서 불일치가 발생하였다. 이를 통해 5번째 인덱스까지는 문자열이 일치한다는 점도 확인할 수 있다.
여기서 1번에서 생성해 둔 lps 배열을 참고하면 lps[5] = 3이므로 패턴의 0~5 인덱스의 부분 문자열에서 prefix와 suffix가 3개 일치한다는 것을 알 수 있다.
이를 활용하여 다음번 검사 시 패턴 시작을 텍스트의 3번째 인덱스로 조정한다.
또 인덱스 3,4,5는 이미 패턴과 일치하다는 것을 알고 있으므로 6번 인덱스부터 비교를 진행하면 된다.
허나 이번에도 패턴의 6번째 인덱스 즉 텍스트의 9번째 인덱스에서 불일치가 발생하였고, 이전과 마찬가지로 인덱스 조정을 진행할 수 있다.
그 다음 패턴 시작을 텍스트의 6번째 인덱스로 조정하였고, 이번에는 패턴과 문자열이 일치하는 부분을 찾게 되었다.
KMP 알고리즘을 활용하니 3번 만에 해당 문자열을 찾을 수 있었고, 6번 걸렸던 브루트 포스보다 비교 횟수가 무려 절반이 줄었다.
또한, 효율적인 인덱스 조정으로 인해 문자열 비교 횟수가 감소하여 시간 복잡도가 O(n + m)으로 개선된다.
자바 코드로의 구현
이제 KMP 알고리즘을 자바 코드로 어떻게 구현하는지 확인해 보자.
비교할 때와 동일하게 패턴에 대한 lps배열을 생성, lps 배열을 활용한 문자열 탐색 총 두 단계로 나뉜다.
1. 패턴에 대한 lps배열 생성
public static int[] makeLps(String pattern) {
int n = pattern.length();
int[] lps = new int[n];
int idx = 0; // 비교할 prefix의 인덱스
// 부분 문자열의 크기 증가시키며 비교 진행
for (int i = 1; i < n; i++) {
while (idx > 0 && pattern.charAt(i) != pattern.charAt(idx)) {
// 문자열이 연속 일치가 발생했을 때(idx>0), 연속적으로 더 일치하지 않으면 인덱스 조정
/*
* idx = lps[idx-1]으로 조정하는 이유
* 문자열 탐색 시 lps 배열을 참고하여 인덱스 조정을 진행하는 것과 동일하게 생각하면된다
* prefix는 패턴, 부분 문자열은 text라 생각하면 된다.
*/
idx = lps[idx - 1];
}
if (pattern.charAt(i) == pattern.charAt(idx)) {
idx++; // 문자열이 일치할 경우 연속으로 일치하는지 확인하기 위해 idx를 증가시킨다.
lps[i] = idx; // 지금까지 일치한 개수 lps 배열에 저장
}
}
return lps;
}
2. lps 배열을 활용한 문자열 탐색
public static void kmp(String text, String pattern) {
int[] lps = makeLps(pattern); // lps 배열 생성
int idx = 0; // 비교할 패턴의 현재 인덱스
// text의 인덱스를 증가시키며 비교 진행
for (int i = 0; i < text.length(); i++) {
while (idx > 0 && text.charAt(i) != pattern.charAt(idx)) {
// 패턴과 text 불일치 시 lps 배열을 활용하여 인덱스 조정
// 이전에 검사 시 패턴과 일치한 부분의 suffix를 prefix라 생각하고 인덱스 조정
idx = lps[idx - 1];
}
if (text.charAt(i) == pattern.charAt(idx)) {
// 글자가 일치할 경우
if (idx == pattern.length() - 1) {
// 패턴의 끝까지 비교한 경우
System.out.println("패턴 시작 위치: " + (i - idx + 1) + ", " + "패턴 끝 위치: " + (i + 1));
idx = lps[idx]; // 다음 비교를 위하여 인덱스 조정
} else {
// 패턴의 끝이 아닌 경우 패턴의 다음 값 확인하기 위해 idx++
idx++;
}
}
}
}'BackEnd > Java' 카테고리의 다른 글
| X바(자바) finalize 메소드 쓰지마세요 (0) | 2024.05.06 |
|---|---|
| Java HashMap의 내부 동작 - 해시 버킷 개수 조정 (0) | 2024.04.21 |
| Java HashMap의 내부 동작 - 실전편 (1) | 2024.04.16 |
| Java HashMap의 내부 동작 - 이론편 (0) | 2024.04.14 |
| DTO 그렇게 쓰는 거 아닌데 ㅋㅋ (0) | 2024.03.17 |