Splunkを利用したテキストマイニングもどき

さて、前回の記事で、PerlからLTSV形式のフォーマットを扱う方法を書いた。

http://rn.hatenablog.com/entry/2013/12/07/012621

そのとき、自然言語処理の分野での適用をぼんやり考えていて、単語とか品詞とか簡単に集計できる仕組みがあると役立つかなと思った。現状、こういったことを簡単にやろうと思っても、それっぽい専用ソフトが必要なので、やりにくいかなと思う。

そこで、Jumanで抽出した形態素解析情報をLTSV形式で表現し、Splunkでビジュアルに扱う方法について書いてみたいと思う。現状、かなり試行錯誤だし、ベストプラクティスを発見できていないが、せっかく試したので書いてみる。というのも、Splunkをテキストマイニングっぽく使うというのは、あまり聞いたことがないからだ。

さて、Splunkというソフトを知っているだろうか?私も最近知ったが、主にログを解析するためのソフトである。日本だと、大手SIerが積極的に扱っている。ただし、大規模なデータを扱うのでなければ、フリーでも利用することができる。

例えば、日本語のホームページは以下にある。

http://ja.splunk.com/

右上にあるダウンロードボタンからダウンロードすることができる。プラットフォームは、WindowsとLinuxとMacなどがある。今回は、Cent OSを利用したので、32bitのLinux版をダウンロードした。ソースからでもrpmからでもどちらでもインストールすることができる。

データとしては、日本語のWikipediaの情報を利用した。Wikipediaからのテキストの抽出については、以下を参照してください。

http://rn.hatenablog.com/entry/2012/09/09/003001

まず、結論からすると、結果の画面は以下のようになった。

f:id:ryokkie:20131209022210p:plain

形態素をテキストごとに表示している。任意のキーワードで検索できるし、その形態素解析結果も見やすいのではないだろうか。

また、以下ののように、もう少し視覚的に、どの品詞がどのぐらい使われているか?ということも見ることができる。

f:id:ryokkie:20131209022223p:plain

さらに、上位10件を表示するコマンドを利用すると、グラフも一発で作成できる。

f:id:ryokkie:20131209022235p:plain

次に、どうやってこんな処理をSplunkで行うか?について説明しておく。私は、Jumanがけっこう好きなので、Jumanを利用したが、別にMeCabでもKyTeaでも問題ない。Splunk自体は、DWHと可視化がセットになっているだけなので、解析器自体はなんでも良い。

まず、Jumanを使って、解析結果を以下のようなLTSV形式にしておく。

base_file_name:txt/00027.txt    title:自然言語  line_no:3       str:「自然言語」という語は特に数式やプログラミング言語など人工的に定義された形式言語・人工言語に対比させる必要がある場合にこ う呼ばれる。    mrph_000_midasi:「      mrph_000_yomi:「        mrph_000_genkei:「      mrph_000_hinsi:特殊     mrph_000_hinsi_id:1     mrph_000_bunrui:括弧始  mrph_000_bunrui_id:3    mrph_000_katuyou1:*  mrph_000_katuyou1_id:0  mrph_000_katuyou2:*     mrph_000_katuyou2_id:0  mrph_000_imis:NIL       mrph_001_midasi:自然    mrph_001_yomi:しぜん    mrph_001_genkei:自然    mrph_001_hinsi:副詞  mrph_001_hinsi_id:8     mrph_001_bunrui:*       mrph_001_bunrui_id:0    mrph_001_katuyou1:*     mrph_001_katuyou1_id:0  mrph_001_katuyou2:*     mrph_001_katuyou2_id:0  mrph_001_imis:"代表表記:自然/しぜん 修飾(ト格)"    mrph_002_midasi:言語    mrph_002_yomi:げんご    mrph_002_genkei:言語    mrph_002_hinsi:名詞     mrph_002_hinsi_id:6     mrph_002_bunrui:普通 名詞    mrph_002_bunrui_id:1    mrph_002_katuyou1:*     mrph_002_katuyou1_id:0  mrph_002_katuyou2:*     mrph_002_katuyou2_id:0  mrph_002_imis:"代表表記:言語/げんご カテゴリ:抽象物"    mrph_003_midasi:」   mrph_003_yomi:」        mrph_003_genkei:」      mrph_003_hinsi:特殊     mrph_003_hinsi_id:1     mrph_003_bunrui:括弧終  mrph_003_bunrui_id:4    mrph_003_katuyou1:*     mrph_003_katuyou1_id:0       mrph_003_katuyou2:*     mrph_003_katuyou2_id:0  mrph_003_imis:NIL       mrph_004_midasi:と      mrph_004_yomi:と        mrph_004_genkei:と      mrph_004_hinsi:助詞  mrph_004_hinsi_id:9     mrph_004_bunrui:格助詞  mrph_004_bunrui_id:1    mrph_004_katuyou1:*     mrph_004_katuyou1_id:0  mrph_004_katuyou2:*     mrph_004_katuyou2_id:0  mrph_004_imis:NIL    mrph_005_midasi:いう    mrph_005_yomi:いう      mrph_005_genkei:いう    mrph_005_hinsi:動詞     mrph_005_hinsi_id:2     mrph_005_bunrui:*       mrph_005_bunrui_id:0    mrph_005_katuyou1:子 音動詞ワ行      mrph_005_katuyou1_id:12 mrph_005_katuyou2:基本形        mrph_005_katuyou2_id:2  mrph_005_imis:"代表表記:言う/いう 補文ト"       mrph_006_midasi:語      mrph_006_yomi:ご     mrph_006_genkei:語      mrph_006_hinsi:名詞     mrph_006_hinsi_id:6     mrph_006_bunrui:普通名詞        mrph_006_bunrui_id:1    mrph_006_katuyou1:*     mrph_006_katuyou1_id:0  mrph_006_katuyou2:*  mrph_006_katuyou2_id:0  mrph_006_imis:"代表表記:語/ご 漢字読み:音 カテゴリ:抽象物"      mrph_007_midasi:は      mrph_007_yomi:は        mrph_007_genkei:は      mrph_007_hinsi:助詞  mrph_007_hinsi_id:9     mrph_007_bunrui:副助詞  mrph_007_bunrui_id:2    mrph_007_katuyou1:*     mrph_007_katuyou1_id:0  mrph_007_katuyou2:*     mrph_007_katuyou2_id:0  mrph_007_imis:NIL    mrph_008_midasi:特に    mrph_008_yomi:とくに    mrph_008_genkei:特に    mrph_008_hinsi:副詞     mrph_008_hinsi_id:8     mrph_008_bunrui:*       mrph_008_bunrui_id:0    mrph_008_katuyou1:*  mrph_008_katuyou1_id:0  mrph_008_katuyou2:*     mrph_008_katuyou2_id:0  mrph_008_imis:"代表表記:特に/とくに 用言弱修飾" mrph_009_midasi:数式    mrph_009_yomi:すうしき  mrph_009_genkei:数式 mrph_009_hinsi:名詞     mrph_009_hinsi_id:6     mrph_009_bunrui:普通名詞        mrph_009_bunrui_id:1    mrph_009_katuyou1:*     mrph_009_katuyou1_id:0  mrph_009_katuyou2:*     mrph_009_katuyou2_id:0       mrph_009_imis:"代表表記:数式/すうしき カテゴリ:抽象物 ドメイン:教育・学習"      mrph_010_midasi:や      mrph_010_yomi:や        mrph_010_genkei:や      mrph_010_hinsi:助詞  mrph_010_hinsi_id:9     mrph_010_bunrui:接続助詞        mrph_010_bunrui_id:3    mrph_010_katuyou1:*     mrph_010_katuyou1_id:0  mrph_010_katuyou2:*     mrph_010_katuyou2_id:0  mrph_010_imis:NIL    mrph_011_midasi:プログラミング  mrph_011_yomi:ぷろぐらみんぐ    mrph_011_genkei:プログラミング  mrph_011_hinsi:名詞     mrph_011_hinsi_id:6     mrph_011_bunrui:サ変名詞        mrph_011_bunrui_id:2 mrph_011_katuyou1:*     mrph_011_katuyou1_id:0  mrph_011_katuyou2:*     mrph_011_katuyou2_id:0  mrph_011_imis:"代表表記:プログラミング/ぷろぐらみんぐ カテゴリ:抽象物 ドメイ ン:科学・技術"  mrph_012_midasi:言語    mrph_012_yomi:げんご    mrph_012_genkei:言語    mrph_012_hinsi:名詞     mrph_012_hinsi_id:6     mrph_012_bunrui:普通名詞        mrph_012_bunrui_id:1 mrph_012_katuyou1:*     mrph_012_katuyou1_id:0  mrph_012_katuyou2:*     mrph_012_katuyou2_id:0  mrph_012_imis:"代表表記:言語/げんご カテゴリ:抽象物"    mrph_013_midasi:など    mrph_013_yomi:など   mrph_013_genkei:など    mrph_013_hinsi:助詞     mrph_013_hinsi_id:9     mrph_013_bunrui:副助詞  mrph_013_bunrui_id:2    mrph_013_katuyou1:*     mrph_013_katuyou1_id:0  mrph_013_katuyou2:*  mrph_013_katuyou2_id:0  mrph_013_imis:NIL       mrph_014_midasi:人工    mrph_014_yomi:じんこう  mrph_014_genkei:人工    mrph_014_hinsi:名詞     mrph_014_hinsi_id:6     mrph_014_bunrui:普通名詞     mrph_014_bunrui_id:1    mrph_014_katuyou1:*     mrph_014_katuyou1_id:0  mrph_014_katuyou2:*     mrph_014_katuyou2_id:0  mrph_014_imis:"代表表記:人工/じんこう カテゴリ:抽象物"       mrph_015_midasi:的に    mrph_015_yomi:てきに    mrph_015_genkei:的だ    mrph_015_hinsi:接尾辞   mrph_015_hinsi_id:14    mrph_015_bunrui:形容詞性名詞接尾辞      mrph_015_bunrui_id:6 mrph_015_katuyou1:ナ形容詞      mrph_015_katuyou1_id:21 mrph_015_katuyou2:ダ列基本連用形        mrph_015_katuyou2_id:7  mrph_015_imis:"代表表記:的だ/てきだ 準内容語 カテゴリ:抽象物"   mrph_016_midasi:定義 mrph_016_yomi:ていぎ    mrph_016_genkei:定義    mrph_016_hinsi:名詞     mrph_016_hinsi_id:6     mrph_016_bunrui:サ変名詞        mrph_016_bunrui_id:2    mrph_016_katuyou1:*  mrph_016_katuyou1_id:0  mrph_016_katuyou2:*     mrph_016_katuyou2_id:0  mrph_016_imis:"代表表記:定義/ていぎ カテゴリ:抽象物 ドメイン:科学・技術"        mrph_017_midasi:さ      mrph_017_yomi:さ     mrph_017_genkei:する    mrph_017_hinsi:動詞     mrph_017_hinsi_id:2     mrph_017_bunrui:*       mrph_017_bunrui_id:0    mrph_017_katuyou1:サ変動詞      mrph_017_katuyou1_id:16 mrph_017_katuyou2:未然形     mrph_017_katuyou2_id:3  mrph_017_imis:"代表表記:する/する 付属動詞候補(基本) 自他動詞:自:成る/なる"   mrph_018_midasi:れた    mrph_018_yomi:れた      mrph_018_genkei:れる mrph_018_hinsi:接尾辞   mrph_018_hinsi_id:14    mrph_018_bunrui:動詞性接尾辞    mrph_018_bunrui_id:7    mrph_018_katuyou1:母音動詞      mrph_018_katuyou1_id:1  mrph_018_katuyou2:タ 形      mrph_018_katuyou2_id:10 mrph_018_imis:"代表表記:れる/れる"      mrph_019_midasi:形式    mrph_019_yomi:けいしき  mrph_019_genkei:形式    mrph_019_hinsi:名詞     mrph_019_hinsi_id:6  mrph_019_bunrui:普通名詞        mrph_019_bunrui_id:1    mrph_019_katuyou1:*     mrph_019_katuyou1_id:0  mrph_019_katuyou2:*     mrph_019_katuyou2_id:0  mrph_019_imis:"代表表記:形式/けいしき カテゴリ:抽象物"       mrph_020_midasi:言語    mrph_020_yomi:げんご    mrph_020_genkei:言語    mrph_020_hinsi:名詞     mrph_020_hinsi_id:6     mrph_020_bunrui:普通名詞        mrph_020_bunrui_id:1 mrph_020_katuyou1:*     mrph_020_katuyou1_id:0  mrph_020_katuyou2:*     mrph_020_katuyou2_id:0  mrph_020_imis:"代表表記:言語/げんご カテゴリ:抽象物"    mrph_021_midasi:・      mrph_021_yomi:・     mrph_021_genkei:・      mrph_021_hinsi:特殊     mrph_021_hinsi_id:1     mrph_021_bunrui:記号    mrph_021_bunrui_id:5    mrph_021_katuyou1:*     mrph_021_katuyou1_id:0  mrph_021_katuyou2:*  mrph_021_katuyou2_id:0  mrph_021_imis:NIL       mrph_022_midasi:人工    mrph_022_yomi:じんこう  mrph_022_genkei:人工    mrph_022_hinsi:名詞     mrph_022_hinsi_id:6     mrph_022_bunrui:普通名詞     mrph_022_bunrui_id:1    mrph_022_katuyou1:*     mrph_022_katuyou1_id:0  mrph_022_katuyou2:*     mrph_022_katuyou2_id:0  mrph_022_imis:"代表表記:人工/じんこう カテゴ リ:抽象物"      mrph_023_midasi:言語    mrph_023_yomi:げんご    mrph_023_genkei:言語    mrph_023_hinsi:名詞     mrph_023_hinsi_id:6     mrph_023_bunrui:普通名詞        mrph_023_bunrui_id:1 mrph_023_katuyou1:*     mrph_023_katuyou1_id:0  mrph_023_katuyou2:*     mrph_023_katuyou2_id:0  mrph_023_imis:"代表表記:言語/げんご カテゴリ:抽象物"    mrph_024_midasi:に      mrph_024_yomi:に     mrph_024_genkei:に      mrph_024_hinsi:助詞     mrph_024_hinsi_id:9     mrph_024_bunrui:格助詞  mrph_024_bunrui_id:1    mrph_024_katuyou1:*     mrph_024_katuyou1_id:0  mrph_024_katuyou2:*  mrph_024_katuyou2_id:0  mrph_024_imis:NIL       mrph_025_midasi:対比    mrph_025_yomi:たいひ    mrph_025_genkei:対比    mrph_025_hinsi:名詞     mrph_025_hinsi_id:6     mrph_025_bunrui:サ変名詞     mrph_025_bunrui_id:2    mrph_025_katuyou1:*     mrph_025_katuyou1_id:0  mrph_025_katuyou2:*     mrph_025_katuyou2_id:0  mrph_025_imis:"代表表記:対比/たいひ カテゴリ:抽象物" mrph_026_midasi:さ      mrph_026_yomi:さ        mrph_026_genkei:する    mrph_026_hinsi:動詞     mrph_026_hinsi_id:2     mrph_026_bunrui:*       mrph_026_bunrui_id:0    mrph_026_katuyou1:サ 変動詞  mrph_026_katuyou1_id:16 mrph_026_katuyou2:未然形        mrph_026_katuyou2_id:3  mrph_026_imis:"代表表記:する/する 付属動詞候補(基本) 自他動詞:自:成る/なる"   mrph_027_midasi:せる mrph_027_yomi:せる      mrph_027_genkei:せる    mrph_027_hinsi:接尾辞   mrph_027_hinsi_id:14    mrph_027_bunrui:動詞性接尾辞    mrph_027_bunrui_id:7    mrph_027_katuyou1:母音動詞      mrph_027_katuyou1_id:1       mrph_027_katuyou2:基本形        mrph_027_katuyou2_id:2  mrph_027_imis:"代表表記:せる/せる"      mrph_028_midasi:必要    mrph_028_yomi:ひつよう  mrph_028_genkei:必要 だ      mrph_028_hinsi:形容詞   mrph_028_hinsi_id:3     mrph_028_bunrui:*       mrph_028_bunrui_id:0    mrph_028_katuyou1:ナノ形容詞    mrph_028_katuyou1_id:22 mrph_028_katuyou2:語幹  mrph_028_katuyou2_id:1       mrph_028_imis:"代表表記:必要だ/ひつようだ 反義:形容詞:不要だ/ふようだ"  mrph_029_midasi:が      mrph_029_yomi:が        mrph_029_genkei:が      mrph_029_hinsi:助詞  mrph_029_hinsi_id:9     mrph_029_bunrui:格助詞  mrph_029_bunrui_id:1    mrph_029_katuyou1:*     mrph_029_katuyou1_id:0  mrph_029_katuyou2:*     mrph_029_katuyou2_id:0  mrph_029_imis:NIL    mrph_030_midasi:ある    mrph_030_yomi:ある      mrph_030_genkei:ある    mrph_030_hinsi:動詞     mrph_030_hinsi_id:2     mrph_030_bunrui:*       mrph_030_bunrui_id:0    mrph_030_katuyou1:子 音動詞ラ行      mrph_030_katuyou1_id:10 mrph_030_katuyou2:基本形        mrph_030_katuyou2_id:2  mrph_030_imis:"代表表記:有る/ある 補文ト 反義:形容詞:無い/ない" mrph_031_midasi:場合    mrph_031_yomi:ばあい mrph_031_genkei:場合    mrph_031_hinsi:名詞     mrph_031_hinsi_id:6     mrph_031_bunrui:副詞的名詞      mrph_031_bunrui_id:9    mrph_031_katuyou1:*     mrph_031_katuyou1_id:0       mrph_031_katuyou2:*     mrph_031_katuyou2_id:0  mrph_031_imis:"代表表記:場合/ばあい"    mrph_032_midasi:に      mrph_032_yomi:に        mrph_032_genkei:に      mrph_032_hinsi:助詞  mrph_032_hinsi_id:9     mrph_032_bunrui:格助詞  mrph_032_bunrui_id:1    mrph_032_katuyou1:*     mrph_032_katuyou1_id:0  mrph_032_katuyou2:*     mrph_032_katuyou2_id:0  mrph_032_imis:NIL    mrph_033_midasi:こう    mrph_033_yomi:こう      mrph_033_genkei:こう    mrph_033_hinsi:指示詞   mrph_033_hinsi_id:7     mrph_033_bunrui:副詞形態指示詞  mrph_033_bunrui_id:3    mrph_033_katuyou1:*  mrph_033_katuyou1_id:0  mrph_033_katuyou2:*     mrph_033_katuyou2_id:0  mrph_033_imis:NIL       mrph_034_midasi:呼ば    mrph_034_yomi:よば      mrph_034_genkei:呼ぶ    mrph_034_hinsi:動詞  mrph_034_hinsi_id:2     mrph_034_bunrui:*       mrph_034_bunrui_id:0    mrph_034_katuyou1:子音動詞バ行  mrph_034_katuyou1_id:8  mrph_034_katuyou2:未然形        mrph_034_katuyou2_id:3       mrph_034_imis:"代表表記:呼ぶ/よぶ"      mrph_035_midasi:れる    mrph_035_yomi:れる      mrph_035_genkei:れる    mrph_035_hinsi:接尾辞   mrph_035_hinsi_id:14    mrph_035_bunrui:動詞 性接尾辞        mrph_035_bunrui_id:7    mrph_035_katuyou1:母音動詞      mrph_035_katuyou1_id:1  mrph_035_katuyou2:基本形        mrph_035_katuyou2_id:2  mrph_035_imis:"代表表記:れる/れる"   mrph_036_midasi:。      mrph_036_yomi:。        mrph_036_genkei:。      mrph_036_hinsi:特殊     mrph_036_hinsi_id:1     mrph_036_bunrui:句点    mrph_036_bunrui_id:1    mrph_036_katuyou1:*  mrph_036_katuyou1_id:0  mrph_036_katuyou2:*     mrph_036_katuyou2_id:0  mrph_036_imis:NIL

ちなみに、PerlからJumanを利用する場合は、Juman.pmを利用するのが便利である。それについては、別の記事で書く。

さて、こんな感じでLTSV形式のフォーマットを用意したら、Splunkで読み込むだけである。ただし、Splunkは、LTSV形式のファイルを読み込むことができないので、自分で解析フォーマットを用意する。解析フォーマットは、以下を参考にした。

https://gist.github.com/takscape/4736182

ただし、このままだと、genkeiとかがすべて分かれたものしかできないので、マージしたファセット項目を作成した方が良い。結局、以下のようにする。

# props.conf
[ltsv]
NO_BINARY_CHECK = 1
REPORT-ltsv = ltsv-extractions
REPORT-genkei = jgenkei-extractions
REPORT-hinsi = jhinsi-extractions
REPORT-bunrui = jbunrui-extractions
SHOULD_LINEMERGE = false
TIME_FORMAT = %d/%b/%Y:%H:%M:%S %z
TIME_PREFIX = time:
pulldown_type = 1

# transforms.conf
[ltsv-extractions]
REGEX = (?:^|\t)([0-9A-Za-z_.-]+):([^\t]*)(?:\t|$)
FORMAT = $1::$2
KEEP_EMPTY_VALS = true
CLEAN_KEYS = 0

