逆順の系列集合を表すSeqBDDの構築 Construction of a SeqBDD representing a set of reversed sequences

この論文をさがす

著者

抄録

トライなどの接頭辞の共通部分を同じグラフで表現する系列集合を表すデータ構造において,系列集合に含まれる全ての系列を逆順にした系列集合を効率良く構築できると,接尾辞を指定した系列の検索を効率良く行うことができる.これは,逆順の系列集合に対しての接頭辞を指定した系列の検索が,元の系列集合に対しての接尾辞による検索に対応するからである.本稿では,接頭辞と接尾辞の共通部分を同じグラフで表現するデータ構造の系列二分決定グラフ(Sequence Binary Decision Diagram, SeqBDD)で系列集合が与えられたときに,与えられた系列集合の逆順の系列集合を表すSeqBDDを構築する手法を示す.提案するアルゴリズムは,SeqBDDの節点をトポロジカルソートに基づいた順番に処理していくことで,同じ節点についての処理を一度だけ行う.このため,同じ節点についての処理を何度も行う単純な再帰的手法よりも効率が良い.実験により,系列間での接頭辞や接尾辞の共有量が多く,SeqBDDで効率良く表現できるデータの場合,本手法が単純な手法と比べて効率良く動作することを確認した.

A trie is a data structure representing a set of sequences by sharing the same prefixes between sequences. Thanks to this sharing, prefix searches on a trie is performed efficiently. Constructing a trie representing a set of reversed sequences is useful for suffix searches on the original sequences. This is because a prefix search on reversed sequences corresponds to a suffix search on the original sequences. A Sequence Binary Decision Diagram (SeqBDD) also represents a set of sequences compactly by sharing the same prefixes between the sequences. In addition, a SeqBDD can share suffixes between the sequences unlike a trie. In this paper, we propose a construction method of a SeqBDD representing a set of the reversed sequences from a given SeqBDD. Our method traverses each node in a SeqBDD only one time since it traverses the nodes based on the topological sorting. Hence, our method is more efficient than a simple recursive method that traverses the same nodes many times. Our experimental results show that our method constructs a SeqBDD representing a set of reversed sequences more efficiently than a simple recursive method when there are many common prefixes and/or suffixes in given sequences.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 111(20), 17-23, 2011-04-15

    一般社団法人電子情報通信学会

参考文献:  11件中 1-11件 を表示

各種コード

  • NII論文ID(NAID)
    110008689187
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    09135685
  • NDL 記事登録ID
    11069788
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