I am implementing an MQTT Broker. After connection, a client subscribes to one or more topics, which might contain one of two wildcard types.
A regular topic might look like foo/bar/baz/blah .
A # wildcard would match the entirety of the remaining string, a + wildcard would match only a single path segment, e.g. foo/bar/+/blah. When a message is published to a topic, the broker would find all matching subscriptions and deliver that message accordingly. This is a bit of a twist on the traditional string search problem, because the wildcards are in the dictionary instead of the query string.

It is expected that the broker should be able to handle 10,000 of connections, with each connection subscribing to an average 20 topics each. It is also expected that there would be many duplicate connections.

I can think of one approach, and I'm not thrilled by it, and that is to build the table using only the path segments themselves, and perform successive searches using only the segments of the path segments of the query. Then I could use the resulting indices into the table as keys into a map of subscribers.

It would still be a bit tricky, because it would require an n-gram search for the resulting subscribers.

e.g. subscribers:
A: is at pizza/+/meats/sausage C: is at pizza/toppings/fruits/tomatoes D: is at pizza/#

Naively**, the dictionary is

pizza/+/meats/sausage$pizza/toppings/fruits/tomatoes$pizza/#
01234567890123456789012345678901234567890123456789

a match at 0, 24,31, 36 would find subscriber A. A match at 0 would find subscriber D.
A message is published at pizza/toppings/fruits/tomatoes

** I big optimization here is that the dictionary doesn't need to duplicate path segments, so we could ensure they're unique. Given the nature of mqtt subscriptions, this would be a big win.

I'm thinking that might be too much effort trying to wedge the suffix table approach where it doesn't fit, and maybe I'm better off building a suffix tree where I can explicitly create and handle wildcard nodes. Also a bitmap index seems promising.

Even simpler but perhaps less performant would be to just build a massive Regex out of each subscription string. (might work for 100 subscriptions, but get unwieldy at 1000+, which is certainly in the realm of possibility.

p.s., I just found http://blog.burntsushi.net/transducers/ which I am attempting to digest.

Hi,

I needed a high performance suffix array lib some time ago for a bioinformatics project, and I ended up working with a crude FFI with divsufsort.

Just so you know, its performances while creating the array is blowing suffix out of the water. So feel free to take a glance if it interests you or to close this issue otherwise ;)

This crate enjoys a small API and has had some minor breaking changes over its lifetime, but given its modest functionality, I don't foresee a major API refactoring in its near future. Therefore, I'd like to move this to 1.0.

When I initially built this crate, I did have a grander vision for building a more complete suffix array implementation. In particular, while this crate provides a nearly optimal construction algorithm implementation, it does not provide an optimal search algorithm implementation. Search should be implementable in O(p+logn) time (where p ~ len(query) and n ~ len(haystack)), but is currently O(p*logn). Improving the bound requires some sophisticated implementation tricks that have proved difficult to extract from the literature. I offered a bounty on a StackOverflow question and got an answer, but I haven't digested it yet. Nevertheless, a plain suffix table is plenty useful in its own right, so a 1.0 release shouldn't be blocked on further improvements even if it requires a rethink of the public API.

After his linear time suffix array work, Pang Ko came up with a string B-tree data structure for cache oblivious access:

https://lib.dr.iastate.edu/rtd/15942/

Any interest in a PR for a string B-tree or should i make a new repository? Ideally it would handle RAM, local disk, and a network store like AWS S3. I know at least one team at Amazon that would use this internally at scale. Toss in a Bloom filter on the network store shards and it could save obscene amounts of IO for cold reads.

I had a question, or perhaps suggestion, but I am new to Rust, so I might be missing something: the SuffixTable struct stores the text as Cow, but the actual table/array as a vector that is always owned. I wondered if you considered making the table Cow as well.

The immediate benefit that I see is that one could write the constructed table to disk and then later use the SuffixTable using a memory mapped table via from_parts.

I made a quick modification to use Cow for the table member and all unit tests pass.

This is 4.5× faster than positions for my use case in the following representative benchmark.

Use case: to deal with serde Deserializers that do not support producing borrowed data (&'de str) we can easily just look up every string produced by the deserializer in the original input, and thereby turn a transient string (&str) into a borrowed string (&'de str) for each one found anywhere in the input. Specifically for serde_yaml, the performance of SuffixTable::new does not matter because we can run it in parallel with yaml-rust's Parser::load step, which will always take longer than the SuffixTable construction.