[jgenkei-extractions]
REGEX = (?:^|\t)(mrph_[0-9]+_genkei):([^\t]*)(?:\t|$)
FORMAT = genkei::$2
REPEAT_MATCH = true
KEEP_EMPTY_VALS = true
CLEAN_KEYS = 0
MV_ADD = 1

[jhinsi-extractions]
REGEX = (?:^|\t)(mrph_[0-9]+_hinsi):([^\t]*)(?:\t|$)
FORMAT = hinsi::$2
REPEAT_MATCH = true
KEEP_EMPTY_VALS = true
CLEAN_KEYS = 0
MV_ADD = 1

[jbunrui-extractions]
REGEX = (?:^|\t)(mrph_[0-9]+_bunrui):([^\t]*)(?:\t|$)
FORMAT = bunrui::$2
REPEAT_MATCH = true
KEEP_EMPTY_VALS = true
CLEAN_KEYS = 0
MV_ADD = 1

これを、以下のフォルダの2つのファイル追加する。なければ、ファイルを作成する。

/opt/splunk/etc/system/local/props.conf
/opt/splunk/etc/system/local/transforms.conf

これで、あとは、LTSV形式にしたWikipediaのデータを読み込むとSplunkの機能で検索したり、集計したり、グラフ作ったりできるようになる。ちなみに、Splunkは、UnixコマンドとSQLを足して2で割ったような操作性であり、そこにstatsコマンドという統計処理用のコマンドで機能を強化している。コマンドリファレンスは、以下にあるので、参考にしてみてください。

http://docs.splunk.com/images/7/78/SearchReference_JA_502.pdf

Splunkの本来の用途であるログ解析から離れて、テキストマイニングもどきに強引に適用してみるということをやってみた。今回は、Wikipediaのデータでやってみたが、時系列が重要なデータだとより良いと思う。というのも、Splunk自体は、時刻を自動でキーにして、時系列の変化を自動でグラフ化してくれるからだ。それを考えると、Twitterなどのデータの方がもっと有益かもしれない。

