Быстрый алгоритм поиска подстрок в строке

Мне нужен эффективный алгоритм (или библиотека), который я могу использовать в Java для поиска подстрок в строке.

Я бы хотел:

Учитывая входную строку – INSTR :

“BCDEFGH”

И набор строк-кандидатов – CAND :

«AB», «CDE», «FG», «H», «IJ»,

Найдите любые строки CAND, которые соответствуют подстрокам в INSTR

В этом примере я бы соответствовал «CDE», «FG» и «H» (но не «AB» и «IJ»)

Может быть много тысяч строк-кандидатов (в CAND), но, что более важно, я буду выполнять этот поиск много миллионов раз, поэтому мне нужно, чтобы это было FAST.

Я хотел бы работать с массивами символов. Кроме того, меня не интересуют архитектурные решения, такие как распространение поиска – всего лишь самая эффективная функция / алгоритм для локального решения.

Кроме того, все строки в CAND и INSTR будут относительно небольшими (<50 символов) – т.е. целевая строка INSTR НЕ длинна относительно строк-кандидатов.


Обновление, о котором я должен был упомянуть, набор строк CAND является инвариантным по всем значениям INSTR.

Обновление. Мне нужно только знать, что был матч, и мне не нужно знать, что такое матч.

Заключительное обновление Я решил попробовать AhoCorsick и Rabin-Karp из-за простоты реализации. Поскольку у меня есть шаблоны переменной длины, я использовал модифицированный Rabin-Karp, который hashирует первые n символов каждого шаблона, где n – длина самого маленького шаблона, тогда N – это длина моего поискового windows подстроки. Для Ахо Корсика я использовал это

В моем тесте я искал 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-2×2.pdf

http://www-igm.univ-mlv.fr/~lecroq/string/index.html *

Прочитайте алгоритм Ахо-Корасика и алгоритм Рабина-Карпа .

Если вход не слишком велик, вы не хотите повторять поиск много раз, и у вас не так много шаблонов, может быть неплохо использовать один шаблонный алгоритм несколько раз. Статья в Википедии о алгоритмах поиска дает множество алгоритмов с временем выполнения и предварительной обработки.

Реализации:

Доклады:

Преобразуйте набор строк-кандидатов в детерминированный автомат конечного состояния, а затем пропустите входную строку в линейном времени. Преобразование одной строки в DFS хорошо описано в стандартных книгах. Вы можете преобразовать набор строк, сначала построив недетерминированный автомат и затем определив его. Это может создать экспоненциальное раздутие в худшем случае в размере автомата, но поиск впоследствии быстрый; особенно если целевая строка длинная, а кандидат короткий, что будет хорошо работать.

Для этого нужны регулярные выражения. Как отмечалось выше, автоматы конечного состояния – это то, что вам нужно, но это точно так же, как стандартный стандартный регулярный указатель.

В 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 метода должен избегать любых символов, которые имеют специальные значения в регулярном выражении.

Быстрый поиск по шаблону Rabin-Karp кажется самым быстрым.

Возможно, вы захотите изучить алгоритм Ахо-Корасика и связанные с ним алгоритмы. Я не знаю ни одной библиотеки, которая реализует это, небрежно, но это classический способ решения этой проблемы.

Также проверьте алгоритм Boyer-Moore для однострочного сопоставления строк.

Мы можем воспользоваться небольшим размером (<50 символов) строк, чтобы построить супер быстрый алгоритм для этого случая за счет памяти.

Мы можем hash всех возможных подстрок INSTR в хеше, один раз, который будет стоить O (n ^ 2). Тогда, независимо от количества строк CAND, поиск будет O (1). Стоит это для очень большого количества строк CAND.

Если INSTR большой, то мы можем построить массив суффикса, а не сортировать его, так что верхний элемент является самым длинным (= N), а нижний элемент – последним символом INSTR. Теперь для каждой строки CAND используйте только поиск сверху, если длина (CAND) <= длина (суффикс). Каждое из этих сравнений будет O (n).

Другим решением является использование массива суффиксов для INSTR .
Поскольку INSTR мал, вы можете сортировать его с помощью сортировки пузырьков.

После этого вы можете искать определенную строку CAND в O (logN),
где N = длина (suffix_array) = длина (INSTR).

Вот некоторые реализации быстрых алгоритмов поиска строк в Java.

 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 в 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 в 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 
  • Хорошо ли использовать java.lang.String.intern ()?
  • Когда следует использовать амперсанд с scanf ()
  • Извлечь цифры из строки в Java
  • Как искать строку в нескольких файлах и возвращать имена файлов в Powershell?
  • Как преобразовать целое число цвета в шестнадцатеричную строку в Android?
  • Как сравнить строки в выражении «if»?
  • Как удалить недопустимые символы из путей и имен файлов?
  • Котировочные знаки внутри строки
  • Как преобразовать строку в enum в C #?
  • Обработка строк с помощью & или + в VB.NET
  • Разделить NSString для доступа к одной конкретной части
  • Давайте будем гением компьютера.