非線形コラージュシステムにおける文字列パターン照合 A String Pattern Matching Algorithm for Non-Linear Collage Systems

この論文をさがす

著者

    • 山本 淳一 YAMAMOTO Junichi
    • 九州大学 大学院システム情報科学府 Graduate School of Information Science and Electrical Engineering, Kyushu University
    • 稲永 俊介 INENAGA Shunsuke
    • 九州大学 大学院システム情報科学研究院 Faculty of Information Science and Electrical Engineering, Kyushu University
    • 竹田 正幸 TAKEDA Masayuki
    • 九州大学 大学院システム情報科学研究院 Faculty of Information Science and Electrical Engineering, Kyushu University

抄録

非線形テキストは,文字列を頂点ラベルとする有向グラフである.本論文では,頂点ラベルが圧縮形式で表現された非線形コラージュシステムを提案する.非線形コラージュシステムは,Kidaらが提案した辞書式圧縮法で圧縮されたテキストを統一的に表現する枠組みであるコラージュシステムの拡張である.nを辞書の句の数,mをパターン長、|E|を有向グラフの辺数,rをパターンの出現数としたとき、非線形コラージュシステムにおける文字列照合問題をO(n+m^2+|E|m+r)時間,O(n+m^2+|E|m)空間で解くアルゴリズムを提案する.

A non-linear text is a directed graph where each vertex is labeled with a string. In this paper, we propose a non-linear collage system where each vertex label is represented in compressed form. The non-linear collage system is a generalization of the collage system proposed by Kida et al., a unified framework for dictionary based text compression schemes. We propose an O(n+m^2+|E|m+r)-time O(n+m^2+|E|m)-space algorithm that solves the pattern matching problem on a non-linear collage system, where n is the number of variables, m is the length of the pattern, |E| is the number of edges in the graph, and r is the number of occurrences of the pattern.

収録刊行物

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

    電子情報通信学会技術研究報告. COMP, コンピュテーション 111(25), 1-7, 2011-05-04

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

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

各種コード

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