A Simple Streaming Bit-parallel Algorithm for Swap Pattern Matching

In this paper we present a streaming algorithm for Pattern Matching with Swaps (Swap Matching).

Abstract

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.

Codes & Other

All related code materials: codes.tar.gz

The code was tested on these corpuses:

void gsm(string &P, const char *T, int p, int t){
    const int u = 0, m = 1, d = 2;
    // DMASK initialization
    int i;
    bint F = 1;
    bint D[SIGMA];
    for(i = 0; i < SIGMA; ++i) D[i] = 0;
    for(i = 0; i < p; ++i){
        D[P[i]] |= F;
        F = F << 1;
    }

    // GSM initialization
    bint tmp[3]; // temporary vectors
    bint r[3]; // result vectors
    r[0]=r[1]=r[2]=0;
    bint resCheck = ((bint)1) << (p - 1);

    // GSM execution
    for(i = 0; i < t; ++i){
        tmp[u] = (r[d] << 1) | 1;
        tmp[m] = (r[m] << 1) | (r[u] << 1) | 1;
        tmp[d] = tmp[m];
        r[u] = tmp[u] & (D[T[i]] << 1);
        r[m] = tmp[m] &  D[T[i]];
        r[d] = tmp[d] & (D[T[i]] >> 1);
        if(((r[m] | r[u]) & resCheck) != 0) {
            FOUND(i - p + 2);
        }
    }
}

Implementation in c++

In practice, the data types required may be way bigger than 4*word-size so next we provide a GSM implementation in cpp which use bitsets.

#define MAX 50001 // maximal pattern length (+some)
// find all positions which contain a swapMatch of pattern in text
// sawp match allows distinct swapps of adjacent characters
vector<ll> gsm(string pattern, string text, int p, int t, int Sigma){
    vector<ll> res;
    for(int i=0; i<t; ++i)text[i]-='a';
    for(int i=0; i<p; ++i)pattern[i]-='a';
    // DMASK initialization
    vector<bitset<MAX>> D(Sigma);
    for(int i=0; i<p; ++i) D[pattern[i]].set(i);
    // GSM initialization
    bitset<MAX> r[3]; // result vectors
    bitset<MAX> tmp[3]; // temporary vectors
    bitset<MAX> resCheck;resCheck.set(p-1);
    bitset<MAX> one;one.set(0);

    // GSM execution
    for(int j=0; j<t; ++j){
        tmp[2] = (r[0] << 1) | one;
        tmp[1] = (r[1] << 1) | (r[2] << 1) | one;
        tmp[0] = tmp[1];
        r[2] = tmp[2] & (D[text[j]] << 1);
        r[1] = tmp[1] & D[text[j]];
        r[0] = tmp[0] & (D[text[j]] >> 1);
        if(!((r[1] | r[2]) & resCheck).none()) res.push_back(j-p+1);
    }
    return res;
}

Presentation

The paper was presented at MACIS 2017.

macis slides pdf