10 papers
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…
Generalized Dictionary Matching under Substring Consistent Equivalence Relations
Diptarama Hendrian
Given a set of patterns called a dictionary and a text, the dictionary matching problem is a task to find all occurrence positions of all patterns in the text. The dictionary match…
Query Learning Algorithm for Residual Symbolic Finite Automata
Kaizaburo Chubachi, Diptarama Hendrian, Ryo Yoshinaka +1
We propose a query learning algorithm for residual symbolic finite automata (RSFAs). Symbolic finite automata (SFAs) are finite automata whose transitions are labeled by predicates…