Video 3-7: Exhaustive Tabulation

0:01 Uh let me comment on the name of this technique. Uh I've abandoned the for Russians technique as as a name because it's a terrible othering term. Uh it was uh I mean there's a um an original paper in Russian um by these four authors Arlatarov Dinitz Grrod and Parachev um probably butchering the pronunciation. They all worked in Moscow in different institutions at the time. So clearly they were all Soviet nationality at the time. Uh Kronrod never lived to uh see the uh what we today call Russia again. So who knows if it's appropriate to call him Russian. Haha. Uh Diniti im immigrated to Israel and now is has Israeli citizenship as far as I know. So it's at least borderline today. And I mean it's uh it's just not a great term. I spell it. It very much sounds like Iron Curtain. It's in widespread use, so you should know what it what is meant by the name, but I will use something that's much more telling because exhaustive calculation is what this really is about. And um we could do it the same kind of disfavor in forgetting who invented it as we do for other computer sciency techniques.

1:18 um where the advantage is that we give it a name that tells us what it is, not who might have invented it. The joke in math is things are always named by someone who invented it the second time or so. So even giving giving credit is nice, but giving credit inappropriately or incorrectly is maybe less less nice than just calling it by some name that's reflects the content. Anyways, uh so here in kind of a bit more cleaner write up um the same application which is I should say is not exactly what they initially thought about. It's not the way they framed the technique. Uh indeed they get a slightly better speed up at the time but the way I'm presenting it here generalizes to other problems. So I think this is closer to the essence of what we now today see as the exhaustive tabulation technique. even though it's not historically how they first thought about it. Um I don't know maybe in hindsight you appreciate this more. I can maybe sketch at the end what they originally did. Uh I want to also use this name here because we'll we'll reuse that where again think of um multiplying matrices that their boolean is not even so important. They could also have values from another very small universe. The the point is it has to be small discrete universe, not some uh uh unbounded or even real numbers. Something like this has to be small discrete and there's some way to to define what multiplication and addition do. And we're not very fuzzy about the details of what these operations are. In particular, you can do it for min plus multiplication as well as for the more standard boolean multiplication.

3:07 Okay. Uh long story short, you divide all the matrices into L by L square submicro matrices. Then clearly all the matrices consist of that many microme matrices and over L^2. And uh each entry in the result you get from summing up n over little products. That's what what we had last time as well. The number of possible different uh pairs of micromatrices really is is this number. You have two entries for each of the L squared cells in the micro matrix and you have two of these. So you take the product that feels like a lot but it's not a lot if L is sufficiently small. That'll be the point in particular if you use square root login with an appropriate factor. one one quarter is enough, then you get precisely the uh square root n different combinations of pairs of micro micro matrices. And since that is not so much compared to the input size, you can uh afford to compute all of those that could possibly arrive whether or not they occur in your matrix. And we can do this for whatever operation is convenient. Here we really don't care and we'll just have separate tables for multiplication and for addition, right?

4:26 it's uh completely oblivious to this um definition of of the matrix multiplication. Uh then if you look at um so how we u um arrange this this table of results um also you have flexibility but one option is you just list all the entries of the two matrices one after the other and you treat the entire bit string of all the entries as one giant or maybe not so giant binary number and because it's a number you can use it as an index in an array and so with a single memory access. You can read off the result of these uh micromeatrix uh operations if well after the premputation and the pre-processing um you can also work out like uh depending how how expensive the pre-processing is um maybe it's at most at most cubic and then the size the L cubed works out to log to the two three halves and you have so many of these. Okay.

5:37 Now the total time to compute one entry in the result is summing up n / l of these micromatrix products. Right? You can do the summing up in constant time each because we premputed the sums as well just because we could. And so the total time um is n / l for each output cell. n / l^2 output cells makes n / l cubed in total. And so you get this the total time n cubed / log to the three halves.

6:22 And the original um variant of uh of the four Russian authors or not of Soviet authors uh they divided the two matrices into very thin or wide strip very thin or tall strips instead of little squares. And then you can work out that there's uh you're essentially decomposing the the result matrix into a sum of of low rank matrices. and you can compute all possible low- rank matrices the way you need them in in a an efficient way. So you're using the same trick that there's only a certain number of possible ways that you have to compute these and you can just brute force those. Um that has the benefit you only have one L in this formula. So you can make L substantially bigger square of what we had and so you get a slightly better speed up in the end. They can't do the summing. they have to do uh trivially. So they don't get the third power of L here but they have a larger L. And so here this works out as the better result. The way I present it here is not to convince you how to do matrix multiplication but to teach the technique that we'll apply to our string alignments and there it's a bit easier if you work with these squares.

