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

Question

我有一个包含 1,000,000 个字符串的排序列表，最大长度为 256，带有蛋白质名称。每个字符串都有一个关联的 ID。我还有另一个未排序的 4,000,000,000 个字符串列表，最大长度为 256 个，单词不在文章中，每个单词都有一个 ID。

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

如果算法可以在没有特殊硬件的普通 PC 上运行，那就太好了。

估计算法所需的时间会很好，但不是强制性的。

Answer 1

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" );
    }
}