フリーソフト・フリーデータ

自家製 #isucon のつくりかた

カテゴリ
ブックマーク数
このエントリーを含むはてなブックマーク はてなブックマーク - 自家製 #isucon のつくりかた
このエントリーをはてなブックマークに追加

こんにちは、ISUCON というイベントのレギュレーションを考えたり環境の準備をやったりコード書いたりしてた tagomoris です。普段はライブドア開発本部のインフラサービス部というところで働いてます。

先日ISUCONは幸いにも大好評のうちに終了したのですが、へとへとになって疲れ切った状態で帰宅し、寝て起きてみると、公開しておいたソースコードをさっそく自分の手元で動かしている人がいました。説明とか何にもなかったのによくそこまで。どういうことなのと思わずにはいられません。

#isucon に参加してきました&isuconツールを試してみました - As a Futurist...

また翌日にはTwitterでも続々と動かしてみた報告が見られ、エンジニアのみなさんのバイタリティには感服するばかりです。

ざいりょう

で、せっかくだから本番と同じデータで同じように試せるようにしたいよね、ということで、ソースコード一式に加えて初期データも用意しました!

ソースコード一式についてですが、ISUCON本番から少しだけ変更を加えてあり、基本的には1台のPCでベンチ対象からベンチマークまで完結する設定・コードが最初から入っています。とりあえずお試しいただくにはこの状態からが多分やりやすいと思います。またベンチマークツールに多少のデバッグが行われています。
ISUCON本番と同じように多数サーバ構成・多数チーム参加で動作させるにはリリースタグの状態でやるのがいいと思いますが、サーバ構成をどうするか次第の部分もあり、なかなか面倒です。試したい人は頑張ってください。どうしてもという場合には @tagomoris 宛にお聞きいただけると答えられるかもしれません。

初期データファイルはISUCON本番のものと同じです。mysqldumpファイルなので、mysqlにそのまま食わせて使用できます。個人的なお勧めは、まずこのファイルを使わない状態でベンチマークを走らせ、その後にこのデータを入れてみることです。データの増大が(プログラムの構造によっては)性能にどれだけ影響を与えるかが実感できます。

したごしらえ

ISUCON環境を作成するPCについてですが、以下の環境のどれかを想定しています。

  • Linux系OSのどれか
    • ISUCONは CentOS 5.6 でしたが、CentOS 6 やDebian系のものでも問題ないと思います
  • Mac OSX
    • 10.6 Snow Leopard を手元では使用していますが、10.7 Lion でも多分大丈夫です
    • Xcode のインストールがおそらく必要です(入ってない環境が手元にないので確認できない……)

BSD系のOSやSolaris等でも気合いを入れれば動くような気がしますが、確認していません。基本的に以下のものが動くことが大前提です。

  • MySQL 5.5 (5.1でも多分動く)
  • Apache 2.2 (無くてもどうにかなる)
  • git
  • perl 5.8 以降
  • node.js 0.4.11 (0.4系の新しめのものなら大丈夫そうだが v0.4.11 おすすめ)
  • supervisord
    • easy_install 経由で入れる(後述)

特に node.js で環境が選ばれるかもしれません。node.js 0.4系はWindowsに対応していないので、WindowsだけでISUCON環境を作ることは残念ながら不可能です。(0.5を使ってもしかしたら動くかもしれませんが、全く試していません。試された方がいましたら教えてくださると嬉しいです。)

準備としてApacheとMySQLをなんとか入れます。ApacheはOSXは最初から入っていますし、MySQL 5.5はLinuxでもOSXでも公式のものが用意されていますので、自分の環境にあわせてインストールして下さい。このあたりはあちこちに案内があるので割愛します。
またperlも対象となる環境ではどれでも最初から使えるので省略します。perlのバージョンを変えて遊んだりしたい気持ちはよくわかりますが説明が大変なので、みなさまで各自頑張ってください。もしくは誰かがblogエントリを書いてくれると思います。

node.jsはちょっとレアなので書きます。nvm というnode.js自体のバージョンを管理するツール経由で入れるのが簡単です。naveという同種の目的のツールもありますので好み次第かなとも思いますが、とりあえず自分のとっている方法で。

このREADMEに従って以下のコマンドを叩きインストールします。ついでに必要なモジュールもインストールしてしまいましょう。

$ git clone git://github.com/creationix/nvm.git ~/.nvm
$ . ~/.nvm/nvm.sh
$ nvm install v0.4.11
$ nvm use v0.4.11
$ nvm alias default v0.4.11
$ npm install express jade mysql jsdom async

これでnodeおよびnode用モジュールのパスは以下のようになるはずです。

  • nodeのパス: ~/.nvm/v0.4.11/bin/node
  • モジュールのディレクトリ: ~/node_modules/

違ったなら nvm の動作が変わったのかもしれません。node.jsまわりにはよくあることなので、動揺せず適宜読み替えてください。

またアプリケーションやベンチマーク管理ツールなどをデーモンとして動作させるため supervisord をインストールします。
無くても試すだけは試せますが、スコアを求めてあれこれやる上ではあった方が便利です。easy_install コマンド経由でインストールするので、その準備をしておいてください。

$ sudo easy_install supervisor

つくりかた

なにはともあれ、ソースコードを取得します。適当なディレクトリを選んで git clone しましょう。isuconディレクトリの中に展開されます。

$ git clone git://github.com/tagomoris/isucon.git
$ cd isucon

まずWebアプリケーションから動作させることにしましょう。データベースにユーザを作成したりスキーマを定義したりします。

$ mysql -u root < webapp/config/database/isucon.sql

Perlでアプリケーションを動作させるには以下の手順でOKです。( webapp/perl/README に書いてある通りです。cpanmはインストール済みなら curl や chmod は不要です。)

$ cd webapp/perl
$ curl -k -L http://cpanmin.us/ > ./cpanm
$ chmod +x ./cpanm
$ ./cpanm -Lextlib -n --installdeps .
$ perl -Mlib=extlib/lib/perl5 extlib/bin/plackup -s Starman -E production --preload-app app.psgi

最後のコマンドを実行すると http://localhost:5000/ でWebアプリケーションにアクセスが可能になるはずです。ブラウザで開いてみてください。
最初の時点では記事が何もないので何も表示されませんが、ISUCONロゴをクリックすると記事投稿画面になり、そこから記事が投稿できます。ひとつ記事を投稿すればそれに対してコメントをつけたりもできるようになり、ブラウザ上にあれこれ表示されるようになってきます。
しばらくこのperlのプロセスは起動したままにしておきましょう。作業は別のターミナルを開いてやることにします。

最後にリバースプロキシとしてApacheの設定を行います。(なくてもとりあえず動くので、省略しても構いません。)
基本的には単純で、ApacheがListenしている port 80 に来たリクエストを、すべてlocalhost:5000に転送します。

ProxyRequests Off
 
<Proxy *>
  Order deny,allow
  Allow from all
</Proxy>
 
ProxyPass / http://127.0.0.1:5000/
ProxyPassReverse / http://127.0.0.1:5000/

mod_proxy (およびAPサーバを複数立てる場合には mod_proxy_balancer)を有効にしたApacheに上記の設定をします。OSXなら /etc/apache2/other/isu.conf などといったファイルを作成し、そこに書いておけば良いでしょう。Linuxの場合は /etc/httpd/conf.d/isu.conf に書く場合や /etc/apache2/site-enabled/default に追記すると良い場合があります。
書いたらApacheに設定を読み込ませます。

$ sudo apachectl restart

これで http://localhost/ でさっきのアプリケーションが見られるようになりました。なりましたよね?

ベンチマークの準備にもいくつかの手順が必要です。まず http_load をビルドします。

$ cd tools
$ tar xzf http_load/http_load-12mar2006.tar.gz
$ cd http_load-12mar2006
$ patch -p1 < ../http_load/http_load.patch
$ make

このとき、恐怖のkazeburoパッチをpatchコマンドで当てています。当てなくても動作はしますが、よりリアルなISUCON環境のためにはぜひとも当てるべきでしょう。
続けてperlのスクリプト用のモジュールの準備。

$ cd ../
$ ../webapp/perl/cpanm -Lextlib -n JSON Furl

もしリバースプロキシを立てない場合は、ベンチマークの設定ファイルの編集が必要です。tools/config.json を次のように書き換えましょう。(リバースプロキシのApacheを立てた場合はこの変更は不要です。)

