Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
はてなダイアリーキーワード抽出・リンクを高速化したい - higepon blog
きまぐれ日記:はてなキーワードを高速に付与という エントリーがとても気になる内容です。 はてなダイアリーの内部処理の中でも重めの処理である、キーワード抽出・リンクについて、高速化を試みるというとてもありがたい内容です。 高速化にはAC法という方法を使用しているようです。(恥ずかしながら全く知りませんでした。） AC法の肝はトライ (TRIE) という木構造を利用して、高速に前方一致検索が出来るところです。 トライの説明は高林さん（namazuの中の人）の説明がとても分かりやすくておすすめです。 要は一文字ごとにばらして、ツリーに格納しておいて、検索後のつづりの通りにツリーをたどるということらしいです。 トライの特徴は、辞書に登録されている項目の数がどんなに多くても、キーの長さに比例した時間で探索が行えるという点である。 実際に 日記で紹介されている hatenakeyword というツール
ラムダ計算基礎文法最速マスター - 貳佰伍拾陸夜日記
ラムダ計算は, 多くのプログラミング言語, とくに関数型言語の原形になっています. ラムダ計算について理解しておくことは, 多くのプログラミング言語の習得に役立つでしょう. ラムダ計算はチューリング完全で, 計算能力としてはふつうのプログラミング言語と同じです. ラムダ計算で計算を書く訓練をしておくことは, 任意の計算を関数のみを使って(他の制御構文を用いずに)書くときに役立ちます. ふつうに書いたら煩雑な処理を, 関数型言語のやり方で書くとすっきりすることが多々あり, コードを自由自在に書くためには必須の考え方と言えるでしょう. 項 ラムダ計算の式を項(term)と言います. 項は変数, 抽象, 適用のいずれかです. 変数 変数(variable)はふつう1文字で書きます. 変数には関数内の束縛変数(bound variable)か自由変数(free variable)かという区別があり
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
