2007-05

Tx: Succinct Trie Data Structure

数千万件の要素(URL)のmapを作りたかったので、Txを試してみた。C++のstd::mapは元データの数倍ものメモリを食ったのに対して、Txは元データの40.5%程のメモリしか必要としなかった。元データの量は大体数Gだったので、十分メモリに保持できてしまう。

検索時間はstd::map等に比べて落ちはするようだが、10msで終わるなら十分すぎるほどなので採用決定。もっと馬鹿でかいデータを入れたりしても落ちたり、データが壊れたりする事も無かったので安心して使えそう。他のアプリケーションにも色々適用できそうなので、書いてみた。

1億件とかそれ以上になると、ディスクを併用しないと無理臭いなぁ。となると流石に処理速度のほうが気になる。そうなって来ると、STXXL: Standard Template Library for Extra Large Data Setsが気になり出す。

flock(2)ではなくlockf(3)だとメールを頂いた。
確かにlockf(3)に変えてみると(lenは0)、排他してくれない。なんで挙動が違うんだ・・・。
２つの違いが分かったらまた書きます。

以下の論文を渡されたので読んでました。

• A Maximum Entropy Approach to Natural Language Processing
• MEによる日本語係り受け解析
• 相対的な係りやすさを考慮した日本語係り受け解析モデル [pdf]

統計的言語モデル(北 研二,辻井 潤一)も参考にしました。MEについては最初の奴よりこの本の方が分かりやすかったです。
来週から実装の予定ですが、どうしたものか。3つ目は精度は出てるけど学習の所でIterative Scalingをしないといけない。この方法を完全に理解してないのと、実装が大変そうというのがある。後2週間しかないので、週明けにその辺を辻井研の人に相談しよう。
しかし工藤さんや岡野原大先生には僕には見えてないものが見えているようにしか思えないなー。
P.S
IterativeScalingも一応理解した。
んでこれはMapReduceっぽく実装出来そう。で、それをやると分散並列化出来て、大規模な素性を持つような学習が可能になりそう。これ絶対ごっごるでやってるなー。

以前人づてに、flock(2)がプロセス間排他はするけどスレッド間排他はしないという話を聞いた。
これが本当だと、今まで自分が書いたマルチスレッドアプリケーションのファイルを扱う部分の根幹が揺らいでしまう。特にファイルが壊れたりするような現象は見られなかったので今まで放置してきたが、非常に心配になってきたので調べてみた。

Continue reading

辻井研で係り受け解析をやることになりました。
1期の人も2期の同じ人も係り受け解析みたいです。何故か人気。MEやSVMといった機械学習系の知識を仕入れるのが目的です。
ただ、水曜日まで五十嵐先生のUIの課題のデスマです。こういうの、いまいち気乗りがしないんだよなぁ・・・。なんというかシステムコールを叩いてる方が楽しい。