4

我有一个包含连接字符串的文件。

find_or_add(string)任何一个：

  • 返回文件中字符串出现的偏移量（不一定是第一个）
  • 将尽可能多的字符串尾部添加到文件中，以使文件包含字符串（然后返回文件中字符串的偏移量）。

伪代码：

file.init()                // file == ""
file.find_or_add("cat")    // file == "cat", returns 0
file.find_or_add("able")   // file == "catable", returns 3
file.find_or_add("table")  // file == "catable", returns 2
file.find_or_add("tables") // file == "catables", returns 2
file.find_or_add("spigot") // file == "catablespigot", returns 7
file.find_or_add("pig")    // file == "catablespigot", returns 8

我应该查看什么算法/结构来“总结”内存中的这个文件，并允许最多 O(log N) 进行所需的操作？

假设文件大于 RAM。

语言并不重要，但我可以阅读 Pseudocode、C、Java、Python、Javascript 和 Haskell。

4

3 回答 3

1

如果您的插入很小，那么您可以构建后缀树或后缀数组（使用惰性实现）。由于插入是 < k 的，因此您只需要将树构建到该深度，并且该结构将只占用有限的内存。

编辑：如果您必须存储后缀 ID（=整数），如果文本不适合，则它不适合内存

后缀树（或更紧凑的后缀数组）然后表示文本的所有子字符串，然后您可以进行简单的查找：

子字符串在树中吗？

是 -> 返回后缀（位于树的叶子中）。

否 -> 添加它并将文本附加到您的源文件中。

我愿意更深入地研究这一点，但我必须先了解图案尺寸。

编辑：请注意，插入只需要 O(k) 时间！

EDIT2：如果模式的长度不受限制，那么您可能必须构建在空间和时间上为 O(N) 的完整树，问题是您通常有一个大于 10bytes/char 的因子。问候， irW

于 2013-07-18T12:04:12.757 回答
1

后缀数组和后缀树可能会引发内存问题。（它们总是比文本大，即使您将它们切割到一定深度，因为您需要将所有后缀 ID 存储在您的结构中）。

您可以创建一组代表某些前缀 ID 的文件。假设我们将所有长度为 2 的前缀存储在不同的文件中并保持排序。该文件将包含平均 1/26^2 的后缀 ID。所以我们有一个文件 aa.txt ， ab.txt 等等。我们保持排序的文件中的条目（后缀数组）。每次您想要进行查找时，您都使用加载这个已经排序和检查的小文件。复杂度为 O(N)（您必须加载作为文本的恒定可控部分的文件），但您可以调整前置因子以获得最佳性能。例如，在 5 Gb 文件中，如果您使用长度为 2 的前缀，那么您将拥有一组 8 Mb 大小的文件，对于 prefixLength 3，您将在 320 kb 左右，等等。

于 2013-07-19T07:01:42.650 回答
0

也许这不适用，但这种技术和算法具有 O(log N) 搜索、快速插入，并且针对大型数据集的高效 IO 进行了大量优化。我可能是错的，但感觉就像插入和搜索之间的一个很好的平衡。你怎么看？

于 2013-07-18T09:07:43.707 回答