A Linear-Time Off-Line Construction of Property SuffixTrees

• UEMURA, Takashi

• KIDA, Takuya

• ARIMURA, Hiroki

Bibliographic Information

Other Title

• プロパティ接尾辞木のオフライン線形時間構築アルゴリズム
• プロパティ セツビジキ ノ オフライン センケイ ジカン コウチク アルゴリズム

Abstract

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

Journal

• 電子情報通信学会論文誌. D, 情報・システム

  電子情報通信学会論文誌. D, 情報・システム J91- (3), 595-607, 2008-03

  電子情報通信学会

Keywords

• テキスト索引
• 情報検索
• プロパティ付き文字列
• 接尾辞木
• パターン照合

Details

• CRID: 1050001339009411328
• NII Article ID: 110007380997
• NII Book ID: AA12099634
• HANDLE: 2115/47141
• NDL BIB ID: 9400352
• ISSN: 18804535
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I9400352
• Text Lang: ja
• Article Type: journal article
• Data Source:
  • IRDB
  • NDL
  • CiNii Articles
  • KAKEN