Abstract
We present new algorithms for the k mismatches version of approximate string matching. Our algorithms utilize the SIMD (Single Instruction Multiple Data) instruction set extensions, particularly AVX2 and AVX-512 instructions. Our approach is an extension of an earlier algorithm for exact string matching with SSE2 and AVX2. In addition, we modify this exact string matching algorithm to work with AVX-512. We demonstrate the competitiveness of our solutions by practical experiments. Our experimental results show that our algorithms outperform earlier algorithms for both exact and approximate string matching on various benchmark data sets.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Prague Stringology Conference 2023 |
| Publisher | Prague Stringology Club |
| Pages | 57-67 |
| ISBN (Print) | 978-80-01-07206-6 |
| DOIs | |
| Publication status | Published - 2023 |
| MoE publication type | A4 Conference publication |
| Event | Prague Stringology Conference - Prague, Czech Republic Duration: 28 Aug 2023 → 29 Aug 2023 |
Conference
| Conference | Prague Stringology Conference |
|---|---|
| Abbreviated title | PSC |
| Country/Territory | Czech Republic |
| City | Prague |
| Period | 28/08/2023 → 29/08/2023 |
Keywords
- approximate string matching
- Hamming distance
- exact string matching
- SIMD computing
- experimental comparison