15

我有一个问题，我正在寻找一些指导来解决最有效的方法。我有 2 亿个数据字符串，大小从 3 个字符到 70 个字符不等。字符串由字母数字和几个特殊字符（如破折号和下划线）组成。我需要能够快速搜索整个字符串或字符串中的任何子字符串（最小子字符串大小为 3）。快速在这里定义为小于 1 秒。

作为我的第一次剪辑，我做了以下事情：

  1. 创建了 38 个索引文件。索引包含以特定字母开头的所有子字符串。前 4mb 包含 100 万个哈希桶（哈希链的开始）。索引的其余部分包含来自哈希桶的链表链。我的散列分布非常均匀。100 万个哈希桶保存在 RAM 中并镜像到磁盘。

  2. 当一个字符串被添加到索引中时，它被分解成它的非重复（在其自身内）3-n 个字符的子字符串（当 n 是字符串 1 的长度时）。因此，例如，“apples”作为 pples,pple,ppl,pp 存储在“A”索引中（子字符串也存储在“L”和“P”索引中）。

搜索/添加服务器作为守护程序运行（在 C++ 中）并且像冠军一样工作。典型的搜索时间小于 1/2 秒。

问题出在流程的前端。我通常一次添加 30,000 个密钥。这部分过程需要很长时间。作为基准，加载到 180,000 个可变长度键的空索引的时间约为 3 1/2 小时。

除了很长的加载时间外，该方案有效。

在我疯狂优化（或尝试）之前，我想知道是否有更好的方法来解决这个问题。对于这么大的数据集，前后通配符搜索（即：DBMS 中的“%ppl%”之类的字符串非常慢（例如，在 MySQL 中大约为几个小时）。所以看起来 DBMS 解决方案是不可能的。我不能使用全文搜索，因为我们处理的不是普通单词，而是可能由也可能不是由真实单词组成的字符串。

4

2 回答 2

1

根据您的描述，加载数据需要花费所有时间，因为您正在处理 I/O，将膨胀的字符串镜像到硬盘。这肯定会是一个瓶颈，主要取决于你读写数据到磁盘的方式。

mmap使用一些 LRU 策略可以实现对执行时间的可能改进。我很确定复制数据的想法是使搜索速度更快，但是由于您使用 - 似乎是 - 只有一台机器，所以您的瓶颈将从内存搜索跳到 I/O要求。

另一个您可能不感兴趣的解决方案——它非常有趣和令人不安（：——，是将数据拆分到多台机器上。考虑到您构建数据的方式，实现本身可能需要一点时间的时间,但这将是非常简单的。你有：

  • 每台机器都由一组桶负责，使用接近的东西选择hash_id(bucket) % num_machines；
  • 从每台机器本地执行插入；
  • 搜索可以通过某种类型的查询 - 应用程序进行接口，或者简单地聚集成查询集 - 如果应用程序不是交互式的；
  • 考虑到您可能从一个节点发送启动请求，并将请求转发到另一个节点（也是集群请求，以避免过多的 I/O 开销），搜索甚至可能具有分布式接口。

另一个好处是，正如你所说，数据是均匀分布的——已经 \o/; 这通常是分布式实现中最挑剔的部分之一。此外，这将是高度可扩展的，因为您可以在数据大小增加时添加另一台机器。

于 2013-01-22T20:53:17.343 回答
1

与其一次性做完所有事情，不如用 38 遍解决问题。

读取 180,000 个字符串中的每一个。在每个字符串中找到“A”，并仅将内容写入“A”哈希表。完成后，将“A”哈希表的整个完成结果写入磁盘。（有足够的 RAM 将整个“A”哈希表存储在内存中——如果你不这样做，制作更小的哈希表。即，在成对的起始字母上有 38^2 个哈希表，并有 1444 个不同的表。你可以甚至可以根据前缀的常见程度动态更改哈希表的键控字母数量，因此它们的大小都适中。跟踪这些前缀的长度并不昂贵。）

然后读取 180,000 个字符串中的每一个，寻找“B”。等等。

我的理论是，由于大量表的缓存抖动，您的速度比您可能的要慢。

接下来可能有帮助的事情是限制您对字符串进行哈希处理的时间长度，以缩小表的大小。

如果您将散列的长度限制为 10 个字符，则不是对长度为 70 的字符串执行所有 2278 个长度为 3 到 70 的子字符串，而是只有 508 个长度为 3 到 10 的子字符串。字符串上的冲突可能不会那么多长度大于 10。再次，您可以让散列的长度是动态的——长度 X 散列可能有一个标志“如果你的字符串长于 X，请尝试长度 X+Y 散列，这太常见了"，否则简单地终止散列。这可能会减少表中的数据量，但在某些情况下会降低查找速度。

于 2013-01-22T21:25:39.080 回答