1 00:00:00,012 --> 00:00:05,388 So the analysis of trie parameters is one of the most challenging in, in the 2 00:00:05,388 --> 00:00:10,456 analysis of, of algorithms and quite interesting to contemplate. 3 00:00:10,456 --> 00:00:13,596 So that's what we're going to look at next. 4 00:00:13,596 --> 00:00:19,163 So again, it's the basis of understanding performance in lots of large scale and 5 00:00:19,163 --> 00:00:24,436 important applications that are part of our infrastructure right now. 6 00:00:24,436 --> 00:00:28,743 So one of the big questions is how much space does a trie take? 7 00:00:28,744 --> 00:00:31,941 Also, numbers of total numbers of external nodes. 8 00:00:31,941 --> 00:00:36,572 And then, if you have the number of strings you're representing, then you 9 00:00:36,572 --> 00:00:41,752 figure out the number of extra nodes, the number of void nodes, that's really the 10 00:00:41,752 --> 00:00:47,297 extra space that, that you're using. What about the expected search cost? 11 00:00:47,297 --> 00:00:51,421 Well, like with BSTs , that's the external path length. 12 00:00:51,421 --> 00:00:56,884 That's the distance from the root to all the external nodes average distance. 13 00:00:56,885 --> 00:01:02,222 So external path length, average external path length of this trial is 3.92. 14 00:01:02,222 --> 00:01:06,568 That's the search cost. Now, you notice that even if half your 15 00:01:06,568 --> 00:01:12,093 nodes are void, that's only going to add half to this extra cost, so that's part of 16 00:01:12,093 --> 00:01:17,958 the reason that our tries are effective. You can have plenty of void nodes, it's 17 00:01:17,958 --> 00:01:21,529 not going to effect the search cost all that much. 18 00:01:21,529 --> 00:01:27,529 And then, in a leader election, that's the length of the rightmost path as I talked 19 00:01:27,529 --> 00:01:31,678 about before. It turns out we can analyze all of these. 20 00:01:31,678 --> 00:01:37,274 I'm going to talk about external path link and the others will be exercises. 21 00:01:37,274 --> 00:01:43,076 And again, the easiest model, the usual model is to think of the trie as built 22 00:01:43,076 --> 00:01:46,951 from inserting n infinite random bit string. 23 00:01:46,951 --> 00:01:52,822 Eventually, they're going to differ and that's where the differ, that's where 24 00:01:52,822 --> 00:01:58,772 you're going to get a nonvoid node, node, that might represent an infinite tail, but 25 00:01:58,772 --> 00:02:02,914 we don't care. The bit strings distinguish themselves, 26 00:02:02,914 --> 00:02:08,957 eventually the trie represents them, according to distinguishing them on the 27 00:02:08,958 --> 00:02:13,730 leading bits. And from an analysis standpoint it's makes 28 00:02:13,730 --> 00:02:20,724 for a reasonable model. because, we can assume that every time, every node that 29 00:02:20,724 --> 00:02:26,770 will randomly go to the left or to the right and this model fits real data 30 00:02:26,771 --> 00:02:33,937 perfectly well when it's been studied. So the starting point if you think back to 31 00:02:33,937 --> 00:02:39,361 the analysis that we did for binary research trees, it's very similar. 32 00:02:39,361 --> 00:02:45,676 It's just that so that is we have a trie of size n. 33 00:02:45,676 --> 00:02:51,412 There, there's k on the left and n minus k on the right for some value of k. 34 00:02:51,413 --> 00:02:58,334 The difference is that two differences. One is what's the probability that there's 35 00:02:58,334 --> 00:03:03,787 k nodes on the left which in the case of binary search trees was just 1 over n. 36 00:03:03,788 --> 00:03:09,498 And the other difference is that you might have no nodes on the left and n nodes on 37 00:03:09,498 --> 00:03:12,879 the right. So that's a technical thing. 38 00:03:12,879 --> 00:03:17,955 That definitely comes directly from the definition of drive, but it makes the 39 00:03:17,955 --> 00:03:24,246 recurrence just a bit, tiny bit trickier. So that's a recurrence down at the bottom. 40 00:03:24,246 --> 00:03:30,361 What's the probability that, that when you've end strings, end random strings, 41 00:03:30,361 --> 00:03:34,408 what's the probability that the k will start with a 0 bit. 42 00:03:34,409 --> 00:03:38,045 This is just 1 over 2 to the n times n choose k. 43 00:03:38,046 --> 00:03:44,980 So and the external path length of a trie if, if you look at the root, that adds N 44 00:03:44,980 --> 00:03:49,751 to the external path length because there's n nodes down below it. 45 00:03:49,751 --> 00:03:54,877 And then 1 over 2 to the n so it's the probability that there's k on the left, 46 00:03:54,877 --> 00:03:59,458 which is n choose k to 2 to the n. And then, its external path length c sub 47 00:03:59,458 --> 00:04:04,121 k, external path length n minus k, with the appropriate starting conditions. 48 00:04:04,121 --> 00:04:08,472 Again, it's just a little tricky to realize that there's a cn on the 49 00:04:08,472 --> 00:04:13,813 right-hand side when k equals 0. So for BST, the probability that the k on 50 00:04:13,813 --> 00:04:18,402 the left is 1 over n. We looked at random Catalan trees where 51 00:04:18,402 --> 00:04:25,675 that's probabilities as a Catalan number and we have the Catalan distribution. 52 00:04:25,675 --> 00:04:31,012 And for tries it's a binomial distribution, so, that's the recurrence 53 00:04:31,012 --> 00:04:36,140 and we can use that to calculate small values, or the distribution. 54 00:04:36,140 --> 00:04:42,738 But that's the one that we want to solve. And again, just by correspondence to the 55 00:04:42,738 --> 00:04:47,118 distributions that we looked at for random cattle entries. 56 00:04:47,118 --> 00:04:52,966 And for binary search trees for binary search trees, the distribution is totally 57 00:04:52,966 --> 00:04:57,173 flat are equally likely for any node to be at the root. 58 00:04:57,174 --> 00:05:03,427 For cattle entries remember we found that there were very likely to have one side or 59 00:05:03,427 --> 00:05:06,874 the other to only have a small number of nodes. 60 00:05:06,875 --> 00:05:11,152 And so the distribution was very skewed and very skinny trees. 61 00:05:11,152 --> 00:05:16,471 For AVL trees, we're trying to make them more balanced, and the distribution shows 62 00:05:16,471 --> 00:05:20,877 this amazing pattern that we haven't characterized analytically. 63 00:05:20,877 --> 00:05:26,109 And for tries, the probability that the root's K is binomial, and that's really a 64 00:05:26,109 --> 00:05:31,179 characteristic that we're looking for that's going to tell us that these things 65 00:05:31,179 --> 00:05:36,932 are going to be pretty well balanced. Because it tends to n over 2 is the most 66 00:05:36,932 --> 00:05:40,390 likely thing. And within the square root if n over 2 is 67 00:05:40,390 --> 00:05:45,304 where the divisions are mostly going to be, which means its going to be pretty 68 00:05:45,304 --> 00:05:50,641 well balanced. But let's look at that analytically. 69 00:05:50,642 --> 00:05:59,204 Now I'm not going to cover every detail in great detail, but I think you'll see how 70 00:05:59,204 --> 00:06:05,324 we go from one step to the other and you can check details. 71 00:06:05,324 --> 00:06:08,928 Offline. So this is the basic recurrence. 72 00:06:08,928 --> 00:06:13,956 We're going to use exponential generating function for this. 73 00:06:13,957 --> 00:06:20,945 And the reason is the N, N choose k allows to if you divide by this equation by N 74 00:06:20,945 --> 00:06:25,880 factorial, then you have C of N over N factorial on the left. 75 00:06:25,881 --> 00:06:33,098 Then some net of [inaudible] you get c of z using the x the exponential generating 76 00:06:33,098 --> 00:06:38,364 function. And then the n [inaudible] a part of it 77 00:06:38,364 --> 00:06:44,226 is, is a convolution of c k over k factorial and 1 over k factorial. 78 00:06:44,226 --> 00:06:50,430 In without very much calculation at all, you can verify this formula, c of z 79 00:06:50,430 --> 00:06:54,384 equals. This is by dividing by n factorial, 80 00:06:54,384 --> 00:06:59,536 summing, multiplying by z to the n, then summing both sides. 81 00:06:59,536 --> 00:07:05,038 Pretty quickly comes down to this formula. And you can also actually get this 82 00:07:05,038 --> 00:07:11,512 directly through the symbolic method with an appropriate operation having to do with 83 00:07:11,512 --> 00:07:17,149 the way trans defied So very simple formula on the generating function. 84 00:07:17,149 --> 00:07:20,932 It's a convolution of E to the Z over 2 and C to Z over 2. 85 00:07:20,932 --> 00:07:28,208 That's the generating function equation. Now, it's not, can't be characterised as 86 00:07:28,208 --> 00:07:34,352 the simplest of generating function equations that we're going to be able to 87 00:07:34,352 --> 00:07:39,733 solve explicitly. Because we have Z over 2 in the argument. 88 00:07:39,733 --> 00:07:44,014 But one way to, deal with it is just to iterate. 89 00:07:44,014 --> 00:07:50,716 So if we apply the same equation for c of z over 2, just plug in the same equation. 90 00:07:50,716 --> 00:07:57,170 Then the z, e to the z becomes z over 2 minus z, because minus z over 2 and then 2 91 00:07:57,170 --> 00:08:04,223 0 4 c to the z over 4 can iterate. And then we the argument gets smaller and 92 00:08:04,223 --> 00:08:10,591 smaller and simplify. So, that's just selecting terms. 93 00:08:10,591 --> 00:08:16,351 We still have an equation that we can iterate. 94 00:08:16,351 --> 00:08:26,608 In another step you can see the pattern is that, what we are going to wind up with is 95 00:08:26,608 --> 00:08:32,067 Z times E to the Z. In every case, and then we have the 96 00:08:32,067 --> 00:08:37,165 declining Z over 2, C3, 3Z over 4, 7Z over 8, and so forth. 97 00:08:37,165 --> 00:08:42,058 So we get a sum of terms in the form Z times E to the Z minus. 98 00:08:42,059 --> 00:08:46,341 E to the half, E and three quarters, E seven eighth C, and so forth. 99 00:08:46,341 --> 00:08:51,226 So it's not, you have to prove that this thing goes away as you go to infinity. 100 00:08:51,226 --> 00:08:55,957 But anyway that's the iteration that we get, an explicit formula for the 101 00:08:55,957 --> 00:09:00,607 generating function for the average external path link, because it's the 102 00:09:00,607 --> 00:09:06,650 average external path link in a trie. Okay, so we're looking for the coefficient 103 00:09:06,650 --> 00:09:11,422 of Z to the N in that. So well, in factorial times Z to the N in 104 00:09:11,422 --> 00:09:15,376 that. And if you go ahead and expand the, the E 105 00:09:15,376 --> 00:09:21,153 to the Z multiplied by a factorial and get the coefficient of Z to the N. 106 00:09:21,153 --> 00:09:27,725 Then we have this difference one minus one minus one over two to the J to the N minus 107 00:09:27,725 --> 00:09:33,180 one, so I'm on J. Again, that's a fairly simple formula, 108 00:09:33,180 --> 00:09:38,850 explicit formula for the average external path length in a trie. 109 00:09:38,850 --> 00:09:44,994 It still does have the infinite sum and we're going to have to work with a little 110 00:09:44,994 --> 00:09:48,386 bit. I'm working through this with elementary 111 00:09:48,386 --> 00:09:54,854 analysis just to make sure that people see ah[COUGH] The, what underlies this 112 00:09:54,854 --> 00:09:58,882 solution, and because we get to a kind of surprising result. 113 00:09:58,883 --> 00:10:03,089 And it's good to see what, what's underlying, what the structure is. 114 00:10:03,089 --> 00:10:07,913 And so that's what we're going to do. To characterize this fully, analytically, 115 00:10:07,913 --> 00:10:11,564 requires complex analytic methods that we'll talk about. 116 00:10:11,565 --> 00:10:18,676 About in part two of the course. So what we're going to see is on the next 117 00:10:18,676 --> 00:10:24,449 slide we're going to use the [unknown] x log approximation. 118 00:10:24,449 --> 00:10:31,043 This, this thing becomes like 1 over 1 minus e to the minus n over 2 j. 119 00:10:31,044 --> 00:10:35,570 And that's not a difficult calculation using X blog. 120 00:10:35,570 --> 00:10:42,168 And in the next slide, we'll show that that's pretty close to N log based two of 121 00:10:42,168 --> 00:10:45,472 N. So that's the external path link in a 122 00:10:45,472 --> 00:10:49,388 trie. So, this step is, is not difficult. 123 00:10:49,388 --> 00:10:53,094 I didn't mean to skip through it so quickly. 124 00:10:53,094 --> 00:10:57,719 But it's not difficult at all to show that with X blog. 125 00:10:57,720 --> 00:11:03,598 But now what I'm interested in is looking at this, sum on J greater than 0, 1 minus 126 00:11:03,598 --> 00:11:08,445 even minus N over 2 to the J. How we're going to characterize that, and 127 00:11:08,445 --> 00:11:12,621 that's a really interesting function to take a look at. 128 00:11:12,622 --> 00:11:17,649 What I'm going to try to do with this analysis is try to isolate the, the 129 00:11:17,649 --> 00:11:23,210 periodic terms that there's an oscillation in here and I want to try to isolate the 130 00:11:23,210 --> 00:11:26,099 part that, that. Oscillates. 131 00:11:26,100 --> 00:11:32,662 And so the way that's going to happen is we're going to take the function log base 132 00:11:32,662 --> 00:11:38,373 two events and we;re going to work the integer part of log base 2 event. 133 00:11:38,373 --> 00:11:43,499 And then the fluctuation is Every time you come to an integer is you go from one 134 00:11:43,499 --> 00:11:49,354 integer to the next There's fluctuation in the, in the function as you're working the 135 00:11:49,354 --> 00:11:53,720 real function log X, but you're only picking off the integer parts of it 136 00:11:53,720 --> 00:11:55,824 unless. So let;see how it works. 137 00:11:55,825 --> 00:12:00,130 So all we're going to do is take that infinite sum, and we're going to break it 138 00:12:00,130 --> 00:12:03,762 into two parts. The part where j is less than floor of log 139 00:12:03,762 --> 00:12:08,799 n, and the part where it's greater than or greater or equal to the floor of log n So 140 00:12:08,799 --> 00:12:12,649 that's just split the sum into two parts at that one point. 141 00:12:12,649 --> 00:12:17,240 And the key thing to notice about this is, when j bigger then log base 2 of n. 142 00:12:17,241 --> 00:12:21,325 Then 2 to the J,uh, is, going to be bigger than N. 143 00:12:21,325 --> 00:12:25,933 And so, we're going to have,uh, minus N over something huge. 144 00:12:25,933 --> 00:12:28,922 We're going to get a number very close to 1. 145 00:12:28,922 --> 00:12:33,207 It's going to go away. So and it's, when it's, j is small like 146 00:12:33,207 --> 00:12:38,663 say j is 2 or something we have e to the minus 10 which is tiny, the sum is just 1. 147 00:12:38,663 --> 00:12:43,961 So basically we're going to have log in terms they are very close to 1 and all the 148 00:12:43,961 --> 00:12:49,342 rest of them are going to very close to 0. We've just a little bit left in the 149 00:12:49,342 --> 00:12:52,171 center. So lets look at how that goes. 150 00:12:52,171 --> 00:12:56,236 So, in this case we just split off the, the log n. 151 00:12:56,236 --> 00:13:02,050 So we get floor of log n and then we have the second [inaudible] e to the minus n 152 00:13:02,050 --> 00:13:07,790 over 2 to the j. And that's just putting the first sum into 153 00:13:07,790 --> 00:13:12,434 two parts. So, and then this one is the same so no 154 00:13:12,434 --> 00:13:19,778 change there so now what we are going to do is let this j go is for negative as at 155 00:13:19,778 --> 00:13:26,918 once doesn't matter because if that j goes for negative this thing is exponentially 156 00:13:26,918 --> 00:13:30,003 small. So, it doesn't matter. 157 00:13:30,004 --> 00:13:38,510 And we're off by an exponentially small amount, so...and that's going to allow us 158 00:13:38,510 --> 00:13:45,811 to combine the two sums in that part. So, now this is not Change j to, j plus 159 00:13:45,811 --> 00:13:52,615 log n in this sum, and, same way i changed j to j minus log n, in that sum. 160 00:13:52,615 --> 00:13:58,553 And so now we have some floor to the log n's, coming in, in to these sums. 161 00:13:58,554 --> 00:14:02,555 But then, there's n over floor to the log n. 162 00:14:02,556 --> 00:14:08,941 Well that's like taking the function log N and tracking off the integer part. 163 00:14:08,941 --> 00:14:15,246 All that's left is the fractional part. So the end sum of this thing is. 164 00:14:15,246 --> 00:14:19,769 What's floor of log n? That's the integer, biggest integer less 165 00:14:19,769 --> 00:14:23,195 than log n. That's the function log n minus floor of 166 00:14:23,195 --> 00:14:26,681 log n. As n increases, this function fractional 167 00:14:26,681 --> 00:14:29,690 part of log n goes from 0 to 1 and back again. 168 00:14:29,691 --> 00:14:34,343 So it's a fractional part of log n. It's an oscillating function. 169 00:14:34,344 --> 00:14:39,960 And then but these other functions also are just functions of the fractional part 170 00:14:39,960 --> 00:14:43,277 of login. Again, again, I skipped through just a 171 00:14:43,277 --> 00:14:48,607 lil, a tiny bit of subtracting login from floor login, but you'll see that, that 172 00:14:48,607 --> 00:14:52,058 works out. So now I have these three parts that are 173 00:14:52,058 --> 00:14:56,884 all functions of the fractional part of login, that is the oscillate. 174 00:14:56,885 --> 00:15:03,364 So this is my external path length over n, and so right here this is proof that it's 175 00:15:03,364 --> 00:15:08,620 asymtotic to n log base 2 n, because the other things are all 0 to 1. 176 00:15:08,620 --> 00:15:15,086 But what's really interesting about this is if we look at these functions, so this 177 00:15:15,086 --> 00:15:20,721 is the proof I just went through. If you have that recurrence, then that 178 00:15:20,721 --> 00:15:26,498 leads to this result. And but let's look at it in just a little 179 00:15:26,498 --> 00:15:33,258 more detail these three terms. So the first one is, again, the fraction 180 00:15:33,258 --> 00:15:37,337 part of log n. And so that's just a plot of the 181 00:15:37,337 --> 00:15:43,841 fractional part of, of log n. Uh,[cough] now the second one is the sum 182 00:15:43,841 --> 00:15:49,116 of e to the minus 2 for actual [inaudible] log n minus j. 183 00:15:49,116 --> 00:15:56,745 And that one also oscillates as, as it increases in it oscillates and that's the 184 00:15:56,745 --> 00:16:02,238 approximate magnitude of it. And this is the third one that also 185 00:16:02,238 --> 00:16:06,192 oscillates. So we have these three terms that 186 00:16:06,192 --> 00:16:12,652 oscillate that we're adding together to give us the difference between log in and 187 00:16:12,652 --> 00:16:17,002 our function. And what's amazing is you add these all 188 00:16:17,002 --> 00:16:22,823 together you get a smooth oscillating curve that's very tiny in magnitude. 189 00:16:22,823 --> 00:16:28,374 Now 10 to the minus 6 in magnitude. Not something you would notice if you 190 00:16:28,374 --> 00:16:33,898 didn't do the math. In, we're going to see in part two, we'll 191 00:16:33,898 --> 00:16:41,414 look into a little bit, how to do the math, but certainly It's quite a surprise 192 00:16:41,414 --> 00:16:48,382 to see these functions that are so difficult, different in character adding 193 00:16:48,382 --> 00:16:54,272 up to this continuous function. So this is a proof that CN over N minus 194 00:16:54,272 --> 00:17:00,112 log N is this strange oscillating function that you wouldn't see unless you look out 195 00:17:00,112 --> 00:17:05,472 to six decimal places and the question is, is there a reason why a recurrence like 196 00:17:05,472 --> 00:17:11,472 that which seems such a natural, natural a recurrence involving our integer cost/g 197 00:17:11,472 --> 00:17:15,107 should have this strange periodic behavior. 198 00:17:15,108 --> 00:17:18,607 And the answer is yes. We're going to see when we get to complex 199 00:17:18,607 --> 00:17:22,216 analysis, analytic techniques into knowing transferring/g. 200 00:17:22,216 --> 00:17:26,773 That uh,there's a perfectly valid explanation for such periodicity. 201 00:17:26,774 --> 00:17:32,922 And not only that, it's bound to appear in the analysis of lots of algorithms that 202 00:17:32,922 --> 00:17:36,910 are based on properties of bit strings like tries. 203 00:17:36,910 --> 00:17:44,044 So applying that result and taking a look at the distribution that we get with tries 204 00:17:44,044 --> 00:17:51,370 you can see that it's even more Tightly bound towards a particular shape basically 205 00:17:51,370 --> 00:17:58,264 divided the center, even then have BSTs. And so just to quote the results that we 206 00:17:58,264 --> 00:18:04,202 get from this kind of analysis. The extra space is about 44% of the 207 00:18:04,202 --> 00:18:10,067 external nodes are void. The expected search cost is about N log 208 00:18:10,067 --> 00:18:15,972 based two of N. So that's a number of bits you have to 209 00:18:15,972 --> 00:18:21,955 examine. So and that's a very acceptable search 210 00:18:21,955 --> 00:18:30,826 clause and competitive. And for leader election, well, that'll be 211 00:18:30,826 --> 00:18:37,591 an exercise. That's a discussion of trie parameters.