BDD, ZDD, フロンティア法, Graphillion - iwiwi 備忘録
詳しい資料へのポインタを示しつつ，自分が読んで理解した範囲の簡潔なまとめを書きます． BDD 入門 湊先生の授業が詳しく分かりやすい． http://www-alg.ist.hokudai.ac.jp/~minato/alg2013.html 概念自体 図を一個見れば一発で理解できる DAG で，各中間ノードは変数で，その変数の値に応じて次に進む子を選ぶ．終着点が答え． 構築法 順序付き既約 BDD (ROBDD) を普通作るらしい．重要な性質を持つらしい． 順序付き ＝ 変数が出現してくる順番が全順序 以下の 2 つのルールを適用し続けていれば既約になる（適用順関係なし） 冗長な接点を全て削除 等価な接点を全て共有 実際には，BDD の間の二項論理演算を繰り返して構築する BDD 同士の演算 (Family Algebra) and, or, xor, not, ... みたいな色々な
ハクビシンにもわかる全文検索 - Qiita
高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。 簡潔データ構造 簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
