JavaScriptで形態素解析してみた
本文を読む前にこのページを開いておこう！(※大量のダウンロードが始まります。太い回線で試してみてください)
http://shogo82148.github.com/igo-javascript/
JavaScriptで形態素解析を行うプログラムとしては、TinySegmentater(作者の工藤さんはMeCabの作者でもあるすごい方です)が有名ですね。TinySegmentaterは非常にコンパクトな設計で、わずか25kB程度の容量しかないも関わらず、95%の精度で分かち書きを行えるとのことです。コンパクトで便利なので、他の言語にも多数移植されています。
しかし、辞書を持っていないため、品詞や読みを推定することは出来ません。HTML5の登場によってJavaScriptでできることがかなり増えてきたし、JavaScriptの実行速度もかなり速くなったし、ネットワーク環境もよくなって動画みたな大容量コンテンツも扱えるようになったし、そろそろJavaScriptでも辞書を使った形態素解析ができるんじゃないか。この前Igoのソースを読んでそんなことを考えたのでやってみました。
ソースはgithubにigo-javascriptとしてあげておきました。
igo-pythonのソースを参考にして書いてみました。サーバにigo-pythonと辞書ファイルを上げておけば簡単に使えるはずです。CGIとかPHPとかRuby on Railsとかよくわからないものをサーバにインストール必要は全くありません。静的ファイルをアップロードできる環境であればそれだけでOKです。セキュリティの関係で残念ながらローカルでは使えません。
クライアントは Chrome 17 と FireFox で動作を確認しました。IE・・・？そんなブラウザは知りません。
辞書ファイルにはigoで生成したものをそのまま使います。・・・はい、そのまま。
igoの辞書ファイルは全部で40MB程度あって、使う時にはこれをすべてダウンロードしなければなりません。
・・・いくらネットワーク環境が良くなったとはいえそのままは大きすぎた・・・。試す時は気長に待ちましょう。
一回ダウンロードしてしまえば、解析自体はかなり高速です(実測したわけではありませんが)。次回以降のアクセスもキャッシュが効くから高速になるはず。
辞書のサイズは大幅に削らないと。何か良い圧縮方法は無いものか・・・。
igo-javascriptを試してみたいかた向けに、github pages(githubを使ってwebページ)を使ってお手持ちのブラウザで試せるようにしてみました。
http://shogo82148.github.com/igo-javascript/
一番最初に示したリンクと同じものですね。一行目を見てリンク先を開いて置けば、この文章を読み終わったころには、ダウンロードが終わっている・・・と信じたい。
Igo 0.4.5 リリース
Igo 0.4.5がリリースされたようです。
日曜日に報告したバグはちゃんと修正されていました。
素早い対応ありがとうございます。
この前の記事にIgoの作者さんからコメントをもらって気がついたんだけど、MeCab-ipadicのright-idとleft-idの数一緒だったんだね。Igoのバグはright-idとleft-idの個数を取り違えていたことにあったんだけど、数が一緒なら問題なく動いてしまうわけだ。
・・・あと、僕自身right-idとleft-idを色々と混同していたみたいですね。問題があったのは「左側の形態素の右文脈ID」と「右側の形態素の左文脈ID」の間のコストを計算する部分。「左側の形態素の～ID」と「左文脈ID」に同じ「left-id」という名前が付けられていたので混乱してました。
加えて混乱の元になったのが「net/reduls/igo/bin/Matrix.java」に書かれていた以下のコメント。
// NOTE: tmpMatrixという一時配列を用いている理由 // // この段階で、fmos.putShort(cost)、などとしてファイルに書き出した場合、 // matrix[leftId][rightId]=cost、といった配列ができる。 // // それでも特に問題はないのだが、今回のケースでは、 // 「rightIdが固定で、leftIdのみが変動する」といったようなメモリアクセスパターンが多い。 // // そのためtmpMatrix配列を用いて、コスト値の並び順を変更し、 // matrix[rightId][leftId]とったように、rightIdが第一添字になるようにした方が // メモリアクセスの局所性が高まり(多分)、若干だが処理速度が向上する。 tmpMatrix[j*leftNum + i] = cost;
外のループはi,jの順番になっているから、「leftNumごと飛び飛びにアクセスしてるじゃん！コメントと違うじゃん！」と思ってrightIdとleftIdを入れ替えるパッチを書いちゃった。でも、これ、よく考えてみると辞書作成時ではなく、解析時の事をいっていたみたい。辞書作成時は少しくらい時間かかってもいいもんね。
「現在の解析ノード」は固定で「遷移コストを最小限にするには、一つ前の形態素はどれが適当か」ってことを計算するから「rightIdが固定で、leftIdのみが変動する」アクセスパターンになるというわけだ。(多いと言っても一つの解析ノードに対してすべてのleftIdを試すわけではなく、せいぜい10件とかそんなもんだろうから処理速度の向上は本当に「若干」だろうけど)
うーん、こういう製作者の意図はもう少しスムーズに読み取れるようになりたい。
散々悩まされたけど、普段見ようと思っても結局見ないソースコードを読む機会になり、勉強になりました。
MeCab互換の形態素解析器 Igo でグロンギ語変換(+ そこから、始まる Igo のデバッグ)
この前のLTで @jewel_x12 さんがDonauってサービスを発表してくれました。内容も面白かったんだけど、Igo-Rubyってのを使ってて「Pure Rubyでこんなことができるんだ！」と関心した。よくよく調べてみると Igo と言うのは元は Java で書かれたもので、構造が比較的簡単なのでいろんな言語にも移植されているようです。最近すっかり Pythonista になってしまったので、Python移植が無いものかと調べてみたらちゃんとありました(igo-python)。
GAEなどPure Pythonでないと動かない環境でも使えるので、これは便利そうです。
この Igo さん、どうやら MeCab と互換性があるらしく、MeCabで使っている辞書がそのまま使えます。
・・・ということは、この前作ったグロンギ語変換辞書もそのまま使える・・・！
ということでやってみた。MeCabとインターフェースはほぼ一緒。違うのは、Taggerの引数が辞書の場所、parseがノードのリストを返す、strにエンコードする必要なくunicodeをそのまま入れられるってとこくらい(元のMeCabのソースを流用したためにエンコード後の文字列を突っ込んでしばらく「動かねー！」って言ってたのはないしょ)。
で、動かしてみたところ
[原文] 殺してやる！ [グロンギ語訳] ボソギデジャス！ [再翻訳] のろってやる！ [原文] 命拾いしたな [グロンギ語訳] ギボヂヂソギギダバ [再翻訳]命拾い下か [原文] これはクウガのベルト [グロンギ語訳] ボセパクウガンデスド [再翻訳] これ羽クウガのてると
やったーできたー！
・・・あれ・・・？なんか・・・再翻訳結果が・・・ヘン・・・
「のろってやる！」はいいとして(同音異義語がたくさんあるから解析器が違えば結果が違うのは仕方がない)、他は文法的にも明らかにおかしい。自分がつまらないミスをしたんじゃないかとソースを見渡したけど、どこにもおかしいところはない。そもそもIgo単体で使っても動作が怪しい。
そういうわけで、Igo の trunk に上がっているコードを読んでみました。すると・・・
28 public short linkCost(int leftId, int rightId) {
29 return matrix[rightId*rightSize + leftId];
30 }
118 int minCost = f.cost + mtx.linkCost(f.rightId, vn.leftId);
お気づきいただけるだろうか・・・。メソッドの定義は(leftId, rightId)になっているのに、呼び出し側は(rightId, leftId)で呼び出していることに・・・。
キャアァアアァァ！
どうやら作者の中でrightIdとleftIdの区別が曖昧になっているようです。[rightId*rightSize + leftId]ってところもなんだかおかしいし。
そしてさらに恐ろしいのは、IgoのJava以外への移植版も同じ間違いをしているということ。全部を確認したわけではないけどね。少なくともPython版とRuby版は間違えている。皆さん特に意味を考えずに移植いちゃったんですね。今の今まで修正されてなかったということは、他の言語への移植でも間違えている可能性大なのではないかと。
JavaとPythonについてはPatchを上げておきました。(https://gist.github.com/1908441)
いろいろと逆になっていたので、MeCabの辞書と同じ順番にしておいた。辞書の互換性はなくなるけど、そもそも今までの辞書は何かがおかしいから別にいいよね。
さあ、修正してテスト
[原文] 殺してやる！ [グロンギ語訳] ボソギデジャス！ [再翻訳] 殺してやる！ [原文] 命拾いしたな [グロンギ語訳] ギボヂヂソギギダバ [再翻訳] 命拾いしたか [原文] これはクウガのベルト [グロンギ語訳] ボセパクウガンデスド [再翻訳] これはクウガのベルト
MeCabでやった時の結果と一致。やったー！
これをGAEにでも上げて、変換APIでもつくろうかと思ったけど、Igo のデバッグに疲れたので今日はここまで。
それにしてもなぜ今まで誰もIgoのバグに気が付かなったんだ・・・なぜ正常に解析できていた・・・漢字混じりだとパスがそこまで多くないからな。
グロンギ語変換は同音異義語が多いからパスが大量に生成されるからね。
今回の件は致命的な気がするので、作者にも報告しておきたいと思います。
雪しか祭り行ってきたよー
雪しか祭りでレスキューロボットの実演&操縦体験のお手伝いしてきました。
「今のキーコンフィグだと少し子供には難しすぎる」とか言われたんで操縦体験中にちょこちょこコントローラのソースいじったり、興味津々に見ている子供に「やってみない？」と声を掛けたり、ひっくり返ったNP-01を元に戻したりしてました。反省点とかもあるので忘れないうちにメモっとく。
- Xは横成分、Yは縦成分だろ > 過去の自分
- そう思ってプログラムを修正したら何故か上手く動かない。合っているはずなのに・・・って言って数分悩みました。実際に色々動かしてみたらXとYが逆だったことが判明。ちゃんと名前と意味があっているかを確認しておくべきだったと反省。
- 見張り役を決めておくべきだったかも
- 操縦席をちらっと見たら子供が席に座ってPCいじってたからびっくりした
- 突然中にフォールドの中に飛び込んでくる子供が
- どっちも近くにいる人がすぐに止めたけど、ちゃんと見張りがいた方がいいかも
- 整理券には連番を振りましょう
- 人数わからない。日曜日は連番振りました。62人きてくれたようです。
- ランダムステップの難易度調整難しい
- 子供は真ん中を走ってくれない。操縦体験で、一回だけ横転して動けなくなった。それくらいがちょうどいいのかな？
- NP-01から焦げた臭いが
- 午前と午後の間に休憩を一回挟んだとはいえ、前倒しで操縦体験開始したから、1時間操縦体験+1時間休憩+1時間操縦体験
- 最後の後一人ってところで異臭がしたので急遽R4で操縦体験をしてもらうことに
- ボディーに外から触ってもぬくもりが感じられる。回路ほんわかあったかい。モータアッツアツ。
- 何も工夫しないと往復約10m×60回=約600mくらいが限界
- 休憩時間にお腹開けて風を通すべきだったね。お腹にも温度センサが必要。
- キラキラネーム()
- 女の子はうまい by sasa
- 女の子逃げてー！
申告制エレベータ
例によってGithub
https://github.com/shogo82148/GoForIt/tree/master/q05
一応送ってみたけど、ギリギリアウトだった気がする。
解いたのはi) ii)のみ。アルゴリズムは問題の通りに実装するだけなので問題無いでしょう。
iii)も一応最適解を求めるプログラム書いたけど、乗客数7人程度が限界。
どの階でドアを開けるかで10通り×何人乗客を乗せて扉を閉じるか6通り＝60通り。一回開け閉めをするだけで60通りもの組み合わせがあるので、力任せの検索では無理ですね・・・。
一応最小解が得られないとわかった時点で枝切りはしているのですが。
「できるだけ少なく」というのいうのは、「(最小じゃなくてもいいから)できるだけ少なく」っていう意味だったんですかね。
[Go For It] 旋律に隠された特徴
Go for itの第4問目、旋律に隠された特徴を考えて見ました。例によって解答のソースコードはGithubにあります。
https://github.com/shogo82148/GoForIt/tree/master/q04
特徴量の演算器に求められている条件は「A≠BかつA＝C」という事ですが、すべての問題を解くためには次の条件をすべて満たす必要があります。
- AとBの特徴量が異なる i)
- AとCの特徴量が等しい i)
- Bと同じ特徴量になる旋律がD,E,Fのうちひとつのみ存在する ii)
- iii)の条件をすべて満たした旋律を生成することができる
これらをすべて満たすだけであれば、次のようなプログラムを書けば解けてしまいます。
def feature(melody):
""" 旋律melodyの特徴量を返す関数 """
if melody==A or melody==C:
return 0
elif melody==B or melody==D:
return 1
else:
return 2
簡単でしたね！
でも、多分この問題はこのような解答を意図したものではないはずです。問題文に書かれた「仕様」も仕様と呼べるか怪しいものです。これはきっと、他の条件は自分で考えてみろ、という事でしょう。
というわけで、少し真面目に考えてみます。旋律の特徴量が持つべき性質にはどのようなものがあるでしょう？
僕は次の2つの性質が必要だと考えました。
- 旋律の絶対的な音の高さについて特徴量が不変である
- 旋律のテンポについて特徴量が不変である
一つ目の「旋律の絶対的な音の高さについて特徴量が不変である」というのは、相対的な音の高さの変化のみが特徴量に影響するという事です。例えば、「ドレミー」という旋律があった場合、1オクターブ高い「ドレミー」を使っても、逆に1オクターブ低い「ドレミー」を使っても同じ旋律の様に聞こえるはずです。そこで「今着目している音符の音の高さ-一つ前の音符の音の高さ」を特徴量の一部として使います。
二つ目の「旋律のテンポについて特徴量が不変である」。すべて四分音符で「ドレミ」となっていた旋律を、すべて八分音符の「ドレミ」に書き換えたとしても、2倍速くなるだけで同じ「ドレミ」の旋律と感じるでしょう。これが二つ目の意味です。これを満たす特徴として「今着目している音符の音の長さ÷一つ前の音符の音の長さ」を使います。
材料は揃ったので、あとはこれを使って一つの特徴量を計算するだけです。試行錯誤で色々試して見ました。その結果∑(ABS(今着目している音符の音の高さ-一つ前の音符の音の高さ)+今着目している音符の音の長さ÷一つ前の音符の音の長さ-1)が最初の条件を満たしそうだということがわかりました。(旋律の譜面とそれを文字列に変換したものとで微妙に違うとかやめてもらえませんかね。譜面を見ながらうまく行きそうと思ってプログマム組んでやってみたら、Cの譜面の最後は休符で終わっているのに文字列変換後だと消えていて計算あわないとか、僕悲しいです。)
これでi),ii)は大丈夫そうです。iii)は少し考え中。
現状は、さっきの式だと小数部がでて面倒なので小数以下を切り捨てて、すでにやってる人と同じ方法をとってやってみた。
でも、無理矢理感が否めないので、もう少し何とかしたいところ。思いついたらここに追記しますね。
日本語とグロンギ語の相互翻訳やってみた
Twitterでの「オンドゥル語なんかよりグロンギ語を」との声を受け、日本語とグロンギ語の翻訳をやってみました。
Githubに上げてあります。
https://github.com/shogo82148/Grongish
これを使うには少しプログラムを組む必要があります。少しだけ遊んでみたいと言う方は、
http://twitter.com/JO_RI_bot
にこの翻訳モジュールを組み込んだTwitterボットをおいておきました。現在ボットは停止中です。復活したらお知らせします。復活したよ！「○○をグロンギ語訳して」「○○を和訳して」とリプライを送ると相互変換の結果を返してくれます。
グロンギ語とは「特撮テレビドラマ『仮面ライダークウガ』に登場する架空の言語。」(Wikipedia)です。オンドゥル語とは違って公式の設定なので、「あ行をガ行に変換する」といった単純な置換えのみで、翻訳が可能です。変換の詳細はグロンギ語 - Wikipediaを参照。
数詞や助詞の扱いが少し面倒なところがありますが、日本語からグロンギ語への翻訳は比較的簡単です。今回はそれに加えて、グロンギ語から日本語への翻訳にもチャレンジしてみました！
日本語からグロンギ語への変換の際、あ行とが行がどちらもガ行に変換されるなど、日本語の複数の音がグロンギ語では同じ音になってしまうため、単純な置換ではうまくいきません。例えば、「ホロ」と「泥(どろ)」はどちらもグロンギ語では「ゾソ」になってしまうため区別ができません。音の並びから意味を正しく読み取って日本語に翻訳する必要があります。
でも、全く別のものが同じ音になるという現象はグロンギ語に限ったことじゃないですよね？
日本語にだって同音異義語があって、同じ音だけど意味が異なるということが頻繁に起こります。「ホロ」だってキャラクタの名前だったり、「幌」だったり、「火炉」だったりします。同じ音でも人間はこれを文脈によって適切に判断することができます。グロンギ語がわかりにくいのは単に慣れの問題です。
さて、これを機械にやらせるにはどうするか。実はパソコンを使っている人なら「音の並びから意味を正しく読み取って日本語に翻訳する」機能にお世話になっているはずです。そう、MS-IMEやGoogle IME、ATOKなどのかな漢字変換ソフトですね。これらのソフトは音の並びでしかない仮名の羅列から、意味を推定し、正しい(と思われる)漢字を当てはめ、日本語の文章を生成します。グロンギ語の和訳も音の並びを日本語の文章に変換すると言う点では大して変わりません。チョットだけ、読み方が違う。それだけです。
元となるかな漢字変換ソフトにはmecab-skkservを使用しました。これはSKKと呼ばれるかな漢字変換サーバを実現するためのソフトですが、裏で実際に変換を行なっているのはMeCabです。そのため、MeCabとの連携ができる言語であれば、手軽にかな漢字変換ができます。このプロジェクトから辞書だけ拝借してきました。
辞書には「『どろ』を『泥』に変換する」と言ったような規則が書いてあります。この読みの部分を「『ゾソ』を『泥』に変換する」のようにグロンギ語に変換してしまいます。こうすることとでかな漢字変換ソフトを、グロンギ語漢字変換ソフトに変身させることができるというわけです。
拗音の扱いなど、少し面倒なところは少しありましたが、やっていることはこれだけです。グロンギ語に変換することによって同音異義語が増えるので、そのぶん少し間違いが多い気がしますが、まあまあの精度で翻訳することができます。
グロンギ語－日本語訳ができたなら、オンドゥル語－日本語訳も同じ方法でできそうです。と思って、実はやってみたのですが、グロンギ語のような単純な置換では無いため、思ったような結果がえられませんでした。読みを単純に置き換えるだけでは不十分で、単語の生起コストとか隣接コストを調整する必要がありそうです。これについてはまたできたらここに書きたいと思います。
