Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching

DOI10.1016/J.EJC.2012.07.013MaRDI QIDQ1761497zbMATH OpenOpenAlexFDO

Authors Kimmo Fredriksson, Szymon Grabowski

Publication date 15 November 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2012.07.013

zbMATH Keywords

approximate string matchingconvolutionspattern matchingword RAM model of computation

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05)

Recommendations

• Fast convolutions and their applications in approximate string matching
• Fast convolutions of packed strings and pattern matching with wildcards
• A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches
• Increased bit-parallelism for approximate and multiple string matching
• Faster approximate string matching for short patterns

Cites work

• Algorithms on Strings, Trees and Sequences
• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Data structures and algorithms for approximate string matching
• Efficient string matching with k mismatches
• Fast convolutions and their applications in approximate string matching
• Faster pattern matching with character classes using prime number encoding
• Finding large 3-free sets. I. The small \(n\) case
• Generalized String Matching
• scientific article; zbMATH DE number 3984596 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 2079401 (Why is no real title available?)
• scientific article; zbMATH DE number 1445379 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• On Certain Sets of Integers
• On Roth's theorem on progressions
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Surpassing the information theoretic bound with fusion trees
• The practical efficiency of convolutions in pattern matching algorithms

Cited in

(7)

• Rank and select operations on a word
• Approximate pattern matching with \(k\)-mismatches in packed text
• An acceleration of FFT-based algorithms for the match-count problem
• Fast convolutions and their applications in approximate string matching
• On approximate pattern matching with thresholds
• Fast convolutions of packed strings and pattern matching with wildcards
• String searching with mismatches using AVX2 and AVX-512 instructions

This page was built for publication: Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching

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