如何高效地搜索子數據集的大數據集？

我有一大組短字符串。用於過濾包含子字符串的項目列表的一些算法和索引策略是什麼？例如，假設我有一個列表：如何高效地搜索子數據集的大數據集？

val words = List(
    "pick", 
    "prepick", 
    "picks", 
    "picking", 
    "kingly" 
    ... 
)

如何找到包含子字符串「king」的字符串？我可以像這樣蠻力的問題：

words.filter(_.indexOf("king") != -1) // yields List("picking", "kingly")

這隻適用於小集;今天，我需要支持1000萬字符串，未來的目標是數十億美元。顯然我需要建立一個索引。 什麼樣的索引？

我已經看過了使用存儲在MySQL的NGRAM指數，但我不知道這是最好的辦法。當搜索字符串長於ngram大小時，我不確定如何優化查詢索引。

我已經使用Lucene也認爲，但這是圍繞優化匹配的令牌，而不是子串匹配，並且似乎不支持簡單的串匹配的要求。 Lucene確實有一些與ngram相關的類（org.apache.lucene.analysis.ngram.NGramTokenFilter就是一個例子），但這些類似於拼寫檢查和自動完成用例，而不是子字符串匹配，而且文檔很薄。

我應該考慮哪些其他的算法和索引策略？有沒有支持這個的開源庫？ SQL或Lucene策略（上面）可以工作嗎？

另一種方式來說明要求與SQL：

SELECT word FROM words WHERE word LIKE CONCAT('%', ?, '%');

凡?爲用戶提供的搜索字符串，其結果是包含搜索字符串中的單詞的列表。

來源

2012-08-02 Landon Kuhn

後綴樹應該完成這項工作。 – nhahtdh 2012-08-02 17:41:02

1000萬個字符串是不同的？ – 2012-08-02 18:34:32

@GordonLinoff是的。 – 2012-08-02 19:30:52

最長的單詞有多大？如果這是約7-8焦炭您可能會發現每個每個字符串的所有子和，並插入在特里子（一種用於在阿霍 - Corasik - http://en.wikipedia.org/wiki/Aho-Corasick）這將需要一些時間來建立樹，但然後搜索所有的發生將是O（長度（搜索字））。

來源

2012-08-02 19:36:57

你的建議是建立一個包含每個子字符串的trie，每個節點包含每個匹配的單詞列表？ – 2012-08-02 20:54:30

因此，它將是，因爲單獨的字母也是子字符串。是的，內存消耗太多了。 – 2012-08-02 21:06:47

我們是從初始字典中檢查的單詞嗎？ – 2012-08-02 21:10:35

Postgres有一個模塊，它做了trigram index

這似乎too-建設卦指數一個有趣的想法。

關於你的問題，關於如何打破文本註釋搜索比正克長度更大：

這裏有一個辦法，將工作：

說我們有一個搜索字符串「ABCDE」，我們建立了一個三元組索引。（你有長度較短的字符串 - 這可能會給你一個甜蜜點）讓abc = S1，bcd = S2，cde = S3的搜索結果（其中S1，S2，S3是索引集）

然後，S1，S2，S3中最長的公共子串將給出我們想要的索引。

我們可以在執行LCS之前，將每組索引轉換爲由分隔符（比如空格）分隔的單個字符串。

當我們找到LCS後，我們必須搜索完整模式的索引，因爲我們已經細分了搜索詞。即我們將不得不修剪具有「abc-XYZ-bcd-HJI-def」的結果

可以有效地找到一組字符串的LCS Suffix Arrays。或後綴樹

來源

2012-08-05 19:07:53 Arvind

@ landon9720：請在您有機會查看我的答案時發表評論。我想知道你對我提出的方法的看法。 – Arvind 2012-08-08 02:54:32

如何高效地搜索子數據集的大數據集？

回答

相關問題