Faster approximate string matching for short patterns

DOI10.1007/S00224-011-9322-YzbMATH Open1280.68304arXiv0811.3490OpenAlexW1821184416MaRDI QIDQ692899FDOQ692899

Philip Bille

Publication date: 6 December 2012

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

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.

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

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

zbMATH Keywords

approximate string matchingword-level parallelism

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
• Fast Packed String Matching for Short Patterns
• New and faster filters for multiple approximate string matching
• Title not available (Why is that?)

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)