Approximate String Matching with SIMD. (23rd February 2021)

• Record Type: Journal Article
• Authors: Fiori, Fernando J; Pakalén, Waltteri; Tarhio, Jorma
• Editors: Wong, Prudence
• Is Part Of: Computer journal. Volume 65:Number 6(2022)
• Page Start: 1472
• Page End: 1488
• Publication Date: 2021-02-23
• Subjects: approximate string -- k mismatches -- Hamming distance -- SIMD; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa193
• Languages: English
• ISSNs: 0010-4620

Abstract

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.