查找大型数据集中最长的公共子字符串

Question

在过去的几天里,我对此进行了广泛的研究,我已经阅读了很多东西,以至于我现在更加困惑.如何在大型数据集中找到最长的公共子字符串？我们的想法是从这个数据集中删除重复的内容(长度不同,因此算法需要连续运行).通过大数据集,我的意思是大约100mb的文本.

后缀树？后缀数组？拉宾,卡普？什么是最好的方式？那里有一个可以帮助我的图书馆吗？

真的希望有一个好的回应,我的头很痛.谢谢!:-)

Answer 1

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

\n\n

如果运行算法的计算机内存不足，您始终可以将数组保存在硬盘驱动器上的文件中。它会大大减慢算法的速度，但至少会提供结果。

\n\n

我认为图书馆不会比编写良好且干净的算法做得更好。

\n\n

LE：顺便说一句，你不需要删除任何数据来找到最长的公共子串。

\n\n

来自最长公共子串问题：

\n\n

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

\n\n

你不需要对任何东西进行排序，你只需要解析一次你的 100MB 数据，并构建一个 n*m 的字符数组来存储你的计算。\n另请检查此页面

\n\n

LE：Rabin-Karp 是一种模式匹配算法，这里不需要它。

\n