包含1亿个字符串的大型文本文件中的高效子字符串搜索（无重复字符串）
我有一个大文本文件（1.5 Gb）有100万字符串（没有重复字符串），所有字符串在文件中逐行排列。 我想在java中进行wepapplication，以便当用户给出一个关键字（Substring）时，他得到包含该关键字的文件中存在的所有字符串的计数。 我知道一种技术LUCENE已经……还有其他方法可以做到这一点。 我想在3-4秒内得到结果。 我的系统有4GB内存和双核心配置….需要在“JAVA ONLY”中执行此操作
尝试使用哈希表。 可以做的另一件事是任何类似于MAP-REDUCE的方法。 我想说的是你可以尝试使用倒排索引。 谷歌使用相同的技术。 所有你可以创建一个停用词文件，你可以在其中放置可以忽略的单词，例如我，我，a，a，an，in，on等。
这是我认为唯一可行的事情。 我在某处读到了搜索，你可以使用数组。
预计关键字会有很多重叠吗？ 如果是这样，您可能能够将关键字（ String ）的哈希映射存储到文件位置（ ArrayList ）。 尽管存在对象开销，但您无法将所有行存储在内存中。
获得文件位置后，您可以在文本文件中查找该位置，然后查看附近以获取封闭的换行符，然后返回该行。 那肯定会少于4秒。 这是一个小信息。 如果这只是一个小练习，那就行得很好。
一个更好的解决方案是两层索引，一个映射关键字到行号，然后另一个映射行号到行文本。 这不适合您机器的内存。 虽然可以很好地使用基于磁盘的大型键值存储 。 如果这不是玩具问题，请使用Reddis路线。
您可以根据每个单词的前几个字母构建目录结构。 例如：
/A /A/AA /A/AB /A/AC ... /Z/ZU
在该结构下，您可以保留包含所有字符串的文件，其中第一个字符与文件夹名称匹配。 搜索字词中的第一个字符会将选区缩小到只包含整个列表的一小部分的文件夹。 从那里，你可以完全搜索该文件。 如果它太慢，请增加目录树的深度以覆盖更多字母。
由于RAM的大小超过文件的大小，因此您可以将整个数据作为结构存储在RAM中并快速搜索。 trie可能是一个很好的数据结构; 它确实有快速的前缀查找，但不确定它如何执行子串。