如何快速搜索数百万条字符串？

Question

所以情况是这样的 我们有250000个电台。 每个电台都有2根弦。在

这两个字符串可以是歌曲名、专辑名或艺人名 我们不知道哪个是什么。但其中一首肯定是歌名，我们不知道是哪首。 另一个通常是艺术家（告诉它对于最坏的情况，我们不想通过假设它是专辑来创建最坏情况的情况）

现在我们有了一个由450万艺术家，700万张专辑和1.5亿首歌曲组成的数据库（还有一堆无关紧要的其他数据），这3个不同的行在不同的表中。我们将在这些表中进行搜索和匹配。我们可以按字母顺序对它们进行排序，或者以适合我们的方式来加快处理速度。在

这些表格是相互关联的。 在这些表中，一首歌的名字总是有一个与之相关联的歌手和专辑（在各自的表中），一个专辑总是有与之相关联的艺术家和歌曲……你明白了吗

每个电台都有2根弦，我必须识别3件事

歌曲名称

专辑名

艺术家姓名

现在我假设最好的情况是，如果我们将第一个通道字符串与表中的艺术家名称相匹配。如果我们找到一个匹配项，我们可以很容易地找到另一个字符串是否在与匹配的艺术家相关联的歌曲名（和专辑名）下找到匹配项。（为了简单起见，我们假设专辑名不能与歌手名或歌曲名相同，反之亦然） 如果第一个字符串不能与Artist匹配，则尝试第二个字符串。如果找不到匹配的唱片，我们会重复同样的方法。在

什么是获得最快结果的算法？ 我有一个56 Gb的服务器（已经使用了一些ram），但我想保留20 Gb用于其他用途。（但如果您可以通过使用保留区提供非常好的解决方案，请不要犹豫提出建议。）

我们也有固态硬盘存储。你认为所有的广播电台都能在一分钟内完成吗？最好是30秒？ 请告诉我如何进行。在

这是为了更好的理解

Answer 1

所有这些都是弦。这是一个有趣的搜索问题，创建一个单独的特定搜索索引（类似Trie的结构）会很好。现在来看看你的问题，索引数据的最佳数据结构是有限状态传感器。它比Trie要紧凑得多，因为在现实世界中，字符串和文本共享许多后缀，而FST允许您共享后缀和前缀，比如图形。但是Trie不允许共享后缀。同样的，你会有你的键的值，所以你需要一个像传感器（想想排序的映射），它发射一个给定键的值，而不是一个有限状态接收器，它更像是一个排序的集合，而不是一个像地图一样的结构。在

Lucene有一个很好的实现，我想很多事情，比如建议，编辑距离都是基于它的。他们还将其与主要的反向指数脱钩。在

关于Lucene有限状态传感器的更多信息：

http://blog.mikemccandless.com/2010/12/using-finite-state-transducers-in.html

索引160000000个带有Automata和Rust的密钥：http://blog.burntsushi.net/transducers/