php - 如何快速搜索数百万个字符串？

Question

关闭。这个问题需要更多 focused .它目前不接受答案。












想改进这个问题？更新问题，使其仅关注一个问题 editing this post .

5年前关闭。




Improve this question




所以这是情况
我们有 250,000 个广播电台。
每个广播电台都带有 2 个字符串。

这 2 个字符串可以是 歌曲名称 , 专辑名 或 艺术家姓名
我们不知道哪个是什么。但其中一个肯定是歌名，我们不知道是哪一个。
通常另一个是艺术家(告诉它最坏的情况，我们不想通过假设它是专辑来创造最坏的情况)

现在我们有一个包含 450 万艺术家、700 万专辑和 1.5 亿首歌曲的数据库。(以及一些其他无关紧要的数据)这 3 个不同的行位于不同的表中。这些是我们将在其中进行搜索和匹配的表。我们可以按字母顺序对它们进行排序，或者它适合我们加快处理过程。

这些表是相互关联的。
在这些表中，歌曲名称始终具有与之关联的艺术家和专辑(在其各自的表中)，专辑始终具有关联的艺术家和歌曲......你明白了

每个广播电台都有 2 个字符串，我必须识别 3 件事

歌曲名称

专辑名

艺术家姓名

现在我假设最好的情况是我们将 channel 的第一个字符串与表中的艺术家姓名相匹配。如果我们得到一个匹配，我们可以很容易地找到另一个字符串是否在与匹配的艺术家关联的歌曲名称(和专辑名称)下得到匹配。 (为了简单起见，我们假设专辑名称不能与艺术家姓名或歌曲名称相同，反之亦然)
如果第一个字符串没有匹配到 Artist，我们尝试第二个字符串。然后如果我们没有匹配到，我们对 Album 重复同样的操作。

获得最快结果的算法应该是什么？
我有一个 56 Gb 的服务器(已经使用了一些内存)，但我想保留 20 Gb 用于其他目的。 (但如果您可以通过使用储备提供非常好的解决方案，请不要犹豫。)

我们还有 SSD 存储。您认为这一切都可以在一分钟内为所有广播电台完成吗？最好30秒？
请让我知道如何进行。

这是更好理解的图像

Answer 1

好吧，所有这些都是字符串。这是一个有趣的搜索问题，创建一个单独的特定搜索索引(类似 Trie 的结构)会很好。现在来解决您的问题，索引数据的最佳数据结构将是有限状态传感器。它比 Trie 紧凑得多，因为在现实世界中，字符串和文本共享很多后缀，而 FST 允许您共享后缀和前缀，想想 Graphs。但是 Trie 不允许您共享后缀。此外，由于您的键有值，因此您将需要像 Transducer(想想排序的映射)这样的东西，它在给定键的情况下发出一个值，而不是更像一个排序集而不是类似结构的映射的有限状态接受器。

Lucene 有一个很好的实现，我想很多东西，比如 Suggestions，Edit Distances 都是基于它的。他们还将其与主要的倒排指数脱钩。

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

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

使用 Automata 和 Rust 索引 1,600,000,000 个键:http://blog.burntsushi.net/transducers/