検索インデックスを作ろう 後編 (Hadoopで転置インデックス)
Hadoopのインストールについては以下を参照。
転置インデックスとは、本の巻末にある索引のことだ。
例えば、るるぶは巻末に転置インデックスがついていて、目的地のページを素早く探せる。
"金閣寺 ・・・ P.15"
"銀閣寺 ・・・ P.15,P.16,P.57"
"高台寺 ・・・ P.11"
前編の単語リストは、文書ID => 単語、単語、単語 だったが、
後編の転置インデックスは、単語 => 文書ID、文書ID、文書ID と、
単語リストをひっくり返す(転置)。
MapReduceの手順
1.文書のURIを並べたテキストファイル
http://localhost/rfc/rfc1.txt
http://localhost/rfc/rfc2.txt
http://localhost/rfc/rfc3.txt
http://localhost/rfc/rfc4.txt
http://localhost/rfc/rfc5.txt
2. Map (各URIをフェッチして、前編の単語リスト生成スクリプトにかける)
rfc1.txtの単語リスト
rfc2.txtの単語リスト
rfc3.txtの単語リスト
rfc4.txtの単語リスト
rfc5.txtの単語リスト
3. Reduce (単語リストをまとめる)
転置インデックスの出来上がり。
RFC文書(英文テキスト243MB)の処理に4分19秒を要した。(Thinkpad X60)
コマンド
Hadoopの分散ファイルシステムに、文書のURIを並べたテキストファイル(rfc_list)を置く。
$ bin/hadoop dfs -copyFromLocal rfc_list rfc_list
HadoopでMapReduceする。Hadoop Streamingを使うと、catやwcなどの標準入出力を使うプログラムを、Mapper、Reducerとして使える。
$ bin/hadoop jar contrib/streaming/hadoop-0.18.1-streaming.jar \ -input rfc_list -output rfc_idx \ -file "getdoc.scm" -mapper "gosh getdoc.scm" \ -file "reducer.scm" -reducer "gosh reducer.scm"
結果を取り出す。
$ bin/hadoop dfs -copyToLocal rfc_idx /tmp/
結果を見てみる。
$ head /tmp/rfc_idx/part-00000
00000000000000001D79EAF247B394BF rfc4418.txt
0000000000000000A6C537D7986FA4AA rfc4418.txt
00000000000000F0 rfc1510.txt
0000000015Full rfc3440.txt
00000000AAFF rfc1493.txt,rfc1748.txt,rfc1743.txt,rfc1286.txt,rfc1230.txt,rfc1231.txt
00000000T000000 rfc4807.txt
00000000T240000 rfc4807.txt
00000001a000015 rfc2259.txt
00000001a000022 rfc2259.txt
00000001a000027 rfc2259.txt
Mapperの解説(getdoc.scm)
前編の単語リスト生成シェルスクリプトを使う。
tr -c '[:alnum:]' '[\n*]' | grep -v '^[0-9]*$' | sort -iu
単語ごとにdoc-idをつけるところが前編とは違う。
A rfc1.txt
ARPA rfc1.txt
Additionally rfc1.txt
After rfc1.txt
Again rfc1.txt
(use rfc.uri) (use rfc.http) (use file.util) (use gauche.process) (define (main args) (port-for-each (lambda (uri) (receive (_ _ hostname _ path _ _) (uri-parse uri) ;;http://localhost/rfc/rfc1.txtなら、doc-idはrfc1.txt。 (define doc-id (receive (_ name ext) (decompose-path path) (string-append name "." ext))) (call-with-process-io (string-append "tr -c '[:alnum:]' '[\n*]' | grep -v '^[0-9]*$' | sort -iu | sed \"s/.*/& " doc-id "/\"") (lambda (in out) ;;URIをフェッチして、シェルスクリプトにパイプで渡す。 (http-get hostname path :sink out :flusher (lambda _ #t)) (close-output-port out) ;;シェルスクリプトの結果を標準出力に渡す。 (copy-port in (standard-output-port)))))) read-line) (exit))
Reducerの解説(reducer.scm)
GoogleのMapReduceは、Reducerはkey valuesを処理するが、
Hadoop Streamingでは、標準入力からこのようにvaluesが分解して入ってくる。
A rfc1.txt
A rfc2.txt
A rfc4.txt
A rfc3.txt
AAA rfc1.txt
なので、プログラマが自分の手で、valuesの形に直す必要がある。
Hadoopは、keyでソートしてからReducerに渡すことになっているので、
1行前のkeyと見比べて同じならvaluesに追加、そこで違っていたら、蓄えたvaluesでreducerを呼ぶという簡単な処理でよい。(そりゃ、もしもソートしてなければ巨大なハッシュテーブルを作るはめになって、MapReduceの意味がないわけだが)
ここでは、valuesの形に直してくれる、call-with-reducerという簡単なラッパーを作った。
(define (call-with-reducer proc) (define key "") (define vals (list)) (define (f! line) (rxmatch-let (#/^(\S*)\s(\S*)/ line) (#f k v) (if (string=? key k) (push! vals v) (begin (and (not (null? vals)) (proc key (reverse! vals))) (set! vals (list v)) (set! key k))))) (port-for-each f! read-line) (f! " ")) (define (main args) (call-with-reducer (lambda (key vals) (print key #\tab (string-join vals ",")))) (exit))
