2

我有 200 万个字符串,我需要在 1 TB 的文本数据中搜索每个字符串。搜索所有这些并不是最好的解决方案,所以我正在考虑一种更好的方法来为所有字符串创建像 trie 这样的数据结构。换句话说,其中的每个节点都是一个单词的 trie。我想问一下,是否有任何好的算法、数据结构或库(在 C++ 中)用于此目的?


让我在这个问题上更具描述性,伙计们,

例如,我有这些字符串: s1-“我爱你” s2-“你好吗” s3-“怎么了伙计”

我有很多文本数据,例如:t1-“嗨,我叫 Omid,我喜欢电脑。你们好吗?” t2-“你的每一个愿望都会实现,他们告诉我......” t3 t4 。. . t10000

然后我想考虑每个文本并搜索它们上的每个字符串。最后,对于这个例子,我只想说:t1 包含 s1,没有别的。我正在寻找一种有效的方法来搜索字符串,但不是每次都愚蠢地搜索它们。

4

2 回答 2

1

很抱歉仅发布链接答案,但如果您不介意阅读研究论文,在我看来,关于字符串匹配算法的权威参考是http://www-igm.univ-mlv.fr/~lecroq /string/以及 Simone Faro 和 Thierry Lecroq 的以下研究论文,他们比较了不少于 85 种不同字符串匹配算法的相对性能。我很确定其中有一个适合您的需求。

于 2014-02-18T17:18:32.373 回答
0

我强烈建议您使用 CLucene ( http://clucene.sourceforge.net/ ),它是 Apache Lucene 项目的一个端口。这将为您构建一个倒排索引并使文本搜索非常快。如果可以选择更改语言,请考虑在 Java 中执行此操作,因为 CLucene 版本有点过时了。它会更慢,但有更多的功能。

于 2014-02-18T06:27:08.467 回答