类似的子字符串快速搜索

Question

我需要找到一个子串字符串模拟一个巨大的字符串。源巨大的字符串可能长达100 Mb。模式很短（10-100个字符）。问题是我需要找到不仅仅是确切的子字符串，而且还需要找出与几个字符中的模式不同的类似子字符串（允许的最大错误数作为参数）。

有什么想法如何加快算法？

Answer 1

1）有很多与字符串搜索有关的算法。其中之一是着名的Knuth–Morris–Pratt Algorithm。

2）您可能还想检查正则表达式（“正则表达式”），无论您使用何种语言。他们一定会帮助您找到与原始字符串“类似”的子字符串。

即【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

听起来像你想Fuzzy/Approximate String Matching。看看维基百科页面，看看你是否找不到适合你需求的算法。

Answer 3

你可以看看Levenshtein distance，在Needleman–Wunsch algorithm和Damerau–Levenshtein distance

他们给你评估指标（即另外的号码，删除，替换等）两个字符串之间的差异量。它们通常用于测量DNA之间的差异。

您可以轻松找到各种语言的实现。