在一個巨大的字符串中發現長重複的子字符串

我天真地想象到，我可以建立一個後綴trie，我爲每個節點保留一個訪問計數，然後計數大於1的最深節點是我正在查找的結果集對於。在一個巨大的字符串中發現長重複的子字符串

我有一個非常長的字符串（數百兆字節）。我有大約1 GB的RAM。

這就是爲什麼使用計數數據構建後綴特里結構對於我而言效率太低的太空效率。引用Wikipedia's Suffix tree：

存儲字符串的後綴樹通常需要比存儲字符串本身更多的空間。

每個邊緣和節點中的大量信息使得後綴樹非常昂貴，在良好的實現中消耗大約十到二十倍的源文本的內存大小。後綴數組將這一要求降低到四分之一，研究人員繼續尋找較小的索引結構。

這就是維基百科對樹的評論，而不是trie。

如何在如此大量的數據中以及在合理的時間內（例如，在現代臺式機上少於一個小時）找到長的重複序列？

（有些維基百科的鏈接，以避免人張貼的「答案」：Algorithms on strings，尤其是Longest repeated substring problem ;-)）

來源

2008-12-29 Will

FWIW，這裏有一個相關的問題，我寫了SpamAssassin的的實現，可能是有用的：http://taint.org/2007/03/05/ 134447a.html – 2010-05-07 11:43:46

執行此操作的有效方法是創建子字符串的索引並對它們進行排序。這是一個O（n lg n）操作。

BWT壓縮執行此步驟，因此它是一個很好理解的問題，並且存在基數和suffix（聲明O（n））排序實現等，以使其儘可能高效。它仍然需要很長時間，也許幾秒鐘的大文本。

如果你想使用的工具代碼，C++ std::stable_sort()執行多比std::sort()更好地爲自然語言（而不是C的qsort()快得多，但出於不同的原因）。

然後訪問每個項目以查看其鄰居的公共子字符串的長度是O（n）。

來源

2009-11-25 11:29:09 Will

這是文本與斷字？然後，我懷疑你想要一個關鍵字在上下文中的變體：爲每行中的n個單詞製作n行每行的副本，在每個單詞上打破每行;排序整個事物的阿爾法;尋找重複。

如果它是一個單一的長鳴號字符串，就像說生物信息學DNA序列一樣，那麼你想要在磁盤上構建類似於你的trie的東西;用下一個節點的磁盤偏移量爲每個字符創建記錄。我會看看Knuth的第3卷第5.4節「外部排序」。

來源

2008-12-29 22:08:19

-1

最簡單的方法可能只是爲plunk down the $100更多的RAM。否則，您可能需要查看磁盤支持的結構來保存後綴樹。

來源

2008-12-29 22:08:24 Eclipse

你可以看看基於磁盤的後綴樹。我通過谷歌發現了這個Suffix tree implementation library，以及一些可以幫助你自己實現的文章。

來源

2008-12-29 22:16:35 orip

Ukkonen後綴樹算法（http://en.wikipedia.org/wiki/Suffix_tree）*非常漂亮。 – 2008-12-29 22:41:50

您可以通過建立suffix array來解決您的問題嗎？否則，您可能需要使用其他答案中提到的其中一種基於磁盤的後綴樹。

來源

2008-12-29 22:20:52

你可以用分而治之來解決這個問題。我想，這應該是相同的算法複雜度，使用特里，但也許不太有效的實現明智

void LongSubstrings(string data, string prefix, IEnumerable<int> positions) 
{ 
    Dictionary<char, DiskBackedBuffer> buffers = new Dictionary<char, DiskBackedBuffer>(); 
    foreach (int position in positions) 
    { 
     char nextChar = data[position]; 
     buffers[nextChar].Add(position+1); 
    } 

    foreach (char c in buffers.Keys) 
    { 
     if (buffers[c].Count > 1) 
      LongSubstrings(data, prefix + c, buffers[c]); 
     else if (buffers[c].Count == 1) 
      Console.WriteLine("Unique sequence: {0}", prefix + c); 
    } 
} 

void LongSubstrings(string data) 
{ 
    LongSubstrings(data, "", Enumerable.Range(0, data.Length)); 
}

在此之後，你需要做的是落實DiskBackedBuffer，以致於它號碼列表類，當緩衝區達到一定的大小時，它會使用臨時文件將自己寫入磁盤，並在讀取時從磁盤讀取。

來源

2008-12-29 22:38:14 FryGuy

回答我的問題：

由於長時間的比賽也只有很短的比賽，你可以通過首先找到短的比賽，然後看如果你可以「長大」這些比賽交易多種通行證RAM。

對此的文字方法是在數據中構建一個固定長度的所有序列的trie（每個節點都有計數）。然後，您清除所有不符合條件的節點（例如最長匹配）。然後做一個隨後的數據傳遞，建立更深層次的，但不是更廣泛。重複，直到找到最長的重複序列。

一位好朋友建議使用散列法。通過對從每個字符開始的固定長度字符序列進行哈希處理，您現在遇到了查找重複哈希值的問題（並驗證重複，因爲哈希是有損的）。如果你分配一個數組的長度來保存哈希值，你可以做一些有趣的事情，例如要查看匹配是否比數據的固定長度更長，您可以比較哈希序列而不是重新生成它們。等

來源

2009-01-01 14:13:47 Will

您是否按照這些方針實施瞭解決方案？我正面臨類似的要求。 – 2013-11-20 05:15:35

只是，發生在我遲來的想法...

根據您的OS /環境。（例如64位指針& mmap（）可用。）

您可能能夠通過mmap（）在磁盤上創建一個非常大的後綴樹，然後保留該樹的緩存最頻繁訪問的子集記憶。

來源

2009-01-02 08:49:01

怎麼樣像這樣一個簡單的程序：

S = "ABAABBCCAAABBCCM" 

def findRepeat(S): 
    n = len(S) 
    #find the maxim lenth of repeated string first 
    msn = int(floor(n/2)) 
    #start with maximum length 
    for i in range(msn,1,-1): 
     substr = findFixedRepeat(S, i) 
     if substr: 
      return substr 
    print 'No repeated string' 
    return 0 

def findFixedRepeat(str, n): 
    l = len(str) 
    i = 0 
    while ((i + n -1) < l): 
     ss = S[i:i+n] 
     bb = S[i+n:] 
     try: 
      ff = bb.index(ss) 
     except: 
      ff = -1 

     if ff >= 0: 
      return ss; 
     i = i+1 
    return 0 
print findRepeat(S)

來源

2012-05-17 16:49:54

在一個巨大的字符串中發現長重複的子字符串

回答

相關問題