19 citations · 65 across the 15 of their papers we have counts for
24 papers · 1 filter
Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries
Philip Bille, Johannes Fischer, Inge Li Gørtz +1
We study the data structure version of the \emph{element distinctness problem}: preprocess an array of elements from an alphabet of size to answer \textsc{All-Distinct} que…
Sliding Window String Indexing in Streams
Philip Bille, Johannes Fischer, Inge Li Gørtz +2
Given a string over an alphabet , the 'string indexing problem' is to preprocess to subsequently support efficient pattern matching queries, i.e., given a pattern string…
Engineering Predecessor Data Structures for Dynamic Integer Sets
Patrick Dinklage, Johannes Fischer, Alexander Herlez
We present highly optimized data structures for the dynamic predecessor problem, where the task is to maintain a set of -bit numbers under insertions, deletions, and predece…
Linear Time Runs over General Ordered Alphabets
Jonas Ellert, Johannes Fischer
A run in a string is a maximal periodic substring. For example, the string contains the runs and $\texttt{ee} = \texttt…
LCP-Aware Parallel String Sorting
Jonas Ellert, Johannes Fischer, Nodari Sitchinava
When lexicographically sorting strings, it is not always necessary to inspect all symbols. For example, the lexicographical rank of "europar" amongst the strings "eureka", "eurasia…
Space Efficient Construction of Lyndon Arrays in Linear Time
Philip Bille, Jonas Ellert, Johannes Fischer +4
We present the first linear time algorithm to construct the -bit version of the Lyndon array for a string of length using only bits of working space. A simpler varia…
Bidirectional Text Compression in External Memory
Patrick Dinklage, Jonas Ellert, Johannes Fischer +2
Bidirectional compression algorithms work by substituting repeated substrings by references that, unlike in the famous LZ77-scheme, can point to either direction. We present such a…
Dismantling DivSufSort
Johannes Fischer, Florian Kurpicz
We give the first concise description of the fastest known suffix sorting algorithm in main memory, the DivSufSort by Yuta Mori. We then present an extension that also computes the…
Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries
Johannes Fischer, Dominik Köppl
We present the first thorough practical study of the Lempel-Ziv-78 and the Lempel-Ziv-Welch computation based on trie data structures. With a careful selection of trie representati…
Simple, Fast and Lightweight Parallel Wavelet Tree Construction
Johannes Fischer, Florian Kurpicz, Marvin Löbel
The wavelet tree (Grossi et al. [SODA, 2003]) and wavelet matrix (Claude et al. [Inf. Syst., 47:15--32, 2015]) are compact indices for texts over an alphabet that support r…
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…
Engineering a Distributed Full-Text Index
Johannes Fischer, Florian Kurpicz, Peter Sanders
We present a distributed full-text index for big data applications in a distributed environment. Our index can answer different types of pattern matching queries (existential, coun…
On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching
Johannes Fischer, Dominik Köppl, Florian Kurpicz
We present parallel algorithms for exact and approximate pattern matching with suffix arrays, using a CREW-PRAM with processors. Given a static text of length , we first sho…
Deterministic Sparse Suffix Sorting in the Restore Model
Johannes Fischer, Tomohiro I, Dominik Köppl
Given a text of length , we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of in $O(c \sqrt{\lg n}…
Lempel Ziv Computation In Small Space (LZ-CISS)
Johannes Fischer, Tomohiro I, Dominik Köppl
For both the Lempel Ziv 77- and 78-factorization we propose algorithms generating the respective factorization using bits (for any positive constant …
Approximating LZ77 via Small-Space Multiple-Pattern Matching
Johannes Fischer, Travis Gagie, Paweł Gawrychowski +1
We generalize Karp-Rabin string matching to handle multiple patterns in time and space, where is the length of the text and is…
LZ-Compressed String Dictionaries
Julian Arz, Johannes Fischer
We show how to compress string dictionaries using the Lempel-Ziv (LZ78) data compression algorithm. Our approach is validated experimentally on dictionaries of up to 1.5 GB of unco…
Alphabet-Dependent String Searching with Wexponential Search Trees
Johannes Fischer, Pawel Gawrychowski
It is widely assumed that is the best one can do for finding a pattern of length in a compacted trie storing strings over an alphabet of size , if one insists o…
Sparse Suffix Tree Construction with Small Space
Philip Bille, Inge Li Gørtz, Tsvi Kopelowitz +2
We consider the problem of constructing a sparse suffix tree (or suffix array) for suffixes of a given text of size , using only words of space during constructio…
Combined Data Structure for Previous- and Next-Smaller-Values
Johannes Fischer
Let be a static array storing elements from a totally ordered set. We present a data structure of optimal size at most bits that allows us to an…
Inducing the LCP-Array
Johannes Fischer
We show how to modify the linear-time construction algorithm for suffix arrays based on induced sorting (Nong et al., DCC'09) such that it computes the array of longest common pref…
LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
Jérémy Barbay, Johannes Fischer
LRM-Trees are an elegant way to partition a sequence of values into sorted consecutive blocks, and to express the relative position of the first element of each block within a prev…
Wee LCP
Johannes Fischer
We prove that longest common prefix (LCP) information can be stored in much less space than previously known. More precisely, we show that in the presence of the text and the suffi…
Optimal Succinctness for Range Minimum Queries
Johannes Fischer
For a static array A of n ordered objects, a range minimum query asks for the position of the minimum between two specified array indices. We show how to preprocess A into a scheme…