Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
Dartsを試してみた - download_takeshi’s diary
ダブル配列なTrie構造を実装するためのライブラリであるDartsを試してみました。 DartsはMeCabの作者として知られる工藤 拓氏の作品で、もともとMeCabに組み込まれていたDouble-Arrayのコード部分を、工藤氏が改めてリパッケージしてものだそうです。 なおDartsそのものはC++ライブラリなので、これを他の言語から使うにはバインディングが必要となります。perlから使うにはCPANにText::Dartsというモジュールがあがっているので、これを使わせてもらいます。 なおText::Dartsは、これまた有名なid:dankogai氏の作品です。 で、これらを試してみたのですが、結論から言うと Dartsを使うには Text::Darts 0.03は現時点でDarts0.32に対応していないっぽい。makeでコケる。なのでDarts0.31を使うべし。 Dartsに付
mixi Engineers’ Blog » 圧縮データベースを使おう
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
きまぐれ日記: はてなキーワードを高速に付与
