Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <suffix_array_check.h>
Static Public Member Functions | |
static bool | isValidSuffixArray (const T s[], const int SA[], int length) |
static bool | isValidSuffixArrayInverses (const T s[], const int SA[], int length) |
Static Protected Member Functions | |
static bool | checkCondition1Holds (const int SA[], int length) |
static bool | checkCondition2Holds (const T s[], const int SA[], int length) |
static bool | checkCondition3HoldsKarkkainen (const T s[], const int SA[], int length) |
static bool | checkCondition3HoldsInverses (const T s[], const int SA[], int length) |
Private Member Functions | |
FRIEND_TEST (SuffixArrayCheck, condition1) |
Class that can check validity of suffix array conditions.
static bool strings::suffix_array::SuffixArrayChecker< T >::checkCondition1Holds | ( | const int | SA[], |
int | length | ||
) | [inline, static, protected] |
Checks that: For all i [0,length), SA[i] [0,length).
static bool strings::suffix_array::SuffixArrayChecker< T >::checkCondition2Holds | ( | const T | s[], |
const int | SA[], | ||
int | length | ||
) | [inline, static, protected] |
Checks that: For all i [1,length), s[SA[i - 1]] <= s[SA[i]]. Warning: there is no out-of bounds checking in this function, so be sure to call checkCondition1Holds() first!
static bool strings::suffix_array::SuffixArrayChecker< T >::checkCondition3HoldsInverses | ( | const T | s[], |
const int | SA[], | ||
int | length | ||
) | [inline, static, protected] |
Check that: For all i [1,length) such that s[SA[i - 1]] = s[SA[i]] and SA[i - 1] != n - 1, there exists j, k [0,n) such that SA[j] = SA[i - 1]+1, SA[k] = SA[i]+1 and j<k.
This algorithm requires linear memory becouse it needs inverse array to suffix array.
Warning: this function does not check for out-of-bounds, check condition 1 first.
static bool strings::suffix_array::SuffixArrayChecker< T >::checkCondition3HoldsKarkkainen | ( | const T | s[], |
const int | SA[], | ||
int | length | ||
) | [inline, static, protected] |
Checks following reformulation of 3. condition: For all characters c alphabet: If SA[a, b] contains the suffixes starting with the character c, then SA[a]+1, SA[a+1]+1,... , SA[b]+1 occur in SA in this order (but not consecutively in general), except that the first entry SA[a] + 1 is missing when c = s[n - 1].
Warning: this function does not check for out-of-the bounds, so you should check condition 1 first!
Note that memory O(sigma) where sigma is size of the alphabet. If your alphabet is positive-indexed and not sparse, you may change std::map to array in this implementation to gain speed and less memory storage.
Note: reformulation of 3rd condition is equal to the 3rd condition itself only when the first two conditions hold. The results of checkCondition3HoldsKarkkainen may be therefore different from checkCondition3HoldsInverses unless you assert the condition 1,2.
Based on pseudocode from the paper.
strings::suffix_array::SuffixArrayChecker< T >::FRIEND_TEST | ( | SuffixArrayCheck | , |
condition1 | |||
) | [private] |
static bool strings::suffix_array::SuffixArrayChecker< T >::isValidSuffixArray | ( | const T | s[], |
const int | SA[], | ||
int | length | ||
) | [inline, static] |
Liner-time check of suffix-array invariant. Uses O(alphabet) memory.
s | original sequence |
sa | suffix array to be checked |
length | length of the sequence (and suffix array) |
static bool strings::suffix_array::SuffixArrayChecker< T >::isValidSuffixArrayInverses | ( | const T | s[], |
const int | SA[], | ||
int | length | ||
) | [inline, static] |
Liner-time check of suffix-array invariant. Uses O(n) memory.
s | original sequence |
sa | suffix array to be checked |
length | length of the sequence (and suffix array) |