bisect - the first character can not be found

[hynekcer]

I'm trying why the output of LCP is so complicated - and I found a bug in bisect:

>>> sequence = 'abc'
>>> sa = pysais.sais(sequence)
>>> lcp, lcp_lm, lcp_mr = pysais.lcp(sequence, sa)
>>> pysais.bisect(sequence, 'c', sa, lcp_lm, lcp_mr)
(2, True)   # OK
>>> pysais.bisect(sequence, 'b', sa, lcp_lm, lcp_mr)
(1, True)   # OK
>>> pysais.bisect(sequence, 'a', sa, lcp_lm, lcp_mr)
(1, True)   # BUG

[AlexeyG]

Hi,

I think a couple of things need to be changed in our example:

1. You need to add a terminal symbol at the end of sequence first (i.e. '$').
2. You should look up the indices returned by bisect in the SA.

In [1]: sequence = 'abc$'

In [3]: import pysais

In [4]: sa = pysais.sais(sequence)

In [5]: lcp, lcp_lm, lcp_mr = pysais.lcp(sequence, sa)

In [6]: pysais.bisect(sequence, 'c', sa, lcp_lm, lcp_mr)
Out[6]: (3, True)

In [7]: pysais.bisect(sequence, 'b', sa, lcp_lm, lcp_mr)
Out[7]: (2, True)

In [8]: pysais.bisect(sequence, 'a', sa, lcp_lm, lcp_mr)
Out[8]: (1, True)

In [9]: sa
Out[9]: array([3, 0, 1, 2], dtype=int32)

[hynekcer]

Yes, I looked in SA and I found 'c', 'b', 'b',

The terminal symbol '$' is problematic. Searched strings that start with ' ', '!', '"' (double quote), '#' can not be with it. An acceptable terminal symbol is '\0'. The terminal symbol is usually used only in the theory to be easier to explain anything as an additional symbol that is outside the character set Ʃ(sequence), less than all other characters. It is usually treated by the algorithm (e.g. sais) by other means and everything works without adding it into the input. Imagine a compression algorithm for binary data with this requirement, or consequences for DNA analysis with 5 character alphabet instead of 4. But I understand, you wan't to fix it and I don't ask it.

[AlexeyG]

Regarding using specifically '$' as a terminal symbol - it's not specified in the implementation that this particular symbol should be used. You cal also go along with '\0'.

I don't have any problems that require me to count every byte. So there's no reason for me personally to optimise memory usage and cut off the additional bit that would be used for storing the terminal symbol. So I won't get to doing this very soon I'm afraid, if at all.