Video 6-6: §6.5 Suffix arrays (part 1)

0:04 in the next section I want to introduce suffix arrays which will be a way to work around this this massive space usage of suffix trees the large constant in the linear linear term

0:19 and to moderate that let's start with the suffix tree so here again uh tilted to the right or tilde 2 well tilted on the side and I wrote it so that for every node the child edges are sorted sorted alphabetically we assume that the end of word marker is smaller than all the real characters and then comes a before B before n and at the other nodes as well B before n and so on and so forth if you do that for every node you notice that the leaves give you the suffixes of that string in sorted order just by the construction of the tree that has to be that way if we sort by alphabetic order the children in each node so one could assume one could say well if this tree with all its pointers and so on is uh too heavy to store maybe we can forget about the tree and just store this sorted list of suffixes

1:25 and I want to point out that maybe some things are lost uh some things will be lost but I will come back to that while some things are lost not everything's lost you can still do string matching or the string indexing problem so you're given the text you compute this now I give you a pattern can you ask can you tell me whether it occurs in the text and where the answer is yes because you can you have a sorted list of things and you try to find something else in that sorted list not exactly but you try to find if that is a prefix of one of these strings so you can do something like a binary search let's let's do this on this example just to illustrate that point we start so we have Anna okay I'll probably have to write indices so I don't make mistakes

2:24 elements initially binary search starts by jumping to the middle let's take a middle round it down is this one so we compare with Anna and um let's say we use the normal order in in dictionaries where a word that ends before another one comes earlier in the alphabet so we say Anna is smaller than a Nana Ben

3:04 this direction now we have these and again we pick the middle uh say this one this time it's bigger so we move down and then another comparison here we would find Anna is smaller so if we wanted to insert Anna in this sorted list of strings it should go into this Gap right that's binary search so what have we won from this we know if there's a string that starts with Anna it has to come right after this position and so we go one step down and check if this string starts with Anna or not in this case it does which means we have found an occurrence of our pattern

4:04 okay we can also find all occurrences of the pattern if we do a second search where whenever we find a word that has Anna and then something else we say that is smaller so we start here again but this time there is Anna so we go down and then well whatever we will probably take this one and decide Anna comes earlier and then this one and it comes earlier so the blue one gives us this one that's the position where you have to insert Anna if we put shorter strings after all the ones that have this as a prefix so again you could take one step up and find okay there's there's n i again in this small example there's really just these two in general this will be a whole range and it will be all the occurrences of Anna in the whole string in the text so with two binary searches you find not just one occurrence or the fact that there is none you actually find all occurrences in a neat compact representation all the indices listed there

5:26 that's the part that we can still do now we don't really want to store a list of strings as in the suffix or a tree that would be space inefficient but the same solution as in the suffix tree is we just store the starting index of a suffix instead of the string and we keep the text around separately and this is it so this list of starting indices of the suffixes so that the suffixes are in sorted order that's called the suffix array so this Beast here foreign

6:02 ly defined again what that should mean so the RF element in the suffix array L of R is the starting index of the earth smallest suffix in lexicographic order and I have to again pay attention that we start at zero and so on

6:22 if you um if you work out what the binary search costs then we need login Plus at most 2 for the binary search but each of the comparison costs us M character comparisons if that's the length of the pattern because we have to do a string comparison in each point so the number of symbol comparisons is a bit more expensive that's how we compare all the time string matching algorithms and so on so that's the fair measure so it's it's not quite as good as suffix trees where we had only the M part there was no dependence on n in tries remember at least assuming that we can go from one node to a child in constant time so suffix suffix arrays are a bit slower they have this login factor in here but log n is fairly small I mean n is an exponential reduction in the time compared to a linear scan that's often good enough even if n is in the billions log n is just 30. right