2011年3月11日金曜日

MapReduceのアルゴリズム(Streaming)

スズキです。

お約束の文字カウントです。
目的は、下記入力ファイルに出てくる英数字のカウントを取ります。

--------【input】--------
suzuki
sato
tanaka
kobayashi
takahashi
--------

結果は下記となるはずです。

--------【output】--------
a,9
b,1
h,3
i,3
k,4
n,1
o,2
s,4
t,3
u,2
y,1
z,1
--------

まずインプットファイルが実行されるMapプログラムの数だけ分割されます。

--------【input (Map1)】--------
suzuki
sato
tanaka
--------

--------【input (Map2)】--------
kobayashi
takahashi
--------

ここでのMapの処理は下記のように、文字列を文字ごとに分割して出力するものとします。

--------【input (for Map1)】--------
suzuki
sato
tanaka
--------

--------【output (for Map1)】--------
s,1
u,1
z,1
u,1
k,1
i,1
s,1
a,1
t,1
o,1
t,1
a,1
n,1
a,1
k,1
a,1
--------

--------【input (Map2)】--------
kobayashi
takahashi
--------

--------【output (Map2)】--------
k,1
o,1
b,1
a,1
y,1
a,1
s,1
h,1
i,1
t,1
a,1
k,1
a,1
h,1
a,1
s,1
h,1
i,1
--------

そして、Mapの結果がマージされてソートもされます。

--------【マージ & ソート】--------
a,1
a,1
a,1
a,1
a,1
a,1
a,1
a,1
a,1
b,1
h,1
h,1
h,1
i,1
i,1
i,1
k,1
k,1
k,1
k,1
n,1
o,1
o,1
s,1
s,1
s,1
s,1
t,1
t,1
t,1
u,1
u,1
y,1
z,1
--------

その後、Reduce用のインプットとして、同じ内容のものが同一インプットとなるように
実行するReduceプログラムの数だけ分割されます。

--------【input (Reduce1)】--------
a,1
a,1
a,1
a,1
a,1
a,1
a,1
a,1
a,1
b,1
h,1
h,1
h,1
i,1
i,1
i,1
--------

--------【input (Reduce2)】--------
k,1
k,1
k,1
k,1
n,1
o,1
o,1
s,1
s,1
s,1
s,1
t,1
t,1
t,1
u,1
u,1
y,1
z,1
--------

ここでのReduceの処理は下記のように、文字ごとに出現回数を集計します。

--------【input (Reduce1)】--------
a,1
a,1
a,1
a,1
a,1
a,1
a,1
a,1
a,1
b,1
h,1
h,1
h,1
i,1
i,1
i,1
--------

--------【output (Reduce2)】--------
a,9
b,1
h,3
i,3
--------

--------【input (Reduce2)】--------
k,1
k,1
k,1
k,1
n,1
o,1
o,1
s,1
s,1
s,1
s,1
t,1
t,1
t,1
u,1
u,1
y,1
z,1
--------

--------【input (Reduce2)】--------
k,4
n,1
o,2
s,4
t,3
u,2
y,1
z,1
--------

最後に各Reduceの結果をマージすると目的の結果になります。

--------【output】--------
a,9
b,1
h,3
i,3
k,4
n,1
o,2
s,4
t,3
u,2
y,1
z,1
--------

次は、MapperとReducerをPHPで実装しよう。
--------
http://www.suz-lab.com

0 コメント: