Approximate String Matching with SIMD

被引：5
作者：
Fiori, Fernando J. [1 ]
Pakalen, Waltteri [2 ]
Tarhio, Jorma [2 ]
机构：
[1] Univ Nacl Rosario, Dept Ciencias Comp, Fac Ciencias Exactas Ing & Agrimensura, Pellegrini 250,S2000BTP, Rosario, Argentina
[2] Aalto Univ, Dept Comp Sci, POB 15400, FI-00076 Aalto, Finland
来源：
COMPUTER JOURNAL | 2022年 / 65卷 / 06期
关键词：
approximate string; k mismatches; Hamming distance; SIMD; ALGORITHMS;
D O I：
10.1093/comjnl/bxaa193
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
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.
引用
收藏
页码：1472 / 1488
页数：17
相关论文
共 37 条
  • [1] GENERALIZED STRING MATCHING
    ABRAHAMSON, K
    [J]. SIAM JOURNAL ON COMPUTING, 1987, 16 (06) : 1039 - 1051
  • [2] Faster algorithms for string matching with k mismatches
    Amir, A
    Lewenstein, M
    Porat, E
    [J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2004, 50 (02): : 257 - 275
  • [3] New and faster filters for multiple approximate string matching
    BaezaYates, R
    Navarro, G
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2002, 20 (01) : 23 - 49
  • [4] A NEW APPROACH TO TEXT SEARCHING
    BAEZAYATES, R
    GONNET, GH
    [J]. COMMUNICATIONS OF THE ACM, 1992, 35 (10) : 74 - 82
  • [5] Fast and practical approximate string matching
    BaezaYates, RA
    Perleberg, CH
    [J]. INFORMATION PROCESSING LETTERS, 1996, 59 (01) : 21 - 27
  • [6] Engineering order-preserving pattern matching with SIMD parallelism
    Chhabra, Tamanna
    Faro, Simone
    Kulekci, M. Oguzhan
    Tarhio, Jorma
    [J]. SOFTWARE-PRACTICE & EXPERIENCE, 2017, 47 (05) : 731 - 739
  • [7] Clifford Raphael, 2016, P 27 ANN ACM SIAM S, P2039, DOI [DOI 10.1137/1.9781611974331.CH142.4, DOI 10.1137/1.9781611974331.CH142]
  • [8] DIXON NR, 1979, AUTOMATIC SPEECH SPE
  • [9] Durian B., 2014, P PRAG STRING C 2014, P71
  • [10] A REVIEW OF SEGMENTATION AND CONTEXTUAL ANALYSIS TECHNIQUES FOR TEXT RECOGNITION
    ELLIMAN, DG
    LANCASTER, IT
    [J]. PATTERN RECOGNITION, 1990, 23 (3-4) : 337 - 346
1234