Video 9-5: §9.5 Exhaustive tabulation

0:03 in the last subsection we'll put these things together and use uh this fact that there's not too many binary trees and a short encoding for those to use The Simple Solution we've seen before with n log n pre-processing time on a slightly smaller instance and then for the remaining bits we'll have to use a new technique that you haven't seen so far called exhaustive tabulation

0:31 uh just as a historic note um the technique is also known in the literature as the four Russians trick which is a terrible othering term so I'm I'm refusing to use it uh but you've seen it if you see it in the literature you should know what it's meant so it's the same thing exhaustive culation is the four Russians trick and well I mean yeah they were in the Soviet Union not even clear if they were Russian it's just a terrible name so uh but it's in widespread use so you should make be able to make the connection uh one step is we already know an N log n Solution that's The Spar tables and as I said before it's enough if we can reduce the input size by a log n Factor if we can get the number of elements down to n divided log n then the pre-processing time would be linear

1:31 overall so what we'll do is we'll use uh a blocking trick similar to some things we've done before so we take our overall array and um we use a judiciously chosen block size don't worry about the constants so much but it's roughly Logan numbers and we treat those as a block now what do we do with those blocks from each block we take the smallest element the minimum in the block BL uh and uh take that out as an an element in this array B which only contains the block Minima now if you if you look at the example here um I think it's to scale but if you imagine the array gets much much bigger then this blue part is substantially larger than one block this has roughly size n divided log n because that's the number of blocks if I have roughly log n in each block uh whereas the blocks are are fairly

2:38 small so this spe will be what we feed into our old algorithm with the N log n pre-processing time so that we'll use um here as our input of size M

2:57 um so we use The Spar tables for this one and and what that means is with just using sparse tables as a black box we can answer rmq queries on the blue part on the blue array alone in constant time and we use linear time pre-processing just because we've shrunk it just enough to be able to do that now how does this help to answer queries um in particular uh one one easy observation if I have a query that's just covering blocks entire L then I could just translate that as answering the same query down here and whatever is the answer is the overall minimum that's fine but in general uh we will not have queries that are aligned with block boundaries in general we'll have something like this a query that spans uh certain blocks entirely and then has an end point and start Point somewhere in the middle of some other blocks

4:06 well we can still do some some parts so there's some range where it's entire blocks and then there's one at most one block at the outermost ends where we we have to look inside blocks and we'll use that to decompose our Arrangement query again the overall argument is the minimum in the entire query range is one of those entries so can be what's the minimum in the blue part or it can be the minimum of that green part or the minimum of that green part that's three candidates and I can find which one is the ultimate minimum by just comparing those three that's the idea that's how we get to constant time queries uh but we still have to work out how to do the how to find the Minima in these other parts uh what's spelled out here is just the formal way to say the minimum minimum from this the minimum from this the minimum from these blue Parts uh it's it's a bit a pain because the indices need to be shifted around um so I want this to be block local whereas this is global and so uh if you read if you read it in detail it just works out to be um the overall index of the

5:30 minimum so we have only three possible values left to check if we can find the Minima in the blue and two green blocks and uh the Blue Block as I just said before is already done all we need to do is find a range minimum in this smaller array and for that we can use our previous data structure The Spar tables what's left is the intrablock queries where I'm I'm just concerned about finding the rangement in this tiny range within one block

6:11 okay we want linear pre-processing time overall and uh we have to do a pre-processing step for all the N over log n blocks so we really can't spend much time on each of them and we also want constant query time so we have quite a lot of blocks but they're all super short and in particular the number of the number of Numbers number of elements in a block is chosen so that with our encoding from before we get a small number so what does that mean um each of these little blocks for the intra block queries we only need to know the relative order within the block so all we need to know for rmq queries is this little cartisian tree within the block and such a cartisian tree with two B elements we can encode with two B bits that was what we've done in the previous section but 2 B bits here that's just one half log n because B is log n divided by four so the number of different cartisian trees of that small size is at most 2 to the 2B and that works out to be square root n so the number of blocks is is large because that's that's that number but the number of different blocks from the r rmq classes

7:38 perspective is not that large it's much much smaller square root is much smaller than n divided log n so we have many blocks that behave identical to all rmq queries we can possibly ask and so that's where this new new trick comes in instead of trying to store for each block IND individually how to solve queries we store once and for all for all possible shapes of the blocks how they solve the queries so we have something of the order of n squ different possible small problems and we just write them all down that's why it's called exhaustive tabulation I don't know if my actual problem uses all of these problem types but I don't care because it's not so many overall so I'll just write them all down

8:35 um what this looks like is one large lookup table for example we could have um this little if that was our tree so if if B was four I have four numbers in my block that's one possible cartisian tree it has an encoding of 1 one and then 0 0 0 1 1 0 0 so the block type here would be just that

9:09 encoding and you can read you can treat that as a binary number and use it as an index in an array if you if you want and then uh I can I I have the this entry a few times for all possible rmq queries for example from 0 to three that one has zero that's three the answer must be one because that's the lowest common ancestor so I have one row in this giant table that looks like this I have another row with the same block type and say from from one to three that's from for this range and the answer is also one then I have 2 three here the answer is two because that's the L higher up in the tree and so on so you you you just have one row for each possible block type and possible I and J within the block uh but this overall table is still not very large because the number of block types is square root n the number of combinations for I and J is b^ squ but that's log squared at most so the overall number of rows is still fairly moderate much much smaller than n and we can pre we can uh we can generate the table in linear time and it

10:33 uses much less than linear space so to put it all together then uh you can use that to answer the int block queries in constant Time by storing for each block its type so you can use that look up the right color the right Row in your large table and look up uh the answer for for the interrup block queries and and then with the finding the minimum of the three candidates you find the overall minimum and so that that in total gives you a linear pre-processing time and constant query time solution for the rangement query problem and um from the discussion from the beginning of today that gives you also a solution for uh longest common extensions in

11:29 strings now if you uh if you think about the problem just as it is uh you can't really improve either of those two um constant query time is of course best possible you at least need to produce the output uh and if you want constant query time someone at some point has to read the array at least once so the linear pre-processing time is also best possible uh the solution surely is a bit complicated maybe that's an under understatement I don't know uh if you've seen it a few times it appears less and less mystical but it's it's a combination of more techniques in one place than we've seen otherwise um everything I told you today kind of came together for this Final

12:18 Solution uh and there's a there's a few things that are still um that you can still improve and that's the space for the pre-processing the time will remain linear but you can you can try to improve on the space and use uh reduce the constant factor in the space that's something that I've worked on um but overall that uh that is a that is the solution for arrangement queries which closes the last black box from Unit 8 that we left open um and showed you a little bit of more Advanced Data structuring techniques especially this um bootstrapping from an exhaustive culation technique is something that often allows you to reduce the space by some logarithmic factor and so that's what's um what's used in in modern solutions for text indexing they're based on what we've done in Unit 8 plus they further compressed the size uh to handle the large data sets we