文法圧縮に基づく自己索引のオンライン構築について

DOI Web Site

書誌事項

タイトル別名
  • Fully-Online Constru tion of Grammar-Based Self-Index
  • ブンポウ アッシュク ニ モトズク ジコ サクイン ノ オンライン コウチク ニ ツイテ

この論文をさがす

抄録

<p>Existing grammar-based self-indexes are efficient for highly repetitive texts. However, the construction space of existing self-indexes depends on input length. Thus, developing an online construction of grammar-based self-index executed on compressed space is important for highly repetitive and streaming texts. In this paper, we present a first online grammar-based self-index named online ESP-index(OESP-index). OESP-index directly encodes an input text into a succinct representation of straight line program(SLP) in an online manner based on fully online LCA(FOLCA) techniques. The succinct representation of SLP is a wavelet tree and a bit array encoded by dynamic range min/max tree. OESP-index supports the pattern search of ESP-index by using such data structures. We experimentally show that the construction of OESP-index for real world texts is executed on compressed space.</p>

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