11 citations · 20 across the 20 of their papers we have counts for
26 papers
MacCorles: Minimum Alignment Cost Computation on Run-Length Encoded Strings
Wing-Kai Hon, Dominik Köppl, Jun-Hong Wang
We study a tie-breaking variant of the longest common subsequence problem on run-length encoded strings. Given two strings, the goal is first to maximize the number of equal aligne…
Indexing Range Maximum-Sum Segment Queries with Offsets
Seungbum Jo, Dominik Köppl
Given an array of real numbers, the maximum segment sum (MSS) problem is to find a contiguous subarray that has the largest sum. While the MSS problem can be solved optimally w…
Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes
Paola Bonizzoni, Younan Gao, Dominik Köppl +1
We revisit the online construction of \emph{smallest suffixient sets} and the online computation of the \emph{longest repeating suffix} (LRS). We give the first compressed-space on…
Compact multi-text index for circular Cartesian tree matching
Roman Pauli, Eric Osterkamp, Dominik Köppl
Cartesian tree matching (CTM) is a structural pattern matching approach that identifies sequences with the same Cartesian tree topology, making it suitable for data with natural va…
Smallest suffixient set maintenance in near-real-time
Dominik Köppl, Gregory Kucherov
The size of the \textit{smallest suffixient set} of positions of a string recently emerged as a new measure of string \textit{repetitiveness} -- a measure reflecting how much of re…
Counting Distinct (Non-)Crossing Substrings in Optimal Time
Haruki Umezaki, Hiroki Shibata, Dominik Köppl +3
Let be a string of length . The problem of counting factors crossing a position -- Problem 64 from the textbook ``125 Problems in Text Algorithms'' [Crochemore, Lecroq, and…
Bijective BWT based compression schemes
Golnaz Badkobeh, Hideo Bannai, Dominik Köppl
We investigate properties of the bijective Burrows-Wheeler transform (BBWT). We show that for any string , a bidirectional macro scheme of size can be induced from the…
NP-Completeness for the Space-Optimality of Double-Array Tries
Hideo Bannai, Keisuke Goto, Shunsuke Kanda +1
Indexing a set of strings for prefix search or membership queries is a fundamental task with many applications such as information retrieval or database systems. A classic abstract…
Edit and Alphabet-Ordering Sensitivity of Lex-parse
Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi +2
We investigate the compression sensitivity [Akagi et al., 2023] of lex-parse [Navarro et al., 2021] for two operations: (1) single character edit and (2) modification of the alphab…
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…
Space-time Trade-offs for the LCP Array of Wheeler DFAs
Nicola Cotumaccio, Travis Gagie, Dominik Köppl +1
Recently, Conte et al. generalized the longest-common prefix (LCP) array from strings to Wheeler DFAs, and they showed that it can be used to efficiently determine matching statist…
Acceleration of FM-index Queries Through Prefix-free Parsing
Aaron Hong, Marco Oliva, Dominik Köppl +3
FM-indexes are a crucial data structure in DNA alignment, for example, but searching with them usually takes at least one random access per character in the query pattern. Ferragin…
Computing NP-hard Repetitiveness Measures via MAX-SAT
Hideo Bannai, Keisuke Goto, Masakazu Ishihata +3
Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation o…
Computing the Parameterized Burrows--Wheeler Transform Online
Daiki Hashimoto, Diptarama Hendrian, Dominik Köppl +2
Parameterized strings are a generalization of strings in that their characters are drawn from two different alphabets, where one is considered to be the alphabet of static characte…
Longest (Sub-)Periodic Subsequence
Hideo Bannai, Tomohiro I, Dominik Köppl
We present an algorithm computing the longest periodic subsequence of a string of length in time with words of space. We obtain improvements when restricting…
Computing Longest (Common) Lyndon Subsequences
Hideo Bannai, Tomohiro I, Tomasz Kociumaka +2
Given a string with length whose characters are drawn from an ordered alphabet of size , its longest Lyndon subsequence is a longest subsequence of that is a Lyndon…
Grammar Index By Induced Suffix Sorting
Tooru Akagi, Dominik Köppl, Yuto Nakashima +3
Pattern matching is the most central task for text indices. Most recent indices leverage compression techniques to make pattern matching feasible for massive but highly-compressibl…
Load-Balancing Succinct B Trees
Tomohiro I, Dominik Köppl
We propose a B tree representation storing keys, each of bits, in either (a) bits or (b) bits of space supporting all B t…
Grammar-compressed Self-index with Lyndon Words
Kazuya Tsuruta, Dominik Köppl, Yuto Nakashima +3
We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data struc…
Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time
Hideo Bannai, Juha Kärkkäinen, Dominik Köppl +1
The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT (BBWT) is a bijective variant of it.…
c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda +4
Given a dynamic set of strings of total length whose characters are drawn from an alphabet of size , a keyword dictionary is a data structure built on that provi…
Compression with the tudocomp Framework
Patrick Dinklage, Johannes Fischer, Dominik Köppl +2
We present a framework facilitating the implementation and comparison of text compression algorithms. We evaluate its features by a case study on two novel compression algorithms b…
Computing All Distinct Squares in Linear Time for Integer Alphabets
Hideo Bannai, Shunsuke Inenaga, Dominik Köppl
Given a string on an integer alphabet, we present an algorithm that computes the set of all distinct squares belonging to this string in time linear to the string length. As an app…
Lempel-Ziv Computation In Compressed Space (LZ-CICS)
Dominik Köppl, Kunihiko Sadakane
We show that both the Lempel Ziv 77- and the 78-factorization of a text of length on an integer alphabet of size can be computed in time (linear time if we…