如何高效地搜索子数据集的大数据集？

我有一大组短字符串。用于过滤包含子字符串的项目列表的一些算法和索引策略是什么？例如，假设我有一个列表：如何高效地搜索子数据集的大数据集？

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

如何高效地搜索子数据集的大数据集？

回答

相关问题