適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと

部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog

KOF 2008 での発表資料「はてな流大規模データ処理」を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/081108huge_data.ppt 一部参考文献からの引用 (Introduction to Information Retrieval から Vector space model の図、たつをの ChangeLog から転置インデックスの図) があります。この場を借りて感謝。 環境によってはおそらくフォントの表示がいまいちだと思いますが、ご了承ください。 追記 SlideShare にアップロードしました。 081108huge_data.pptView SlideShare presentation or Upload your own. (tags: linux mysql) 追記: メモリはディスクの 150 倍について

,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ|　　　　　　　　　　あ…ありのまま 今日　起こった事を話すぜ！ |i i|　 　 }!　}} /／| |l､{　 　j}　/,,ｨ//｜　　　　　　　『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' }　 ,ﾉ　_,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ　, ﾀ人　　　　　　　　な…　何を言ってるのか　わからねーと思うが /' 　 ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ　　　　　　　　おれも何をされたのかわからなかった… ,ﾞ　 ／ )ヽ iLﾚ 　u' |　| ヾｌﾄﾊ〉 |／_／　 ﾊ !ニ⊇　'／:} 　V:::::ヽ　　　　　　　　頭がどうにかなりそうだった… /／ 二二二7'T'' ／u'　__ /:::::::/｀ヽ /'

autobox を使ったコードをここ最近よく見た ので、ややいまさらですが自分もすこし遊んでみました。autobox は Perl の組み込みのデータ (bless されていないスカラー、リスト、ハッシュほか) をファーストクラスオブジェクトとして扱うための機構を提供するモジュール(レキシカルプラグマ)です。 #!/usr/local/bin/perl use strict; use warnings; use FindBin::libs; use autobox; use autobox::Core; use autobox::Encode; use autobox::Hatena::Feed; use autobox::Accessor; shift->b(qw/perl autobox/)->items->foreach(sub { $_[0]->title->encode('utf

Today I've been thinking about what to talk in YAPC::EU (and OSCON if they're short of Perl talks, I'm not sure), and came up with a few hours of hacking with web-content scraping module using Domain Specific Languages. 使ってみたよ! #!/usr/local/bin/perl use strict; use warnings; use FindBin::libs; use URI; use Web::Scraper; use Encode; use List::MoreUtils qw/uniq/; my $links = scraper { process 'a.key

