1. 소개
이 기사에서는 큰 텍스트에서 패턴을 검색하는 여러 알고리즘을 보여줍니다. 제공된 코드와 간단한 수학적 배경을 사용하여 각 알고리즘을 설명합니다.
제공된 알고리즘은 더 복잡한 응용 프로그램에서 전체 텍스트 검색을 수행하는 가장 좋은 방법이 아닙니다. 전체 텍스트 검색을 제대로 수행하려면 Solr 또는 ElasticSearch를 사용할 수 있습니다 .
2. 알고리즘
가장 직관적이고 해당 작업과 관련된 다른 고급 문제를 발견하는 데 도움이되는 순진한 텍스트 검색 알고리즘으로 시작합니다.
2.1. 도우미 방법
시작하기 전에 Rabin Karp 알고리즘에서 사용하는 소수를 계산하는 간단한 방법을 정의 해 보겠습니다.
public static long getBiggerPrime(int m) {
BigInteger prime = BigInteger.probablePrime(getNumberOfBits(m) + 1, new Random());
return prime.longValue();
}
private static int getNumberOfBits(int number) {
return Integer.SIZE - Integer.numberOfLeadingZeros(number);
}
2.2. 간단한 텍스트 검색
이 알고리즘의 이름은 다른 설명보다 더 잘 설명합니다. 가장 자연스러운 솔루션입니다.
public static int simpleTextSearch(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;
int i = 0;
while ((i + patternSize) <= textSize) {
int j = 0;
while (text[i + j] == pattern[j]) {
j += 1;
if (j >= patternSize)
return i;
}
i += 1;
}
return -1;
}이 알고리즘의 아이디어는 간단합니다. 텍스트를 반복하고 패턴의 첫 글자와 일치하는 항목이 있으면 패턴의 모든 글자가 텍스트와 일치하는지 확인합니다.
경우 m은 패턴에 문자의 수이고, n은 본문의 문자의 개수이며,이 알고리즘의 시간 복잡도는 O (m (㎚ + 1)) .
부분 발생이 많은 문자열 의 경우 최악의 시나리오가 발생합니다.
Text: baeldunbaeldunbaeldunbaeldun
Pattern: baeldung2.3. Rabin Karp 알고리즘
위에서 언급했듯이 단순 텍스트 검색 알고리즘은 패턴이 길고 패턴의 반복 요소가 많을 때 매우 비효율적입니다.
Rabin Karp 알고리즘 의 아이디어는 해싱을 사용하여 텍스트에서 패턴을 찾는 것입니다. 알고리즘의 시작 부분에서 나중에 알고리즘에서 사용되는 패턴의 해시를 계산해야합니다. 이 프로세스를 지문 계산이라고하며 여기 에서 자세한 설명을 찾을 수 있습니다 .
전처리 단계에서 중요한 점은 시간 복잡도가 O (m) 이고 텍스트를 통한 반복은 O (n) 을 사용하여 전체 알고리즘 O (m + n) 의 시간 복잡도를 제공한다는 것 입니다.
알고리즘 코드 :
public static int RabinKarpMethod(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;
long prime = getBiggerPrime(patternSize);
long r = 1;
for (int i = 0; i < patternSize - 1; i++) {
r *= 2;
r = r % prime;
}
long[] t = new long[textSize];
t[0] = 0;
long pfinger = 0;
for (int j = 0; j < patternSize; j++) {
t[0] = (2 * t[0] + text[j]) % prime;
pfinger = (2 * pfinger + pattern[j]) % prime;
}
int i = 0;
boolean passed = false;
int diff = textSize - patternSize;
for (i = 0; i <= diff; i++) {
if (t[i] == pfinger) {
passed = true;
for (int k = 0; k < patternSize; k++) {
if (text[i + k] != pattern[k]) {
passed = false;
break;
}
}
if (passed) {
return i;
}
}
if (i < diff) {
long value = 2 * (t[i] - r * text[i]) + text[i + patternSize];
t[i + 1] = ((value % prime) + prime) % prime;
}
}
return -1;
}최악의 시나리오에서이 알고리즘의 시간 복잡도는 O (m (n-m + 1)) 입니다. 그러나 평균적으로이 알고리즘은 O (n + m) 시간 복잡도를 갖습니다 .
또한이 알고리즘의 Monte Carlo 버전이 더 빠르지 만 잘못된 일치 (거짓 긍정)가 발생할 수 있습니다.
2.4 Knuth-Morris-Pratt 알고리즘
단순 텍스트 검색 알고리즘에서 패턴과 일치하는 텍스트 부분이 많은 경우 알고리즘이 어떻게 느려질 수 있는지 확인했습니다.
Knuth-Morris-Pratt 알고리즘 의 아이디어는 패턴 후보를 검색해야하는 정보를 제공하는 시프트 테이블 계산입니다.
KMP 알고리즘의 Java 구현 :
public static int KnuthMorrisPrattSearch(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;
int i = 0, j = 0;
int[] shift = KnuthMorrisPrattShift(pattern);
while ((i + patternSize) <= textSize) {
while (text[i + j] == pattern[j]) {
j += 1;
if (j >= patternSize)
return i;
}
if (j > 0) {
i += shift[j - 1];
j = Math.max(j - shift[j - 1], 0);
} else {
i++;
j = 0;
}
}
return -1;
}시프트 테이블을 계산하는 방법은 다음과 같습니다.
public static int[] KnuthMorrisPrattShift(char[] pattern) {
int patternSize = pattern.length;
int[] shift = new int[patternSize];
shift[0] = 1;
int i = 1, j = 0;
while ((i + j) < patternSize) {
if (pattern[i + j] == pattern[j]) {
shift[i + j] = i;
j++;
} else {
if (j == 0)
shift[i] = i + 1;
if (j > 0) {
i = i + shift[j - 1];
j = Math.max(j - shift[j - 1], 0);
} else {
i = i + 1;
j = 0;
}
}
}
return shift;
}이 알고리즘의 시간 복잡도는 O (m + n) 입니다.
2.5. 간단한 Boyer-Moore 알고리즘
Boyer와 Moore라는 두 과학자는 또 다른 아이디어를 내놓았습니다. 이동 방향을 동일하게 유지하면서 패턴을 왼쪽에서 오른쪽이 아닌 오른쪽에서 왼쪽으로 텍스트와 비교하지 않는 이유는 무엇입니까?
public static int BoyerMooreHorspoolSimpleSearch(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;
int i = 0, j = 0;
while ((i + patternSize) <= textSize) {
j = patternSize - 1;
while (text[i + j] == pattern[j]) {
j--;
if (j < 0)
return i;
}
i++;
}
return -1;
}예상대로 이것은 O (m * n) 시간에 실행됩니다. 그러나이 알고리즘은 발생과 일치 휴리스틱을 구현하여 알고리즘 속도를 크게 높였습니다. 여기에서 더 많은 정보를 찾을 수 있습니다 .
2.6. Boyer-Moore-Horspool 알고리즘
Boyer-Moore 알고리즘의 휴리스틱 구현에는 다양한 변형이 있으며 가장 간단한 변형은 Horspool 변형입니다.
이 버전의 알고리즘은 Boyer-Moore-Horspool이라고 불리며,이 변형은 음수 이동 문제를 해결했습니다 (Boyer-Moore 알고리즘 설명에서 음수 이동 문제에 대해 읽을 수 있음).
Boyer-Moore 알고리즘과 마찬가지로 최악의 시나리오 시간 복잡도는 O (m * n) 이고 평균 복잡도는 O (n)입니다. 공간 사용량은 패턴의 크기에 의존하지 않고 256 인 알파벳의 크기에만 의존합니다. 이는 영어 알파벳에서 ASCII 문자의 최대 값이기 때문입니다.
public static int BoyerMooreHorspoolSearch(char[] pattern, char[] text) {
int shift[] = new int[256];
for (int k = 0; k < 256; k++) {
shift[k] = pattern.length;
}
for (int k = 0; k < pattern.length - 1; k++){
shift[pattern[k]] = pattern.length - 1 - k;
}
int i = 0, j = 0;
while ((i + pattern.length) <= text.length) {
j = pattern.length - 1;
while (text[i + j] == pattern[j]) {
j -= 1;
if (j < 0)
return i;
}
i = i + shift[text[i + pattern.length - 1]];
}
return -1;
}4. 결론
이 기사에서는 텍스트 검색을위한 몇 가지 알고리즘을 제시했습니다. 여러 알고리즘에는 더 강력한 수학적 배경이 필요하기 때문에 각 알고리즘 아래에 주요 아이디어를 표현하고 간단한 방식으로 제공하려고했습니다.
그리고 항상 그렇듯이 소스 코드는 GitHub 에서 찾을 수 있습니다 .