Compressed string dictionary search with edit distance one

DOI10.1007/s00453-015-9990-0zbMath1333.68095OpenAlexW1967042936MaRDI QIDQ270017

Djamal Belazzougui, Rossano Venturini

Publication date: 6 April 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11568/800760

zbMATH Keywords

pattern matchingapproximate searchcompressed data structure

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20) Algorithms on strings (68W32)

Related Items (1)

Index structures for fast similarity search for symbol strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved bounds for dictionary look-up with one error
• Efficient fully-compressed sequence representations
• Improved space-time tradeoffs for approximate full-text indexing with one edit error
• A simple storage scheme for strings achieving entropy bounds
• Compressed suffix trees with full functionality
• Succinct Representation of Balanced Parentheses and Static Trees
• Compressed String Dictionary Look-Up with Edit Distance One
• New Lower and Upper Bounds for Representing Sequences
• Compressed representations of sequences and full-text indexes
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• The compressed permuterm index
• Succinct indexes for strings, binary relations and multilabeled trees
• Fully compressed suffix trees
• An analysis of the Burrows—Wheeler transform
• Indexing compressed text
• Dictionary matching and indexing with errors and don't cares
• Faster and Space-Optimal Edit Distance “1” Dictionary
• Efficient randomized pattern-matching algorithms
• Dictionary Look-Up with One Error
• Efficient Storage and Retrieval by Content and Address of Static Files
• Text Indexing and Dictionary Matching with One Error
• Alphabet-Independent Compressed Text Indexing
• Polynomial hash functions are reliable
• Compressed text indexes
• Space/time trade-offs in hash coding with allowable errors
• Compressed Static Functions with Applications

This page was built for publication: Compressed string dictionary search with edit distance one