scientific article; zbMATH DE number 3845091
[This article was published in this book announced in this Zbl 0513.00010.] The edit distance between two strings is usually measured as the minimum number of deletions, insertions and changes of symbols needed to transform one string into the other. Also the transposition of two ajacent symbols can be included in the editing operations. This paper gives an improved algorithm for computing the edit distance. For two strings \(a_ 1a_ 2...a_ m\) and \(b_ 1b_ 2...b_ n\) the algorithm computes the edit distance s as well as the corresponding sequence of editing steps (insertions, deletions, changes, transpositions) in time 0(\(s\cdot \min(m,n))\) and in space \(0(s^ 2)\). If the editing sequence is not needed, the space requirement reduces to 0(s). Given a threshold value t, the algorithm can also be modified to test in time 0(\(t\cdot \min(m,n))\) and space 0(t) whether the edit distance of the two strings is at most t. For small s, this algorithm significantly improves the well-known dynamic programming method for this problem [see e.g. the paper by \textit{R. A. Wagner} ad \textit{M. J. Fischer}, J. Assoc. Comput. Mach. 21, 168-173 (1974; Zbl 0278.68032)], whose time requirement is 0(mn) and space requirement is 0(mn) or 0(min(m,n)) depending on whether or not the editing sequence is needed. Also note that instead of 'edit distance' the terms 'evolutionary distance' and 'string-to-string correction' are sometimes used in the literature.
- An integer linear programming approach for approximate string comparison
- Optimal sequence alignment using affine gap costs
- Constrained string editing
- Data structures and algorithms for approximate string matching
- A lower bound for the edit-distance problem under an arbitrary cost function
- Fast string matching with k differences
- A survey of multiple sequence comparison methods
- Lazy dynamic-programming can be eager
- String editing under a combination of constraints
- Using Hirschberg's algorithm to generate random alignments of strings
- Efficient matching of nonrectangular shapes.
- Block edit models for approximate string matching
- Generalized quasi-metric on strings
- Approximate regular expression matching with multi-strings
- Speeding up the detection of tandem repeats over the edit distance
- Vector representations for efficient comparison and search for similar strings
- Bit-parallel approximate string matching algorithms with transposition
- Optimal spaced seeds for faster approximate string matching
- Fast string matching in stationary ergodic sources
- The string edit distance matching problem with moves
- Fast and simple computations using prefix tables under Hamming and edit distance
- Accurate and efficient methods to improve multiple circular sequence alignment
- String comparison by transposition networks
- Notes on generating completely condensed d-neighborhoods
- A new algorithm for the characteristic string problem under loose similarity criteria
- Approximate String Matching: A Simpler Faster Algorithm
- Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time
- Dynamic edit distance table under a general weighted cost function
- A low-complexity distance for DNA strings
- Efficient Parallel Algorithms for String Editing and Related Problems
- Some applications of string algorithms in human-computer interaction
- Edit distance with combinations and splits and its applications in OCR name matching
- Calcul de la distance par les sous-mots
- scientific article; zbMATH DE number 4053031 (Why is no real title available?)
- A new filtration method and a hybrid strategy for approximate string matching
- Two algorithms for approximate string matching in static texts. (Extended abstract)
- Similarity in two-dimensional strings
- Algorithms for transposition invariant string matching
- scientific article; zbMATH DE number 2052917 (Why is no real title available?)
- scientific article; zbMATH DE number 1482232 (Why is no real title available?)
- scientific article; zbMATH DE number 1516705 (Why is no real title available?)
- Charge and reduce: A fixed-parameter algorithm for string-to-string correction
- scientific article; zbMATH DE number 2149348 (Why is no real title available?)
- scientific article; zbMATH DE number 2119725 (Why is no real title available?)
- scientific article; zbMATH DE number 826062 (Why is no real title available?)
- Dynamic edit distance table under a general weighted cost function
- scientific article; zbMATH DE number 1446756 (Why is no real title available?)
- Boosting the Quality of Approximate String Matching by Synonyms
- Boyer-Moore approach to approximate string matching
- A space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithm
- Multiple approximate string matching
- From Winner-Takes-All to Winners-Share-All: Exploiting the Information Capacity in Temporal Codes
- Approximate String Matching Using a Bidirectional Index
- Average-optimal single and multiple approximate string matching
- Computing the cyclic edit distance for pattern classification by ranking edit paths
- Hardness of string similarity search and other indexing problems
- Transposition invariant string matching
- Listing center strings under the edit distance metric
- String Matching: Communication, Circuits, and Learning.
- Bit-parallel approximate string matching algorithms with transposition.
- The approximate swap and mismatch edit distance
- Near-linear time edit distance for indel channels
- On-line approximate string matching with bounded errors
- Bounds and estimates on the average edit distance
- Approximate string matching with suffix automata
- General methods of sequence comparison
- String matching with weighted errors
- An O(NP) sequence comparison algorithm
- Optimal sequence alignment allowing for long gaps
- An algorithm with linear expected running time for string editing with substitutions and substring reversals
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3315039)