--- config.json	2011-08-28 21:51:02.000000000 +0900
+++ config.json.2	2011-08-29 19:08:15.000000000 +0900
@@ -10,6 +10,6 @@
     "team01" 
   ],
   "teams": {
-    "team01": {"id":"team01", "name":"oreore", "pass":"pass", "bench":"bench01", "target":"127.0.0.1:80"}
+    "team01": {"id":"team01", "name":"oreore", "pass":"pass", "bench":"bench01", "target":"127.0.0.1:5000"}
   }
 }  

target の指定のところでポート番号を変更していますね。ここだけで大丈夫です。

ここまでやれば、コマンドラインベースでのベンチマークは動作します(そのようなオプションをISUCON後に追加しました)。以下のコマンドを実行しましょう!

$ NODE_PATH=lib node bench.js team01 standalone

実行すると1分間、すごい勢いでアプリケーションにリクエストが飛びます。1分経過後、ベンチマークおよびWebアプリケーション動作チェックの結果が次のように表示されればOKです。(これはtagomorisのMacBookAirで実行した結果。)

tools tagomoris$ NODE_PATH=lib node bench.js team01 standalone
{ teamid: 'team01',
 resulttime: Mon, 29 Aug 2011 10:02:48 GMT,
 test: true,
 score: 7102,
 bench: 
  { fetches: 7102,
    'max parallel': 10,
    bytes: 245187000,
    seconds: 60.0002,
    'mean bytes/connection': 34523.6,
    'msecs/connect': { mean: 0.378283, max: 36.007, min: 0.081 },
    'msecs/first-response': { mean: 12.754, max: 1254.57, min: 0.906 },
    response: { success: 7102, error: 0 },
    responseCode: { '200': 7102 } },
 checker: 
  { checker: { summary: 'success' },
    poster: { summary: 'success' } } }

ここに出ている "test:true" が動作チェックにパスしたということ、そして "score: 7102" がベンチマークの結果のスコアです。当日はみんなでこの数値を競っていたわけですね。これであなたもISUCON参加者!
なおここに表示されたデータ(およびこれから後に書く方法で実行されたベンチマークのデータ)はすべて tools/data 下に保存され、後から確認できます。

もりつけ

実質的にはここまでで動くのですが、このままではちょっと見た目が残念ですし、コードや設定に変更を加えた場合にもいろいろと面倒です。なので、まず各種ツールが常時起動した状態になるようにします。
これが完了すると、ISUCONのように21チーム準備した場合にはこんな画面が見られるわけですね!

master

このために supervisord を使用します。他にも daemontools など同種のツールがありますが、supervisordのシンプルさにひかれて今回はこれを使いました。
以下の作業を始める前に、前の方で perl コマンドを叩いて起動しっぱなしにしていたプロセスは ctrl-C して停止させておきましょう。

スコアはデータベースに格納されますので、そのためのスキーマをMySQLに導入します。以下のコマンドで一発です。

$ mysql -u root < tools/etc/master.sql

で、おひとり様用のsupervisord.conf全部入りを作りましたので、これを使うのが楽です。が、その前に各種パス用の設定ファイルを修正します。

$ cd isucon
$ cat standalone/env.sh
#!/bin/bash
 
USERNAME=tagomoris
USER_HOME=/Users/tagomoris
NODE_VERSION=v0.4.11
 
export PATH=$PATH:$USER_HOME/.nvm/$NODE_VERSION/bin
export NODE_PATH=$NODE_PATH:$USER_HOME/node_modules/

ここで USERNAME および USER_HOME はnvmのインストールなどをしたユーザ名およびそのホームディレクトリを入れておきます。このあたりは普通 $HOME を使えばいいのですが supervisord を使う場合は root から呼ばれる場合などもあるので、このようにしてあります。
また NODE_VERSION や PATH や NODE_PATH には nvm 関連のパス等をセットしています。これはインストール後に確認したご自分の環境に合わせてください。

これが終わったら、次に standalone/supervisord.conf を /etc/ 以下にコピーし、自分の環境にあわせて書き換えます。

$ sudo cp standalone/supervisord.conf /etc/
$ sudo vi /etc/supervisord.conf

ログファイルの場所や細かいパラメータなどいろいろありますが、とりあえず動作させるために書き換えるのは以下の7ヶ所に埋まっている、isuconリポジトリの場所、およびユーザ名だけです。

[program:master]
command=/Users/tagomoris/Documents/isucon/tools/etc/master.sh
process_name=isucon bench master
user=tagomoris
...
 
[program:agent]
command=/Users/tagomoris/Documents/isucon/tools/etc/agent.sh
process_name=isucon bench agent
user=tagomoris
...
 
[program:isucon_perl]
directory = /Users/tagomoris/Documents/isucon/webapp/perl
command=perl -Mlib=/Users/tagomoris/Documents/isucon/webapp/perl/extlib/lib/perl5 /Users/tagomoris/Documents/isucon/webapp/perl/extlib/bin/plackup -s Starman -E production --preload-app --disable-keepalive --workers 10 /Users/tagomoris/Documents/isucon/webapp/perl/app.psgi
user=tagomoris

ここに /Users/tagomoris/Documents/isucon とあるのが自分がOSX上でisuconのリポジトリを置いた場所ですね。これをみなさんのPC上のパスにあわせて変更してください。 program:isucon_perl の command 行には何ヶ所かに埋まっているので修正漏れがないようにしてください。
また user も何ヶ所かにありますが、これはあなたのユーザ名に変更してください。

変更が終わったら sudo supervisord -n とすると、その端末内で supervisord が立ち上がり master.js と agent.js および perl のアプリケーションをすべて起動します。何か修正ミスなどがあればこのときにエラーになるので、端末内に表示される supervisord のエラーログ、あるいは /tmp/isucon.perl.log や /tmp/isucon.master.log などとして作成される各ツールのログを確認してください。
さらっと書いてきましたが、master/agentとは以下のような役割のプログラムです。

  • master
    • ベンチマークのスコアを各チームについて表示したり、ベンチマークの起動を指示したりするためのツール
    • 起動していれば http://localhost:3080/ でアクセスできる
  • agent
    • masterからのベンチマーク起動の指示を受け取って bench.js を実行したり、ベンチマークの走行状況がどのようになっているかを報告したりするためのツール
    • 特にベンチマークをかける側を複数台のサーバに分散したりする場合にこのようなものが必要
    • 人が直接見られる画面はなし

supervisord を起動して問題なく各プロセスが上がるようになれば、あとはもう sudo supervisord だけで起動してバックグラウンドにいってもらっても大丈夫です。

supervisord 経由で各プロセスが無事に起動していれば、以下のように「記録なし!」な画面が出てきますね。チームがひとつなのはちょっとさびしいですが、おひとり様用なのでしょうがありません。
"idle" をクリックするとベンチマークを起動できますので、初期パスワード "pass" を入力して "START" をクリックすれば状態が "running" となります。無事ベンチマークが完走したらチーム名の部分が青くなると同時にスコアが表示され、さあチューニングのはじまりだ!

123

かくしあじ

ここまでで初期データのないISUCON環境ができて、成績の数値も出てきました。6000とかすごいスコアですねISUCON上位に入れるじゃん! と思ったあなた、初期データの導入をお忘れですね。
ページ先頭のリンクから初期データ isucon_db.sql.gz をダウンロードし、適当な場所に置いておきます。次のようなコマンドで MySQL に読み込ませましょう。

$ gzcat isucon_db.sql.gz | mysql -uroot

完了後にそのままもういちどベンチマークを回してみると……

d1

スコアなんとたったの58・・・! 俺たちのISUCON坂はまだはじまったばかりだ! という気分になりますね! (サーバでの動作とはいえ)ISUCON優勝チームが1分だと90,000のスコアを叩き出していたことを考えるとどれだけ先が長いかがわかります。

またPCでの実行で、かつベンチマーク対象もベンチマーク元も同じPCになっていると、デフォルトの状態でも "FAILED" となることがあります。その表示をクリックしてみるとこんなダイアログが出るので確認してください。

2

