A succinct four Russians speedup for edit distance computation and one-against-many banded alignment
From MaRDI portal
Publication:5140776
DOI10.4230/LIPICS.CPM.2018.13zbMATH Open1497.68596MaRDI QIDQ5140776FDOQ5140776
Authors: Brian Brubach, Jay Ghurye 
Publication date: 16 December 2020
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
- Algorithms on Strings, Trees and Sequences
- A faster algorithm computing string edit distances
- An \(O(ND)\) difference algorithm and its variations
- Geometric applications of a matrix-searching algorithm
- Fast approximate search in large dictionaries
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- Algorithms for approximate string matching
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- A Four Russians algorithm for regular expression pattern matching
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- A space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithm
- A Subquadratic Algorithm for Approximate Regular Expression Matching
- Fast string correction with Levenshtein automata
- Better greedy sequence clustering with fast banded alignment
Cited In (1)
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)
