Быстрый алгоритм поиска подстрок в строке
Мне нужен эффективный алгоритм (или библиотека), который я могу использовать в Java для поиска подстрок в строке.
Что я хотел бы сделать:
Учитывая входную строку - INSTR:
"BCDEFGH"
И набор строк-кандидатов - CAND:
"AB", "CDE", "FG", "H", "IJ"
Найдите строки CAND, которые соответствуют подстрокам в INSTR
В этом примере я бы соответствовал "CDE", "FG" и "H" (но не "AB" и "IJ" )
Может быть много тысяч строк-кандидатов (в CAND), но, что более важно, я буду выполнять этот поиск много миллионов раз, поэтому мне нужно, чтобы он был FAST.
Я хотел бы работать с массивами char. Кроме того, меня не интересуют архитектурные решения, такие как распространение поиска - всего лишь самая эффективная функция/алгоритм для локального решения.
Кроме того, все строки в CAND и INSTR будут относительно небольшими (< 50 символов), то есть целевая строка INSTR НЕ длинна относительно строк-кандидатов.
Обновить. Я должен был упомянуть, набор строк CAND является инвариантным по всем значениям INSTR.
Обновить Мне нужно только знать, что было совпадение - и мне не нужно знать, что такое матч.
Окончательное обновление
Я решил попробовать AhoCorsick и Rabin-Karp из-за простоты реализации.
Поскольку у меня есть шаблоны переменной длины, я использовал модифицированный Rabin-Karp, который хэширует первые n символов каждого шаблона, где n - длина самого маленького шаблона, тогда N - это длина моего поискового окна подстроки.
Для Ахо Корсика я использовал this
В моем тесте я искал 1000 шаблонов в двух документах, посвященных газетным бумагам, усредненным по 1000 итераций и т.д....
Нормализованное время для завершения:
AhoCorsick: 1
RabinKarp: 1,8
Наивный поиск (проверьте каждый шаблон и используйте string.contains): 50
* Некоторые ресурсы, описывающие альгоны, упомянутые в ответах ниже:
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html
http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2x2.pdf
http://www-igm.univ-mlv.fr/~lecroq/string/index.html *
Ответы
Ответ 1
Прочитайте алгоритм Aho-Corasick и Rabin -Karp алгоритм.
Если вход не слишком велик, вы не хотите повторять поиск много раз, и у вас не так много шаблонов, может быть неплохо использовать один шаблонный алгоритм несколько раз. Статья Википедии об алгоритмах поиска дает множество алгоритмов с временем выполнения и предварительной обработки.
Реализации:
Презентации:
Ответ 2
Преобразуйте набор строк-кандидатов в детерминированный автомат конечного состояния, а затем пропустите входную строку в линейном времени. Преобразование одной строки в DFS хорошо описано в стандартных книгах. Вы можете преобразовать набор строк, сначала построив недетерминированный автомат и затем определив его. Это может создать экспоненциальное раздутие в худшем случае в размере автомата, но поиск впоследствии быстрый; особенно если целевая строка длинная, а кандидаты - короткие, что будет хорошо работать.
Ответ 3
Это регулярные выражения. Как отмечалось выше, автоматы с конечным состоянием - это то, что вам нужно, но это точно так же, как реализовано стандартное регулярное выражение.
В java вы можете написать что-то вроде:
StringBuilder sb = new StringBuilder();
bool first = true;
for (String subStr : substrings) {
if (first)
first = false;
else
sb.append('|');
sb.append(escape(subStr));
}
Pattern p = Pattern.compile(sb.toString());
метод escape
должен избегать любых символов, которые имеют специальные значения в регулярном выражении.
Ответ 4
Быстрый поиск по шаблону Rabin-Karp является самым быстрым.
Ответ 5
Возможно, вы захотите изучить алгоритм Aho-Corasick и связанные с ним алгоритмы. Я не знаю ни одной библиотеки, которая реализует это, небрежно, но это классический способ решения этой проблемы.
Ответ 6
Также проверьте алгоритм Boyer-Moore для однострочного сопоставления строк.
Ответ 7
Мы можем воспользоваться небольшим размером (< 50 char) строк для создания супербыстрого алгоритма для этого случая за счет стоимости памяти.
Мы можем хэшировать все возможные подстроки INSTR в хеше, который будет стоить O (n ^ 2). Тогда, независимо от количества строк CAND, поиск будет O (1). Стоит это для очень большого количества строк CAND.
Если INSTR большой, то мы можем построить массив суффикса, а не сортировать его, так что верхний элемент является самым длинным (= N), а нижний элемент - последним char INSTR. Теперь для каждой строки CAND используйте только поиск сверху, если длина (CAND) <= длина (суффикс). Каждое из этих сравнений будет O (n).
Ответ 8
Другим решением является использование массива сущностей для INSTR.
Поскольку INSTR мал, вы можете сортировать его с помощью сортировки пузырьков.
Впоследствии вы можете найти определенную строку CAND в O (logN),
где N = длина (suffix_array) = длина (INSTR).
Ответ 9
Здесь - некоторая реализация быстрых алгоритмов поиска строк в Java.
Ответ 10
import java.util.Scanner;
public class StringMatch
{
static int temp,i=0,j=0; static boolean flag=true,matcher=false;
static String str=null,mstr=null;static char astr[],amstr[];
static void getter(){
Scanner sc = new Scanner(System.in);
str = sc.nextLine();
//String str="today is Monday";
astr=str.toCharArray();
mstr = sc.nextLine();
//String mstr="is";
amstr=mstr.toCharArray();
}
static void stringMatch(){
while(i<astr.length){
if(astr[i]==amstr[j]){
while((j!=amstr.length)&&flag){temp=i;
if(astr[i]!=amstr[j]) {flag=false;matcher=false;}
else{matcher=true;}
i++;j++;
//System.out.println(i+"\t"+j);
}if(matcher==true)break;i=temp;}i++;j=0;flag=true;
}
if(matcher==true) {System.out.println("true");}
else {System.out.println("false");}
}
public static void main(String[] args) {
StringMatch.getter();
StringMatch.stringMatch();
}
}