Perlメモ(2)

Perlを触りだすと、自分のネイティブプログラミング言語は、Perlだなと実感します。ただ、Perlに限らず、プログラムは好きなので、9時~17時の労働で、プログラムだけ書いて適当に過ごせないものかと思うが、日本では難しいようだ。がんばるしかない。

さて、自分は、学生の時から入力ファイルと出力ファイルを残しながらプログラムを作っていくということをやっている。どういうことかというと、

cat input1.txt | ./1.pl > output1.txt
cat output1.txt | ./2.pl > output2.txt
cat output2.txt | ./3.pl > output3.txt

みたいな感じで、中間結果を残しつつ加工している。もちろん、業務で必要とされているプログラムでこんなことはしない。ただ、研究の時のように、結果を見ながら試行錯誤が必要なプログラムでは、このようなやり方の方が、中間結果をいつでも確認できて、都合が良い。

しかし、このスタイルの問題点として、中間結果のフォーマットを決めるのがめんどうだということがある。例えば、CSVだと、地味にParser書くのがめんどうだし、tsvだと、フォーマットの間に値を格納したくなった場合に、後のプログラムを全部直さなくてはならなくてなかなかめんどうである。

そんな時に、LTSV形式というフォーマットに出会いました。

http://ltsv.org/

このフォーマットがなかなか便利である。良い点は、以下の記事にまとまっている。

http://d.hatena.ne.jp/naoya/20130209/1360381374

さて、Perlで扱う場合は、Text::LTSVというcpanモジュールを利用するのが便利である。

http://search.cpan.org/~naoya/Text-LTSV-0.07/lib/Text/LTSV.pm

では、この形式を自然言語処理に応用するとどうなるか?というのを明日やってみよう。うん。眠い。

Perlメモ(1)

最近、久しぶりにPerlを使ってみたが、UTF-8のデータの扱いで決定版みたいなのがネットではわからなかったので、いろいろと調べたことをメモしておく。PerlでのUTF-8のデータの処理のイメージとしては、Javaとかに近く、内部表現は、Unicodeで管理しているっぽい。Perl的には、UTF-8フラグとか言ってて、それが話をややこししくしている気がする。基本的には、

  1. UTF-8エンコードされたデータを入力する。
  2. Perlプログラムでデコードして、文字として扱える内部表現(Unicodeみたいなもの)に変換して、プログラムを実行する。
  3. 内部表現をUTF-8エンコードして出力する。

というだけなので、難しくない。Javaに近い。

また、実際にコードを書く時には、以下の2つの場合で、書き方を変える。

  1. マシンログのように、永久にASCIIの範囲の文字しか扱わない場合(バイト単位でデータを扱う場合)
  2. 日本語とかも扱う場合(文字単位でデータを扱う場合)

1.の場合、"use utf8;"とかせずに、いつも通りにperlプログラムを書けば良い。

#! /usr/bin/env perl

use strict;
use warnings;

みたいな感じで良いと思う。特に、入出力や正規表現で困ることもない。length関数などの動きも変わらない。ソースは、UTF-8で保存しておくと良い。

2.の場合、I/Oレイヤをutf8で扱って、入出力時に自動的に、decode/encodeしてくれる仕組みにしておくと楽である。

#! /usr/bin/env perl

use utf8;
# perlのIOレイヤーで自動的に標準入出力(STDIN、STDOUT、STDERR)をutf8対応にする。
# open時に自動で、decodeする。
# print時に自動で、encodeする。
use open qw(:std :utf8);

use strict;
use warnings;

# utf8のバイト単位ではなく、文字単位で処理する。
while ( <> ) {
  chomp;
  print "$_\n";
  print length($_), "\n";
}

open(my $fhi, "<", "text.txt") or die $!;
open(my $fho, ">", "out.txt") or die $!;
# 以下で直接指定しても良い。
#open(my $fh, "<:utf8", "text.txt") or die $!;
while ( <$fhi> ) {
  chomp;
  print $fho "$_\n";
  print $fho length($_), "\n";
}

としておけば、標準入出力時もファイル入出力時もdecode/encodeを気にしなくて良い。IO::Fileを使っていても、以下のようにすれば良い。

my $fhi = IO::File->new($path, "<:utf8") or die $!;
my $fho = IO::File->new($path, ">:utf8") or die $!;

UTF-8のデータをPerlの内部表現に正しく変換できれば、日本語で書かれたデータであってもきちんと扱うことができる。

統計処理の勉強メモ(1)

しばらく統計処理を勉強するつもりなので、ページを立ち上げてみる。そうやって放置されているページがブログ内に散見されるが、あまり気にしない。ただ、文法圧縮だけは、年内に完備辞書のライブラリを完成させて一区切りつける予定である。

ページの趣旨としては、私自身がRを使いこなせるようになりたいので、そのメモ用として書いていく。完全に素人なので、Rをインストールするところから始めている。とりあえず、R Studioをダウンロードした。

勉強の仕方はいろいろあると思いますが、私自身は、ブログに書いたりしている方がモチベーションが持続できるので、そういうやり方をしています。

とりあえず、当面の教科書は、以下としている。

マンガでわかる統計学

マンガでわかる統計学

マンガでわかる統計学 回帰分析編

マンガでわかる統計学 回帰分析編

マンガでわかる統計学 因子分析編

マンガでわかる統計学 因子分析編

上記の3冊は、統計素人の私にとって、どれも秀逸だった。最近、技術書コーナーには、萌え絵の技術書がたくさんあるが、その手の本とはレベルが違う。というのも、基本的に説明はマンガでしてくれる。最初に萌え絵があって、後は文字だけの技術書とそこが違う。また、題材に使う例が良い。身近な想像しやすい例を使って説明してくれるし、何なら本編の物語にもつながっている。道具として統計を学ぼうとしている人にとっての入門書に最適だと思う。逆に、数学が得意で、数学的側面からの統計に興味がある人は、古くからあるきちんとした数学の統計本を読む方が良いと思う。

