10 citations · 45 across the 21 of their papers we have counts for
5 papers · 1 filter
Queries on LZ-Bounded Encodings
Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski +4
We describe a data structure that stores a string in space similar to that of its Lempel-Ziv encoding and efficiently supports access, rank and select queries. These queries ar…
Online Pattern Matching for String Edit Distance with Moves
Yoshimasa Takabatake, Yasuo Tabei, Hiroshi Sakamoto
Edit distance with moves (EDM) is a string-to-string distance measure that includes substring moves in addition to ordinal editing operations to turn one string to the other. Altho…
Rank, select and access in grammar-compressed strings
Djamal Belazzougui, Simon J. Puglisi, Yasuo Tabei
Given a string of length on a fixed alphabet of symbols, a grammar compressor produces a context-free grammar of size that generates and only . In this p…
Improved ESP-index: a practical self-index for highly repetitive texts
Yoshimasa Takabatake, Yasuo Tabei, Hiroshi Sakamoto
While several self-indexes for highly repetitive texts exist, developing a practical self-index applicable to real world repetitive texts remains a challenge. ESP-index is a gramma…
Fully Online Grammar Compression in Constant Space
Shirou Maruyama, Yasuo Tabei
We present novel variants of fully online LCA (FOLCA), a fully online grammar compression that builds a straight line program (SLP) and directly encodes it into a succinct represen…