A faster algorithm computing string edit distances
From MaRDI portal
Publication:1140994
DOI10.1016/0022-0000(80)90002-1zbMath0436.68044OpenAlexW2012010763WikidataQ55891303 ScholiaQ55891303MaRDI QIDQ1140994
Michael S. Paterson, William J. Masek
Publication date: 1980
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(80)90002-1
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items
Deposition and extension approach to find longest common subsequence for thousands of long sequences ⋮ Performance analysis of some simple heuristics for computing longest common subsequences ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ A faster linear systolic algorithm for recovering a longest common subsequence ⋮ A fast algorithm for computing a longest common increasing subsequence ⋮ Rational equivalence relations ⋮ Dynamic Set Intersection ⋮ Faster subsequence recognition in compressed strings ⋮ Fast and compact regular expression matching ⋮ A linear space algorithm for computing a longest common increasing subsequence ⋮ New tabulation and sparse dynamic programming based techniques for sequence similarity problems ⋮ Fast approximate matching of words against a dictionary ⋮ The longest common subsequence problem revisited ⋮ Constrained string editing ⋮ An \(O(ND)\) difference algorithm and its variations ⋮ The set LCS problem ⋮ Breadth-first search strategies for trie-based syntactic pattern recognition ⋮ A novel look-ahead optimization strategy for trie-based approximate string matching ⋮ A new distance metric on strings computable in linear time ⋮ Constrained pairwise and center-star sequences alignment problems ⋮ Data structures and algorithms for approximate string matching ⋮ A lower bound for the edit-distance problem under an arbitrary cost function ⋮ A simple algorithm for the constrained sequence problems ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ Approximating the geometric edit distance ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ Optimality regions and fluctuations for Bernoulli last passage models ⋮ A hardness result and new algorithm for the longest common palindromic subsequence problem ⋮ Hardness and approximation of the asynchronous border minimization problem ⋮ Algorithms in the Ultra-Wide Word Model ⋮ Computing a longest common subsequence that is almost increasing on sequences having no repeated elements ⋮ Fast Algorithms for Local Similarity Queries in Two Sequences ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Fast Algorithms for Computing Tree LCS ⋮ Constrained LCS: Hardness and Approximation ⋮ On the Longest Common Parameterized Subsequence ⋮ Unified compression-based acceleration of edit-distance computation ⋮ A fully compressed algorithm for computing the edit distance of run-length encoded strings ⋮ Calcul de la distance par les sous-mots ⋮ The longest commonly positioned increasing subsequences problem ⋮ String matching with weighted errors ⋮ Quadratic-time algorithm for a string constrained LCS problem ⋮ Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence? ⋮ An O(NP) sequence comparison algorithm ⋮ FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Approximate Boyer-Moore string matching for small alphabets ⋮ Fast computation of a longest increasing subsequence and application ⋮ A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ Faster algorithms for computing longest common increasing subsequences ⋮ Algorithms for computing variants of the longest common subsequence problem ⋮ Edit distance with move operations ⋮ Edit distance with block deletions ⋮ Dynamic edit distance table under a general weighted cost function ⋮ On the generalized constrained longest common subsequence problems ⋮ An improved algorithm for computing the edit distance of run-length coded strings ⋮ Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition ⋮ Fast linear-space computations of longest common subsequences ⋮ Finding the longest common subsequence for multiple biological sequences by ant colony optimization ⋮ 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 ⋮ Constrained sequence analysis algorithms in computational biology ⋮ Efficient algorithms for the longest common subsequence in \(k\)-length substrings ⋮ A practical semi-external memory method for approximate pattern matching ⋮ New efficient algorithms for the LCS and constrained LCS problems ⋮ Faster approximate string matching for short patterns ⋮ Fast searching in packed strings ⋮ Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics ⋮ Finding common structured patterns in linear graphs ⋮ The intractability of computing the Hamming distance ⋮ Unnamed Item ⋮ Diversity metrics for direct-coded variable-length chromosome shortest path problem evolutionary algorithms ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ LCS approximation via embedding into locally non-repetitive strings ⋮ Efficient algorithms for finding a longest common increasing subsequence ⋮ Fast algorithms for computing tree LCS ⋮ A new efficient algorithm for computing the longest common subsequence ⋮ Semi-local longest common subsequences in subquadratic time ⋮ Communication-Efficient Private Protocols for Longest Common Subsequence ⋮ Shift-or string matching with super-alphabets ⋮ LCS Approximation via Embedding into Local Non-repetitive Strings ⋮ Fast Searching in Packed Strings ⋮ Periodic String Comparison ⋮ New Error Tolerant Method for Search of Long Repeats in DNA Sequences ⋮ An algorithm for distinguishing efficiently bit-strings by their subsequences ⋮ The constrained longest common subsequence problem ⋮ The set-set LCS problem ⋮ On the longest common parameterized subsequence ⋮ Matching for run-length encoded strings ⋮ Efficient error-correcting parsing for (attributed and stochastic) tree grammars ⋮ Complexity measures of words based on string matching and edit distance ⋮ Computing a longest common subsequence for a set of strings ⋮ BIT-PARALLEL COMPUTATION OF LOCAL SIMILARITY SCORE MATRICES WITH UNITARY WEIGHTS ⋮ Fast distance multiplication of unit-Monge matrices ⋮ A fast and practical bit-vector algorithm for the longest common subsequence problem ⋮ Resequencing a set of strings based on a target string ⋮ New algorithms for the LCS problem ⋮ Enumeration of maximal common subsequences between two strings ⋮ A data structure for substring-substring LCS length queries ⋮ A common basis for similarity measures involving two strings† ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False) ⋮ On locally optimal alignments in genetic sequences ⋮ Longest common subsequences ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ Absent Subsequences in Words ⋮ A Linear-Time n 0.4 -Approximation for Longest Common Subsequence ⋮ Longest Common Subsequence with Gap Constraints ⋮ Unnamed Item ⋮ Space-efficient STR-IC-LCS computation ⋮ Near-optimal quantum algorithms for string problems ⋮ Unnamed Item ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Longest increasing subsequence under persistent comparison errors ⋮ Normalization of edit sequences for text synchronization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A learning algorithm for the longest common subsequence problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Unnamed Item ⋮ APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
Cites Work
