プロパティ接尾辞木のオフライン線形時間構築アルゴリズム A Linear-Time Off-Line Construction of Property Suffix Trees

この論文にアクセスする

この論文をさがす

著者

    • 上村 卓史 UEMURA Takashi
    • 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University
    • 喜田 拓也 KIDA Takuya
    • 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University
    • 有村 博紀 ARIMURA Hiroki
    • 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University

抄録

プロパティ付きテキストとは,長さnのテキストに,補助情報としてテキスト上の互いにオーバラップを許した区間の集合(プロパティという)が付加された構造化文書の一種であり,アノテーション付きの系列データの形式的なモデルとなっている. このプロパティ付きテキストへの全文テキスト索引として, Amirら(CPM2006) は,プロパティ接尾辞木を提案した. これは,プロパティの各区間に含まれるすべての部分文字列を格納する索引構造であり,遺伝子情報や,ビデオストリーム,メタデータ付き時系列データなどへの応用がある. また,高度な検索問題である重み付きパターン照合にも用いられる. Amirらは,定数サイズのアルファベット上で,プロパティ接尾辞木をO(n log log n)時間でオフライン構築するアルゴリズムを与えたが,その線形時間構築アルゴリズムは,現在まで未解決の問題であった. 本論文では,定数アルファベット上で,プロパティ接尾辞木を線形時間で構築するオフラインアルゴリズムを与え,この問題を肯定的に解決する. 提案アルゴリズムは,接尾辞リンクの巡回を用いた簡潔な手法であり,理論的に効率良いだけでなく,実際のデータに対しても高速に動作する. 更に,人工データ上の計算機実験を行い,実際の性能を評価する.

収録刊行物

  • 電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition)

    電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition) 91(3), 595-607, 2008-03-01

    電子情報通信学会

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

各種コード

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