WEB+DB PRESS Vol.38 の見本誌が届きました。連載も今回で7回目。今回は POE の話の後編です。複数の HTTP サーバーに非同期で同時アクセスするクライアントプログラムを POE::Component::* に頼らずつくり、その後 POE::Component を紹介しつつ IRC bot を作る、という内容になってます。先日の前編の vol.37、それから先日の YAPC::Asia の資料とあわせてお読みいただけると理解が深まるかなと思います。 今月号は新連載が色々始まってたりして関心が高いわけですが、断固guy 小飼弾さん (http://blog.livedoor.jp/dankogai/) の Alpha Geek に逢いたいのゲストがIT戦記の id:amachang とあの"はまちちゃん"で、はまちちゃんの写真が載っていました。はまちちゃんの顔が見たい人は

YAPC::Asia で Perl UNIX ネットワークプログラミングについての発表をしてきました。UNIX ネットワークプログラミングの基礎の概論、I/O多重化の話、Perl のモダンなネットワークライブラリの話です。資料を以下に置いておきます。 http://bloghackers.net/~naoya/ppt/070404Perl_and_UNIX_Network_Programming.ppt (ppt, 122k) なお、会場では口頭で触れましたが、資料中のソースは簡単のためエラー処理を飛ばしています。また、途中で出てくる図は例えば vfs のページキャッシュをはしょってあったりとこれも簡単のため省略事項がある点にご注意ください。 それからフォントが Consolas なので Consolas が入ってない環境だと変になる、かも。

Comet については、普及するかどうかという以前に、どう使えばいいのか、正しく使った場合に何をどこまでできるのか、という理解が共有されていないように思います。なので、(あくまで私見ですが) 使用したスライドの一部を公開したいと思います。よろしければごらんください。 サイボウズラボの奥さんによる Comet のサーバー周りの資料。すばらしい。C10K に対してどのようなアーキテクチャをとるのが良いかとの考察が特に勉強になりました。 また、問題や改善すべき点があれば、教えていただければ幸いです。 というので問題、改善すべきというわけではないですが Perl 周りの話で少し補足を。 資料中の「初心者へのオススメが PoCo::Server::HTTP でパフォーマンスが欲しい人には Sys::Syscall qw/:epoll/」の点。おそらく Perl でも epoll を使えますよというこ

続きまして「コピーしてインスタンスを作る」Prototype パターンです。デザパタ本では6章にあたります。 var Main = Class.create(); Main.prototype = { initialize : function () {}, main : function() { var manager = new Manager(); var upen = new UnderlinePen('~'); var mbox = new MessageBox('*'); var sbox = new MessageBox('/'); manager.register("strong message", upen); manager.register("warning box", mbox); manager.register("slash box", sbox); docum

先日 PerlでCSSセレクタ で HTML::Selector::XPath がいい感じであると思ったわけですが、CSS セレクタだけじゃなく何気に HTML::TreeBuilder::XPath とのコンボがすげーイイ!ということにいまさら気づきました。 HTML::TreeBuilder::XPath で findnodes するとツリー状に連なった HTML::Element なデータ構造が返ってくるんですが、HTML::Element は API をかなりいろいろ持ってて、これをうまく使ってやるとスクレイピングを自然な感じで書けます。 例えばはてなダイアリーの任意のページから、本文部分だけをスクレイピングしたいと思ったときにキーワードリンクが邪魔だったりするわけですが、とりあえず HTML::Selector::XPath で div.section をぶっこ抜いて取れた HT

ruby でスクレイピングして web の情報を取得するのには、今まで正規表現か xpath でやってたので、わりと面倒でした。で、ふと scrAPI というスクレイピングツールキットを知ったのですが、これがかなり便利そう。 このツールキットを使うと、CSS3 なセレクタを記述することで、要素を取得することができます。 という Ruby の scrAPI での CSS セレクタがいい感じでございますなあと指をくわえて見てたんだけど、 Per discussions in CSS Selector in Perl, I made a quick perl module HTML::Selector::XPath, which is available at http://svn.bulknews.net/repos/public/HTML-Selector-XPath/trunk/ now.

UP しときました。時間が15分だったので、ちょっとあっさりめの内容ではありますが。 http://bloghackers.net/~naoya/pdf/060909devcon.pdf 個人的にはここ最近のカンファレンスの中では一番面白かったかなと思いました。いろいろ役に立つ話とか、自分もやってみようみたいな話がいろいろ聞けたのが大きかったのかも。 2回目はどうだろう、だいたい話す内容が被りそうなので難しいかもね(笑) あ、そうだ。昨日の感想とかいろいろ読みたいので blog に書いた人は Shibuya.js のページなりこのエントリなりにトラックバックしていただけると大変嬉しいです。読んだやつは http://b.hatena.ne.jp/naoya/decon/ あたりに。

いつもお世話になってるあの人とかあの人とかが山口家の逆襲->perl-解説->クロージャというクロージャの解説ページをブックマークしてるのをきっかけに、 Perl のクロージャについて自分もちゃんと理解できてるのかというのを考えてみましたが、どうも微妙です。 クロージャについて、何でいまいち理解しきれてない感じがあるのかというと、クロージャがどういうものであるかは知ってるけど、クロージャをどういう時に使うと良いのかが具体的にあれとこれという感じで思い付かないからなのではないかと思った。 なので、Perl でクロージャを使ってる実装とかを見て、どんなときに使われるものなのかをリストアップして理解を深めてみよう..のコーナーです。 クラスにデータを保持するためのクロージャ 僕がぱっと思いついたのは Class::DBI の中で使われている Ima::DBI におけるデータベースハンドラのキャッ

use strict がどうのこうのという話があって、そういえば昔自分もそんなこと書いたなあと思っていろいろ自分の書いた Perl の話を見返してて、せっかくだから拙作のまとめでも作っておくかと思いました。とりあえず文章量がそれなりにあって、まとまりのあるものだけを見繕ってみます。 今見ると、当時の理解が不十分で微妙なところもあったりしますが、そのあたりはご愛嬌。 いま読んでもまだ陳腐化はしてなさそうな話 お薦めの Perl 本をいくつか紹介 : NDO::Weblog Perlおすすめの書籍や情報。今ならここにPerl救命病棟とWEB+DB PRESS総集編を入れるかな。 Perlプログラマのレベル10 - Perlプログラミング救命病棟より - naoyaのはてなダイアリー Perlプログラマのレベル10。なんか他言語にも飛び火した。 Perl の変数に関するちょっとした誤解と、動的な

にわかに盛り上がりを見せている microformats。Technorati が最近注力しているので有名で、Web 2.0 のディスカッションの中でもときおり出てくる重要な要素らしい。アルファギークな人たちも、近頃は microformats について触れることが多くなってきました。 が、僕は頭が悪いんだろうか、いまいち何のことだかよくわからなくって困ってたので、ここで少し腰を据えて、色々見て回り勉強中です。まだ細かいところがもやもやしてはいるものの、ようやくその実体が掴めて来た感じです。 「microformats とは何か?」と言われると、その答えはズバリ About microformats というエントリーに書かれているのですが、これを理解するよりまず具体例から入った方が分かりやすい。現在 microformats と呼ばれているもののうち、すでに実用段階に入っているものがありま