タグ

2009年6月8日のブックマーク (3件)

  • Aho Corasick 法 - naoyaのはてなダイアリー

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

    Aho Corasick 法 - naoyaのはてなダイアリー
  • B木 - naoyaのはてなダイアリー

    昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ

    B木 - naoyaのはてなダイアリー
  • app-engine-patchを使ってみる - 西尾泰和のはてなダイアリー

    Django on Google App Engineでちょこちょこ開発しているけども、やっぱりDjangoなのにあのきれいなadmin画面が使えないのではDjango人生の80%くらいを損していると思うのでid:voluntasにすすめられたapp-engine-patchを使ってみる。 http://code.google.com/p/app-engine-patch/ バージョン1.0がリリースされて2週間くらい経ったし。安定版と見なしていいだろう〜と。まずはGettingStartedを読む。なるほど。 サンプルプロジェクトをダウンロードする app.yamlのapplicationのところをGAEのcreate applicationで作ったアプリケーション名にする settings.pyのSECRET_KEYをランダムな文字列で書き換える。これはDjangoに標準搭載のCSRF

    app-engine-patchを使ってみる - 西尾泰和のはてなダイアリー