So in this section, we are going to talk about setting up checkpoints. So let me remind you a little bit about the BWT. So the BWT matrix is formed by sorting on the cyclic rotations of the string. That is why, if you search for a pattern, and the pattern appears in the stream, that should exist a row that this pattern appears as prefix. And if the pattern appear at multiple positions in the stream, these rows should be consecutive. Like this in the picture. So, this one allow us to represent the result by using just two index. The top index and the bottom index. The next property of using BWT for searching a pattern is that, we iteratively build the patterns from the end to the start. Like this. So searching a pattern using BWT is an iterative process. In other words, it is. What we do is just updating the indexes. For example, in this case,, we start with an empty string so that the indexes can be from 0 to 13. When we start finding a, the index is one to six. When we add one more symbol to a, that is ana, the index is updated from 9 to 11. And, when we add the final a, so we are searching the for the pattern ana, so the index is three to five. Okay. So let's look at a little bit more detail. So this is the first column, the last column which is a BWT, the index, and the last to first which allow us to quickly allocate the positions of a character in the first column very quickly. So this is one iteration. So the next iteration, we are actually moving to this range of indices. Okay, so the pseudo code for the BWT matching is described as an iterative procedure, but if you believe me and try to code like this, it will take you a very long time to run. And if you analyze the code, most of the time, the program will spend his time in this region. So updating index is actually a critical point in this algorithm. It's clear that this way, we cannot update the index in a constant time. So, I have to describe another definition, so that we can come up with a faster approach. Let's define the count of a symbol for an index i and a string Text as the number of occurrences of symbol in the first i positions of the string Text. For example, the count of the symbol A with index four in this screen is equal to zero, because there's no symbol A appearing in the first one, two, three, four characters. But the count of symbol N in this string is three. So, let's look at the algorithm there again, so this is the LastColumn which is the BWT. This is the FirstColumn which is obtained by sorting the LastColumn. This is the indexes. You can see that here, we add some information over there. So for each index e, and for each symbol in the alphabet, we calculate a number. That is the count of the single i, sorry the count of the symbol at the position i using the LastColumn. So using this information, we can update the indexes. But can we find it quickly? Well, it's not clear how to find quickly in constant time. So we have to get another information, which is the FIRSTOCCURRENCE of the symbol, is the first position of the symbol in the FirstColumn. So this is the FirstColumn. The first occurrence of dollar sign is 0. The first occurrence of a is one. The first occurrence of b is seven. The first occurrence of m is eight. Okay. So using the information about the first occurrence of the symbol, and also the count matters. We can quickly update the indexes. And here, you can clearly see that the indexes can be updated in constant time. But you notice that I store too much information here. We don't have enough memory to store that much information. So, there should be a way to bypass this problem. This is the Checkpoint Arrays approach. So instead of storing all the count matrix, now we just store the rows of this matrix, the row i, if it is divisible by a constant C. So what happen if we want to calculate the count of a symbol? At the indexes where we we did not store? We can construct it by using the information that we stored and looking back at some characters. For example, we look at the position number ten. So, we see that a up here, positioned in by 11, a also up here. So, the count of a less 11, is equal to the count at index 10 plus 2. Equal to 5. Similarly, when you want to find the positions of the matching, we need to start the suffix array right. But even we don't need to store the suffix array completely. We just store it partially and reconstruct if we need to. For example, and in here at this position we don't have the suffix array stored. So we can go back to b1 and from b1 we go to a1. So at a1 is the position one here we store in the suffix array's number five. So we get information. So in summary, BWT is an approach that you can mash the button very quickly and efficiently
