我有一个要索引的文件(具体来说是fasta文件)，这样我可以快速找到文件中的任何子字符串，然后在原始的fasta文件中找到位置。

在许多情况下，使用Trie或者子字符串数组可以轻松做到这一点，不幸的是，我需要索引的字符串超过800 MB，这意味着以不可接受的方式在内存中进行存储，因此我正在寻找一种合理的方法来创建此字符串在磁盘上建立索引，以最小的内存使用量。

(为澄清而编辑)

我只对蛋白质的标头感兴趣，因此对于我感兴趣的最大数据库，这是大约800 MB的文本。

我希望能够基于输入字符串在O(N)时间内找到确切的子字符串。它必须在32位计算机上可用，因为它将被运送到不希望拥有64位计算机的随机人员。

我希望能够对一行中的任何单词中断进行索引，直到该行的末尾(尽管行的长度可能为几MB)。

希望这可以弄清需要什么，以及为什么给出的当前解决方案不能说明问题。

我还应该补充一点，这需要从Java内完成，并且必须在各种操作系统上的客户端计算机上完成，因此我不能使用任何特定于OS的解决方案，并且它必须是程序性解决方案。

解决方案

回答

我与一些同事交谈，他们只是在需要时使用VIM / Grep进行搜索。大部分时候，我都不希望有人搜索这样的子字符串。

但是我不明白为什么MS Desktop搜索或者Spotlight或者google的等效项在这里无法为我们提供帮助。

我的建议是按基因或者物种拆分文件，希望输入序列不会交错。

回答

在某些语言中，程序员可以访问OS提供的"直接字节数组"或者"内存映射"。在Java中，我们有java.nio.MappedByteBuffer。这样一来，就可以像对待内存中的字节数组一样处理数据，而实际上它就位于磁盘上。一个人可以使用的文件大小仅受操作系统的虚拟内存功能限制，对于32位计算机，通常约为4GB。 64位？从理论上讲16艾字节(172亿GB)，但我认为现代CPU限于40位(1TB)或者48位(128TB)地址空间。

这将使我们轻松处理一个大文件。

回答

FASTA文件格式非常稀疏。我要做的第一件事是生成紧凑的二进制格式，并为其编制索引，索引大小应约为当前文件的20％至30％，并且编码/解码数据的过程应足够快(即使使用4GB)，不会有问题。

此时，即使在32位计算机上，文件也应适合内存。让OS对其进行分页，或者如果要确定它全部在内存中，则制作一个ramdisk。

请记住，内存每GB仅约30美元(并且越来越便宜)，因此，如果我们使用的是64位操作系统，则甚至可以处理内存中的完整文件而无需将其编码为更紧凑的格式。

祝你好运！

-亚当

回答

我不认为原始发布者仍然会遇到此问题，但是任何需要FASTA文件索引和子序列提取的人都应该查看fastahack：http://github.com/ekg/fastahack

它使用索引文件来计算换行符和序列起始偏移量。生成索引后，我们可以快速提取子序列。提取由fseek64驱动。

如果序列与发布者的序列一样长，它将非常非常好。但是，如果FASTA文件中有成千上万个序列(如短读序列或者某些从头汇编的输出一样)，我们将需要使用其他解决方案，例如磁盘支持的密钥-值存储。