Video 9-5: §9.5 Exhaustive tabulation

0:00 Introduction

0:03 in the next section we'll put all of this together um and it will it will both be required in a way using this um this new technique that you haven't seen so that's that's another tiny little uh gem maybe that you enjoy the exhaustive tabulation technique is sometimes called the four Russians trick and you find this in the literature many times it's a terrible name for one it's super derogatory also I think um is only for two I'm sure they're Russian but the others it was just the Soviet Union at the time and um authors in the US didn't care too much so just as a kind of you need to recognize the term for Russian strict because it's in wide use I don't think it's a good name so exhaustive tabulation is a much more telling name that's pretty much what what it is about uh but yeah um it may be maybe reasonable to attribute the the four authors that first invented this technique

1:15 foreign but what is it really about um we'll first use a trick we've seen before we we have a solution for the range for the arrangement problem with n log n pre-processing time and space but constant query time which is close but not quite what we want but as I said earlier if we just reduce the input a slight bit by a log n Factor then M log M turns into o of n just by the cancellation of this log term but how can we make use of that one way to do that here is to break the array into regular sized blocks of roughly log n elements each but what's on this slide this this curious factor of one quarter doesn't matter but it will matter later so let's keep that in mind but I'll just um uh stick for this slide with roughly login numbers in each block and then instead of remembering all the elements we'll just keep the smallest of each block in this blue array and I think my drawing is roughly to scale so it's this login factors doesn't sound like such a much such a lot but it's reducing it quite a bit uh so you keep just the uh the Minima of of each block and on on this much smaller array we can

2:41 use our n log n solution from before the sparse tables so in a way we can we can solve rmq queries on Block Level if you just care about queries that contain entire blocks so a query like from here to here you can basically solve that with just looking at the blue thing because the answer will be one of the blue block Minima but of course that's not all we can have queries that straddle blocks or cut a block in half or what between two arbitrary positions so that's that's not good enough uh but it's at least a partial solution

3:31 in the general case we can at least decompose a query into different parts now so a general query from either J may look like the the red one here and then there's um a green part which is the remainder of one block that still is in the query part but it's not an entire block and you can have the same thing at the end a prefix of a block and then there may be a middle part that spans entire blocks

4:09 and for the middle part we can use the trick from the previous slide we just store the the Minima of each block um and I lied a little bit on the previous slide we store two arrays because we need the Minima and we need where in the block is that minimum we need both pieces of information to solve the puzzle but it's just a factor of two in the space if you want so here uh this B array stores the the relative index within the block of the minimum so this is one because this is at position one this is four because it's at position 0 1 2 3 4 and so on okay

4:56 so with that we can we can decompose Arrangement query into different parts and again we're using the same trick all over uh as as we did before the minimum in the red range it has to come from somewhere it can be in the blue part or it can be in the left or right green part and we still have to figure out which of the three it is uh but we can reduce the candidates to these three options so this this set K is a set of positions where could the minimum be and we can nail it down to one of three positions so this is this is constant time to evaluate and what are the positions well uh the position one the first green one is wherever is the minimum in this green range and we don't know how to do that yet but at least it's local to one block it's just a tiny range and the second Green Block is symmetric it's the minimum in this prefix of a block we don't exactly know how to do that but we'll come to it and it's local to one and the middle part is using the sparse table referring to the previous slide because these are covering entire blocks the minimum must come from one block

6:10 minimum and so well formally written we're using rmq on M to copied values of the Minima but we also need to access the array B to know at which position is the minimum

6:29 so far so good so if you if you understand this slide you you get most of the uh the key idea from this the rest is a bit uh technicalities to get it to work and the formulas are a bit in a nuisance but the picture I think um conveys the idea without much of the the nasty detail

6:59 so we have only three values to check uh two are from intra block queries local to one block and one inter block queries and for the second one the blue one we already know how to solve it see the previous slide

7:13 Minima

7:16 we just use sparse tables so the only thing we have to still worry about is how to find range Minima if they're in a tiny range within one of these blocks uh so that's the the green bits and we would like to do this with linear space and pre-processing time over all the blocks because otherwise we don't get our our ultimate solution a linear pre-processing time in space and constant query time so we have to somehow do this pre-processing of of all these blocks so the number of blocks is denoted by m as before and that's n divided this this small B and that was essentially undivided login blocks

