bash + awk で TF-IDF を書いてみた

# TF-IDFとは
よく知らんが文章中の単語の重要度を測る指標らしい。

## なぜTF-IDFなのか
一番簡単そうだったから。実装に時間がかからなそうな気がしたので。

### 材料

* MeCab
* bash
* awk

## 作り方 捕捉
一応並列処理屋さんのはしくれなので並列処理をしました。

### 文章の単語のリストを作る
作り方はかんたんに言うと
    `TF=[cat 文章|MeCab|sort|uniq -c]`を作ります
        こんな感じ
```bash:samplecode-1
cat 文章 | 前処理 | MeCab | sort | uniq -c | awk -f tf.awk > TFの一覧
```
```awk:tf.awk
{
c = "" ; for(i=2;i<=NF;i++) c=c $i" "
DIC[c] +=$1 
}
END {
	for (str in DIC) N+=DIC[str]
	for (str in DIC) printf "%10.9f %s\n",DIC[str]/N,str
}
```
要するに、`uniq -c` の処理で出て来た`出現回数 単語の詳細`という列を取り出しそれを基にTFを求めます。
一例を出すとするとこんな感じ
```
12928  ある 助動詞,*,*,*,五段・ラ行アル,基本形,ある,アル,アル
```
この集合を単語帳TFとします。

次に、
`DF=[cat 文章 | MeCab|sort|uniq]`で得られる各文章の単語一覧を単語帳TFで出て来た単語と照らし合わせて単語帳TFに出て来た単語と一致するものをカウントしていきます。

ここで並列化をします。対象になっている文章ファイルたちを並列で処理します。こんな感じ

```bash
find ${文章の入っているディレクトリ} -name \*.txt | xargs -I {} -P 並列数 TF計測プログラム {} 
```

そしたら、単語帳TFに入っている単語一覧を並列数でsplitします。

```bash
split -n l/並列数 単語帳TF tfidf_tmp.
```
こうすると並列数の数に分割されたファイルができます。

あとは、DFを計算するためにもう一度並列化します。
```bash
find ./ -name tfidf_tmp.\* | xargs -I {} -P 並列数 ./tf-idf_p {} 全文章の一覧 一時ファイル置き場
```

こうすることで、一時ファイル置き場に全文章から単語帳TFに記載されているものと一致した単語が記載されたファイルが書かれるようにします。

あとは、

```bash
while read FILE
do
	cat < ${FILE} >> DF一覧
done <一時ファイル置場にある一時ファイル
```
### ビバ!!連想配列

ここで連想配列が効果を発揮してくれます。
たとえば、

```
11228  自分 名詞,一般,*,*,*,*,自分,ジブン,ジブン
```

の様に「出現回数 単語」の順で並んでいるデータを扱っていきます。

```bash
while read LINE
do
	l=$(echo ${LINE} | cut -d " " -f2-)
	df=$(echo ${LINE} | cut -d " " -f1)
	DF["${l}"]=${df}
done < ${TMPFILE}
```
ご覧になればわかるかと思いますが、連想配列のインデックスは単語で、その持つ値は全文章での出現回数になります。
これを単語帳TFの単語とすると、こう計算されます、

```
TF=単語帳TFの持っているTF
DF=単語帳TFの持っている単語と一致したDF(連装配列で取ってくる)
N=総文章数
TFIDF=TF×log((N+1)/(DF+1))
```
DF+1はDFが0の時除算できないのを防ぐためです。

これでTF-IDFが計算できます。時間は青空文庫

https://github.com/aozorahack/aozorabunko_text

に登録されている文章全体とその文章からひとつ適当に選んだ文章をつかって計算させると

```
Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
```

を使用して8並列で行った時に

```
Making TF-IDF from 17161 Text file(s)(8 proc(s)).
real    15m21.721s
user    109m8.239s
sys     7m32.863s
```
となりました。チャンチャン、ではないのです。

## これで終わりだと思うなよ。AWK満載のTF-IDFの作り方。

