有效的算法來搜索長度超過另一個文本中的文本的14個字符匹配的子字符串

我有一個長文本（約5 MB文件大小）和另一個文本稱爲模式（約2000字符）。有效的算法來搜索長度超過另一個文本中的文本的14個字符匹配的子字符串

任務是從長文本中的15個字符或更長的基因模式中找到匹配的部分。

例如：

長文： ACGTACGTGTCA AAAACCCCGGGGTTTTA GTACCCGTAGGCGTAT 和更長

模式： ACGGTATTGAC AAAACCCCGGGGTTTTA TGTTCCCAG

我看看提供高效（易於理解和實施）的算法。

一個獎金將是一種方法來實現這一點，只需char-array在C++中，如果可能的話。

來源

2012-05-08 Hedge

是否允許其他字符進行干預？這是常見子序列（「ABC」和「ADC」份額「AC」）與常見子詞（「ABC」和「ADC」僅共享單字符子詞「A」和「B」）之間的區別。 –

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem –

@JasonZhu情況並非如此，他希望所有常見的子序列超過15個字符，而不僅僅是最長的一個。 – Imp

Stand back，我要活代碼：

void match_substring(const char *a, const char *b, int n) // n=15 in your case 
{ 
    int alen = strlen(a); // I'll leave all the null-checking and buffer-overrun business as an exercise to the reader 
    int blen = strlen(b); 
    for (int i=0; i<alen; i++) { 
     for (int j=0; j<blen; j++) { 
      for (int k; (i+k<alen) && (j+k<blen) && a[i+k]==b[i+k]; k++); 
      if (k >= n) 
       printf("match from (%d:%d) for %d bytes\n", i, j, k); 
     } 
    } 
}

來源

2012-05-08 01:17:04

那個被稱爲Naïve字符串搜索，我去了。 Knuth-Morris-Pratt算法易於實現。 – Hedge

如果你正在使用C庫的一個很好的實現（或者像glibc這樣的平庸的實現這個函數的好實現），那麼strstr會很好。我聽說有一種新算法對DNA（小字母）特別有用，但我現在找不到該參考文獻。除此之外，2way（glibc使用的）是最佳選擇。

來源

2012-05-08 01:15:39

我不認爲它是線程安全的！ –

當然它是線程安全的。它不會修改任何內容。或者更正式地說，沒有專門記錄爲非線程安全的所有功能都是線程安全的。 –

你是否建議OP在2000字符模式的每15個字符子序列上使用'strstr（）'？ – caf

一種方法是獲得的Aho-Corasick實現的並且使用它創造的東西，會認識到在任何15個字符塊該模式，然後使用它來搜索文本。有了Aho-Corasick，構建匹配器的成本和搜索成本都是線性的，所以這應該是實用的。

來源

2012-05-08 04:12:53 mcdowella

這裏有一個算法 - 我不知道它是否有名稱。它需要一個「滾動散列」 - 一個（非密碼）散列函數，它具有給定散列的散列的屬性，計算序列B...CD的散列是高效的。

計算序列pattern[0..14]，pattern[1..15]，pattern[2..16]的滾動散列...和在pattern每個索引存儲在哈希表中。
計算滾動散列haystack[0..14]並查看它是否在散列表中。如果是，則將haystack[0..14]與pattern[pos..pos+14]進行比較，其中pos是從散列表中檢索的。
從滾動散列haystack[0..14]有效計算滾動散列haystack[1..15]並查看它是否在散列表中。重複，直到到達haystack的末尾。

注意您的15個字符的字符串僅具有2 ^30個可能的值，以便你的「哈希函數」可以是一個簡單的映射，以作爲一個15位鹼基-4號，它是處理的字符串的值快速計算，具有滾動散列屬性並且是唯一的。

來源

2012-05-08 04:34:55 caf

我不確定，但我懷疑這將在DNA的情況下發生大量的碰撞。即使你只是比較哈希值，而不是完整的比較（沒有碰撞），它仍然和我的算法一樣大。不過，它確實有更好的緩存局部性。 –

@R .:如果你確定散列表的大小來得到'O（1）'攤銷查找，這應該是'O（m + n）' - 不是你的'O（mn）'？ – caf

對於haystack（'n'）中的每個偏移量，您都需要檢查它的哈希值，而不是針對模式中的一個偏移量（'m'）。也就是說，你比較'm'不同的預計算哈希。這使得算法'O（nm）'。 –

我強烈建議去圖書館閱讀Robert Sedgwick和Kevin Wayne的「Algorithms 4th Edition」。他們有一整章專門討論子字符串搜索。此外，它可能是值得檢查的書籍網站algs4.cs.princeton.edu。

TL; DR - 如果你確定了，你可以使用字符數組在保證時間內對輸入長度進行線性搜索。書中和在線都有代碼示例。沒有比這更容易。

來源

2012-05-08 04:44:35 themaestro

-1

我認爲「後綴樹」可以更好地解決它的性能O（log n）

來源

2012-05-11 05:16:03 kaitian521

有效的算法來搜索長度超過另一個文本中的文本的14個字符匹配的子字符串

回答

相關問題