Struct sacapart::PartitionedSuffixArray

pub struct PartitionedSuffixArray<'a, Index> where
    Index: ToPrimitive + Send,  { /* fields omitted */ }

A partitioned suffix array, that is faster to construct but finds slightly worse matches in a slightly longer amount of time.

Suffix sorting is an expensive operation that is hard to parallelize well. The idea behind a partitioned suffix array is to suffix sort multiple parts of a text (in parallel) rather than the full text.

Using two partitions will result in roughly 2x faster construction (assuming there are two cores available), but search will now take O(2 * log n), and matches across the boundaries may be much worse.

For example, the text "totor" may be partitioned into "tot" and "or". Looking for matches for "tor" may well only return a substring of "to", at offset 0, because the first partition only has the suffixes "t", "to", and "tot". The second partition only has the suffixes "or" and "r". So, it finds the substring "(to)tor", tries to extend it to the right, and fails. It doesn't try to extend "to(t)or", because in the suffix array of that partition, that substring is a weaker match than "(to)tor".

For some applications (like bsdiff-like algorithms), this is an acceptable tradeoff (the resulting patch will be slightly larger). For others, it isn't.

Methods

impl<'a, Index> PartitionedSuffixArray<'a, Index> where
    Index: ToPrimitive + Send, 

pub fn new<F>(text: &'a [u8], num_partitions: usize, f: F) -> Self where
    F: Fn(&'a [u8]) -> SuffixArray<'a, Index> + Sync, 

pub fn num_partitions(&self) -> usize

Trait Implementations

impl<'a, Index> StringIndex<'a> for PartitionedSuffixArray<'a, Index> where
    Index: ToPrimitive + Send, 

fn longest_substring_match(&self, needle: &[u8]) -> LongestCommonSubstring<'a>

Returns the longest substring that matches needle in text