3

我有一大堆短字符串。有哪些算法和索引策略可以过滤包含子字符串的项目列表？例如，假设我有一个列表：

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('%', ?, '%');

用户提供的搜索字符串在哪里?，结果是包含搜索字符串的单词列表。

4

2 回答 2

2

最长的单词有多大？如果那大约是 7-8 个字符，您可能会找到每个字符串的所有子字符串，并将这些子字符串插入 trie（在 Aho-Corasik 中使用的那个 - http://en.wikipedia.org/wiki/Aho-Corasick）它构建树需要一些时间，但是搜索所有出现的时间将是 O(length(searched word))。

于 2012-08-02T19:36:57.227 回答
1

Postgres 有一个做三元索引的模块

这似乎也是一个有趣的想法——建立一个三元组索引。

关于您的问题中关于如何分解大于 n-gram 长度的文本搜索的评论：

这是一种可行的方法：

假设我们有一个搜索字符串 "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-05T19:07:53.113 回答