快速进行字符串搜索

Question

我有一个问题,我正在寻找一些指导来解决最有效的方法.我有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解决方案是不可能的.我不能使用全文搜索,因为我们不是处理普通单词,而是可能或可能不是由真实单词组成的字符串.

Answer 1

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

使用一些 LRU 策略可以实现执行时间的可能改进mmap。我很确定复制数据的想法是为了使搜索更快，但由于您只使用（看起来）一台机器，因此您的瓶颈将从内存搜索转向 I/O要求。

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

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

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