7:40 How can we apply this to edit distance? um we have as output a matrix. So clearly there's some superficial similarity and we can divide the output matrix or L in in some submatrices micromatrices L * L the way the alignment matrix or the dynamic programming matrix is set up these correspond to two substrings of the strings that we align. And now um you have to study a bit deeper what the problem is about. Um and here I I took the figure from from Dan Gusfield's book where this is also explained in in more detail than I'll I'll talk about if uh if you want to read it up. There's different parts in the matrix. There's the top left corner which plays somewhat special role. Then there's this first row and first column. And of course there's the string um the substring that corresponds to this cell. And the claim is that you can compute all the values in F which if L is not very tiny here L is four. So it's a small example. But if L is a little bit bigger than that, F is the the majority of the matrix. It's the big big part of the matrix. And you can compute all the values in F just from these ABCDE E.

8:59 Why is that useful? Well, we can again apply exhaustive tabulation to all those entries. Um A B C uh these are not too many numbers roughly L numbers two L numbers and then there's uh some letters from the strings. If we make L sufficiently small there shouldn't be too many possibilities how these can look like.

9:23 And so uh you could premp compute filling much of the matrix in the same way we've done this for boolean matrix multiplication. Uh there's a few catches though in that if you think about the typical edit distance matrix, it tends to start with zeros and then the numbers progressively become bigger and at the end in the bottom right corner you have the final edit distance of the strings which might be up to n. Right? We hope that it's a bit smaller otherwise the alignment is useless but it might be large numbers. It's certainly not just zero ones. It's certainly not just a bounded range. grows with the input size in any any ways in the worst case it does. So this doesn't seem to work. Uh how can we apply this exhaustive tabulation here?

10:13 And the trick is uh the numbers do grow but in a way they grow in a very predictable fashion and they can't grow by all that much. They don't jump. Uh you usually do an increment by one. Maybe you leave something the same but that's about it. So in a way we want to use a difference encoding and then things are back to uh a nicer small range. In the recursion you never decrement a value but you do the minimum from different places. So if you carefully study this um if you look at a certain cell and its neighbors so here here's J then you might go to the next row or column and also the diagonal one. So these are the differences that we look at. Uh each of these cells takes that upper left one as one of its minimum possibilities as one of its entries in the minimum of three. And so clearly these cells uh will not be much bigger than the top the top left cell.

11:24 That's the uh the trivial part. Um they cannot the difference cannot be more than one. But it can also be minus one in uh cases where the minimum comes from the outside of this little figure. So if if this cell takes its minimum from above or from here, then you can work out that it might end up being one smaller than the left neighbor.

11:54 Uh basically if if you have some value x here what's the worst it can happen this can be the same for edit distance this could be x + one right then you have your distance one uh that's one case and you have to study the others uh in principle you could go up and down uh could go up for a long time and then at some point you branch off but you can show you never differ by more than this uh plus - one. [snorts] So if we apply uh conceptually the operation to the differences not the matrix entries in absolute terms then we can still use this exhaustive tabulation.

12:40 Uh one way to do it um that is again uh optimizing a few things a little bit further um is that you leave out this topmost top leftmost cell essentially give that an offset of zero and now each of the cells here these are input cells that you have to specify. Same with this. Let me maybe mark this.

13:07 These are cells that are input to the micro operation. Uh and these are outputs for the micro operation. Each of these cells you have to read as uh a difference to the left neighbor. Right? Uh this this cell could be substantially bigger than the left top corner. But if you want to know its value, you have to add one, subtract one, do nothing, add one. So it's one bigger in this case.

13:39 Okay. Um these you fill essentially from from the recurrence that comes uh recursively back to [clears throat] you. And now the micro operation has to fill the the light green part. And that is all determined from the numbers that you have. and maybe uh maybe the string as well. Although you can also like in this um more recent paper they they tried to get the dependence on the string uh minimal.

