string - 搜索和追加连接的字符串

Question

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

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。

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

Answer 1

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

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