Improved space-time tradeoffs for approximate full-text indexing with one edit error

DOI10.1007/S00453-014-9873-9MaRDI QIDQ494804zbMATH OpenOpenAlexFDO

Authors Djamal Belazzougui

Publication date 2 September 2015

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

edit distanceapproximate string matchingcompressed index

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Abstract: In this paper we are interested in indexing texts for substring matching queries with one edit error. That is, given a text $T$ of $n$ characters over an alphabet of size $sigma$, we are asked to build a data structure that answers the following query: find all the $occ$ substrings of the text that are at edit distance at most $1$ from a given string $q$ of length $m$. In this paper we show two new results for this problem. The first result, suitable for an unbounded alphabet, uses $O(nlo{g}^{e}psilonn)$ (where $epsilon$ is any constant such that $0<epsilon<1$) words of space and answers to queries in time $O(m+occ)$. This improves simultaneously in space and time over the result of Cole et al. The second result, suitable only for a constant alphabet, relies on compressed text indices and comes in two variants: the first variant uses $O(nlo{g}^{epsilon}n)$ bits of space and answers to queries in time $O(m+occ)$, while the second variant uses $O(nloglogn)$ bits of space and answers to queries in time $O((m+occ)loglogn)$. This second result improves on the previously best results for constant alphabets achieved in Lam et al. (Algorithmica 2008) and Chan et al. (Algorithmica 2010).

Recommendations

• Faster and Space-Optimal Edit Distance “1” Dictionary
• Text Indexing and Dictionary Matching with One Error
• Fast string dictionary lookup with one error
• scientific article; zbMATH DE number 2185612
• Compressed string dictionary search with edit distance one

Cites work

• scientific article; zbMATH DE number 1670652 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• scientific article; zbMATH DE number 871936 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• A linear size index for approximate pattern matching
• Algorithms and Computation
• Algorithms on Strings, Trees and Sequences
• Alphabet-independent compressed text indexing
• Combinatorial Pattern Matching
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed indexes for approximate string matching
• Dictionary matching and indexing with errors and don't cares
• Efficient Storage and Retrieval by Content and Address of Static Files
• Efficient randomized pattern-matching algorithms
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast prefix search in little space, with applications
• Faster and Space-Optimal Edit Distance “1” Dictionary
• Improved approximate string matching using compressed suffix data structures
• Indexing compressed text
• Jewels of Stringology
• Optimal succinctness for range minimum queries
• Succinct data structures for flexible text retrieval systems
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Suffix Arrays: A New Method for On-Line String Searches
• Text Indexing and Dictionary Matching with One Error
• Time-Space Trade-Offs for Longest Common Extensions
• Time-space trade-offs for compressed suffix arrays.

Cited in

(5)

• Text Indexing and Dictionary Matching with One Error
• Compressed string dictionary search with edit distance one
• Compressed string dictionary look-up with edit distance one
• Faster and Space-Optimal Edit Distance “1” Dictionary
• Deterministic document exchange protocols and almost optimal binary codes for edit errors

This page was built for publication: Improved space-time tradeoffs for approximate full-text indexing with one edit error

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