FIT2016 第15回情報科学技術フォーラム 開催日:2016年9月7日(水)~9日(金) 会場:富山大学キャンパス
抄録
D-024
短縮した遷移パターンによるダブル配列構築法の提案
瀬社家奨・望月久稔(大阪教育大)
高速な探索手法にトライ木があり,トライ木の探索性能を維持したまま,より小さな領域で表現する実装法としてダブル配列がある.
ダブル配列は配列上にトライ木における節点ごとの遷移集合を組み合わせて構築するが,組み合わせる際の基底値算出に膨大な時間計算量を要する.
基底値を算出する際には,遷移集合における遷移種の有無を表した遷移パターンを用いるが,遷移パターンの長さに応じてパターン数は膨大になる.
本稿では,遷移パターンを循環させることで遷移パターンを縮小する手法を提案する.