Binary jumbled string matching for highly run-length compressible texts

DOI10.1016/J.IPL.2013.05.007MaRDI QIDQ2444848zbMATH OpenOpenAlexFDO

Authors Golnaz Badkobeh, Gabriele Fici, Steve Kroon, Zsuzsanna Lipták

Publication date 11 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.2523

zbMATH Keywords

data structuresjumbled pattern matchingParikh vectorsprefix normal formrun-lenght encodingstring algorithm

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: The Binary Jumbled String Matching problem is defined as: Given a string $s$ over $a,b$ of length $n$ and a query $(x,y)$, with $x,y$ non-negative integers, decide whether $s$ has a substring $t$ with exactly $x$ $a$'s and $y$ $b$'s. Previous solutions created an index of size O(n) in a pre-processing step, which was then used to answer queries in constant time. The fastest algorithms for construction of this index have running time $O(n^2/logn)$ [Burcsi et al., FUN 2010; Moosa and Rahman, IPL 2010], or $O(n^2/lo{g}^{2}n)$ in the word-RAM model [Moosa and Rahman, JDA 2012]. We propose an index constructed directly from the run-length encoding of $s$. The construction time of our index is $O(n+h{o}^{2}logho)$, where O(n) is the time for computing the run-length encoding of $s$ and $ho$ is the length of this encoding---this is no worse than previous solutions if $ho=O(n/logn)$ and better if $ho=o(n/logn)$. Our index $L$ can be queried in $O(logho)$ time. While $|L|=O(min(n,h{o}^2))$ in the worst case, preliminary investigations have indicated that $|L|$ may often be close to $ho$. Furthermore, the algorithm for constructing the index is conceptually simple and easy to implement. In an attempt to shed light on the structure and size of our index, we characterize it in terms of the prefix normal forms of $s$ introduced in [Fici and Lipt'ak, DLT 2011].

Recommendations

• Approximate matching of run-length compressed strings
• scientific article; zbMATH DE number 1786446
• Fast and simple jumbled indexing for binary run-length encoded strings
• scientific article; zbMATH DE number 2140438
• scientific article; zbMATH DE number 1615281
• Approximate string matching using compressed suffix arrays
• Combinatorial Pattern Matching
• Approximate string matching on Ziv--Lempel compressed text
• Matching for run-length encoded strings
• Approximate string matching with compressed indexes

Cites work

• Algorithms for jumbled pattern matching in strings
• Indexing permutations for binary strings
• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• On approximate jumbled pattern matching in strings
• On prefix normal words
• Sub-quadratic time and linear space data structures for permutation matching in binary strings

Cited in

(13)

• New algorithms for binary jumbled pattern matching
• Orthogonal range searching for text indexing
• Binary jumbled pattern matching on trees and tree-like structures
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Algorithms for computing abelian periods of words
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
• Fast and simple jumbled indexing for binary run-length encoded strings
• On the complexity of indeterminate strings matching
• Binary jumbled pattern matching: suffix tree indexing
• Binary jumbled indexing: suffix tree histogram
• On prefix normal words and prefix normal forms
• Binary jumbled pattern matching on trees and tree-like structures

This page was built for publication: Binary jumbled string matching for highly run-length compressible texts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444848)