这更像是一个架构问题，你将如何在规模上解决这个问题。
假设您有一个数百万单词的列表，并且您需要搜索这些数百万单词是否存在于一个万亿单词的集合中。
例如：
Word_List =
["This", "a", "test", "of", "two", "words","what","words"]
The_corpus =
["This", "a", "test", "of", "two", "words","what","words","blah","blah2"]在上面的示例中，word\列表中的所有单词都在\语料库中找到，因此我们的函数将返回true。注意“单词”必须出现两次。
我想知道我们可以通过hadoop或spark来解决这个问题，方法是在集群上分发单词库，并编写mapper和reducer来检查单词是否存在于语料库中，但我不知道单词\u列表将如何分布。我不能在主节点上保留单词列表，因为它太大了。
4条答案
按热度按时间llew8vvj1#
我猜你的问题是如何使用一个聚类来加速搜索，聚类中的语料库以某种方式在聚类节点之间进行了划分。在这里我概述了我将要做的事情。
对语料库进行排序并删除重复项，但为每个单词添加一些重复项，例如1，blah 1，blah2 1，of 1，test 1，this 1，two 1，what 1，words 2，等等，可能每行一个单词以简化搜索过程，或者以某种打包形式以加速io。
将语料库分成n个部分，并记录每个部分中单词的字母范围，例如，第1部分有从a到aff的单词，第2部分有从afg到amp的单词，等等。将所有部分放在每个节点可访问的共享存储上。
对单词列表进行排序（删除重复项，但增加每个单词的计数），将单词分成m个组，每个组分配给一个节点进行搜索。
对每个节点上的每个单词进行二进制搜索（因为单词是经过排序的）（搜索工具根据字母表范围知道要搜索的语料库部分）并返回true（如果找到的所有单词的计数都正确）或false（一旦一个单词失败就可以返回）。当然，你自己决定什么才算成功。可以对搜索进行优化。例如，如果将一个节点分配给组，其中包含三个单词test、this和two，并且单词test位于第x部分的中间，则只需在第x部分的右半部分执行单词this的搜索。
uidvcgyl2#
您可以在hadoop中的hdfs上添加word\u列表和语料库，这将在所有节点上分发这两个文件。现在您可以从hdfs读取这两个文件。在Map程序代码中，可以使用filesystem类从Map程序代码中的hdfs访问word\ u列表文件。您可以在hadoopjar命令中将您的语料库文件作为输入文件路径。
dxpyg8gm3#
您的任务具有类似于普通联接操作的目标。在实施过程中，您可以考虑以下几点：
您可以使用基于单词列表的bloomfilter来缩小\u语料库集合中潜在值的范围
对于小集合，通常使用分布式缓存使所有任务节点上的资源可用。在您的情况下，这可能是一个很大的空间命中，因为它将被复制到执行实际任务的每个节点。为了改进这一点，您可以使用更大的复制因子（例如10，取决于集群中的节点数）将文件直接放入文件系统，以提高其可用性。然后在您的任务中，您将能够直接下载它，这将大大节省您的空间相比，分布式缓存方法，但成本将是您的带宽在非本地读取。您可以使用它来找到最佳的复制次数。
umuewwlo4#
单词\u列表可以通过hadoop的distributedcache机制分布在节点上。实际上，文件（-s）是在初始作业配置阶段指定的，然后物理地复制到将运行Map任务的所有节点。然后每个map任务都可以访问和使用该文件的内容。
因此，您的示例任务在hadoop中的解决方法如下：将单词表和语料库放入hdfs中；在作业中，单词列表被设置为使用distributedcache跨所有节点分布；在Map阶段，根据特定的语料库分割检查单词表（即每个Map任务都有完整的单词表和64/128/…mb的语料库分割，其中64/128/。。。由为语料库文件设置的hdfs块大小定义）；在reduce阶段，需要进行聚合，例如，如果只返回true/false，则reducers输入可能是word\u列表中所有单词的出现次数：如果所有单词至少出现一次，则返回true，否则返回false。
一般来说，这类任务称为map-side-join。参见一些示例代码（使用distributedcache），例如，这里。