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

Bibliographic Information

Other Title

• 簡潔索引を用いたVF符号上の部分文字列抽出

Abstract

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.

Journal

• IPSJ SIG Notes

  IPSJ SIG Notes 2014 (8), 1-5, 2014-06-06

  Information Processing Society of Japan (IPSJ)

Details

• CRID: 1571980077770150528
• NII Article ID: 110009785568
• NII Book ID: AN1009593X
• ISSN: 09196072
• Text Lang: ja
• Data Source:
  • CiNii Articles