Algorithms for approximate string matching
From MaRDI portal
Publication:3694730
DOI10.1016/S0019-9958(85)80046-2zbMath0575.68090OpenAlexW2011632873WikidataQ29038248 ScholiaQ29038248MaRDI QIDQ3694730
Publication date: 1985
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(85)80046-2
Analysis of algorithms and problem complexity (68Q25) Pattern recognition, speech recognition (68T10)
Related Items (69)
Approximate pattern matching and transitive closure logics. ⋮ Performance analysis of some simple heuristics for computing longest common subsequences ⋮ A sublinear algorithm for approximate keyword searching ⋮ New and faster filters for multiple approximate string matching ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Boyer-Moore approach to approximate string matching ⋮ Edit distance for a run-length-encoded string and an uncompressed string ⋮ Fast approximate matching of words against a dictionary ⋮ Breadth-first search strategies for trie-based syntactic pattern recognition ⋮ Classes of cost functions for string edit distance ⋮ Sequence comparison with concave weighting functions ⋮ A novel look-ahead optimization strategy for trie-based approximate string matching ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ Refined algorithms for hitting many intervals ⋮ Approximating the geometric edit distance ⋮ Co-linear chaining with overlaps and gap costs ⋮ A dynamic edit distance table ⋮ On locally optimal alignments in genetic sequences ⋮ Longest common subsequences ⋮ Multiple approximate string matching ⋮ Block edit models for approximate string matching ⋮ Fast Algorithms for Local Similarity Queries in Two Sequences ⋮ The longest common extension problem revisited and applications to approximate string searching ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Fast Approximate Search in Large Dictionaries ⋮ On the Simon's congruence neighborhood of languages ⋮ Volume formula and growth rates of the balls of strings under the edit distances ⋮ Levenshtein graphs: resolvability, automorphisms \& determining sets ⋮ Unnamed Item ⋮ String matching with weighted errors ⋮ Extending alignments with \(k\)-mismatches and \(\ell\)-gaps ⋮ An O(NP) sequence comparison algorithm ⋮ Text indexing with errors ⋮ EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS ⋮ DICTIONARY LOOK-UP WITHIN SMALL EDIT DISTANCE ⋮ Edit distance with block deletions ⋮ An improved algorithm for computing the edit distance of run-length coded strings ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ Approximate string-matching with \(q\)-grams and maximal matches ⋮ A survey of multiple sequence comparison methods ⋮ A space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithm ⋮ An algorithm for matching run-length coded strings ⋮ VECTOR ALGORITHMS FOR APPROXIMATE STRING MATCHING ⋮ Approximate string matching with suffix automata ⋮ A practical semi-external memory method for approximate pattern matching ⋮ Faster approximate string matching for short patterns ⋮ Pattern matching in pseudo real-time ⋮ Efficient algorithms for the block edit problems ⋮ Deciding word neighborhood with universal neighborhood automata ⋮ Unnamed Item ⋮ Closest substring problems for regular languages ⋮ FINDING ALL APPROXIMATE GAPPED PALINDROMES ⋮ A Formal Investigation of Diff3 ⋮ A learning algorithm for the longest common subsequence problem ⋮ Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation ⋮ Weighted automata computation of edit distances with consolidations and fragmentations ⋮ Near optimal multiple alignment within a band in polynomial time ⋮ Unnamed Item ⋮ What’s Behind Blast ⋮ Efficient algorithms for approximate string matching with swaps ⋮ Exploiting distance coherence to speed up range queries in metric indexes ⋮ Approximate string matching using factor automata ⋮ Bit-parallel approximate string matching algorithms with transposition ⋮ Edit distance of run-length encoded strings. ⋮ General methods of sequence comparison ⋮ Finding approximate palindromes in strings ⋮ APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ † ⋮ Communication networks from the enron email corpus ``It's always about the people. Enron is no different ⋮ Discovering instances of poetic allusion from anthologies of classical Japanese poems
This page was built for publication: Algorithms for approximate string matching
