Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
string libraries developed using CUDA
branch: master
Failed to load latest commit information.
README

README

This project is actually kept at http://code.google.com/p/exactstrmatchgpu
Motivation

This was started because the author's intense interest at the awesome raw power of GPUs. As a novice GPU developer, the author does hope to become a very good one.
Where we are going with this

For starters, the author will concentrate on parallelizing exact string matching algorithms since this topic is the author's favourite for the next couple of months...
What's there now
29 Nov 2010

   1. Naive String Matcher
   2. Horspool String Matcher
   3. QuickSearch? String Matcher 

Serial Algorithm Characteristics
Naive String Matcher

    * no preprocessing phase;
    * constant extra space needed;
    * always shifts the window by exactly 1 position to the right;
    * comparisons can be done in any order;
    * searching phase in O(mn) time complexity;
    * 2n expected text characters comparisons. 

Horspool String Matcher

    * simplification of the Boyer-Moore algorithm;
    * easy to implement;
    * preprocessing phase in O(m+sigma) time and O(sigma) space complexity;
    * searching phase in O(mn) time complexity;
    * the average number of comparisons for one text character is between 1/sigma and 2/(sigma+1). 

QuickSearch? String Matcher

    * simplification of the Boyer-Moore algorithm;
    * uses only the bad-character shift;
    * easy to implement;
    * preprocessing phase in O(m+sigma) time and O(sigma) space complexity;
    * searching phase in O(mn) time complexity;
    * very fast in practice for short patterns and large alphabets. 

Future work

    * Produce optimized versions of the algorithms (This should be done second)
    * Produce more CUDA-ized algorithms (This should be done first) 
Something went wrong with that request. Please try again.