c++ - 快速的字符串搜索

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

作为我的第一个切入点，我做了以下工作:

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

将字符串添加到索引时，它会分解为3个非重复(在其内部)的3-n个字符子字符串(当n是字符串-1的长度时)。因此，例如，“苹果”作为pples，pple，ppl，pp存储在“A”索引中(子字符串也存储在“L”和“P”索引中)。

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

问题出在流程的前端。我通常一次添加30,000个 key 。该过程的这一部分需要永远的时间。通过基准测试，装入18万个可变长度键的空索引中的加载时间约为3 1/2小时。

除了非常长的加载时间外，此方案都有效。

在我进行优化(或尝试进行优化)之前，我想知道是否有更好的方法来解决此问题。对于如此大的数据集，前后通配符搜索(例如，DBMS中的字符串，例如'％ppl％')非常慢(例如，在MySQL中为数小时)，因此DBMS解决方案似乎是不可能的。我不能使用全文搜索，因为我们不是在处理普通单词，而是可能由真实单词组成的字符串。

最佳答案

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

使用带有某些LRU策略的mmap可以实现执行时间的改善。我非常确定复制数据的想法是为了使搜索更快，但是由于您正在使用-似乎只使用了一台计算机，因此瓶颈将从内存搜索转移到I/O要求。

您可能不感兴趣的另一种解决方案-有趣的是，它也令人讨厌并且令人不安(:-)，将数据拆分到多台计算机上。考虑到数据的结构方式，实现本身可能需要一些时间时间，但这将非常简单。您将拥有:

每台机器由一组存储桶负责，使用类似于hash_id(bucket) % num_machines的东西选择存储桶；

插入是在每台计算机上本地执行的；

搜索可以通过您的查询应用程序的某种类型进行接口(interface)，也可以简单地聚集成查询集-如果应用程序不是交互式的；

考虑到您可能从一个节点发送开始请求，然后将请求转发到另一个节点(也包括集群请求，以避免过多的I/O开销)，因此

搜索甚至可能具有分布式接口(interface)。

正如您所说，另一个好处是，数据是均匀分布的-已经\o/;这通常是分布式实现中最挑剔的部分之一。此外，这将具有很高的可扩展性，因为每当数据大小增加时，您可能会添加另一台计算机。

关于c++ - 快速的字符串搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14467396/