Fast Packed String Matching for Short Patterns

DOI10.1137/1.9781611972931.10zbMATH Open1430.68460arXiv1209.6449OpenAlexW4205287277MaRDI QIDQ5232452FDOQ5232452

Authors: Simone Faro, M. Oğuzhan Külekci 

Publication date: 12 September 2019

Published in: 2013 Proceedings of the Fifteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Abstract: Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. In the last two decades a general trend has appeared trying to exploit the power of the word RAM model to speed-up the performances of classical string matching algorithms. In this model an algorithm operates on words of length w, grouping blocks of characters, and arithmetic and logic operations on the words take one unit of time. In this paper we use specialized word-size packed string matching instructions, based on the Intel streaming SIMD extensions (SSE) technology, to design very fast string matching algorithms in the case of short patterns. From our experimental results it turns out that, despite their quadratic worst case time complexity, the new presented algorithms become the clear winners on the average for short patterns, when compared against the most effective algorithms known in literature.

Full work available at URL: https://arxiv.org/abs/1209.6449

Recommendations

• Fast and flexible packed string matching
• Efficient string matching on packed texts
• Faster approximate string matching for short patterns
• Towards optimal packed string matching
• Fast Searching in Packed Strings
• Fast searching in packed strings
• Fast convolutions of packed strings and pattern matching with wildcards
• Optimal packed string matching
• scientific article; zbMATH DE number 1045405
• Fastest Pattern Matching in Strings

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithms on strings (68W32)

Cited In (5)

• The order-preserving pattern matching problem in practice
• Fast and flexible packed string matching
• Parallel String Matching
• Efficient string matching based on a two-step simulation of the suffix automaton
• Compact suffix automata representations for searching long patterns

This page was built for publication: Fast Packed String Matching for Short Patterns

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