A succinct four Russians speedup for edit distance computation and one-against-many banded alignment
From MaRDI portal
Publication:5140776
Recommendations
- A space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithm
- String Processing and Information Retrieval
- A fast bit-vector algorithm for approximate string matching based on dynamic programming
- A unified algorithm for accelerating edit-distance computation via text-compression
- Near-linear time edit distance for indel channels
Cites work
- A Four Russians algorithm for regular expression pattern matching
- A Subquadratic Algorithm for Approximate Regular Expression Matching
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- A faster algorithm computing string edit distances
- A space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithm
- Algorithms for approximate string matching
- Algorithms on Strings, Trees and Sequences
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- An \(O(ND)\) difference algorithm and its variations
- Better greedy sequence clustering with fast banded alignment
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Fast approximate search in large dictionaries
- Fast string correction with Levenshtein automata
- Geometric applications of a matrix-searching algorithm
This page was built for publication: A succinct four Russians speedup for edit distance computation and one-against-many banded alignment
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140776)
