トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記
以前実装した構築速度重視の動的ダブル配列 (表中 dda) の構築速度を Darts, darts-clone (0.32g beta5, 0.32e5), DASTrie (1.0), doar (0.0.10)，簡潔データ構造を利用したトライ (tx 0.16) ，STL コンテナ (std::map, std::tr1::unordered_map) 辺りと比べてみた．キー集合としては，中規模で疎な集合（Wikipedia 英語版記事タイトル）と小規模で密な集合（郵便番号辞書）を用いた． ====================================================================== Wikipedia-en 記事タイトル | Build | Search | Search* | Size [bytes] =================
構築した辞書を元にAho Corasick法を使ってキーワードを探す - yasuhisa's blog
どのようなときにAho Corasick法が必要か辞書構築した後の応用先(?)の一つとして、辞書を元にした転置インデックスを作ることがあげられる。「どのキーワードがどの文章に登場したか」が一番簡単な転置インデックスだと思うんだけど、今回は登場した文章のどの位置にあったかまで記録したい(例えばリンクを張る時に使いたいから)。転置インデックス作るときは、通常 形態素解析ベース N-gramベース の2種類が主な手法だと思うんだけど、今回はせっかく構築した辞書をもとに転置インデックスを作りたいので、上の2つではうまくできない。かといって、文章とキーワード総当たりとかやっていたら死ぬので、効率のよい方法が必要。そこでAho Corasick法ですよ、奥さん。はてなキーワードへのリンク処理とかに使われたりします。 入力と出力入力と出力を先に紹介しよう。入力は辞書とこんな感じの文章。 <総説誌名>蛋白
min_heapを用いた上位r個の要素の抽出 - tsubosakaの日記
MG勉強会の発表があるため4.6ランキング検索の部分を読むついでに、最後のサブセクションの上位r個の要素を取り出す部分について実装してみた。 情報検索において、N個の候補集合から上位r個の要素を取り出すことが多い。 値が配列に格納されているとするとこれを実現するためのコードはもっとも単純に行うと以下のようになる //長さlenの配列arrayの中でトップr個の値をresultに挿入する void sort_method(int * array , int len, int r , vector<int> & result){ sort(array , array + len); copy(array + len - r , array + len , back_inserter(result)); } しかし、Nが大きいとき、MGの例だとN=100万のときにsortの処理にはおおよそ100
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
