Алгоритми за търсене на низове за големи текстове с Java

1. Въведение

В тази статия ще покажем няколко алгоритма за търсене на шаблон в голям текст. Ще опишем всеки алгоритъм с предоставен код и проста математическа основа.

Забележете, че предоставените алгоритми не са най-добрият начин за пълнотекстово търсене в по-сложни приложения. За да правим пълнотекстово търсене правилно, можем да използваме Solr или ElasticSearch.

2. Алгоритми

Ще започнем с наивен алгоритъм за търсене на текст, който е най-интуитивният и помага да се открият други напреднали проблеми, свързани с тази задача.

2.1. Помощни методи

Преди да започнем, нека дефинираме прости методи за изчисляване на прости числа, които използваме в алгоритъма на Рабин Карп:

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) = patternSize) return i; } i += 1; } return -1; }

Идеята на този алгоритъм е ясна: прегледайте текста и ако има съвпадение за първата буква на шаблона, проверете дали всички букви на шаблона съвпадат с текста.

Ако m е брой на буквите в шаблона и n е броят на буквите в текста, сложността във времето на тези алгоритми е O (m (nm + 1)) .

Най-лошият сценарий възниква в случай на низ, който има много частични повторения:

Text: baeldunbaeldunbaeldunbaeldun Pattern: baeldung

2.3. Алгоритъм на Рабин Карп

Както бе споменато по-горе, алгоритъмът за обикновено търсене на текст е много неефективен, когато шаблоните са дълги и когато има много повтарящи се елементи на шаблона.

Идеята на алгоритъма на Рабин Карп е да използва хеширане, за да намери шаблон в текст. В началото на алгоритъма трябва да изчислим хеш на шаблона, който по-късно се използва в алгоритъма. Този процес се нарича изчисляване на пръстови отпечатъци и тук можем да намерим подробно обяснение.

Важното при стъпката на предварителна обработка е, че нейната сложност във времето е 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) .

Освен това има версия на Монте Карло на този алгоритъм, която е по-бърза, но може да доведе до грешни съвпадения (фалшиви положителни резултати).

2.4 Алгоритъм на Кнут-Морис-Прат

В алгоритъма за просто търсене на текст видяхме как алгоритъмът може да бъде бавен, ако има много части от текста, които съответстват на шаблона.

Идеята на алгоритъма на Knuth-Morris-Pratt е изчисляването на таблицата за смяна, която ни предоставя информация къде трябва да търсим нашите кандидати за модели.

Java реализация на KMP алгоритъм:

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) = 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) 
    
      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. Прост алгоритъм на Бойер-Мур

Двама учени, Бойер и Мур, излязоха с друга идея. Защо не сравните шаблона с текста отдясно наляво вместо отляво надясно, като същевременно оставите посоката на смяна еднаква:

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. Алгоритъм на Бойер-Мур-Хорспул

Има много варианти на евристична реализация на алгоритъма на Бойер-Мур, а най-простият е вариацията на Horspool.

Тази версия на алгоритъма се нарича Boyer-Moore-Horspool и тази вариация решава проблема с отрицателните отмествания (можем да прочетем за проблема с отрицателното изместване в описанието на алгоритъма на 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.