如何在查询中找到前缀的匹配项目

Question

我不知道如何在问题标题中解释它。假设我有一个“红利蛋糕”的问题（抱歉）。我想搜索一个大的数据库项目（比如描述）。我需要找到所有将这个完整查询作为其描述的一部分或作为前缀的描述/项目。例如：

红有趣的蛋糕

可享有，因为它有 '红'， '兴趣' 和 '蛋糕'。

这个想法是否清楚？我该怎么做？我想过使用一个trie，但我不确定它会工作得很好。

Answer 1

首先，查询作为前缀意味着查询作为一个整体存在，这样我们只需要关注问题的第二部分，从而降低算法成本。 以下是我对纯粹数学的想法。假设你的数据库包含大约100万个描述，并且每个描述的长度都是1000个字符。并且您的查询的长度为100个（平均约10个字） 我建议尽可能多地检索适合您机器的描述。然后在每个记录abd上运行一个kmp字符串匹配算法，如果匹配将其附加到结果字典中。 应用kmp算法最坏情况执行的代价是1 mil *（10 *（1000 + 100））操作。我想大概需要10秒才能得到所有的比赛。 不知道这是一个可接受的解决方案，或者如果我的假设是准确的。但是，尝试使用kmp并为您的问题添加一些优化将非常有趣。