14:15 The number of different micro matrices um if you include the string in the simple version is uh two strings of length L each. So if you have sigma characters that's sigma the two l different possibilities of things that you could have written uh on top of the matrix and the entries in the top and left um first first row first column that can be one of three things each plus one one minus one plus one 0 to minus one and we have 2 l minus one of those. So here if we want again the number of different uh micro matrices that we have to do the exhaustive tapulation for to be reasonably small say root n uh we have to pick a a fairly small L in particular the log here is involving the alphabet size. So even if we set sigma to four that's already taking log base base 12.

15:14 So if you think about that's essentially the length of decimal number, right? So uh uh you want to be in the millions before this makes any sense. Uh so in practical speed up terms, you have to work on this more and people have tried to reduce the size here a bit more. Uh but in theory like if you look just at the asmtoic scale up and pretend that sigma is a small constant um it helps a bit. So in in particular you can choose L to be essentially a logarithmic. You have N / L^2 microme matrices to fill. By the way in each case you're you're never filling these middle these middle values in the recursion at least not until you have to. And you can work your way around to never do it. Um filling the table this way gives you the bottom right corner which is the answer the final edit distance. And for the back trace uh you can also involve micro matrix operations um if you want to.

16:21 Okay. Uh and uh the only thing you fill is this this grid of uh this sparse grid of rows and columns which gives you enough information for the next cell to feed into.

16:36 Uh so overall time under these uh assumptions um are proved a good bit. You essentially get the the two logarithmic factors speed up um one from filling fewer numbers. The number of things you fill in the cell goes down by this logarithmic factor. And you're also speeding up the computation in the micro matrices by doing table lookup. it becomes constant time would used to be uh size or linear in the in the size of the submatrix.

17:18 Okay, so that's the positive part. Now I said um I started this this section asking can we do better? Is there something inherently quadratic about edit distance? And it seems so. Uh this is all fairly um recent developments compared to other parts of of complexity theory. This is from an area called conditional lower bounds or fine grain complexity theory where you try to use uh np hardness like reductions to prove lower bounds for polomial time algorithms. Uh and in this case um the result you can prove is that any any edit distance algorithm for two strings of length n that would take uh a strictly so for well n^ the 2 minus delta uh time but delta has to be a constant. So our logarithmic scala speed up does not qualify for this. If you had such an algorithm, you would refute the strong exponential time hypothesis which is listed down below. I'll I'll briefly comment on it. Uh but for for this module, I guess you can pretend it's a somewhat widely believed complexity theoretic assumption. So we don't have strong uh evidence in either direction if you're very strict. But a lot of people are uh building things on top of uh Seth the strong exponential time hypothesis and nobody has refuted it. So um it seems reasonable to assume that this stronger uh running time for edit distance is not possible.

18:57 Uh so people often call this strictly sub quadratic or um sorry was there a better term uh truly subquadratic something like this uh is not very well defined but um what we mean is the exponent should be strictly less than two. Uh the exponential time hypothesis is something that popped up in advanced algorithms. um where it says uh I can essentially not solve three in subexponential time but I might be able to squeeze the exponent or the basis of the exponent to some smaller constant than two who knows you should compare this to the easy brute force algorithm for three sets where you just guess an assignment and that's there are two to the n assignments or two to the k for the number of variables So that's easily doable. The exponential time hypothesis says maybe you can lower the exponential growth by some constant factor, but you need exponential. And this is I think very widely believed. It's it's stronger than assuming P not equals NP, but still um there's good support for this in terms of the number of people that speak up for it, whatever that says. uh the strong exponential time hypothesis makes this assumption a bit more quantitative and a bit more strict or a bit more strong hence the name. Uh here you look at the generalization of threes set where the literals have k literal sorry the clauses have k literal each not just three as in three set and then it says uh whenever you pick some epsilon by which you want to improve the exponential basis then there is a a size for the literals where you'll fail where uh the kat problem needs at least um well the this the stated bound uh you can't reduce the exponential basis um arbitrarily much if you're willing to look into larger and larger clauses and so that's that's the thing that uh this statement here is based on again all the algorithms we know uh respect this so we have no reason to believe it's false so in a way uh we have a lower bound that says we can't reduce the exponent strictly by anything that is constant and we have an upper bound that says yeah we can shave off logarithmic factors and for a whole class of problems that's the kind of state-of-the-art unlikely that we'll see uh subcontratic algorithms in the strict sense uh that's maybe worth mentioning that this this reduction even works if the alphabet is constant. So it it falls in this range where we do get this logarithmic speed up from the exhaustive tabulation technique.