在另一个大列表中搜索大量单词列表

问题描述：

我有一个1,000,000个字符串的排序列表，其中最大长度为256个蛋白质名称。每个字符串都有一个关联的ID。我有另一个未排序的4,000,000,000字符串的列表，最大长度为256，文章中出现单词，每个单词都有一个ID。在另一个大列表中搜索大量单词列表

我想查找蛋白质名称列表和文章的单词列表之间的所有匹配。我应该使用哪种算法？我应该使用一些预建API吗？

如果算法在没有特殊硬件的普通PC上运行，那将会很好。

该算法需要的时间估计是好的，但不是强制性的。

答

40亿字符串是很多字符串搜索。

您可能能够将整个数据结构放入内存哈希中进行快速查找，但更有可能您希望将整个列表存储在更宽敞（但速度更慢）的磁盘上，在这种情况下，已排序的列表会出借本身是相对有效的二进制搜索算法。

如果您的二进制搜索或这样的函数被调用find_string_in_articles()，然后伪代码：

foreach $protein_name (@protein_names) { 
    if ($article_id = find_string_in_articles($protein_name)) { 
     print("$protein_name matches $article_id\n"); 
    } 
}

磁盘存储上的大多数搜索算法在性能方面都非常糟糕。交换收藏品，以便您可以在蛋白质记忆中查找，并顺序扫描文章词语。 – 2010-04-01 00:23:25

答

听起来像你应该使用二叉树的东西。

答

你可以对它们进行排序，然后做“归并”，这实际上不会合并，但发现你复制/重叠。*有很好的参考。

排序该数据量可能需要比您可访问的更多的内存。我不知道unix是否可以处理（Windows/Mac上也可以），但任何体面的SQL数据库都可以做到这一点。

另一种可能性是在你的蛋白名称上使用一个基数树（那些以A开始到bin A，B到bin B等）的基数树。然后，循环使用4个巨大的单词并定位重叠（您可能必须实施多个深度基数筛选以一次丢弃更多蛋白质）。

答

我会在2种方式中的任何一种中去解决这个问题。

将它插入SQL数据库和拔出你需要的数据（较慢，但更容易）
排序列表，然后做二进制搜索找到你所需要的（速度快，但很困难）

答

这实质上是一个关系连接。假设你不已经整理的文章的话，你的基本的算法应该是：

for word in article_words: 
    if (proteins.find(word)): 
     found_match(word)

proteins.find（）是困难的部分，你将不得不实验，以获得最佳的性能，这样的问题是缓存效果开始起作用的地方。我首先尝试一个基数排序，它非常简单，可能足够快，但二进制搜索和哈希也是替代方法。

在另一个大列表中搜索大量单词列表

相关推荐