10 papers · 1 filter
Height-bounded Lempel-Ziv encodings
Hideo Bannai, Mitsuru Funakoshi, Diptarama Hendrian +2
We introduce height-bounded LZ encodings (LZHB), a new family of compressed representations that are variants of Lempel-Ziv parsings with a focus on bounding the worst-case access…
Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching
Kento Iseri, Tomohiro I, Diptarama Hendrian +3
A parameterized string (p-string) is a string over an alphabet , where and are disjoint alphabets for static symbols (s-symbols) and for paramet…
In-Place Bijective Burrows-Wheeler Transforms
Dominik Köppl, Daiki Hashimoto, Diptarama Hendrian +1
One of the most well-known variants of the Burrows-Wheeler transform (BWT) [Burrows and Wheeler, 1994] is the bijective BWT (BBWT) [Gil and Scott, arXiv 2012], which applies the ex…
Grammar compression with probabilistic context-free grammar
Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka +2
We propose a new approach for universal lossless text compression, based on grammar compression. In the literature, a target string has been compressed as a context-free gramma…
Fast and linear-time string matching algorithms based on the distances of -gram occurrences
Satoshi Kobayashi, Diptarama Hendrian, Ryo Yoshinaka +1
Given a text of length and a pattern of length , the string matching problem is a task to find all occurrences of in . In this study, we propose an algorithm…
Computing Covers under Substring Consistent Equivalence Relations
Natsumi Kikuchi, Diptarama Hendrian, Ryo Yoshinaka +1
Covers are a kind of quasiperiodicity in strings. A string is a cover of another string if any position of is inside some occurrence of in . The shortest and lon…