先の方法でもまぁまぁ速いですが、もう少し頑張ってみます。
AWKでもう少し早くならんかなぁと思ったので、書いてみました。

### やっぱりビバ!!連想配列

ここでも連装配列が役に立ちます。

```awk:tf.awk
#!/usr/bin/awk -f
{
	str = "" ; for ( i=2 ; i <= NF ; i++ ) str = str" "$i
	MOR[str]+=$1
}
END {
	for ( str in MOR ) N += MOR[str]
	for ( str in MOR ) printf "%10.9f %s\n", MOR[str]/N,str
}
```
前半部分で単語と詳細な情報をすべて半角スペースで区切って書き出します。もちろん値は`uniq -c`で取ってきた値を入れておいてENDの部分で連装配列による加算をしています。

これを応用すると素晴らしく簡単にいろいろ書けます。
まずは、DFの求め方。

```awk:df.wak
#!/usr/bin/awk -f
BEGIN {
    while ((getline < "/dev/stdin") > 0) {str =""; for ( i=1 ; i <= NF ; i++ ) str = str" "$i;WORDS[str]=0;}
	for ( arg in ARGV ){ while ( ( getline < ARGV[arg] )>0){str = ""; for ( i=1 ; i <= NF ; i++ ) str = str" "$i; if (str in WORDS){WORDS[str]+=1;}}}
	for ( word in WORDS) printf "%d %s\n",WORDS[word],word
}
```
標準入力から単語帳TFのデータを取得し、DFの計算に使います。そして引数に全文章を羅列する様にします。どうやるかは以下の通りです。

```bash:tfidf
split -n l/並列数 単語帳TF  一時フォルダ/target.part.
find 全文章が入ったフォルダ -name \*.txt -type f | xargs -I {} -P 並列数 ./bin/mkwords {}
find 一時フォルダ -name target.part.\* -type f | xargs -I {} -P 並列数 ./bin/dfpart {} 
```

```bash:mkwords
#!/bin/bash
cat 文章ファイル | mecab | sort | uniq > $(mktemp 一時フォルダ/words.XXXXXX.txt)
```

```bash:dfpart
#!/bin/bash
cat 単語帳TF | ./bin/df.awk $(find 一時フォルダ -name words.\*.txt) > $(mktemp 一時フォルダ/dfparts.XXXXXX.txt)
```

そしてdf.awkで連装配列を使ってデータを取りまとめます。
```awk:df.awk
#!/usr/bin/awk -f
BEGIN {
    while ((getline < "/dev/stdin") > 0) {str =""; for ( i=1 ; i <= NF ; i++ ) str = str" "$i;WORDS[str]=0;}
	for ( arg in ARGV ){ while ( ( getline < ARGV[arg] )>0){str = ""; for ( i=1 ; i <= NF ; i++ ) str = str" "$i; if (str in WORDS){WORDS[str]+=1;}}}
	for ( word in WORDS) printf "%d %s\n",WORDS[word],word
}
```
ざっとこんな感じです。これを実行すると…。

```bash
Calc TF-IDF from 17161 files in 8 parallels.
real    6m2.957s
user    42m19.169s
sys     3m41.690s
```
ほら、短くなった。速くなりましたね。
まだまだ改良の余地はありますが、最初1日でも終わらない気がしていた15000オーバーの文章からのTF-IDFの計算が10分もしないうちに終えることができるなんて夢にも思っていませんでした。

ちなみに、ここまで到達するに何日かかかりました。orz

今回のミソは、
単語帳TFを分割して並列化させたところ
です。
何故かというと、照合する文章群を分割したところで、その後のマージに時間がかかるからです。

単語帳TFのデータを分割したら、各文章から出来上がるDFのパーツをあとでマージするときに、
```bash:tfidf
while read FILE
do
    cat < ${FILE} >> ${DF}
done < DFの元ファイル群
```
だけで済むからです。

改良したらまた書きます。もう少し速くできるかと思います。

