Approximate String Matching with SIMD

Fernando J. Fiori, Waltteri Pakalen, Jorma Tarhio

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)

Abstract

We consider the k mismatches version of approximate string matching for a single pattern and multiple patterns. For these problems, we present new algorithms utilizing the single instruction multiple data (SIMD) instruction set extensions for patterns of up to 32 characters. We apply SIMD computation in three ways: in counting of mismatches, in comparison of substrings and in calculation of fingerprints. We show the competitiveness of the new algorithms by practical experiments.
Original languageEnglish
Pages (from-to)1472–1488
JournalThe Computer Journal
Volume65
Issue number6
DOIs
Publication statusPublished - 23 Feb 2021
MoE publication typeA1 Journal article-refereed

Fingerprint

Dive into the research topics of 'Approximate String Matching with SIMD'. Together they form a unique fingerprint.

Cite this