Подобная подстрока быстрого поиска

Question

Мне нужно найти подстроку SIMILAR для данного шаблона в огромной строке. Исходная огромная строка может иметь длину до 100 Мб. Картина довольно короткая (10-100 символов). Проблема в том, что мне нужно найти не только точные подстроки, но и похожие подстроки, которые отличаются от шаблона в нескольких символах (максимально допустимое количество ошибок указывается в качестве параметра).

Есть ли идеи, как ускорить алгоритм?

Answer 1

1) Существует множество алгоритмов, связанных с поиском строк.Одним из них является знаменитый алгоритм Кнута-Морриса-Пратта .

2) Вы также можете проверить регулярные выражения ("Regex") на любом языке, который вы используете.Они наверняка помогут вам найти подстроки, «похожие» на исходные.

то есть [Java]

String pat = "Home";
String source = "IgotanewHwme";

for(int i = 0; i < pat.length(); i++){
    //split around i .. not including char i itself .. instead, replace it with [a-zA-Z] and match using this new pattern.
    String new_pat = "("+pat.substring(0, i)+")"+ "[a-zA-Z]" + "("+pat.substring(i+1, pat.length())+")";
    System.out.println(new_pat);
    System.out.println(source.matches("[a-zA-Z]*"+new_pat+"[a-zA-Z]*"));
}

, и я думаю, что легко заставить его принимать любое количество ошибок.

Answer 2

Вы можете взглянуть на расстояние Левенштейна , алгоритм Нидлмана – Вунша и расстояние Дамерау – Левенштейна

Они даютВы метрики, оценивающие количество различий между двумя строками (то есть числа сложения, удаления, замены и т. д.).Они часто используются для измерения различий между ДНК.

Вы легко найдете реализации на разных языках.

Answer 3

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