大数据必须掌握的三个基本算法

杨利霞

" a, X+ z3 }7 \大数据必须掌握的三个基本算法
一全排序
# }' T7 j( [6 _) w- x  d# O




Hadoop自带的Partitioner的实现有两种，一种为HashPartitioner, 默认的分区方式，计算公式 hash(key)%reducernum，另一种为TotalOrderPartitioner, 为排序作业创建分区，分区中数据的范围需要通过分区文件来指定。
1 g# @- C. }# q( T8 e6 V
6 C$ _' m1 l1 f. D8 R



2 N, p# Q6 y- ]很多初学者，对大数据的概念都是模糊不清的，大数据是什么，能做什么，学的时候，该按照什么线路去学习，学完往哪方面发展，想深入了解，想学习的同学欢迎加入大数据学习qq群：199427210，有大量干货（零基础以及进阶的经典实战）分享给大家，并且有清华大学毕业的资深大数据讲师给大家免费授课，给大家分享目前国内最完整的大数据高端实战实用学习流程体系

  ^7 ^, Q/ j2 ]* G; }; j% Q9 ^9 G
分区文件可以人为创建，如采用等距区间，如果数据分布不均匀导致作业完成时间受限于个别reduce任务完成时间的影响。
1 {* O& r( A& b  C8 Z+ q

; k9 f4 f( e/ h- k5 B* A也可以通过抽样器，先对数据进行抽样，根据数据分布生成分区文件，避免数据倾斜。
: N% Z2 n, J* n

注意，key可以是数字型，也可以是BinaryComparable（字符串），当是BinaryComparable时，则以key构造Trie Tree；否则以二分查找来确定key的所属区间。
. m1 u8 [+ v1 V4 a' A! \
5 F2 s) Y5 O& W7 z5 o) T2 T  o
二单词共现矩阵算法

2 O5 i0 t3 L' j9 i4 b; w


0 w, c/ Q5 U; F6 d
9 W! y7 X/ M4 o; l: P5 O其目的是在海量语料库中发现在固定窗口内单词a和单词b共同出现的频率，从而构建单词共现矩阵，这样的矩阵可以是对称的，也可以是不对称的，这要看具体的应用。
6 q4 b9 J( R* P5 c. Q

这种抽象化的任务的有效解决在实际生活中有着很多的应用。例如电子商家希望发现不同物品被同时购买的情况以便有效安排货物的摆放位置；同时对信息检索领域同义词词典的构建以及文本挖掘等都有着重要的实际应用价值。
' o4 |1 k- r  w6 e
* J0 M  g/ b/ N# |. z
/ n% z/ ?7 H; R8 L8 Z根据同现关系的不同，可能需要实现和定制不同的FileInputFormat和RecordReader，如同现关系为一个英文句子，则需要实现以一个英文句子为单位的FileInputFormat和RecordReader，如同现关系为一个段落，则需要实现以一个段落为单位的FileInputFormat和RecordReader

7 K# u5 W4 J. H% G
% Y7 X4 q9 O5 e0 G; \7 U. O

$ _* g: |0 {3 ]. P! q0 F三倒排索引
+ o- q/ e7 e* g  v8 j
  O: `7 O( \( b/ o/ d
& w6 D# J) j1 h4 ^9 W
5 J/ c! k( F" T, \! a$ }8 p9 e  D
% v) b" ^& W7 i- |5 J! t


1 C  v9 h- ], T2 K* V* u

8 @' S+ {% x4 O& h% M/ T# KInverted Index(倒排索引)是目前几乎所有支持全文检索的搜索引擎都要依赖的一个数据结构。基于索引结构，给出一个词(term)，能取得含有这个term的文档列表(the list of documents)，没什么可说的，必须掌握。
————————————————
版权声明：本文为CSDN博主「铁拳虎」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/juan189/article/details/84932486

7 j) L) ^' |3 L! h5 G) P! m
: U) t( E) c4 z; F

1051373629

非常感谢楼主！