プロパティ付き接尾辞木の効率よいオフライン構築について On an Efficient 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

抄録

高度なテキスト検索処理においては,テキストの特性(プロパティ)を考慮し,ある条件を満たす区間のみを対象として検索を行うという要求が存在する.本論文では,このプロパティを考慮した索引構造を構築する問題に取り組む.2006年にAmirらは,プロパティに属する区間に含まれる部分文字列のみを格納するプロパティ付き接尾辞木PSTを提案した.彼らの構築アルゴリズムは,接尾辞木から不要なノードを削除することでプロパティ付き接尾辞木を得るものである.本論文では,PSTの線形時間構築への第一歩として,必要な部分と不要な部分との境界となる位置を見つけるための新たなアルゴリズムを提案する.アルゴリズム全体の線形時間性の証明は今後の課題である.

In some intelligent application of text retrieval, it is required to do a search just through particular parts of target text data with consideration for some properties that the text have. Namely, the texts are followed by additional information, and the each target part satisfies a certain condition on it. In this paper, we address the problem to construct an efficient index structure for this kind of search. In 2006, Amir et al. proposed a modified suffix tree for this problem, called the property suffix tree, which stores only substrings that belong to the given property. This algorithm constructs a suffix tree at first, and then pluning edges indicating substrings which are not included in the property. In this paper, we present an algorithm for finding all borders between nodes to be remained and nodes to be eliminated in the suffix tree.

収録刊行物

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

    電子情報通信学会技術研究報告. COMP, コンピュテーション 107(24), 71-78, 2007-04-26

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

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

各種コード

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