gpt4 book ai didi

algorithm - 子串搜索算法(很大的大海捞针,很小的针)

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:29:30 26 4
gpt4 key购买 nike

我知道这里已经有几个类似的问题,但我需要一些针对我的案例的建议(找不到任何类似的问题)。

我必须在大量数据中搜索一个子字符串,该子字符串大约要小十亿倍(100 亿字节中的 10 个字节)。干草堆不会改变,所以如果需要的话,我可以忍受大量的预计算。我只需要搜索部分尽可能快。

我发现算法需要 O(n) 时间(n = 大海捞针的大小,m = 针的大小),而朴素的搜索需要 O(n+m)。由于这种特殊情况下的 m 会非常小,是否有任何其他算法可以研究?

编辑:谢谢大家的建议!更多信息 -数据可以被认为是随机位,所以我认为任何类型的索引/排序都是不可能的。要搜索的数据可以是任何内容,不能是英文单词或任何可预测的内容。

最佳答案

您正在寻找名为 Trie 的数据结构或“前缀树”。简而言之,该数据结构对可以在您的语料库中找到的所有可能的字符串前缀进行编码。

Here is a paper它使用前缀树在 DNA 序列中搜索小子串。我想这可能对您有所帮助,因为您的情况听起来很相似。

如果您知道输入搜索字符串长度的明确限制,则可以限制您的 Trie 的增长,以便它不会存储任何超过此最大长度的前缀。这样,你或许可以将一个代表所有10G的Trie放入不到10G的内存中。特别是对于高度重复的数据,任何一种 Trie 都是一种压缩数据表示。 (或者应该,如果实现得当的话。)将 Trie 深度限制为最大输入搜索字符串允许您进一步限制内存消耗。

关于algorithm - 子串搜索算法(很大的大海捞针,很小的针),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3432400/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com