Map Reduce 简明教程
MapReduce - Algorithm
MapReduce 算法包含两项重要任务，即 Map 和 Reduce。
-
Map 任务由映射程序类完成
-
还原任务由还原程序类完成。
映射程序类接受输入，对输入进行标记化、映射和排序。映射程序类的输出作为还原程序类的输入，还原程序类反过来搜索匹配对并减少它们。
MapReduce 实施各种数学算法，将任务划分为较小的部分并将其分配给多个系统。从技术角度而言，MapReduce 算法有助于将 Map 和 Reduce 任务发送到集群中的适当服务器。
这些数学算法可能包括以下内容：
-
Sorting
-
Searching
-
Indexing
-
TF-IDF
Sorting
排序是处理和分析数据的基本 MapReduce 算法之一。MapReduce 实施排序算法，通过键自动对映射程序的输出键值对进行排序。
-
排序方法在映射程序类本身中实现。
-
在混合和排序阶段，在映射程序类中标记值之后， Context 类（用户定义类）将匹配的值键作为集合收集起来。
-
为了收集类似的键值对（中间键），映射程序类借助 RawComparator 类对键值对进行排序。
-
Hadoop 会自动对给定 Reducer 的中级键值对集合进行排序，以形成键值（K2，{V2，V2，…}），然后才会将它们呈交给 Reducer。
Searching
搜索在 MapReduce 算法中扮演着重要的角色。它有助于合并器阶段（可选）和 Reducer 阶段。让我们尝试借助一个示例了解搜索的运作方式。
Example
以下示例展示了 MapReduce 如何采用搜索算法找出给定员工数据集中薪水最高员工的详细信息。
-
假设我们有四个不同文件中的员工数据 - A、B、C 和 D。我们还要假设所有这四个文件中都有重复的员工记录，因为员工数据是从所有数据库表中反复导入的。参见以下图示。
-
The Map phase 处理每个输入文件，并提供键值对形式的员工数据（<k, v>：<员工姓名，工资>）。参见以下图示。
-
The combiner phase （搜索技术）将接受 Map 阶段的输入，作为带有员工姓名和工资的键值对。使用搜索技术，合并器将检查所有员工的工资，以找出每个文件中工资最高的员工。请参阅以下代码片段。
<k: employee name, v: salary>
Max= the salary of an first employee. Treated as max salary
if(v(second employee).salary > Max){
Max = v(salary);
}
else{
Continue checking;
}预期结果如下：
<satish，26000><gopal，50000><kiran，45000><manisha，45000> |
<satish, 26000> |
<satish, 26000> |
<gopal, 50000> |
<gopal, 50000> |
<kiran, 45000> |
<kiran, 45000> |
<manisha, 45000> |
<manisha, 45000> |
-
Reducer phase − 您将从每个文件中找出工资最高的员工。为了避免冗余，检查所有 <k，v> 对，并消除重复项（如果有）。相同的算法用于四个 <k，v> 对之间，这些对来自四个输入文件。最终输出应如下所示 −
<gopal, 50000>Indexing
通常，索引用于指向特定数据及其地址。它对特定 Mapper 的输入文件执行批处理索引。
MapReduce 中通常使用的索引技术称为 inverted index. Google 和 Bing 等搜索引擎使用反向索引技术。让我们尝试借助一个简单示例了解索引的运作方式。
Example
以下文本是反向索引的输入。其中 T[0]、T[1] 和 t[2] 是文件名，其内容置于双引号中。
T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"应用索引算法后，我们得到以下输出 −
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}此处 "a": {2} 表示术语 "a" 出现在 T[2] 文件中。类似地，"is": {0, 1, 2} 表示术语 "is" 出现在文件 T[0]、T[1] 和 T[2] 中。
TF-IDF
TF-IDF 是一种文本处理算法，是术语频率 - 逆向文件频率的缩写。它是常见的 Web 分析算法之一。在此，术语“频率”是指术语在文档中出现的次数。
Term Frequency (TF)
它测量特定术语在文档中出现的频率。它通过将单词在文档中出现的次数除以该文档中单词总数来计算。
TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)