1

我需要一个“出发点”来研究用于在大量随机数据中查找随机字符串的高效搜索算法、方法和技术的选项。我只是在学习这些东西，所以有人有这方面的经验吗？以下是我要优化的一些条件：

  1. 第一个想法是在搜索索引等方面最小化文件大小 - 所以尽可能小的索引，甚至更好 - 动态搜索。
  2. 要搜索的数据是大量完全随机的数据——例如，没有可感知模式的随机二进制 0 和 1。千兆字节的东西。
  3. 提供一个同样随机的搜索字符串，比如 0111010100000101010101 在大量随机数据中找到相同字符串的最有效方法是什么？性能等方面的权衡是什么？
  4. 需要定位该搜索字符串的所有实例，因此这似乎是限制要实施的解决方案类型的重要条件。

任何提示、线索、技术、维基文章等将不胜感激！我现在正在研究这个，看起来很有趣。谢谢。

4

1 回答 1

2

一种简单的方法是在可搜索数据的所有可能的 N 字节子串上建立一个索引（N = 4 或 8 或类似的东西）。索引将从小块映射到该块出现的所有位置。

当你想查找一个值时，取前 N 个字节并使用它们来查找所有可能的位置。当然，您需要验证所有位置。

N 的高值意味着更多的索引空间使用和更快的查找，因为会发现更少的误报。

这样的索引在大小上可能是基本数据的小倍数。

第二种方法是将可搜索数据拆分为连续的、不重叠的 N 字节块（N = 64 左右）。将每个块散列到更小的大小 M（M = 4 或 8 左右）。

这节省了大量的索引空间，因为您不需要所有重叠的块。

当您查找一个值时，您可以通过查找要找到的字符串的所有连续、重叠的子字符串来定位候选匹配项。这假定要找到的字符串的大小至少为 N * 2 个字节。

于 2012-09-26T20:27:14.517 回答