なので、対象読者は、以下ぐらいの人だと思う。

  • とりあえず、仕事で統計が必要になったが、何から始めれば良いかわからない人
  • 数学は嫌いではないが、雰囲気を理解しつつ、統計で何ができるかてっとり早く理解したい人
  • 行列を一通り習った人
  • Excelが使える人
  • マンガが好きな人

ちなみに、行列の知識は、「マンガでわかる統計学」の方では不要ですが、回帰分析編と因子分析編を読むには、行列の知識があった方が楽です。また、「マンガでわかる統計学」の方では、Excelでいろんな計算をしていますが、私自身がRを勉強しようと思っているため、Rで同じことをやってみるつもりです。ちょっと調べたら、Rで主成分分析とか因子分析とかできそうでした。

文法圧縮(4)

前回、紹介した論文で、かなりざっくりとRe-Pairを実装してみた。

An Online Algorithm for Lightweight Grammar-Based Compression.
Shirou Maruyama, Algorithms 2012, 2012.

バグもいっぱいあると思うし、後処理もさぼってはいるが、それなりに動く。

class RePair {
    
    RePair() { }
    
    int lca( final int i, final int j ) {
        return SBVUtility.getMSB(i ^ j);
    }
    
    boolean replacedPair(
            final Queue<Integer> pQueue,
            final int pLeaveNum,
            final int pIndex
            ) {
        
        Iterator<Integer> itr = pQueue.iterator();
        
        // pIndexまで読み飛ばす。
        int prevElem0 = 0;
        for ( int i = 0; i < pIndex; i++ ) {
            prevElem0 = itr.next();
        }
        
        // index iの要素を取得する。
        Integer elem0 = itr.next();
        // index i + 1の要素を取得する。
        Integer elem1 = itr.next();
        
        // Is w[i, i+1] repetitive pair ?
        if ( elem0 == elem1 ) {
            return true;
        }
        
        // index i + 2の要素を取得する。
        Integer elem2 = itr.next();
        
        // Is w[i+1, i+2] repetitive pair ?
        if ( elem1 == elem2 ) {
            return false;
        }
        
        // index i + 3の要素を取得する。
        Integer elem3 = itr.next();
        
        // Is w[i+2, i+3] repetitive pair ?
        if ( elem2 == elem3 ) {
            return true;
        }
        
        int prevLeaveNum = (pLeaveNum << 1) | 1;
        int leaveNum0 = ((pLeaveNum + 1) << 1) | 1;
        int leaveNum1 = ((pLeaveNum + 2) << 1) | 1;
        int leaveNum2 = ((pLeaveNum + 3) << 1) | 1;
        int leaveNum3 = ((pLeaveNum + 4) << 1) | 1;
        if ( -1 == prevElem0 ) { // dummyである。
            leaveNum0 = (pLeaveNum << 1) | 1;
            leaveNum1 = ((pLeaveNum + 1) << 1) | 1;
            leaveNum2 = ((pLeaveNum + 2) << 1) | 1;
            leaveNum3 = ((pLeaveNum + 3) << 1) | 1;
        }
        
        // Is w[i, i+1] is minimal pair or maximal pair ?
        if ( -1 != prevElem0 ) { // dummyではない。
            if ( elem0 < prevElem0 && elem0 < elem1 ) { // minimal pair ?
                return true;
            } else if ( lca(leaveNum0, leaveNum1) > lca(prevLeaveNum, leaveNum0)
                    && lca(leaveNum0, leaveNum1) > lca(leaveNum1, leaveNum2) ) { // maximal pair ?
                return true;
            }
        }
        
        // Is w[i+1, i+2] is minimal pair or maximal pair ?
        if ( elem1 < elem0 && elem1 < elem2 ) { // minimal pair ?
            return false;
        } else if ( lca(leaveNum1, leaveNum2) > lca(leaveNum0, leaveNum1)
                && lca(leaveNum1, leaveNum2) > lca(leaveNum2, leaveNum3) ) { // maximal pair ?
            return false;
        }
        
        return true;
        
    }
    
    void insertSymbol(
            final Map<String, Integer> pDictionary,
            final int pMaxCodePoint,
            final List<Queue<Integer>> pQueueList,
            final List<Integer> pLeavesList,
            final int pQueueIndex,
            final int pCodePoint
            ) {
        
        // 対象となるキューを取得する。
        Queue<Integer> queue = pQueueList.get(pQueueIndex);
        
        Integer leaveNum = pLeavesList.get(pQueueIndex);
        
        // キューに文字を格納する。
        queue.offer(Integer.valueOf(pCodePoint));
        
        // 5文字以上格納されているか?
        if ( 5 <= queue.size() ) {
            if ( replacedPair(queue, leaveNum.intValue(), 1) ) {
                Integer y0 = queue.poll();
                Integer y1 = queue.poll();
                Integer y2 = queue.peek();
                
                StringBuffer keyBuffer = new StringBuffer(8);
                keyBuffer.appendCodePoint(y1.intValue());
                keyBuffer.appendCodePoint(y2.intValue());
                String key = keyBuffer.toString();
                Integer z = Integer.valueOf(pDictionary.size() + pMaxCodePoint);
                if ( pDictionary.containsKey(key) ) {
                    z = pDictionary.get(key);
                    insertSymbol(pDictionary, pMaxCodePoint, pQueueList, pLeavesList, pQueueIndex + 1, z.intValue());
                } else {
                    pDictionary.put(key, z);
                    insertSymbol(pDictionary, pMaxCodePoint, pQueueList, pLeavesList, pQueueIndex + 1, z.intValue());
                }
                
                if ( -1 == y0.intValue() ) {
                    // dummy
                    leaveNum++;
                } else {
                    leaveNum += 2;
                }
            } else {
                Integer y0 = queue.poll();
                Integer y1 = queue.poll();
                insertSymbol(pDictionary, pMaxCodePoint, pQueueList, pLeavesList, pQueueIndex + 1, y1.intValue());
                Integer y2 = queue.poll();
                Integer y3 = queue.peek();
                
                StringBuffer keyBuffer = new StringBuffer(8);
                keyBuffer.appendCodePoint(y2.intValue());
                keyBuffer.appendCodePoint(y3.intValue());
                String key = keyBuffer.toString();
                Integer z = Integer.valueOf(pDictionary.size() + pMaxCodePoint);
                if ( pDictionary.containsKey(key) ) {
                    z = pDictionary.get(key);
                    insertSymbol(pDictionary, pMaxCodePoint, pQueueList, pLeavesList, pQueueIndex + 1, z.intValue());
                } else {
                    pDictionary.put(key, z);
                    insertSymbol(pDictionary, pMaxCodePoint, pQueueList, pLeavesList, pQueueIndex + 1, z.intValue());
                }
                if ( -1 == y0.intValue() ) {
                    // dummy
                    leaveNum += 2;
                } else {
                    leaveNum += 3;
                }
            }
        }
        
        pLeavesList.set(pQueueIndex, Integer.valueOf(leaveNum));
        
        return;
        
    }
    
