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

DOI10.1007/S00453-014-9873-9zbMATH Open1328.68321arXiv1103.2167OpenAlexW1808478258MaRDI QIDQ494804FDOQ494804

Authors: Djamal Belazzougui 

Publication date: 2 September 2015

Published in: Algorithmica (Search for Journal in Brave)

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).

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

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

zbMATH Keywords

edit distanceapproximate string matchingcompressed index

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• 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
• Text Indexing and Dictionary Matching with One Error

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)