簡潔索引を用いたVF符号上の部分文字列抽出 Simple Substring Extraction for Grammar Compressed Text using VF coding and Succinct Index

この論文にアクセスする

この論文をさがす

著者

    • 笹川裕人
    • 北海道大学大学院情報科学研究科 Hokkaido University, Graduate School of Information Science and Technology
    • 関根渓
    • 北海道大学大学院情報科学研究科 Hokkaido University, Graduate School of Information Science and Technology
    • 吉田諭史
    • 北海道大学大学院情報科学研究科 Hokkaido University, Graduate School of Information Science and Technology
    • 喜田拓也
    • 北海道大学大学院情報科学研究科 Hokkaido University, Graduate School of Information Science and Technology

抄録

本稿では,可変長-固定長符号(VF符号)により符号化された圧縮テキストに対する,高速な部分文字列抽出法を提案する.提案手法では,圧縮テキストに対して,符号語の境界に対応する元テキストの位置を格納した簡潔索引を付加することで,圧縮テキストから部分文字列を抽出する問題を平均 O(N/n+l) 時間で解く.ここで,N と,n,l は,それぞれ元テキスト長,圧縮テキスト長,抽出する部分文字列長である.計算機実験では,提案手法を Re-Pair-VF アルゴリズム上で実装し,高速に部分文字列抽出問題を解けることを実証した.In this paper, we propose a simple method solving the substring extraction problem for variable-to-fixed length codes (VF codes) by adding an auxiliary succinct index structure. The method solves the problem in O(N/n + l) time in the average case, where N, n, and l, are the original text length, the encoded text length, and the length of the target substring, respectively. We implemented our methods with exploiting Re-Pair-VF and showed that our methods run fast in actual.

In this paper, we propose a simple method solving the substring extraction problem for variable-to-fixed length codes (VF codes) by adding an auxiliary succinct index structure. The method solves the problem in O(N/n + l) time in the average case, where N, n, and l, are the original text length, the encoded text length, and the length of the target substring, respectively. We implemented our methods with exploiting Re-Pair-VF and showed that our methods run fast in actual.

収録刊行物

  • 研究報告アルゴリズム(AL)

    研究報告アルゴリズム(AL) 2014-AL-148(8), 1-5, 2014-06-06

    一般社団法人情報処理学会

各種コード

  • NII論文ID(NAID)
    110009785568
  • NII書誌ID(NCID)
    AN1009593X
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • ISSN
    09196072
  • データ提供元
    NII-ELS  IPSJ 
ページトップへ