    void compress(final String pStr) {
        
        // 文字数を取得する。
        int codePointCount = pStr.codePointCount(0, pStr.length());
        
        // 辞書
        Map<String, Integer> dictionary = new HashMap<String, Integer>();
        
        // 取得した文字数からparse treeの高さを計算する。
        int height = SBVUtility.getMSB(codePointCount);
        
        // キューを高さ分用意して、初期化する。
        List<Queue<Integer>> queueList = new ArrayList<Queue<Integer>>(height);
        // 完全二分木のin-orderでの葉の番号のリスト
        List<Integer> leavesList = new ArrayList<Integer>(height);
        for ( int i = 0; i < height; i++ ) {
            Queue<Integer> queue = new LinkedList<Integer>();
            // dummyを格納する。
            queue.add(Integer.valueOf(-1));
            queueList.add(queue);
            leavesList.add(Integer.valueOf(0));
        }
        
        // 最大のコードポイントを取得する。
        CodePointIterator itr = new CodePointIterator(pStr);
        int maxCodePoint = 0;
        for ( ; itr.hasNext(); ) {
            int codePoint = itr.next();
            if ( maxCodePoint < codePoint ) {
                maxCodePoint = codePoint + 1;
            }
        }
        
        // Algorithm2 LCA-online
        itr = new CodePointIterator(pStr);
        int queueIndex = 0;
        for ( ; itr.hasNext(); ) {
            
            // コードポイントを取得する。
            int codePoint = itr.next();
            
            // キューに文字を挿入する。
            insertSymbol(dictionary, maxCodePoint, queueList, leavesList, queueIndex, codePoint);
            
        }
        
        // post-process
        for ( int i = 0; i < height - 1; i++ ) {
            Queue<Integer> targetQueue = queueList.get(i);
            Queue<Integer> nextQueue = queueList.get(i + 1);
            if ( 0 != targetQueue.size() ) {
                targetQueue.poll();
            }
            while ( 0 != targetQueue.size() ) {
                Integer elem = targetQueue.poll();
                nextQueue.add(elem);
            }
        }
        
        // 残った文字列を出力する。
        Queue<Integer> queue = queueList.get(height - 1);
        StringBuffer resultBuffer = new StringBuffer();
        queue.poll();
        while ( 0 != queue.size() ) {
            resultBuffer.appendCodePoint(queue.poll().intValue());
        }
        
        System.out.println( "入力文字列:" + pStr );
        System.out.println( "結果文字列:" + resultBuffer.toString() );
        
        System.out.println();
        
        System.out.println( "辞書定義:" );
        
        // 辞書
        for ( String key : dictionary.keySet() ) {
            System.out.println( key + " ---> " + new String(Character.toChars(dictionary.get(key).intValue())) );
        }
        
        // 最大文字は、サロゲートペアの範囲に気を付ける。
        
        return;
        
    }

}

実行は、以下です。

String str = "abababcccccc";
RePair rePair = new RePair();
rePair.compress( str );

実行結果は、以下です。

入力文字列:abababcccccc
結果文字列:aebffcc

辞書定義:
dd ---> e
ba ---> d
cc ---> f

かなり怪しいが、それなりには動く。これをビットベクトルに適用して、辞書を簡潔データ構造で表現して、ランダムアクセス可能な補助データ構造を作成すると、Re-Pairを利用した簡潔ビットベクトルができるはず。

ここまで来るのに半年かかってしまった。

文法圧縮(3)

落ち着いて作業できました。

さて、前回、文法圧縮のRe-Pairを効率的に実装するのはなかなか難解だと書いたが、非常にシンプルに線形時間で実装できる論文を発見した。

An Online Algorithm for Lightweight Grammar-Based Compression.
Shirou Maruyama, Algorithms 2012, 2012.

http://www.mdpi.com/1999-4893/5/2/214

このアルゴリズムを利用すると、LZ圧縮のように入力文字列を前から参照しながら、オンラインでRe-Pair圧縮を実現することができる。しかも、入力文字列の5文字だけを見るだけというシンプルさで。かなり、感動した。こんなシンプルにできるんですね。ただ、LCAを定数時間で求める方法が勉強不足でわかっていない。調査する。

また、著者が作成したプログラムが以下にあるので、簡単に試したい場合は使ってみるのが良いと思います。

https://code.google.com/p/lcacomp/

あと、最近、Re-Pairの簡潔ビットベクトルについて、よくまとまった論文が出てたので、紹介しておく。

General Document Retrieval in Compact Space.
Gonzalo Navarro, ACM Journal of Experimental Algorihtmics, 2013.

