Faster approximate string matching for short patterns

DOI10.1007/S00224-011-9322-YMaRDI QIDQ692899zbMATH OpenOpenAlexFDO

Authors Philip Bille

Publication date 6 December 2012

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0811.3490

zbMATH Keywords

approximate string matchingword-level parallelism

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: We study the classical approximate string matching problem, that is, given strings $P$ and $Q$ and an error threshold $k$, find all ending positions of substrings of $Q$ whose edit distance to $P$ is at most $k$. Let $P$ and $Q$ have lengths $m$ and $n$, respectively. On a standard unit-cost word RAM with word size $wgeqlogn$ we present an algorithm using time ${\displaystyle }$ O(nk cdot min(frac{log^2 m}{log n},frac{log^2 mlog w}{w}) + n) ${\displaystyle }$ When $P$ is short, namely, $m=2^{o(sqrtlogn)}$ or $m=2^{o(sqrtw/logw)}$ this improves the previously best known time bounds for the problem. The result is achieved using a novel implementation of the Landau-Vishkin algorithm based on tabulation and word-level parallelism.

Recommendations

• scientific article; zbMATH DE number 1303588
• Approximate String Matching: A Simpler Faster Algorithm
• Faster approximate string matching
• Fast and practical approximate string matching
• scientific article; zbMATH DE number 2087055

Cites work

• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• A faster algorithm computing string edit distances
• Algorithms for approximate string matching
• Algorithms on Strings, Trees and Sequences
• An Improved Algorithm For Approximate String Matching
• An \(O(ND)\) difference algorithm and its variations
• Approximate String Matching: A Simpler Faster Algorithm
• Approximate string matching using withinword parallelism
• Approximate string matching with suffix automata
• Bit-parallel witnesses and their applications to approximate string matching
• Data structures and algorithms for approximate string matching
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast and compact regular expression matching
• Fast parallel and serial approximate string matching
• Improved parallel integer sorting without concurrent writing
• Introduction to algorithms
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• New and faster filters for multiple approximate string matching
• On the sorting-complexity of suffix tree construction
• Sorting in linear time?
• The String-to-String Correction Problem
• The theory and computation of evolutionary distances: Pattern recognition

Cited in

(8)

• Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
• Lossless seeds for searching short patterns with high error rates
• Fast Packed String Matching for Short Patterns
• Fast and simple computations using prefix tables under Hamming and edit distance
• Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
• New and faster filters for multiple approximate string matching
• scientific article; zbMATH DE number 2087055 (Why is no real title available?)
• A practical semi-external memory method for approximate pattern matching

This page was built for publication: Faster approximate string matching for short patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692899)