[If you happen to know: is suffix array even the right data structure for this use case? A key characteristic of the use case is that Σm = O(n) i.e. I only ever look up non-overlapping substrings of the original text, so the sum of lengths of all queries is no more than n. With a suffix array each query is O(m log n) so total O(n log n). From some naive napkin sketches I believe O(n) is achievable with a hash-based structure, with amortized O(m) time per query. I'm not really interested in inventing a novel algorithm though if this is a solved problem.]

#![feature(test)]
extern crate test;

use serde_json::Value;
use suffix::SuffixTable;

fn setup() -> (String, Vec<String>) {
    const JSON: &str = include_str!("twitter.json"); // https://github.com/serde-rs/json-benchmark/tree/master/data
    let json_value: Value = serde_json::from_str(JSON).unwrap();
    let yaml = serde_yaml::to_string(&json_value).unwrap();

    let mut strings = Vec::new();
    let mut stack = Vec::new();
    stack.push(json_value);
    while let Some(value) = stack.pop() {
        match value {
            Value::Null | Value::Bool(_) | Value::Number(_) => {}
            Value::String(string) => strings.push(string),
            Value::Array(array) => stack.extend(array),
            Value::Object(object) => {
                for (key, value) in object {
                    strings.push(key);
                    stack.push(value);
                }
            }
        }
    }

    (yaml, strings)
}

#[bench]
fn bench_positions(b: &mut test::Bencher) {
    let (yaml, strings) = setup();
    let index = SuffixTable::new(&yaml);
    b.iter(|| {
        for string in &strings {
            test::black_box(index.positions(string));
        }
    });
}

#[bench]
fn bench_any_position(b: &mut test::Bencher) {
    let (yaml, strings) = setup();
    let index = SuffixTable::new(&yaml);
    b.iter(|| {
        for string in &strings {
            test::black_box(index.any_position(string));
        }
    });
}

I've been recently teaching myself bioinformatics and algorithms. I got really confused when while delving into suffix arrays, particularly when it comes to the use of sentinels.

As suggested by WillamFiset in his video, a generalized suffix array using different types of sentinels must be used to solve the LCS problem. However, I don't really see the need for sentinels. Indeed, according to (Shrestha et al., 2014) that's cited by you, sentinels are crucial by suffix trees but are not absolutely needed for suffix arrays, though some algorithms for constructing suffix arrays need them.

Based on WillamFiset's video (which uses sentinels), I devised the following algorithm for solving the LCS problem which uses this crate (that does not use sentinels and is not so-called 'generalized suffix array').

So the question is, what exactly defines a generalized suffix array, and how is a generalized suffix array (with multiple sentinels) is superior to the following algorithm in solving the LCS problem?

(Or probably the following algorithm itself is an implementation of the generalized suffix array without sentinels? (since I saw from some sources that a 'generalized suffix array/tree' is just a fancy name for a suffix array/tree to which multiple strings can be added))

extern crate suffix;
use suffix::SuffixTable;

fn main() {
    // find the longest common substring (LCS) of the following 5 strings
    let strs =
        ["ZYABCAGB", "BCAGDTZYY", "DACAGZZYSC", "CAGYZYSAU", "CAZYUCAGF"];
    let number_of_strings = strs.len();
    let mut boundaries = Vec::new();
    let mut concatenated = String::new();
    for s in strs.iter() {
        concatenated.push_str(*s);
        boundaries.push(concatenated.len());
    }

    let sa = SuffixTable::new(&concatenated);

    let pos = sa.table();
    let lcp = sa.lcp_lens();

    // for demonstration.
    // SA: suffix array
    // LCP: LCP array
    // n: the index of the original string this character belongs to
    // suffix: the suffix (of the concatenated string)
    println!(" SA LCP n Suffix");
    println!("--------------------");
    for (&p, &l) in pos.iter().zip(lcp.iter()) {
        let n = string_number(p, &boundaries);
        println!("{:>3} {:>3} {} {}", p, l, n, &concatenated[(p as usize)..])
    }
    println!("{:?}", boundaries);

    let mut lcs_len = 0u32;
    let mut lcs_pos: u32 = 0;

    'outer: for (win_p, win_l) in
        pos.windows(number_of_strings).zip(lcp.windows(number_of_strings))
    {
        // examine if each window contains substrings coming from different original strings
        // use a vector of booleans to track whether a substring has been included.
        // upon duplication, abort and continue scanning the next frame
        let mut included = vec![false; number_of_strings];
        // this step should be O(number_of_strings) ?
        for &p in win_p {
            let n = string_number(p, &boundaries);
            if included[n] {
                continue 'outer;
            } else {
                included[n] = true;
            }
        }
        // this window contains one and only one suffixes from each original strings;
        // calculate the LCS within this window
        let m = win_l.iter().skip(1).min().unwrap(); // win_l always has length 3
        let this_cs_len = *m;
        let this_cs_pos = win_p[0];
        let this_cs = concatenated
            .chars()
            .skip(this_cs_pos as usize)
            .take(this_cs_len as usize)
            .collect::<String>();
        if this_cs.len() > 0 {
            println!("Found common substring: {}", this_cs);
        }

        if *m > lcs_len {
            lcs_len = this_cs_len;
            lcs_pos = this_cs_pos;
        }
    }

    println!(
        "LCS: {:?}",
        concatenated
            .chars()
            .skip(lcs_pos as usize)
            .take(lcs_len as usize)
            .collect::<String>()
    );
    println!("LCS length: {}", lcs_len);
}

fn string_number(position: u32, boundaries: &[usize]) -> usize {
    match boundaries.binary_search(&(position as usize)) {
        Ok(idx) => idx + 1,
        Err(idx) => idx,
    }
}

which prints:

SA LCP n Suffix
--------------------
  2   0 0 ABCAGBBCAGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 18   1 2 ACAGZZYSCCAGYZYSAUCAZYUCAGF
  5   1 0 AGBBCAGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 10   2 1 AGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 42   2 4 AGF
 28   2 3 AGYZYSAUCAZYUCAGF
 20   2 2 AGZZYSCCAGYZYSAUCAZYUCAGF
 34   1 3 AUCAZYUCAGF
 37   1 4 AZYUCAGF
  7   0 0 BBCAGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
  3   1 0 BCAGBBCAGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
  8   4 1 BCAGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
  4   0 0 CAGBBCAGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
  9   3 1 CAGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 41   3 4 CAGF
 27   3 3 CAGYZYSAUCAZYUCAGF
 19   3 2 CAGZZYSCCAGYZYSAUCAZYUCAGF
 36   2 4 CAZYUCAGF
 26   1 2 CCAGYZYSAUCAZYUCAGF
 17   0 2 DACAGZZYSCCAGYZYSAUCAZYUCAGF
 12   1 1 DTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 44   0 4 F
  6   0 0 GBBCAGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 11   1 1 GDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 43   1 4 GF
 29   1 3 GYZYSAUCAZYUCAGF
 21   1 2 GZZYSCCAGYZYSAUCAZYUCAGF
 33   0 3 SAUCAZYUCAGF
 25   1 2 SCCAGYZYSAUCAZYUCAGF
 13   0 1 TZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 40   0 4 UCAGF
 35   3 3 UCAZYUCAGF
  1   0 0 YABCAGBBCAGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 16   1 1 YDACAGZZYSCCAGYZYSAUCAZYUCAGF
 32   1 3 YSAUCAZYUCAGF
 24   2 2 YSCCAGYZYSAUCAZYUCAGF
 39   1 4 YUCAGF
 15   1 1 YYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 30   1 3 YZYSAUCAZYUCAGF
  0   0 0 ZYABCAGBBCAGDTZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 31   2 3 ZYSAUCAZYUCAGF
 23   3 2 ZYSCCAGYZYSAUCAZYUCAGF
 38   2 4 ZYUCAGF
 14   2 1 ZYYDACAGZZYSCCAGYZYSAUCAZYUCAGF
 22   1 2 ZZYSCCAGYZYSAUCAZYUCAGF
[8, 17, 27, 36, 45]
Found common substring: A
Found common substring: AG
Found common substring: CAG
Found common substring: G
Found common substring: Y
Found common substring: ZY
LCS: "CAG"
LCS length: 3

Text example

この麗しき御方こそが、甲斐この麗しき御方こそが、甲斐源氏の本この麗しき御方こそが、甲斐源氏の本流たる武この麗しき御方こそが、甲斐源氏の本流たる武田家の第この麗しき御方こそが、甲斐源氏の本流たる武田家の第十九代目この麗しき御方こそが、甲斐源氏の本流たる武田家の第十九代目の当主。武この麗しき御方こそが、甲斐源氏の本流たる武田家の第十九代目の当主。武田信玄そこの麗しき御方こそが、甲斐源氏の本流たる武田家の第十九代目の当主。武田信玄その人だ。この麗しき御方こそが、甲斐源氏の本流たる武田家の第十九代目の当主。武田信玄その人だ。

My test case is pretty simple:

let suffix_table = suffix::SuffixTable::new(text) //text is variable that contains quoted string above
println!("suffix[1]={}", suffix_table.suffix(1).to_string())

Code will panic:

panicked at 'byte index 70 is not a char boundary; it is inside '、' (bytes 69..72) of この麗しき御方こそが、甲斐この麗しき御方こそが、甲斐源氏の本この麗しき御方こそが、甲斐 源氏の本流たる武この麗しき御方こそが、甲斐源氏の本流たる武田家の第この麗しき御方こそ[...]', src\libcore\str\mod.rs:2179

The suffix array table has the same length as the text in bytes. The invariant check in from_parts, however, checks that the suffix array size is the same as the number of characters. This invariant holds when a string only contains ASCII characters, but it fails otherwise.

Modify the check to use the length of the string in bytes.

• Added 2 examples and an examples/ directory
• updated the example found in the readme so it compiles
• added a step to the github actions ci. examples/basic will run as a confirmation that the readme example works