http://www.dcc.uchile.cl/~gnavarro/ps/jea13.pdf

p.17の4章に説明と図があります。

Wavelet TreeのTop-Kの改善

Wavelet Treeは強力なデータ構造ですが、ひとつどうしても気になる点があります。それは、Top-Kの列挙です。文字列本で紹介されているGreedyな方法は、結果がK件しか必要ないにもかかわらず、計算時間がけっこうかかります。他の操作は、最悪値の計算量が小さく、安心して使えるのに対して、Top-Kだけは、少し注意する必要があります。そのことは、文字列本にも書いてあって、最悪計算量も明示してあります。

その最悪計算量ですが、要素間の頻度に大きな偏りがある場合は、無断な節点を調べずに済み、計算量はO(klogσ)に近づくとあります。つまり、ある区間内の数値に偏りがあると、問題ないということです。

1 2 3 4 2 3 4 3 4 4

上記のような場合だと、Top-1のクエリを発行すると、O(logσ)です。頻度に偏りがあると、Wavelet Treeの上段での見積もりがうまく機能するので、無駄な節点を調べる必要がなくなるからです。

ただし、それぞれの数値がまんべんなく出現する場合は、上段での見積もりがうまく機能しません。

1 2 3 4 1 2 3 4

上記の場合は、上段での見積もりは、どの節点も同じなので、結局、一番下の段まで調べないとTop-1を決定できません。

こんなケースはレアだということで済ますこともできるんですが、実運用を考えると少し不安です。例えば、英語の文書で、ある程度の文書数で、ある程度同じ長さの場合、「The」の出現頻度が高い順にTop-K文書を表示するとやっかいなわけです。
(もちろん、すべての文書で、「The」の出現頻度が同じということはないですが、ある程度の文書数があると、上段の見積もりはほとんど意味がなく、無駄な節点の計算が必要になります。)

その点を考慮に入れて、Wavelet TreeのTop-Kの性能を改善したNavarro神の論文が以下です。

Space-Efficient Top-k Document Retrieval
Gonzalo Navarro, SEA'12, 2012.

http://www.dcc.uchile.cl/~gnavarro/ps/sea12.2.pdf

この論文を理解するためには、Suffix Treeを利用してTop-Kを取得する方法を理解しなければならない。それについては、以下の岡野原さんのブログに詳しく書いてある。

http://hillbig.cocolog-nifty.com/do/2010/02/top-k-f0d9.html

基本的な概念は、非常に丁寧に説明されているので、上記を読めば理解できると思います。
(もちろん、私も何回も読んでようやく理解しました。)

読んでから気づいたんですが、私は、Suffix Arrayから興味を持ったので、Suffix Treeについては、あまり理解していなかったなということです。なので、今は、「Algorithms on Strings」を読んで、Suffix Treeに対する理解を深めています。

さて、Suffix TreeをTop-K用の補助的データ構造に使うんですが、岡野原さんのブログで紹介されている方法は、厳密な方法なので、サイズが大きいです。なので、情報を減らして、サイズを削減します。やり方は簡単で、Suffix Treeの葉を一定間隔でサンプリングし、それぞれのLCAを求めます。そのLCAに、サンプリングした区間のTop-Kを事前計算して付与しておきます。そして、Suffix Treeの木構造は、LOUDSで表現しておきます(いわゆるパトリシアトライに近いものです)。実際は、各区間のLCAのノードがわかれば良いので、すべての木構造を再現する必要はないと思います。

このTop-K用に特化しつつサイズを抑えたSuffix TreeをSSGST(Succinct Sparsied Generalized Suffix Tree)と呼びます。さて、理解しやすい図が欲しいところだと思いますので、以下のスライドを紹介しておきます。

http://www.cikm2012.org/keynote/Keynote_Jeffrey_S_Vitter.pdf

p.27~40まで見ればイメージできると思います。ちなみに、一般化接尾辞木というのは、複数の文書を対象に作ったSuffix Treeをそう呼んでいるようです。

ようやく本題ですが、このSSGSTを使って、なぜ、Wavelet TreeのTop-K操作が改善されるかということですが、それは、「無駄な節点の計算をしないようにする」ということです。つまり、計算が不要な節点がWavelet Treeの上段でわかれば、早めに打ち切れるので、性能がアップするわけです。

さて、どうやってTop-Kに活かすかということですが、例えば、FM-Indexで検索した結果として、[sp, ep]が得られたとします。そして、あるLCAで事前計算された範囲が、[lsp, lep]とします。そのとき、以下のような関係になっているとします。

sp --- lsp --- lep --- ep 

このlspとlepの区間のTop-K件は事前計算によりわかっています。なので、問題は、[sp, lsp]と[lep, ep]の区間です。[lsp, lep]の区間にあるTop-K件は、[sp, ep]を考慮すると内容が入れ替わる可能性があります。つまり、重要なのは、[sp, lsp]と[lep, ep]を考慮すると[lsp, lep]のTop-K件の内容が入れ替わるかということです。

上記のことを考慮して、Wavelet Treeに対して、[sp, ep]の区間のTop-K操作を行います。ただし、[sp, lsp]か[lep, ep]の範囲の数値が含まれている節点だけを計算対象とします。これにより、[sp, lsp]か[lep, ep]の数値が含まれていない節点を展開しなくてよくなりますし、事前計算されたTop-Kの中で最も頻度が低いものよりも数が少ない節点に到達した時点で探索を打ち切ることもできます。

多くの場合、高速化されるようです。

ただ、最近は、さらに良いデータ構造が提案されていて、以下は、SSGSTを使ったものより数十倍も高速になるようです。

Faster Compact Top-k Document Retrieval
Gonzalo Navarro, DCC'13, 2013.

http://www.dcc.uchile.cl/~gnavarro/ps/dcc13.1.pdf

Table1がわかりやすいと思います。こちらは、まだ読んでいないので、読んでみようと思います。