sais 0.0.2

Rust version of libsais
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

use rayon::prelude::*;
use std::cmp::Ordering;
use std::sync::Mutex;

extern crate num_cpus;

// A struct representing a suffix, consisting of a start index and a length
#[derive(PartialEq, Eq)]
struct Suffix<'a> {
    start_index: usize,
    text: &'a [u8],
}

impl<'a> PartialOrd for Suffix<'a> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.text[self.start_index..].partial_cmp(&other.text[other.start_index..])
    }
}

impl<'a> Ord for Suffix<'a> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.text[self.start_index..].cmp(&other.text[other.start_index..])
    }
}

// A function for constructing the suffix array in parallel
pub fn construct_suffix_array_parallel(text: &[u8]) -> Vec<usize> {
    let mut suffixes: Vec<_> = (0..text.len())
        .map(|i| Suffix {
            start_index: i,
            text,
        })
        .collect();

    suffixes.par_sort_unstable_by(|a, b| a.cmp(b));
    // Sort the suffixes in parallel
    let sorted_suffixes: Vec<_> = suffixes
        .into_iter()
        .map(|suffix| suffix.start_index)
        .collect();

    sorted_suffixes
}

pub fn lcp_array_parallel(sa: &[usize], a: &[u8]) -> Vec<usize> {
    let n = sa.len();
    let mut lcp = vec![0; n - 1]; // One less than the length of the input
    let mut rank = vec![0; n];

    for i in 0..n {
        rank[sa[i]] = i;
    }

    let lcp_ref = Mutex::new(&mut lcp);
    let rank_ref = &rank;

    sa.par_iter().enumerate().skip(1).for_each(|(_i, &suf)| {
        let rank = rank_ref[suf];
        let prev_suf = sa[rank - 1];
        let mut length = 0;
        while suf + length < n && prev_suf + length < n && a[suf + length] == a[prev_suf + length] {
            length += 1;
        }
        lcp_ref.lock().unwrap()[rank - 1] = length;
    });

    lcp
}

// Serial implementation of LCP array construction for validation
pub fn lcp_array_serial(sa: &[usize], s: &[u8]) -> Vec<usize> {
    let n = sa.len();
    let mut lcp = vec![0; n - 1]; // One less than the number of suffixes
    let mut rank = vec![0; n];

    for i in 0..n {
        rank[sa[i]] = i;
    }

    let mut h = 0;
    for i in 0..n {
        if rank[i] > 0 {
            let k = sa[rank[i] - 1];
            while i + h < n && k + h < n && s[i + h] == s[k + h] {
                h += 1;
            }
            lcp[rank[i] - 1] = h;
            if h > 0 {
                h -= 1;
            }
        }
    }
    lcp
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_construct_suffix_array_parallel() {
        let text = "banana".as_bytes();
        let sa = construct_suffix_array_parallel(text);
        assert_eq!(sa, vec![5, 3, 1, 0, 4, 2]);
    }

    #[test]
    fn test_lcp_array_parallel() {
        let text = "banana".as_bytes();
        let sa = construct_suffix_array_parallel(text);
        let lcp_parallel = lcp_array_parallel(&sa, text);
        let lcp_serial = lcp_array_serial(&sa, text);
        // The expected LCP array for "banana" with sa [5, 3, 1, 0, 4, 2] is [1, 3, 0, 0, 2]
        assert_eq!(lcp_parallel, lcp_serial); // The last element is always 0 as there is no suffix after the last one.
    }
}