理由としては負荷をかけたときにサーバが重過ぎて、表示内容のチェックを行うためのHTTPリクエストがぜんぜん通ってないんですね。HTMLの内容を確認することができず、レギュレーション上のチェックが通らないため、そのまま FAILED となっています。
根本的な原因はアプリケーションが重過ぎることですが、特にリバースプロキシにApacheを立てていて、かつプロセス数が少ないような場合にこういうことが起こります。お使いの環境で以下の項目をチェックしてみてください。

  • Apache のプロセス数が少なすぎる数になっていないか
  • Apache の設定で keepalive が有効になっていないか
  • そもそも非力すぎるマシンで実行していないか

どうしてもFAILEDが消せない場合、以下の対策を複合すればとりあえず通るようになるかもしれません。

  1. リバースプロキシのApacheを使うのをやめてベンチマークをアプリケーションに直接向ける
    • tools/config.json の変更を行うこと
  2. Perl版アプリケーションをやめてNode.js版を使う
    • アプリケーション単体での高負荷耐性はNode.js版の方が良いです
    • supervisord.conf でPerl版アプリケーションの設定セクションをコメントアウトし、Node.js版の側のコメントアウトを外してから supervisord を起動します
    • 各種パスの修正に気をつけてやってあれば、そのまま起動するはずです

さて、実はこの「おひとり様用」の設定は http_load の並列度をわざと2に落としています。これは初期状態でのベンチマークが通りやすくするためですね。パフォーマンスが十分に高い環境では並列度はもっと上げた方がスコアは上がります。
ISUCON本戦では http_load の並列度は 10 という設定に固定してありました。あなたのアプリケーションが高スコアを叩き出すようになってきたら、この数値に戻してみてもいいでしょう。tools/bench.js の9行目を変更してお試しください。

できあがり

これで環境は完成です。思う存分にあなたのISUCONをお楽しみください! 高得点をゲットできたらblogなどに書いていただけると我々もとても嬉しいです。

ライブドアではISUCONと楽しく激しく格闘できるエンジニアを募集しています!

livedoor グルメの DataSet を公開

カテゴリ
ブックマーク数
このエントリーを含むはてなブックマーク はてなブックマーク - livedoor グルメの DataSet を公開
このエントリーをはてなブックマークに追加

櫛井です。

以前 livedoor clip のデータを学術研究用に公開しましたが,おかげさまで,たまに発表等で livedoor clip という名前が引用されているのを見かけるようにもなり感慨深い限りです。

さて,今回は第二弾としまして,livedoor グルメのデータをまとめてダウンロード & 利用可能にしようと思います。

今回はいろいろと余裕がなかったため

  • 豪華なイラスト付きページが用意できませんでした
  • livedoor clip のデータとは違い,定期アップデートはされません。2011年4月22日の時点のデータのみとなります

...が,なにかしら皆様の研究のお役に立てればと思います。

よくありそうな質問と答え

  • ライブドアグルメのユーザですが,自分の個人情報が公開されちゃうってこと?困ります!
    • 公開されるのは,もともとライブドアグルメのサイトで誰でも見れるようになっている情報だけです。また,ユーザ名はハッシュ化されています。ライブドアグルメのサイト本体を閲覧すれば分かる内容以上のことは,このデータセットからも分かりません。
  • サイト本体と同じデータしかないのなら,このデータセットを公開する意味はなんですか?
    • 研究者がサイトからデータを取得するには,自動的にサイトを巡回してデータをもれなく読み出す専用のプログラムを作る必要があります。これをクローリングやスクレイピングと呼びます。しかし,(1) 研究自体よりもこの準備の方に時間をとられてしまいがち (2) サイト上のデータは日々変化するので,クローリングで取得したデータに再現性がない (他の研究者が同一のデータを使って検証実験をすることができない) という問題がある (3) サイト運営側としても,クローリングでサーバに負荷をかけられるよりは最初からダウンロードしてもらった方が問題が少ない ... という双方のメリットがあります。
  • 利用上の注意事項,制限事項などがあれば教えて
    • 下に規約を載せてありますので,これに沿って利用してください。
  • データにはどんな内容が含まれますか?
    • レストランの基本データと,それに対する口コミ,さらに口コミに対する投票から成ります。このページの一番下に詳しい説明と定義を載せてありますので参考にしてください。
  • 最新のデータもほしい。
    • ライブドアグルメには データAPIもあります。クローラを作るよりは使いやすいかもしれませんのでご検討下さい。
  • ライブドアグルメじゃなくて食べログのデータがほしいです
    • デスヨネー

利用規約

・ 「livedoorグルメDataSets」は、株式会社ライブドア(以下、「弊社」といいます。)が提供する「livedoorグルメ」サービスを利用する「livedoorグルメ会員」(以下、「会員」といいます。)が、「livedoorグルメ」に登録した店舗情報、会員が登録した情報等(以下「本件情報」といいます。)を、CSVファイルにまとめたものです。なお、ユーザIDは、会員のプライバシー保護のため、暗号化されています。

・ livedoorグルメDataSetsにおけるデータは、平成23年(2011年) 4年22日時点のものであり、それ以降の店舗移転や閉店、その他本件情報の変更について反映しておりませんのでご注意下さい。

・ livedoorグルメDataSetsのご利用は、学術研究の目的に限ります。livedoorグルメDataSetsは、商用目的には提供いたしませんので、あらかじめご了承下さい。

・ livedoorグルメDataSetsのお申込みにあたっては、弊社のプライバシーポリシーが適用されます。

【プライバシーポリシーへのリンクの設定】

・ livedoorグルメDataSetsから得られる情報のうち、氏名、団体名等個人を識別または特定する要因となり得る情報につきましては、いかなる目的または方法であっても、これを使用または複製してはならないものとします。

・ 弊社からlivedoorグルメDataSets内の特定の情報の削除を求められた場合、これに応じなければなりません。

・ 本件情報のうち、会員が登録した情報の著作権は、当該情報を登録した会員に帰属します。そのため、当該情報の無断利用は、会員の著作権侵害となる可能性がありますのでご注意下さい。

・ 弊社は、livedoorグルメDataSetsの正確性、完全性、最新性、有用性等について一切保証しておりません。また、弊社は、livedoorグルメDataSetsのお申込みまたはご利用により生じたあらゆる障害、不利益、損害等に対して、一切責任を負わず、また損害賠償の義務を負いません。

・ livedoorグルメDataSetsの提供は、弊社の判断により、予告なく内容が変更されたり、または終了したりすることがあります。

データセット詳細

ダウンロードは [こちら]

フィールドの名前や内容の説明は以下の通りです。

※ネーミングは,すでに公開している livedoor グルメ API に準じていますのでこちらもご覧&ご利用ください。

  • restaurants.csv お店データ
    • id お店ID
    • name 店名
    • property 支店名
    • alphabet 店名欧文
    • name_kana 店名ひらがな
    • pref_id 都道府県ID (prefs.csv参照)
    • area_id エリアID (areas.csv参照)
    • station_id1, station_time1, station_distance1 最寄り駅ID(stations.csv参照),時間(分),距離(m)
    • station_id2, station_time2, station_distance2 (同上)
    • station_id3, station_time3, station_distance3 (同上)
    • category_id1カテゴリID(categories.csv参照)
    • category_id2, category_id3, category_id4, category_id5 (同上)
    • zip 郵便番号
    • address 住所
    • north_latitude 北緯
    • east_longitude 東経
    • description 備考
    • purpose お店利用目的
    • open_morning モーニング有
    • open_lunch ランチ有
    • open_late 23時以降営業
    • photo_count 写真アップロード数
    • special_count 特集掲載数
    • menu_count メニュー投稿数
    • fan_count ファン数
    • access_count 類型アクセス数
    • created_on 作成日
    • modified_on 更新日
    • closed 閉店
  • prefs.csv 都道府県マスタ
    • id 都道府県ID
    • name 都道府県名
  • areas.csv エリアマスタ
    • id エリアID
    • pref_id 都道府県ID
    • name エリア名
  • stations.csv 駅マスタ
    • id 駅ID
    • pref_id 都道府県ID
    • name 駅名
    • name_kana 駅名ひらがな
    • property 路線名
  • categories.csv カテゴリマスタ
    • id カテゴリID
    • name カテゴリ名
    • name_kana カテゴリ名ひらがな
    • parent1, parent2 親カテゴリID
    • similar 類似カテゴリ名
  • ratings.csv 口コミデータ
    • id 口コミID
    • restaurant_id 対象お店ID
    • user_id ユーザID
    • total 総合評価(0-5)
    • food 料理評価(0-5)
    • service サービス評価(0-5)
    • atmosphere 雰囲気評価(0-5)
    • cost_performance コストパフォーマンス評価(0-5)
    • title 口コミコメントタイトル
    • body 口コミコメント
    • purpose 利用目的
    • created_on 投稿日時
  • ratings_votes.csv 口コミへの投票データ
    • rating_id 対象口コミID
    • user ユーザID
    • 投票日時

