在大数据集中查找最长公共子串

Question

在大数据集中查找最长公共子串

algorithmstringlarge-filessuffix-tree

10

在过去的几天里，我进行了大量研究，读了很多东西，现在比以前更加困惑了。如何在一个大数据集中找到最长的公共子字符串？这个算法需要连续运行，以从该数据集中删除重复内容（长度各不相同）。所谓大数据集是指大约100MB的文本。

后缀树？后缀数组？Rabin-Karp算法？哪种方法最好？是否有可以帮助我的库？

真心希望得到一个好的回答，我的头已经很疼了。谢谢！ :-)

- diffuse

为什么需要持续运行？数据是否在变化？ - jonderry

为什么不使用现成的压缩软件？ - Jason Orendorff

jonderry：我可能表达不清楚，我的意思是在每次遍历之后，它都需要找到下一个最长的子字符串，依此类推。 - diffuse

Jason：哪些压缩算法可以实现这一点？ - diffuse

重复的问题：https://dev59.com/c3I-5IYBdhLWcg3wTWn4? - Patrick

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sdadffdfd · Accepted Answer

我一直在使用后缀数组。因为我一直被告知这是最快的方法。

如果您的机器上的算法正在耗尽内存，您可以将数组保存在硬盘上的文件中。这会显著减慢算法的速度，但至少可以提供结果。

我认为一个好的编写和清晰的算法不会比库做得更好。

LE: 另外，您不需要删除任何数据即可找到最长公共子串。

从最长公共子串问题：

function LCSubstr(S[1..m], T[1..n])
    L := array(1..m, 1..n)
    z := 0
    ret := {}
    for i := 1..m
        for j := 1..n
            if S[i] = T[j]
                if i = 1 or j = 1
                    L[i,j] := 1
                else
                    L[i,j] := L[i-1,j-1] + 1
                if L[i,j] > z
                    z := L[i,j]
                    ret := {}
                if L[i,j] = z
                    ret := ret ∪ {S[i-z+1..i]}
    return ret

你不需要排序任何东西，只需解析一次你的100MB数据，并构建一个n*m的字符数组来存储计算结果。同时，查看this page。

注：Rabin-Karp是一种模式匹配算法，在这里用不到。