Synopsis
Efficient parallel and serial approximate string matching explores how to find pattern occurrences in text when up to k differences are allowed.
It presents new algorithms that work in parallel and in series to handle the k-differences problem efficiently.
The book explains the problem setup, introduces a three-part approach, and shows how a powerful characterization of the text can lead to fast solutions. It discusses computational models like RAM and PRAM, and compares new methods to classical exact matching algorithms, highlighting where parallelism helps and where it does not.- How to model and measure differences between a pattern and text, including mismatches, deletions, and insertions.
- How to build a compact description of the text that supports fast final search for all valid occurrences.
- How the serial and parallel algorithms are structured: pattern analysis, text analysis, and locating all matches with at most k differences.
- What the workload looks like on parallel hardware, including processor counts and time bounds for each stage.
"synopsis" may belong to another edition of this title.