8:06 the trick why this is at all possible is that each of these blocks is really short namely roughly so many numbers if we build a Cartesian tree for each of the little blocks there's only so many ways that this Cartesian tree can look like just because we reduced it to such a tiny range that all the all the different options uh condense to one out of the Cartesian trees or B elements and we know there is at most two to the two B such Cartesian trees that's where we used our little tricky tree encoding for so each of these Cartesian trees can be encoded with two times B bits and that's if you just work out the math is a half log n now why is that why is that helpful the reason is that if you take 2 to the power of one half log n that's just square root of n and that's not a big number so you can afford to uh just store all possible shapes of Cartesian trees for these tiny blocks and I have one big one big table where you write down all solutions so in a way we're doing the pre-compute all solutions for each of the possible ways that the blocks could look like and the trick rather than the the magic

9:35 that makes this work is there's square root and different types of blocks how they can look like locally but many more blocks so we will have um a lot of blocks that look exactly the same through the range Min lens many equivalent blocks

9:57 and that's where the exhaustive tabulation technique comes in it consists of these three steps we uh replace each local block so the little block of numbers by the code for its Cartesian tree so by two B bits each

10:18 then we have a table separate from that that lists all possible Cartesian trees and all the arrangement queries in these Cartesian trees we can afford to be be generous there because there's only root n of them it's a lower order term

10:36 and then we use the type of a block as the index in a large lookup table and for that let me let me show you this um this example before we come to this so the the way you should think about this large lookup table is the following for each Cartesian tree shape say uh B is four to have small examples uh what kind of card what can a binary tree over four nodes look like it could be like this or it could be the other way around that's sorted lists but of course there's many other options uh

10:41 Example

11:24 let me pick a less degenerate one oh come on so I have one row in this table for each shape of the Cartesian tree and each position I and each position J

11:46 for example one entry here could be well this tree and these two indices that's these two nodes the range minimum is the lowest common ancestors one so I would have this entry but I would have another one with the same tree and the whole range would also be a one and another one zero one and that would be again the one well because that's the root so you can imagine how this looks like for every possible tree shape and every combination of I and J you have a row but because the number of possible tree shapes is small enough we can do that

12:31 foreign what we also need is for each of the each of the blocks that our array has we compute the little 2B bit representation of its Cartesian tree and so instead of storing this tree here what we really store is encoding

12:54 0 0 zero one zero zero in this case you could check that and so you you will arrange this table so that these codes are in order so this is this is really the index in the table if you know the tree encoding you can jump to the right position in the table with the look with just looking up the position in an array

13:26 here's the math of how big the table is we have square root and block types we have B squared combinations for I and J so that's square root and log squared and rows but that's much much less than n and we can compute them quickly so the overall pre-processing time for the table is still linear

13:47 Summary

13:51 if you put out all of that together we get our our linear pre-processing time constant query time solution so again this was all about solving the little green parts for which we you would use the query for the green part would look up the code for this little block use that as an index into the the rows table and then use the positions I and J to look up what the arrangement in that little block is

14:24 all right that gives us by what many slides ago was stated we have a solution for arrangement we get the same with a plus or order n on the pre-processing but that vanishes here so we get the same time for for lce lowest common and longest common extensions in strings and that was the the black box from unit 6.

14:53 the the pre-processing and query time in this case are best possible yeah you can at least in this combination you can't get faster queries than uh than this and if you want something with fast queries you need to read the array at least once it's admittedly more complicated than some other things we've seen but it's still it's still a somewhat practical solution you can implement this with um with these lookup tables if you choose the parameters right it can work fast in practice

15:28 and I want to point out that this is also closer to actual research so the solution I presented is also from this millennium it's not not so long ago that people thought about this um and you can think about how to further reduce the space you use and you can even play the game a little differently our solution still needed the array at query time to compare a few things we could narrow down the minimum to three candidates but we still had to do uh comparisons to find out which is the actual minimum but you can avoid that if you go to the Cartesian tree right away so then you can you can do uh you can give me the array for pre-processing time and then take it away from me you don't need it at career time anymore