(以上)

wikipediaのデータや顔文字辞書からmecabのユーザ辞書を作成するフレームワーク

カテゴリ
ブックマーク数
このエントリーを含むはてなブックマーク はてなブックマーク - wikipediaのデータや顔文字辞書からmecabのユーザ辞書を作成するフレームワーク
このエントリーをはてなブックマークに追加

突然ですが,mecabの辞書 (mecab-ipadic) をデフォルトのまま使って,mecab意外と使えねぇとか文句言ってる悪い子はおらんかね?

mecab-ipadic は比較的お行儀のよい日本語をベースに作られているので,そのままでは web上の口語文体のテキストはうまく扱えないことがあります。本来は教師データを用意し,学習させるといった手法を使うのが正攻法だと思いますが,とりあえず名詞を充実させるだけでも実用度はだいぶ上がるでしょう。

人間の話す言語には,動詞の語幹や名詞には日々新しく語彙が増えるけど,助詞や活用のルールは簡単には変化しない,という特性があります。特に「いま最もつぶやかれている単語ランキング」といった集計をするような場合は,名詞の範囲の切り出しさえ間違えなければそれなりの結果を出せることも多いのです。

ただ,辞書への単語追加はここにある通り簡単にできるのですが,単語の生起コストを決める部分で躓いてしまうことも多いと思います。

そこで,うちで以前から使っていた mecab の辞書増強用のフレームワークを公開することにしました。wikipedia のデータや顔文字辞書などからユーザ辞書を作成することができます。

mecab-dic-overdrive

https://github.com/nabokov/mecab-dic-overdrive

GenDic.pm のサブクラスを作成することで,さまざまな形式の入力データから単語を読み取り,(それなりに)適切な生起コストを自動的に推測してユーザ辞書ファイルを生成してくれる仕組みになっています。デフォルトでは wikipedia 日本語版の jawiki-latest-page.sql.gz と顔文字辞書用のtsvとから,それぞれユーザ辞書を作成することができます。

似たようなスクリプトや記事がすでにいくつか公開されているのであえて公開することもないかなと思っていたのですが,後で述べるように,生起コストの計算方法や,ノーマライゼーションまで含めた辞書管理に多少の独自性というか公開する意義がある気がしましたので。何かの参考になれば幸いです。

mecab-dic-overdriveの機能

辞書のutf-8化

mecabを使うのにipadic自体をutf-8化する必要は必ずしもないのですが,次に述べる辞書パッチを作る場合や,各種プログラムから参照する場合などには utf-8 の方が便利なので,最初に文字コードの変換をします。

辞書へのパッチ適用

