D-009
重み付き有向非巡回グラフに対する効率良いテキスト索引の構築アルゴリズム

◎山岸大騎・髙木拓也（北大）・渋谷哲朗（東大）・有村博紀（北大）

本稿では，遷移確率を表す正実数値と記号がラベル付けされた多重辺を持つDAGである重み付きDAG（WDAG）上の検索について考察する．WDAGは，生物情報学の重み付き配列や，GISの遷移ネットワークのモデルである．はじめに，定数アルファベットに対して，頂点数nと辺数mを持つWDAGと最小重み閾値パラメータz>0を入力としたとき，任意の文字列パターンに対する重み付き照合計算をO(|P|+occ)時間で実現するようなO(nz)語サイズの索引が存在することを示す．ここで，occはパターンPの出現回数である．さらに，入力WDAGから索引をO(nz log n)時間で構築するアルゴリズムを与える．