マルチトラック文字列の順列パターン照合と索引構造 (Theoretical Foundations of Computing) Permuted Pattern Matching and Indexing Structure for Multi-Track Strings

この論文をさがす

著者

抄録

文字列の多重集合,すなわちマルチトラック文字列上の新しいパターン照合として順列パターン照合を提案する.順列パターン照合では,トラック長n,トラック数Nのマルチトラックテキスト中に出現するトラック長m,トラック数Mのマルチトラックパターンを探す我々はこの問題が,一般のアルファベットではO(nN log lΣl)時間・0(mM+N)領域,整数型のアルファベットではO(nN)時間・領域で解くことができることを示す.また,テキストとパターンのトラック数が等しい場合(全順列パターン照合)に対し,我々はマルチトラック接尾辞木と呼ばれる新たな索引構造を提案し,このデータ構造の0(nN log lΣl)時間・0(nN)領域構築アルゴリズムを示す.マルチトラック接尾辞木を用いることで,全順列パターン照合問題が0(mN log lΣl+occ)時間で計算可能であることを示す.

We propose a new variant of pattern matching on a multi-set of strings, or multi-tracks, called permuted-matching, that looks for occurrences of a multi-track pattern of length m with M tracks, in a multi-track text of length n with N tracks. We show that the problem can be solved in 0(nN log lEl) time and O(mM N) space, and further in 0(nN) time and space when assuming an integer alphabet. For the case where the number of strings in the text and pattern multi-track are equal (full-permuted-matching), we propose a new index structure called the multi-track suffix tree, as well as an 0(nN log lEl) time and 0(nN) space construction algorithm. Using this data structure, we can solve the full-permuted-matching problem in 0(mN log lEl + occ) time for any multi-track pattern of length m with N tracks.

収録刊行物

  • 電子情報通信学会技術研究報告 : 信学技報

    電子情報通信学会技術研究報告 : 信学技報 112(199), 1-8, 2012-09-03

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

各種コード

  • NII論文ID(NAID)
    110009669778
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    JPN
  • ISSN
    0913-5685
  • NDL 記事登録ID
    024000773
  • NDL 請求記号
    Z16-940
  • データ提供元
    NDL  NII-ELS 
ページトップへ