検索インデックスを作ろう前編〜シェルスクリプトの力〜

1行のシェルスクリプトで単語リストを作る

TAOUP:7.2 Pipes, Redirection, and Filtersを参考にした。

tr -c '[:alnum:]' '[\n*]' | grep -v '^[0-9]*$' | sort -iu

1番めのコマンドで、アルファベット数字以外を改行に変換する。
2番めのコマンドで、数字だけの行を消す。
3番めのコマンドで、行をソートする、ついでに重複を省く。
これで単語リストができる。

文書群はRFCを用いる。英文テキスト243MB。ftp://ftp.rfc-editor.org/in-notes/tar/RFC-all.tar.gz

rfc1.txtの単語リストを作ってみる。(

<rfc1.txt tr -c '[:alnum:]' '[\n*]' | grep -v '^[0-9]*$' | sort -iu

A
ARPA
Additionally
After
Again
...
would
write
written
x
yet

さらに、単語の出現回数をつけてみる。

<rfc1.txt tr -c '[:alnum:]' '[\n*]' | grep -v '^[0-9]*$' | sort -i | uniq -c

8 A
1 ARPA
1 Additionally
4 After
1 Again
...
10 would
2 write
1 written
1 x
1 yet

各文書を処理する。rfc1.txtのインデックスのファイル名はrfc1.txt.idx。

for file in *.txt; do 
  <$file tr -c '[:alnum:]' '[\n*]' | grep -v '^[0-9]*$' | sort -i | uniq -c >$file.idx
done

インデックスが完成した。さっそくキーワードcoffeeで検索してみよう。grepではなくfgrepを使うと速い。fgrepの結果を、単語の出現回数でソートする。

fgrep coffee *.idx | sort -nk2

rfc1259.txt.idx: 1 coffee
rfc1727.txt.idx: 1 coffee
rfc2905.txt.idx: 1 coffee
rfc4555.txt.idx: 1 coffee
rfc549.txt.idx: 1 coffee
rfc82.txt.idx: 1 coffee
rfc909.txt.idx: 1 coffee
rfc1391.txt.idx: 2 coffee
rfc1539.txt.idx: 2 coffee
rfc1718.txt.idx: 2 coffee
rfc2399.txt.idx: 2 coffee
rfc4485.txt.idx: 2 coffee
rfc546.txt.idx: 2 coffee
rfc2324.txt.idx: 3 coffeepot
rfc3160.txt.idx: 3 coffee
rfc4589.txt.idx: 3 coffee
rfc4677.txt.idx: 4 coffee
rfc2325.txt.idx: 14 coffee
rfc2324.txt.idx: 62 coffee

rfc2324はHyper Text Coffee Pot Control Protocol (HTCPCP/1.0)
だから、うまく動いている。

インデックス作成には、Thinkpad X60で5分かかった。

time fgrep coffee *.idx
real	0m0.335s
user	0m0.264s
sys	0m0.072s
インデックスを使っての検索は0.3秒。

time fgrep coffee *.txt
real	0m0.607s
user	0m0.456s
sys	0m0.152s
直接にファイルを検索は0.6秒。