如何在查詢中找到前綴的匹配項目

Question

我不知道如何在問題標題中解釋它。假設我有一個「紅利蛋糕」的問題（抱歉）。我想搜索一個大的數據庫項目（比如描述）。我需要找到所有將這個完整查詢作爲其描述的一部分或作爲前綴的描述/項目。例如：

紅有趣的蛋糕

可享有，因爲它有 '紅'， '興趣' 和 '蛋糕'。

這個想法是否清楚？我該怎麼做？我想過使用一個trie，但我不確定它會工作得很好。

Answer 1

首先，查詢作爲前綴意味着查詢作爲一個整體存在，這樣我們只需要關注問題的第二部分，從而降低算法成本。 以下是我對純粹數學的想法。假設你的數據庫包含大約100萬個描述，並且每個描述的長度都是1000個字符。並且您的查詢的長度爲100個（平均約10個字） 我建議儘可能多地檢索適合您機器的描述。然後在每個記錄abd上運行一個kmp字符串匹配算法，如果匹配將其附加到結果字典中。 應用kmp算法最壞情況執行的代價是1 mil *（10 *（1000 + 100））操作。我想大概需要10秒才能得到所有的比賽。 不知道這是一個可接受的解決方案，或者如果我的假設是準確的。但是，嘗試使用kmp併爲您的問題添加一些優化將非常有趣。