9

你知道一种快速过滤字符串列表以获得包含指定字符串的子集的方法吗？显而易见的实现是遍历列表，检查每个字符串是否包含搜索字符串。有没有办法索引字符串列表，以便更快地完成搜索？

4

6 回答 6

13

维基百科文章列出了几种索引子字符串的方法。你有：

于 2009-08-19T11:11:14.330 回答
2

是的，例如，您可以为字符串中的所有字符组合创建索引。像“hello”这样的字符串将被添加到“he”、“el”、“ll”和“lo”的索引中。要搜索字符串“hell”，您将获取所有“he”、“el”和“ll”索引中存在的所有字符串的索引，然后遍历这些索引以检查字符串中的实际内容。

于 2009-08-19T11:09:02.617 回答
1

如果您可以预处理集合，那么您可以做很多不同的事情。

例如，您可以构建一个包含所有字符串后缀的 trie，然后使用它进行非常快速的匹配。

于 2009-08-19T11:12:58.053 回答
1

如果您要重复搜索相同的文本，那么后缀树可能是值得的。如果仔细应用，您可以对大多数字符串问题实现线性时间处理。如果不是，那么在实践中你将无法比Rabin-Karp做得更好，它基于散列，并且在预期时间内是线性的。

There are many freely available implementations of suffix trees. See for example, this C implementation, or for Java, check out the Biojava framework.

于 2009-08-19T11:25:27.063 回答
0

不是真的任何可行的东西，不，除非您对数据和/或搜索词有额外的先验知识 - 例如，如果您只在字符串的开头搜索匹配项，那么您可以对字符串进行排序并且只查看搜索词范围内的那些（甚至将它们存储在二叉树中，只查看可能匹配的分支）。同样，如果您的潜在搜索词有限，您可以在最初输入字符串时对字符串运行所有可能的搜索，然后只存储一个表，其中包含哪些词匹配哪些不匹配。

除了那种东西，基本上就是迭代。

于 2009-08-19T11:08:08.173 回答
0

这取决于子字符串是在字符串的开头还是可以在字符串中的任何位置。

如果它在任何地方，那么您几乎需要遍历整个列表，除非您的列表太大并且查询发生得足够频繁，以至于值得构建更复杂的索引解决方案。

如果子字符串位于字符串的开头，那么这很容易。对列表进行排序，通过二分搜索找到开始/结束并获取该子集。

于 2009-08-19T11:08:52.807 回答