misc/dic/*.patch に,ipadic に対するパッチがいくつか用意してあります。"A" "B" などの英数字が単独で切り出されにくくなるための変更や,"ゎ" "ょ" などが助詞として認識されるようになるためのパッチが含まれます。この他にも自前で何か変更を加えたい場合は *.patch ファイルを (utf-8で) 書いてここに置いておくと自動的に適用されます。

辞書のノーマライズ

辞書を有効活用するためには,

など,さまざまな手法を駆使して表現揺れを吸収しておく必要があります。辞書作成時と文章解析時の両方で同じノーマライゼーションを適用するのも重要な注意点です。

デフォルトでは以下のノーマライズ処理がこの通りの順で適用されます。NFKCとlc以外はバッドノウハウの塊です。改行の扱いなどは辞書作成時には無害ですが,特に顔文字や記号を含むテキストに大きく影響する設定も含まれるので,必ず,解析時に使う正規化と同じものを設定するようにしてください。

  1. decode_entities : HTMLエンティティをユニコード文字にデコード [ &hearts; → ♥ ]
  2. strip_single_nl : 単独の改行を除去 (二つ以上連続する改行は区切りと見なす)
  3. wavetilde2long : 波ダッシュを長音記号に置き換える [ プ〜 → プー ]
  4. fullminus2long : 全角マイナス記号を長音記号に置き換える [ プ− → プー ]
  5. dashes2long : ダッシュ全般を長音記号に置き換える [ プ— → プー ]
  6. drawing_lines2long : 罫線に使われる横線などを長音記号に置き換える (参考:[1] [2]) [ プ─ → プー ]
  7. unify_long_repeats : 連続する長音記号を長音記号一個に置き換える [ プーーー → プー ]
  8. nfkc : NFKC正規化 [ フ゜ブ→ ププ ]
  9. lc : アルファベットを小文字に統一 [ ABC → abc ]

変更したい場合は lib/MecabTrainer/NormalizeText.pm を参照の上,etc/config.pl の内容を編集します。bin/normalize_text.pl を使ってノーマライゼーションの結果を確認することもできます。

>bin/normalize_text.pl
キタ━━━━━━(゚∀゚)━━━━━━ !!!!!
キター(゚∀゚)ー !!!!!

>bin/normalize_text.pl --normalize_opts=decode_entities,nfkc
㍖ &frac12;
レントゲン 1⁄2

単語生起コストの自動割り当て

新しく単語を登録する場合に問題になるのが,上で述べた単語生起コストの算出です。ここで"鼻セレブ" という商品名を例に,単語生起コストの調整のしかたを考えてみましょう。

鼻セレブタワー
鼻セレブ(ウサギ限定)ばかり買ってる人の例

単語が単体で現れた場合に,分割されないぎりぎりのラインを求める方法

素の辞書で"鼻セレブ"だけからなる文を mecab で解析すると以下のように「鼻」と「セレブ」が別々の単語として認識されてしまいます。

形態素 連接コスト 単語生起コスト 累積コスト
BOS - 0 0
-283 - -283
鼻(名詞/一般) - 6033 5750
62 - 5812
セレブ(名詞/一般) - 9461 15273
-573 - 14700
EOS - 0 14700

(BOSは文頭,EOSは文の終わりを表します。)

そこで,単語「鼻セレブ」が単体の文章として現れた場合に,それ以上分割されないようにすることを目標としてみます。

まず辞書に形態素「鼻セレブ(固有名詞/一般)」を追加します。そして,mecab が「『鼻+セレブ』に分解するより『鼻セレブ』単体とした方がトータルコストが低い」と判断するように単語生起コストを調節することを考えます。

つまり,

形態素 連接コスト 単語生起コスト 累積コスト
BOS - 0 0
-310 - -310
鼻セレブ(固有名詞/一般) - *1 *
-919 - *
EOS - 0 *2

上表の *1 を何にすれば *2 が 14700 以下になるか? という穴埋め問題を解くことになるわけです。この場合は *1 を 15928 以下にすれば,全体のコストが「鼻+セレブ」の14700よりも低くなります。

BlogPaint

※1「明日の鼻セレブ祭りは中止です」のように前後に他の形態素がつながる場合は,前後の連接コストが変わってきます。「単体の文章として(BOSとEOSの間に)現れた場合に分割されないようにする」というルールはあくまでも恣意的な基準にすぎません。

※2 ときどきここにあるAuto Linkの例に従って,cost = (int)max(-36000, -400 * (length^1.5)) という式をそのまま使っている記事を見かけますが,この式はあくまでこの辞書だけを使って mecab を AutoLink 専用に用いる場合 を想定して書かれたもので,これを ipadic と混ぜると基準値が合わなくなると思います。ipadicにある生起コストは四桁ぐらいまでの正の数ですが,この式だとコストがマイナスになるので,文脈に関わらずほぼ常にユーザ辞書のエントリが優先されるでしょう。(勿論そういう意図ならそれで構わないのですが。)

既存辞書から,同じ品詞&同じ長さの形態素の平均コストを計算しておく方法

上とは別に,もう少し単純に生起コストの目安を得る方法もあります。

例えば既存のipadicの中から「固有名詞/一般」の単語だけを取り出し,単語の長さごとに生起コストの平均をとっておきます。

文字数 平均コスト
1 8998
2 8242
3 8339
4 7989
5 6947
... ...
10 5038
... ...

このテーブルをあらかじめつくっておき,新たな単語を登録する際は,同じ品詞&同じ長さの既存の形態素の平均値をあてはめるようにするわけです。"鼻セレブ"の場合は4文字なので生起コストとして7989を採用することになります。まあ,大雑把ではありますが何もしないよりはだいぶマシな感じになると思います。

mecab-dic-overdrive のコスト生成方式

mecab-dic-overdrive では,この二つの方式を組み合わせてコスト決定を行います。デフォルトの動作は

  1. 同じ品詞&同じ長さの既存単語の平均コスト (※条件を満たす既存単語が見つからない場合はあらかじめ決めた固定値を利用)
  2. 上で示した「単独で現れた場合にそれ以上細分割されないぎりぎりのコスト」x 0.7

の,どちらか小さい方をとるようになっています。(この動作は GenDic.pm の200行目からのあたりを編集すればカスタマイズ可能です。)

前者の計算には辞書の元のcsvファイル,後者の計算には left-id.def, right-id.def, matrix.def を参照するため,mecab-ipadic のソースの場所を config に設定してやる必要があります。

mecab-dic-overdrive 使用方法

辞書のインストール & ユーザ辞書作成

(1) 事前に必要なライブラリ等の準備
  • あらかじめ mecab本体, および,以下のperlライブラリをインストールしておく
    • Text::MeCab
    • Unicode::Normalize
    • Unicode::RecursiveDowngrade
    • HTML::Entities
    • File::Spec
    • Path::Class
    • Log::Log4perl
  • mecab-dic-overdrive本体をgithubから入手する
  • mecab-ipadic-2.7.0-20070801 をダウンロードし,解凍しておく。(他のバージョンの場合,前述のパッチの段階などでこける可能性があります)
> git clone https://github.com/nabokov/mecab-dic-overdrive.git
> tar -xvzf mecab-ipadic-2.7.0-20070801.tar.gz
(2) config.pl / log.conf の設定

mecab-dic-overdrive/etc/config.pl の内容を環境にあわせてカスタマイズする。最低でも

  • $HOME (mecab-dic-overdrive を解凍したディレクトリ)
  • $DIC_SRC_DIR (mecab-ipadic-2.7.0-20070801 を解凍したディレクトリ)

は編集してください。

また,ノーマライゼーションを変更したい場合は上の「辞書のノーマライズ」の項を参考に default_normalize_opts を編集してください。

(例)
default_normalize_opts => [qw(decode_entities strip_html nfkc lc)],

動作ログの書き出し先を変えたり,ログレベルを変えたい場合は etc/log.conf を編集してください。

(例)
log4perl.rootLogger=DEBUG, LOGFILE
log4perl.appender.LOGFILE.filename=/path/to/log.txt
(3) utf8化+ノーマライズ+パッチ適用された mecab-ipadic の作成
>bin/initialize_dic.pl

これで (1)辞書のutf-8化 (2)辞書へのパッチ適用 (3)辞書のノーマライズ (4)辞書のコンパイル&インストール,までが完了します。

"make install failed" と言われてしまう場合,あるいは既存の辞書 (/usr/local/lib/mecab/dic/ipadic) を残して別の場所へインストールしたい場合は,以下のように別の場所へ手作業で辞書をコピーし, mecab 呼び出しの際に -d オプションを使って辞書ディレクトリを指定するようにしてください。

(手動で /usr/local/lib/mecab/dic/ipadic-utf8 へインストールする場合の例)

>bin/initialize_dic.pl --noinstall
>mkdir /usr/local/lib/mecab/dic/ipadic-utf8
>cp [ipadicのソースディレクトリ]/*.bin /usr/local/lib/mecab/dic/ipadic-utf8/
>cp [ipadicのソースディレクトリ]/*.def /usr/local/lib/mecab/dic/ipadic-utf8/
>cp [ipadicのソースディレクトリ]/*.dic /usr/local/lib/mecab/dic/ipadic-utf8/
>cp [ipadicのソースディレクトリ]/dicrc /usr/local/lib/mecab/dic/ipadic-utf8/

(このあと etc/config.pl の dicdir = "/usr/local/lib/mecab/dic/ipadic" を
 "/usr/local/lib/mecab/dic/ipadic-utf8" へ変更する)

(mecab をコマンドラインから使う場合は -d オプションを指定)
>mecab -d /usr/local/lib/mecab/dic/ipadic-utf8/

(4) wikipediaのデータからユーザ辞書を作成する

日本語版wikipediaのダンプサイトから jawiki-latest-page.sql.gz を入手して misc/dic 以下に .gz のまま保存します。( zcat/gzcat が利用できない環境では解凍しておきます。ファイル名や置き場所を変えたい場合は GenDic/WikipediaFile.pm を適宜変更してください。)

>bin/generate_dic.pl --target=wikipedia_file

とすると,SQLファイルを直接読み込んで記事タイトルを抽出し,「固有名詞/一般」としてユーザ辞書ファイル misc/dic/wikipedia.dic に書き出します。

※SQL文を直接強引にパースする仕組みのため,今後wikipediaのダンプ仕様に変更があると動かなくなる可能性もあります。その場合はいったんデータをDBに読み込み,DBから書き出しを行うより確実な方法( --target=wikipedia_file のかわりに --target=wikipedia を指定) も利用できます。詳しい設定方法は GenDic/Wikipedia.pm を参照してください。

(5) 顔文字辞書からユーザ辞書を作成する (optional)

顔文字辞書用として様々な場所で配布されているtsvを読み込んでユーザ辞書を作ることができます。

読み込み元は misc/dic/kaomoji.tsv にあるので,追加したい顔文字がある場合はここに追記したあと,

>bin/generate_dic.pl --target=kaomoji

とすると,各顔文字を「記号/一般」として misc/dic/kaomoji.dic に書き出します。

wikipedia.dic にある記号系エントリより優先度を高くするために,先に作成した wikipedia.dic を読み込んだ mecab をつかって生起コスト計算をするようになっています。そのため,misc/dic/wikipedia.dic がないと動きません。この仕様を変更したい場合は GenDic/Kaomoji.pm の defaults メソッドを編集してください。

(6) その他,wikipediaにない固有名詞などを追加する (optional)

上記以外に追加したい名詞がある場合は misc/dic/simple_list.txt に改行区切りで列挙し,

>bin/generate_dic.pl --target=simple_list

とすると,それらをすべて「名詞/固有名詞/一般」として読み込み,misc/dic/simple_list.dic に書き出します。

作成した辞書の利用

上記ステップ(4)-(6)で作成したユーザ辞書は,mecab の -u オプションで指定して利用できます。

>mecab -u misc/dic/wikipedia.dic,misc/dic/kaomoji.dic,misc/dic/simple_list.dic
(使用前)
> mecab
崖の上のポニョニコ動で見た
崖	名詞,一般,*,*,*,*,崖,ガケ,ガケ
の	助詞,連体化,*,*,*,*,の,ノ,ノ
上	名詞,非自立,副詞可能,*,*,*,上,ウエ,ウエ
の	助詞,連体化,*,*,*,*,の,ノ,ノ
ポニョニコ	名詞,一般,*,*,*,*,*
動	名詞,一般,*,*,*,*,動,ドウ,ドー
で	助詞,格助詞,一般,*,*,*,で,デ,デ
見	動詞,自立,*,*,一段,連用形,見る,ミ,ミ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
EOS

(使用後)
>mecab -u misc/dic/wikipedia.dic
崖の上のポニョニコ動で見た
崖の上のポニョ	名詞,固有名詞,一般,*,*,*,崖の上のポニョ,Wikipedia:1070057
ニコ動	名詞,固有名詞,一般,*,*,*,ニコ動,Wikipedia:1347271
で	助詞,格助詞,一般,*,*,*,で,デ,デ
見	動詞,自立,*,*,一段,連用形,見る,ミ,ミ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
EOS

utf-8版 ipadic をデフォルトの場所とは違う場所に書き出した場合は,-d オプションも指定します。

>mecab -d /usr/local/lib/mecab/dic/ipadic-utf8

ノーマライザの利用

前述のように,解析時には辞書作成時と同じノーマライザを通さないと意味がないので,作成した辞書を使う場合には以下のように MecabTrainer::NormalizeText のインスタンスを通すようにしてください。

use Encode;
use MecabTrainer::NormalizeText;
new $normalizer = MecabTrainer::NormalizeText->new(
    [decode_entities strip_single_nl nfkc lc]
);

$normalized_decoded_text = $normalizer->normalize(
    Encode::decode('utf8', $raw_input_text)
)

使用方法については bin/normalize_text.pl のソースなども参照。

コマンドラインで使う場合には bin/normalize_text.pl をパイプでかませて利用することができます。

使用例と解析結果の例を以下にいくつか載せておきます。

> bin/normalize_text.pl | mecab -d /usr/local/lib/mecab/dic/ipadic-utf8/ -u misc/dic/wikipedia.dic,misc/dic/kaomoji.dic
ひまなう(´・ω・`)
^D
ひま	名詞,一般,*,*,*,*,ひま,ヒマ,ヒマ
なう	助詞,終助詞,*,*,*,*,なう,ナウ,ナウ
( ́・ω・`)	名詞,固有名詞,一般,*,*,*,( ́・ω・`),Wikipedia:700982
EOS

久々更新〜 お腹へったょ
^D
久々	名詞,一般,*,*,*,*,久々,ヒサビサ,ヒサビサ
更新	名詞,サ変接続,*,*,*,*,更新,コウシン,コーシン
ー	記号,一般,*,*,*,*,─,─,─
お腹	名詞,一般,*,*,*,*,お腹,オナカ,オナカ
へっ	動詞,自立,*,*,五段・ラ行,連用タ接続,へる,ヘッ,ヘッ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
ょ	助詞,終助詞,*,*,*,*,よ,よ,よ

朝からテゴマスのあいCMやってた
^D
朝	名詞,副詞可能,*,*,*,*,朝,アサ,アサ
から	助詞,格助詞,一般,*,*,*,から,カラ,カラ
テゴマスのあい	名詞,固有名詞,一般,*,*,*,テゴマスのあい,Wikipedia:2035668
cm	名詞,一般,*,*,*,*,CM,シーエム,シーエム
やっ	動詞,自立,*,*,五段・ラ行,連用タ接続,やる,ヤッ,ヤッ
て	動詞,非自立,*,*,一段,連用形,てる,テ,テ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
EOS

( ゚∀゚)アハハ八八ノヽノヽノヽノ \ / \/ \
^D
( ゚∀゚)アハハ八八ノヽノヽノヽノ  / / 	記号,一般,*,*,*,*,( ゚∀゚)アハハ八八ノヽノヽノヽノ  / / \n

カスタムの読み込みクラスの作成

GenDic/ 以下にサブクラスを作成することで,任意の入力からユーザ辞書をつくることができます。MecabTrainer::GenDic クラスを継承して

  • 入力ストリームの開き方
  • 入力を一行ずつ読み,パースする方法
  • 読みとった単語にどんな品詞,featuresを割り当てるか

を記述しておけば,生起コストの計算や辞書のコンパイルは親クラスがすべて肩代わりしてくれる仕組みです。詳しくは GenDic ディレクトリ以下の各ソースを参照して下さい。

generate_dic.pl の --target オプションでサブクラス名を指定 (CamelCaseを小文字+"_"に置き換え) することで,作成したサブクラスを呼び出すことができます。

(サブクラス TestClass.pm を指定する場合の例)
>bin/generate_dic.pl --target=test_class

decision tree (決定木) でユーザエージェント判定器を作ってみる

カテゴリ
ブックマーク数
このエントリーを含むはてなブックマーク はてなブックマーク - decision tree (決定木) でユーザエージェント判定器を作ってみる
このエントリーをはてなブックマークに追加

アクセスログのユーザエージェント(UA)からブラウザを判別するのって,みんな何使ってますか?

自分が作ったアクセス解析システムでは HTTP::BrowserDetectHTTP::MobileAgent にそれぞれ独自パッチをあてたものを使っています。これらはルールベースの判定器なので,新しいブラウザや新種の bot が登場するたびに手作業でルールを追加し,パッチを作って配布するという作業が必要になります。

この更新作業が大変面倒くさくて対応が遅れがちになるので,「このUA文字列はこのブラウザですよ、という例を大量に与えたら、自分で勝手に判定ルールを学習してくれるようになったら便利なのになぁ」と思い,decision tree (決定木)を使ってみることを思い立ちました。

目標は,

  • "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15" は Firefox
  • "Mozilla/5.0 (iPod; U; CPU iPhone OS 4_1 like Mac OS X; ja-jp) AppleWebKit/532.9 (KHTML, like Gecko) Version/4.0.5 Mobile/8B117 Safari/6531.22.7" は Safari
  • ...

というふうに例を与えていくと,UA文字列からブラウザを判定するルールを自動的に獲得するプログラムを作成することです。Perlの場合 AI::DecisionTreeというライブラリがあって,手軽に decision tree で遊ぶことができます。

BlogPaint

decision tree の動きを見てみる

以下の簡単なスクリプト dt_test.pl を使って,AI::DecisionTree がルールを学習する過程をみていきましょう。(あらかじめCPAN経由でAI::DecisionTreeがインストールされていることが前提です。)

・dt_tree.pl

#!/usr/bin/perl

use strict;
use AI::DecisionTree;

my $dtree = new AI::DecisionTree( prune => 0 );

# stdinから教師データ(UA文字列+タブ+正解文字列)読み込み
while(<>) {
    chomp;
    my ($attributes, $result) = split(/\t+/);

    $dtree->add_instance(
        attributes => { map { $_ => 1 } split(/\s+/, $attributes) }, # UA文字列をスペースで分割したものをすべてattributeとする。
        result => $result,
    );
}

$dtree->train; # 学習

# 学習したルールを表示
print "\n--- rules\n";
print join "\n", $dtree->rule_statements;
print "\n---\n";

動作例

> ./dt_test.pl
Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15	Firefox/3.6
Mozilla/5.0 (iPod; U; CPU iPhone OS 4_1 like Mac OS X; ja-jp) AppleWebKit/532.9 (KHTML, like Gecko) Version/4.0.5 Mobile/8B117 Safari/6531.22.7	Safari/4.0
^D
--- rules
if Mac='' -> 'Firefox/3.6'
if Mac='1' -> 'Safari/4.0'
---
>

イタリックの部分がユーザ入力です。dt_test.pl を起動したあと,Firefox と Safari を表す2行の教師データ (UA文字列と正解のブラウザ名をタブでつなげたもの) を入力しています。プログラムはこの教師データを

  • 「"Mozilla/5.0", "(Windows;", "U;", "NT", "6.1;" ... などの文字列があれば "Firefox/3.6"」
  • 「"Mozilla/5.0", "(iPod;", "U;", "CPU" ... などの文字列があれば "Safari/4.0"」

というふうに記録していきます。この "Mozilla/5.0" などの文字列ひとつひとつを attribute と呼びます。ここでは与えられたUA文字列を空白で分割したものを attribute として利用しています。

プログラムは与えられた例の中から "Firefox/3.6" と "Safari/4.0" を見分ける一番簡潔なルールを探します。その結果,"Mac" という attribute に注目し,

  • 「"Mac" という attribute がなかったら Firefox,あったら Safari」

というルールを導きだしました。

実際には "Mac" があっても Firefox の可能性はあります。その例を教師データとして追加し,プログラムがルールをどう修正するかみてみましょう。

> ./dt_test.pl
Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15	Firefox/3.6
Mozilla/5.0 (iPod; U; CPU iPhone OS 4_1 like Mac OS X; ja-jp) AppleWebKit/532.9 (KHTML, like Gecko) Version/4.0.5 Mobile/8B117 Safari/6531.22.7	Safari/4.0
Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; ja-JP-mac; rv:1.9.2.11) Gecko/20101012 Firefox/3.6.11 GTB7.1	Firefox/3.6
^D
--- rules
if like='' -> 'Firefox/3.6'
if like='1' -> 'Safari/4.0'
---
>

今度は "Mac" という attribute の有無では Firefox と Safari とを見分けられなかったため,

  • 「"like" がなければ Firefox,あれば Safari」

というルールに変わりました。まあ確かに言われてみれば...という気がしないでもないですが,ここでさらに Internet Explorer と Chrome の例を二つ加えて混乱させてみましょう。

>./dt_test.pl 
Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15	Firefox/3.6
Mozilla/5.0 (iPod; U; CPU iPhone OS 4_1 like Mac OS X; ja-jp) AppleWebKit/532.9 (KHTML, like Gecko) Version/4.0.5 Mobile/8B117 Safari/6531.22.7	Safari/4.0
Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; ja-JP-mac; rv:1.9.2.11) Gecko/20101012 Firefox/3.6.11 GTB7.1	Firefox/3.6
Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 5.1; Trident/4.0; GTB6.6; .NET CLR 1.1.4322)	Internet Explorer/8.0
Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_5_8; en-US) AppleWebKit/534.13 (KHTML, like Gecko) Chrome/9.0.597.102 Safari/534.13	Chrome/9.0
^D
--- rules
if like='' and MSIE='' -> 'Firefox/3.6'
if like='' and MSIE='1' -> 'Internet Explorer/8.0'
if like='1' and AppleWebKit/534.13='' -> 'Safari/4.0'
if like='1' and AppleWebKit/534.13='1' -> 'Chrome/9.0'
---
>

今度は判定が以下のように二段階になりました。

  • "like" がなかったら
    • → "MSIE" がなかったら Firefox,あったら InternetExplorer
  • "like" があったら
    • → "AppleWebKit/534.13" がなかったら Safari,あったら Chrome

まだまだUAの判定ルールとして使い物になるレベルではないですが,たった5例しか教師データを与えていないのにここまで簡潔なルールを導きだしたことに注目してください。

このように decision tree は,与えられた例を一般化してツリー状の分類ルールを推定してくれるわけです。

もう少し実用的なUA判定器と,教師データセットを作成する

ここまでで decision tree の動きを確認してきましたが,これを実用的なものにするには

  1. UA文字列をスペースだけで分割するのは大雑把すぎるので,もう少し工夫して精度を上げる。
  2. 種別 (PCブラウザ/モバイルブラウザ/クローラ etc.),OS名,ブラウザ名の三段階の判別ができるようにする。
  3. 大量の教師データを与えて,あらゆるパターンを網羅できるようにする。
  4. (しかし,大量の教師データ読み込みには時間がかかるので) いったん学習したルールを保存しておけるようにする。

などの努力が必要です。

UA文字列から attribute を抽出する方法を工夫する

例えば

Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US) AppleWebKit/534.13 (KHTML, like Gecko)

というUA文字を見てみると,

  • 空白よりも先に,"(", ")", ",", ";" などの記号で分割する。
    • → "Windows NT 6.1", "Mozilla/5.0" といった文字列が,ひとまとまりのまま attribute になる。
  • それらをさらに空白や"/" などで分割してみて,分割できたらそれらも attribute に加える。
    • → "Windows NT 6.1", "Windows", "NT", "6.1", "Mozilla/5.0", "Mozilla", "5.0" などがすべて attribute になる。

という二段階の文字列分解をするとうまくいきそうな気がします。

最初から空白や"/"で分割してしまわないのは,例えば "Windows NT 5.0" と "Mozilla/5.0" の "5.0" は前の文字列とくっついた状態でないと意味をなさないからです。かといって "Mozilla/5.0" のようにバージョン番号がくっついたものだけを attribute にしてしまうと,分類器が "Mozilla/4.0" と "Mozilla/5.0" の類似性に気づかず,一般化に苦労するはめになります。そこで,細分割前の文字列と後の文字列を両方 attribute として記録しておき,どの attribute を採用するかは AI::decisionTree に任せることにします。

  • UA文字列から,attribute の候補をすべて array ref で返すメソッドの例
sub breakdown_ua {
    my ($ua) = @_;

    $ua = lc($ua);
    my @ua_str = map { s/^\s+//;s/\s+$//;$_ } grep $_, split (/[,;\"\(\)]/, $ua);
    my @sub_ua_str;
    for (@ua_str) {
        push @sub_ua_str, grep { $_ !~ /^[0-9\._\-\+]*$/ } split(/[\s\/\-]/);
    }

    return [@ua_str, @sub_ua_str];
}

※UA文字列の付け方に関しては,[ここ][ここ]が参考になりました。

UA種別,OS名,ブラウザ名の三段階の判別ができるようにする

UA判定器の典型的な使い方としては,

  • "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15"
    • → PCブラウザ / Windows 7 / Firefox/3.6
  • "DoCoMo/2.0 N01B(c500;TB;W24H16) Mobile Browser DoCoMo N01B"
    • → モバイルブラウザ / DoCoMo / N01B
  • "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html) "
    • → クローラ / - / Googlebot

というふうに一つのUA文字列から三段階のタイプ判定をすることが挙げられます。

しかし,decision tree は基本的には「与えられた attribute のセットから,ひとつの判定結果を導きだす」ために使われます。上の例のように三段階の判定を同時にしたい場合は

  1. "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15" は "PC - Windows 7 - Firefox/3.6" という名前のブラウザです」というように,種別/OS名/ブラウザ名をひとまとまりの result として扱う
  2. 分類器を三つ用意し,それぞれを独立に「"Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15" は "PCブラウザ" です」「"Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15" は "Windows 7" です」「"Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15" は "Firefox/3.6" です」と訓練していく。

の二種類の方法があります。組み合わせが増える分,前者のほうがルールが無駄に複雑になる気がしたので,今回は後者の方法を採用しました。

十分な量の教師データを用意する

最初の例でみたように,データ量が十分でなかったり偏っていたりすると実用的なルールが学習できません。

今回は

  1. DoCoMo, SoftBank, AU の各キャリアの公式サイトの情報を元に独自に生成したもの
  2. useragentstring.com のデータを色々アレして独自に加工したもの
  3. livedoor のサーバの実際のアクセスログのUAをサンプリングし,(一部UAの端末IDフィールドを取り除いたり,重複処理をした後) すでに利用しているルールベースのUA判定器にかけたもの

の三種類のデータを用意しました。

試してみたい方は [こちら] から自由にダウンロードして頂けます

  • データの正確性は保証しません
  • いずれもUA文字列の後ろにタブ区切りでフィールドが3つ入っています。フィールドは以下の通りです。
    • PC&スマートフォンブラウザは "Browser / (OS名) / (ブラウザ名)"
    • モバイルブラウザは "Mobile Browser / (キャリア名) / (機種名)"
    • クローラは "Crawler / (空フィールド) / (クローラ名)"

学習済みの判定器を保存しておけるようにする

上のような大量のデータを読み込んでルールを生成するにはそれなりの時間が必要になります。。プログラムを起動するたびにデータ読み込みとルール生成をしていては,実際の判別処理ができるようになるまでに時間がかかってしまいます。

そこで,学習プログラムが AI::DecisionTree のインスタンスをStorable にてファイルに保存し,判別プログラムはそこからインスタンスを解凍して使うようにプログラムを二つに分割します。

出来上がったものがこちらです

  • build_tree.pl (与えられた例から decision tree を構築する)
#!/usr/bin/perl

use strict;
use AI::DecisionTree;
use Storable qw(store_fd);

$| = 1;

my $N_TREES = 3;
my $FREEZER = 'frozen_dt.dat';

my @trees;
for my $i (1..$N_TREES) {
    push @trees, new AI::DecisionTree(
        prune => 1,
        noise_mode => 'pick_best',
    );
};

while (<>) {
    chomp;
    my ($ua, @results) = split(/\t/);
    return unless $ua;

    my $ua_fragments = breakdown_ua($ua);

    for my $i (0..$N_TREES-1) {
        next unless $results[$i];
        $trees[$i]->add_instance(
            attributes => {
                map {$_ => 1} @$ua_fragments,
            },
            result => $results[$i],
        );
    }
    print ".";
}

print "\ndone.\n";

open FH, ">$FREEZER";
for my $i (0..$N_TREES-1) {
    print "\ntraining tree $i\n";
    $trees[$i]->train;

    my @s = $trees[$i]->rule_statements;
    print "\n==============\n";print join "\n",@s;print "\n";

    store_fd $trees[$i], \*FH;
}
close FH;

sub breakdown_ua {
    my ($ua) = @_;

    $ua = lc($ua);
    my @ua_str = map { s/^\s+//;s/\s+$//;$_ } grep $_, split (/[,;\"\(\)]/, $ua);
    my @sub_ua_str;
    for (@ua_str) {
        push @sub_ua_str, grep { $_ !~ /^[0-9\._\-\+]*$/ } split(/[\s\/\-]/);
    }

    return [@ua_str, @sub_ua_str];
}
  • 使用例
> cat *.tsv | build_tree.pl
  • decide_ua.pl (あらかじめ保存した decision tree を使ってUAの判定をする)
#!/usr/bin/perl

use strict;
use AI::DecisionTree;
use Storable qw(fd_retrieve);

my $N_TREES = 3;
my $FREEZER = 'frozen_dt.dat';

my @trees;
open FH, $FREEZER;
for my $i (1..$N_TREES) {
    push @trees, fd_retrieve(\*FH);
}
close FH;

my $ua = $ARGV[0];
if ($ua) {
    my $ua_fragments = breakdown_ua($ua);
    for my $i (0..$#trees) {
        my $result = $trees[$i]->get_result(
            attributes => {
                map {$_ => 1} @$ua_fragments,
            }
        );
        print "$result\n";
    }
} else {
    for (@trees) {
        my @s = $_->rule_statements;
        print "\n==============\n";print join "\n",@s;print "\n";
    }
}

sub breakdown_ua {
    my ($ua) = @_;

    $ua = lc($ua);
    my @ua_str = map { s/^\s+//;s/\s+$//;$_ } grep $_, split (/[,;\"\(\)]/, $ua);
    my @sub_ua_str;
    for (@ua_str) {
        push @sub_ua_str, grep { $_ !~ /^[0-9\._\-\+]*$/ } split(/[\s\/\-]/);
    }

    return [@ua_str, @sub_ua_str];
}

※ breakdown_ua メソッドなど,生成と判定の両方で必要な処理・変数がいくつかありますので,実用に使う場合は適宜共通化してください。

  • 使用例
> decide_ua.pl "Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; .NET4.0C)"
Browser
Windows 7
Internet Explorer/8.0
>

decide_ua.pl は,引数を与えた場合はそのUA文字列に対する判定結果を,引数がない場合は保存された判定ルールを,それぞれ表示します。

オチ

で、こうして出来たUA判定器を実際の業務で使っているかということですが、結局使っていません。

確かに,ルールを手で作成するのではなく例を列挙していくだけでよい,というのはメンテナンスが楽そうなのですが,そのためには「webから簡単に例が追加できて,再学習→テスト→本番反映がボタンひとつでできる」という管理システムまで作らないと意味ないし,そこが非常に面倒くさかったので…

また,例えばルールベースの場合,このようにバージョン番号や機種名の取り出し方を記述しておくことで、新しく"MSIE 99.9" など,教師データにない新顔が出現した場合にも対応し続けることができます。

if ($ua =~ /MSIE\s+([0-9\.]+)/i) {
  $browser = 'Internet Explorer';
  $version = $1;
}

しかし,ここで示したような decision tree 方式だと,バージョンや機種毎に別々の教師データが必要になります。(可変部分を全部 "#" に置き換えるなどの工夫が出来そうな気はするけど…。)

というわけで,現状ルールベースでなんとかなっている+いろいろ面倒くさい,のコンボでいまのところ試しただけで終わりになっているのですが,この decision tree はUA判定器以外にも様々な用途に使えますので,心の片隅においておくときっといつか役に立つときが来ると思います。

(この記事中の「面倒くさい」の出現頻度: 4回)

本当はもっと速いImlib2: Imlib2でもImageMagickと同じ仕組みでサムネイル画像生成を速くする方法

カテゴリ
ブックマーク数
このエントリーを含むはてなブックマーク はてなブックマーク - 本当はもっと速いImlib2: Imlib2でもImageMagickと同じ仕組みでサムネイル画像生成を速くする方法
このエントリーをはてなブックマークに追加
こんにちは!こんにちは!
開発部のやましーです。
今回はSmallLightの中でやっている細かいことについてです。



SmallLightとは


SmallLightとは、2010年末にlivedoor labs EDGEにてリリースした画像サムネイル生成用Apacheモジュールです。



JPEG画像の読み込み処理の最適化

JPEG画像は、その圧縮アルゴリズムの特性で読み込み時に1/2、1/4、1/8にダウンスケーリングすることができます。libjpegでは画像読み込み時にjpeg_decompress_struct構造体のscale_denomにダウンスケーリング指数を指定します。

SmallLightではこれをJPEGヒントオプションとして実装しています。パターン文字列に jpeghint=y を付与することで有効になります。(SmallLightの README の100行目)

JPEGヒントオプションはImageMagickとImlib2に実装してあります。
それぞれの実装は下記のようになっています。

ImageMagick

ImageMagickには既にこの処理が備わっています。
詳しくは下記のページにて解説つきで詳しく述べられています。

本当は速いImageMagick: サムネイル画像生成を10倍速くする方法

具体的にはというと、ImageMagickは「jpeg:size」オプションを渡すことで自動的にscale_denomによるダウンスケーリングをさせることが出来るため、118行目辺りにMagickSetOptionでjpeg:sizeをセットするコードを追加しただけです。

Imlib2

Imlib2にはこの処理をできるオプションが無かったため、JPEGローダーの部分をSmallLight側に内包しました。

load_jpeg関数のコードの場所は73行目辺りになります。先にJPEGヘッダー情報から画像サイズを取得し、この関数が呼ばれるときに渡された縮小後のサイズを元にscale_denom値を指定しています。load_jpeg関数はピクセルデータを返すので、Imlib2のimlib_create_image_using_dataを使用してピクセルデータからImageインスタンスを生成しています。



ベンチマークテスト

上記のJPEGヒントオプションでの最適化を行わない場合と行った場合の処理速度のベンチマークテストを行いました。

条件


ベンチマークテストの実施条件。

  • 画像変換エンジンはImageMagickとImlib2を使用
  • 大きい画像2560x1920と小さい画像640x480を、それぞれ250x187に縮小する処理を100回繰り返す
  • JPEGヒントオプション利用の有無
  • 画像キャッシュなどは行わない

結果

ベンチマークテストの実施結果。

エンジン 画像サイズ JPEGヒント
無効 有効
ImageMagick 2560x1920 43.39s 12.96s
640x480 8.53s 8.41s
Imlib2 2560x1920 10.55s 3.06s
640x480 0.69s 0.70s
この結果からは、ImageMagickもImlib2もJPEGヒントを有効にすると画像サイズ2560x1920の処理時間は1/3〜1/4程度の短縮が見られ、画像サイズ640x480はほとんど変わらないことが分かります。これは画像の読み込み時に予めダウンスケーリングするという最適化の処理なので、画像サイズ2560x1920は640x480に大きくダウンスケーリングされるため読み込み速度の短縮に大きく影響しますが、画像サイズ640x480はこれ以上小さく読み込めずダウンスケーリングされないためです。

読み込み・変換・保存の処理時間

具体的にどの処理時間がどれくらい短縮したのかを見るために、画像サイズ2560x1920の読み込み・変換・保存の処理時間を計測しました。

エンジン 処理 JPEGヒント
無効 有効
ImageMagick 読み込み 221ms 48ms
変換 233ms 88ms
保存 4ms 4ms
Imlib2 読み込み 186ms 44ms
変換 15ms 1ms
保存 2ms 2ms
ImageMagickもImlib2も読み込み処理時間の短縮と共に変換処理時間も短縮されています。これは通常は2560x1920の画像を250x187へ縮小していたのが、最適化による読み込み時のダウンスケーリングによって640x480の画像を250x187へ縮小すればよくなったためです。



課題


読み込み処理の最適化

現在のSmallLightは、基本的に全てをImageMagickやImlib2に任せてあまり複雑化させないように作り始めたので、読み込み処理の最適化は行われていません。ImageMagickやImlib2はメモリ上に用意した元画像のバイナリ、またはファイルから画像を読み込むため、その辺の最適化はやりにくいところです。
しかし直接libjpegなどの画像ライブラリを使えば、フィルターの入力ストリームを徐々にライブラリに渡すことで元画像サイズ分の入力バッファを持たなくて済むため、無駄なメモリ間のコピーやメモリ消費量を抑えることができます。

Imlib2でのGIF形式の出力

Imlib2のGIFローダープラグインはGIF形式の出力に対応していません。現状では元画像がGIF形式ならJPEG形式で出力するなどの回避策が必要なので、GIF形式での出力機能を内包するなどの対応をする必要があります。


今後もSmallLightのような「地味だけど結構需要があったりする小物」を何か作って公開していければと思います。