在包含1亿个字符串(无重复字符串)的大型文本文件中进行高效的子字符串搜索

Question

我有一个大的文本文件(1.5 Gb)，有1亿个字符串(没有重复的字符串)，所有的字符串在文件中都是逐行排列的。我想用java做一个网络应用程序，这样当用户给出一个关键字(子字符串)时，他就会得到包含该关键字的文件中所有字符串的计数。我知道一种技术LUCENE already..is有任何其他的方法来做到这一点。我想在3-4秒内得到结果。我的系统有4 4GB内存和双核配置...我需要在"JAVA ONLY“中做到这一点

Answer 1

尝试使用哈希表。可以做的另一件事是任何类似于MAP-REDUCE的方法。我想说的是，您可以尝试使用倒排索引。谷歌也使用了同样的技术。你可以创建一个停用词文件，你可以在其中放置可以忽略的单词，例如I，am，the，a，an，in，on等。

我想这是唯一可能的事情。我在某处读到，为了搜索，你可以数组。

Answer 2

你的关键词会有很多重叠吗？如果是这样的话，您也许能够存储从关键字(String)到文件位置(ArrayList)的散列映射。尽管有对象开销，但不能将所有行都存储在内存中。

有了文件位置后，您可以在文本文件中查找该位置，然后查找附近的位置以获取封闭的换行符，并返回该行。这肯定不会超过4秒。Here是关于这方面的一点信息。如果这只是一个小小的练习，那将会很好。

不过，更好的解决方案是两层索引，一个将关键字映射到行号，另一个将行号映射到行文本。这将无法放入您机器的内存中。不过，也有一些很棒的disk based key-value stores可以很好地工作。如果这不仅仅是一个玩具问题，那就使用Reddis路线。

Answer 3

您可以根据每个单词的前几个字母构建一个目录结构。例如：

/A
/A/AA
/A/AB
/A/AC
...
/Z/ZU

在该结构下，您可以保留一个包含所有字符串的文件，这些字符串的第一个字符与文件夹名称相匹配。搜索词中的前几个字符会将选择范围缩小到整个列表中只有一小部分的文件夹。从那里，您可以只对该文件进行完整的搜索。如果速度太慢，可以增加目录树的深度以覆盖更多的字母。