A Simple Streaming Bit-parallel Algorithm for Swap Pattern Matching

The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols. The goal is to design fast matching algorithm that takes advantage of the bit parallelism of bitwise machine instructions and has only streaming access to th...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-09
Main Authors: Blažej, Václav, Suchý, Ondřej, Valla, Tomáš
Format: Article
Language:English
Subjects:
Algorithms
Automata theory
Pattern analysis
Pattern matching
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols. The goal is to design fast matching algorithm that takes advantage of the bit parallelism of bitwise machine instructions and has only streaming access to the input. We introduce a new approach to solve this problem based on the graph theoretic model and compare its performance to previously known algorithms. We also show that an approach using deterministic finite automata cannot achieve similarly efficient algorithms. Furthermore, we describe a fatal flaw in some of the previously published algorithms based on the same model. Finally, we provide experimental evaluation of our algorithm on real-world data.
ISSN:2331-8422