## まだだ、まだ終わらんよ
実行していて気がつきました。後半の処理より前半の処理に時間がかかっていることを、
そこで、ちょっと計測しました。
プログラムはこんな感じ

```bash:test1.sh
#!/bin/bash
LIST=$(mktemp)
find ${1} -type f -name \*.txt > ${LIST}
./test2.sh ${LIST}
```
```bash:test2.sh その1
#!/bin/bash
tmp=$(mktemp)
wc -l ${1}
while read FILE
do
        iconv -f SHIFT_JISX0213 -t UTF-8 ${FILE}> ${tmp}
        #mecab -b $(wc -c ${tmp}) ${tmp} > /dev/null #|sort|uniq >/dev/null
done < ${1}
```
この実行時間は
```bash
$ time ./test.sh aozorabunko_text-master/cards/
17161 /tmp/tmp.iTu7SpdAD0

real    0m20.389s
user    0m11.735s
sys     0m8.602s
```
```bash:test2.sh その2
#!/bin/bash
tmp=$(mktemp)
wc -l ${1}
while read FILE
do
        iconv -f SHIFT_JISX0213 -t UTF-8 ${FILE}> ${tmp}
        mecab -b $(wc -c ${tmp}) ${tmp} > /dev/null #|sort|uniq >/dev/null
done < ${1}
```
この実行時間は
```bash
$ time ./test.sh aozorabunko_text-master/cards/
17161 /tmp/tmp.tGDGBx3rnZ

real    3m30.766s
user    2m35.250s
sys     0m57.698s
```
```bash:test2.sh その3
#!/bin/bash
tmp=$(mktemp)
wc -l ${1}
while read FILE
do
        iconv -f SHIFT_JISX0213 -t UTF-8 ${FILE}> ${tmp}
        mecab -b $(wc -c ${tmp}) ${tmp} |sort >/dev/null #|uniq >/dev/null
done < ${1}
```
この実行時間は
```bash
$ time ./test.sh aozorabunko_text-master/cards/
17161 /tmp/tmp.26ap8fTWtw

real    33m39.201s
user    32m52.530s
sys     1m24.546s
```
あひゃ、ってことは…

### ソートに相当時間がかかっていました
もう、`uniq`やるまでもないですね、たぶん。これ以上時間を費やさないためにも、この`sort`コマンドをなんとかせにゃなりません。
そこで考えました。
「必要なのはソート機能ではなくてこの文章でユニークな形態素示す機能である」と。
ですので、`sort|uniq`に変わる機能をAWKで作成しました。
それが、これです。もうお馴染みですよね？
```awk:uniq.awk
#!/usr/bin/awk -f
BEGIN{
        while((getline < "/dev/stdin") > 0)
        {
            str = $1"\t";
            for(i=2;i<=NF;i++)
            {
                str = str $i" ";
            }
            UNIQ[str]+=1
        }
        for( str in UNIQ )
        {
            printf "%s\n",str;
        }
}
```
これで実行してみましょう。
さきほどのスクリプトを改造してこうします。
```bash:test2.sh その4
#!/bin/bash
tmp=$(mktemp)
wc -l ${1}
while read FILE
do
        iconv -f SHIFT_JISX0213 -t UTF-8 ${FILE}> ${tmp}
        mecab -b $(wc -c ${tmp}) ${tmp} |./uniq.awk >/dev/null
done < ${1}
```
…、さて、実行時間は…？
```bash
$ time ./test.sh aozorabunko_text-master/cards/
17161 /tmp/tmp.XbLP8OousD

real    3m39.679s
user    4m41.474s
sys     1m9.672s
```
おぉ、10倍くらい速い。
ってことで`sort`コマンドは捨てawkスクリプトに交換してTF-IDFを再度計測。
```bash
$ time ./tfidf
Calc TF-IDF from 17161 text file(s) in 8 proc(s).Temp dir is /tmp/nlp.zaawXQG

real    1m54.402s
user    10m53.186s
sys     3m33.032s
```
あひゃ、3倍近く速くなった。ってことでだいぶ速くなりました。