我有一个包含连接字符串的文件。
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。
最佳答案
后缀数组和后缀树很可能会诱发内存问题。 (它们总是比文本大,即使您将它们切割到一定深度也是如此,因为您需要在结构中存储所有后缀 ID)。
您可以创建一组文件来表示某些前缀的 ID。假设我们将所有长度为 2 的前缀存储在不同的文件中并保持排序。此文件将包含平均 1/26^2 的后缀 ID。所以我们有一个文件 aa.txt , ab.txt 等等。我们保持排序的文件中的条目(后缀数组)。每次你想做一个查找时,你都使用加载这个小文件,它已经被排序和检查。复杂度为 O(N)(您必须加载文件,该文件是文本的恒定可控部分),但您可以调整预因子以获得最佳性能。例如,在一个 5 Gb 的文件中,如果您使用长度为 2 的前缀,那么您将拥有一组 8 Mb 大小的文件,对于 prefixLength 3,您将大约为 320 kb 等等。
关于string - 搜索和追加连接的字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17718817/