類似的子字符串快速搜索

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之間的差異。

您可以輕鬆找到各種語言的實現。