我有一个要索引的文件（具体来说是 fasta 文件），以便我可以快速找到文件中的任何子字符串，然后在原始 fasta 文件中找到该位置。
在许多情况下，使用 Trie 或子字符串数组很容易做到这一点，不幸的是，我需要索引的字符串是 800+ MB，这意味着在内存中执行它们是不可接受的，所以我正在寻找一种合理的方法来创建它磁盘上的索引，内存使用量最少。
（编辑澄清）
我只对蛋白质的标题感兴趣，所以对于我感兴趣的最大数据库，这是大约 800 MB 的文本。
我希望能够根据输入字符串在 O(N) 时间内找到确切的子字符串。这必须在 32 位机器上可用，因为它将被运送给随机的人，他们预计不会拥有 64 位机器。
我希望能够针对一行中的任何断字进行索引，直到行尾（尽管行可能有几 MB 长）。
希望这可以阐明需要什么以及为什么给出的当前解决方案没有启发性。
我还应该补充一点，这需要在 java 中完成，并且必须在各种操作系统的客户端计算机上完成，所以我不能使用任何特定于操作系统的解决方案，它必须是一个编程解决方案。
在某些语言中，程序员可以访问操作系统提供的“直接字节数组”或“内存映射”。在 java 中，我们有java.nio.MappedByteBuffer。这允许人们像处理内存中的字节数组一样处理数据，而实际上它在磁盘上。可以使用的文件大小仅受操作系统的虚拟内存能力限制，对于 32 位计算机，通常约为 <4GB。64位？理论上 16 艾字节（172 亿 GB），但我认为现代 CPU 仅限于 40 位（1TB）或 48 位（128TB）地址空间。
这将使您轻松处理一个大文件。
FASTA 文件格式非常稀疏。我要做的第一件事是生成一个紧凑的二进制格式，并为其编制索引——它应该是当前文件大小的 20-30%，并且编码/解码数据的过程应该足够快（即使是 4GB）这不会是一个问题。
此时，您的文件应该适合内存，即使在 32 位机器上也是如此。让操作系统对其进行分页，或者如果您想确定它全部在内存中，请制作一个 ramdisk。
请记住，内存仅为每 GB 30 美元左右（而且越来越便宜），因此如果您有 64 位操作系统，那么您甚至可以处理内存中的完整文件，而无需将其编码为更紧凑的格式。
祝你好运！
-亚当
我和几个同事谈过，他们只是在需要时使用 VIM/Grep 进行搜索。大多数时候，我不希望有人搜索这样的子字符串。
但我不明白为什么 MS 桌面搜索或聚光灯或谷歌的同等产品在这里不能帮助你。
我的建议是按基因或物种拆分文件，希望输入序列不会交错。
我不认为原始海报仍然存在这个问题，但是任何需要 FASTA 文件索引和子序列提取的人都应该查看 fastahack：http: //github.com/ekg/fastahack
它使用索引文件来计算换行符和序列起始偏移量。生成索引后，您可以快速提取子序列；提取由 fseek64 驱动。
如果您的序列与海报的序列一样长，它将非常非常好地工作。但是，如果您的 FASTA 文件中有数千或数百万个序列（如短读测序或一些从头组装的输出的情况），您将需要使用另一种解决方案，例如磁盘支持的密钥-价值存储。