Dictionary matching and indexing with errors and don't cares
From MaRDI portal
Publication:3580961
DOI10.1145/1007352.1007374zbMath1192.68818OpenAlexW2085218027MaRDI QIDQ3580961
Richard John Cole, Lee-Ad J. Gottlieb, Moshe Lewenstein
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007374
Related Items (73)
Approximate string matching using compressed suffix arrays ⋮ A metric index for approximate string matching ⋮ A matching algorithm in PMWL based on CluTree ⋮ Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis ⋮ Compressed string dictionary search with edit distance one ⋮ Document retrieval with one wildcard ⋮ The property suffix tree with dynamic properties ⋮ Efficient computation of sequence mappability ⋮ Less space: indexing for queries with wildcards ⋮ From Nerode's congruence to suffix automata with mismatches ⋮ Pattern matching with don't cares and few errors ⋮ Breadth-first search strategies for trie-based syntactic pattern recognition ⋮ Space-Efficient Frameworks for Top- k String Retrieval ⋮ Indexing factors with gaps ⋮ Approximate string matching with compressed indexes ⋮ Motif discovery by monotone scores ⋮ A filtering algorithm for \(k\)-mismatch with don't cares ⋮ On building minimal automaton for subset matching queries ⋮ Fast String Dictionary Lookup with One Error ⋮ Dictionary Matching with Uneven Gaps ⋮ Upper and Lower Bounds for Dynamic Data Structures on Strings ⋮ Compressed indexes for text with wildcards ⋮ Mind the gap! ⋮ On the average-case complexity of pattern matching with wildcards ⋮ Fast index for approximate string matching ⋮ Simple, compact and robust approximate string dictionary ⋮ On the Suffix Automaton with Mismatches ⋮ Approximate all-pairs suffix/prefix overlaps ⋮ Elastic-degenerate string matching with 1 error ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Compressed text indexing with wildcards ⋮ Multi-pattern matching algorithm with wildcards based on bit-parallelism ⋮ Dictionary matching with a bounded gap in pattern or in text ⋮ String matching with up to \(k\) swaps and mismatches ⋮ Online recognition of dictionary with one gap ⋮ Pattern matching with address errors: rearrangement distances ⋮ Text indexing with errors ⋮ A linear size index for approximate pattern matching ⋮ Improved approximate string matching using compressed suffix data structures ⋮ Property matching and weighted matching ⋮ Languages with mismatches ⋮ Algorithms for extracting motifs from biological weighted sequences ⋮ Improved space-time tradeoffs for approximate full-text indexing with one edit error ⋮ On the string matching with \(k\) mismatches ⋮ Succincter Text Indexing with Wildcards ⋮ Index structures for fast similarity search for binary vectors ⋮ Dynamic relative compression, dynamic partial sums, and substring concatenation ⋮ String indexing for patterns with wildcards ⋮ Cache-oblivious index for approximate string matching ⋮ Optimal prefix and suffix queries on texts ⋮ Maximal intersection queries in randomized input models ⋮ Faster algorithms for 1-mappability of a sequence ⋮ Succinct non-overlapping indexing ⋮ Compressed indexes for approximate string matching ⋮ Index structures for fast similarity search for symbol strings ⋮ Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances ⋮ Internal dictionary matching ⋮ \(k\)-difference matching in amortized linear time for all the words in a text ⋮ Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing ⋮ Faster and Space-Optimal Edit Distance “1” Dictionary ⋮ Streaming Dictionary Matching with Mismatches ⋮ Unnamed Item ⋮ Off-line and on-line algorithms for closed string factorization ⋮ A new method for approximate indexing and dictionary lookup with one error ⋮ Orthogonal Range Searching for Text Indexing ⋮ Indexes for Document Retrieval with Relevance ⋮ A note on the longest common substring with \(k\)-mismatches problem ⋮ Dictionary matching with a few gaps ⋮ Linear-Time Algorithm for Long LCF with k Mismatches ⋮ Compressing dictionary matching index via sparsification technique ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges ⋮ Streaming dictionary matching with mismatches
This page was built for publication: Dictionary matching and indexing with errors and don't cares
