sais breaks if string starts with \0

[faassen]

I noticed that if you try to build a sais (and thus fmindex) with a string that starts with \0 things break. I figured a way around this in my code, but I wanted to leave this report here.

[faassen]

It would be nice to support this as it would let me write efficient starts with, ends with and equals searches. That is, if I want to look for the text "foo", "\0foo" would look for starts with, "foo\0" would look for ends with, and "\0foo\0" would look for exact identity. If the whole text cannot start with \0, then the starts with and equals searches cannot be implemented this way, as there would be no preceding \0.

[ajalab]

I noticed that if you try to build a sais (and thus fmindex) with a string that starts with \0 things break.

I believe the recent update #56 resolved this issue.

fm-index/src/suffix_array/sais.rs

Lines 445 to 451 in 43546c1

	#[test]
	fn test_sais_starting_with_zero() {
	let text = b"\0\0mm\0\0ii\0s\0\0\0sii\0ssii\0ppii\0".to_vec();
	let sa = build_suffix_array(&text, &RangeConverter::new(b'a', b'z'));
	let expected = build_expected_suffix_array(text);
	assert_eq!(sa, expected);
	}

[ajalab]

That is, if I want to look for the text "foo", "\0foo" would look for starts with, "foo\0" would look for ends with, and "\0foo\0" would look for exact identity.

Noted this. I'll consider adding test cases for the upcoming multi-text FM-index with such input patterns.

[faassen]

I came up with this "add \0 to the front of the string and look for matches" method because I had trouble comprehending the following in the "Fast XPath" paper, but perhaps you can now:

starts-with(P, [x, y]): The goal is to find texts in range [x, y] prefixed by the given pattern P . After the normal backward search, the range [sp, ep] in T bwtcontains the end markers of all the texts prefixed by P. Now [sp, e] x [x, y] can be mapped to Doc, and existential and counting queries can be answered in O(log | Alphabet | + log d) time. Matching text identifiers can be reported in O(log d) time per identifier. If [x, y] is [1, d] and Doc is an array, the counting time after the backward search is O(log |Alphabet|), and each text identifier can be reported in constant time.