在十億個唯一字符串列表中搜索一個子字符串

Question

我有一個大約十億個唯一字符串的列表，其中最多有幾十個字符。我希望找到包含或匹配搜索字符串的所有字符串，理想情況下小於100-200毫秒，儘可能少的硬件（我假設我需要大量的RAM）。什麼是最好的方式去存儲和檢索？

• 從我讀過，MySQL的LIKE '%search%'不使用索引，但LIKE '%search'和LIKE 'search%'都這樣做。這是可以接受的最後手段，但不是理想的，因爲我想在目標字符串中的任何位置找到搜索字符串。
• 使用像Redis這樣的鍵值存儲將需要存儲每個可能的子串組合，並且我假設有很多RAM。
• 字符串列表大概是十幾GB大。像Lucene這樣的全文搜索服務器是否可行，甚至是理想的，而不是擁有數十億行/文檔/記錄？它肯定會保存在解析。

Answer 1

您是否考慮過使用衆多MapReduce框架之一來解決您的問題？ MapReduce的本質是你分而治之，所以你要解決一個非常簡單的問題（比如說，你的十億個唯一的字符串中只有一個包含了你的搜索術語）十億次，然後你將十億個答案結合成一個答案。而不是隻有一臺擁有大量RAM的機器來解決您的問題，您可以請求許多裝備較少的機器一起解決您的問題。一探究竟。這可能是你在找什麼。