1 00:00:00,012 --> 00:00:06,452 Now we're going to look at Tries, which is a class of common material objects that 2 00:00:06,452 --> 00:00:13,306 now really hasn't only come into study in recent years due to computer applications. 3 00:00:13,306 --> 00:00:17,602 And are not found in classical comminatory, but actually are very 4 00:00:17,602 --> 00:00:21,708 interesting rich comminatorial analytic properties. 5 00:00:21,708 --> 00:00:27,048 So I'll spend some time,really, just talking about what Tries are and, and 6 00:00:27,048 --> 00:00:31,931 their applications before we talk about the analysis. 7 00:00:31,931 --> 00:00:35,968 So, one way to look at a Trie is just at, as a binary tree. 8 00:00:35,968 --> 00:00:43,095 Where the external nodes can be marked. Black ones are called void nodes and then 9 00:00:43,095 --> 00:00:48,318 the white ones are non-void. So you take a binary tree, and mark some 10 00:00:48,318 --> 00:00:53,840 of the external nodes to be void. Now there's a rule, and that is that you 11 00:00:53,840 --> 00:00:59,398 can never have two void nodes that are siblings of each other in a leaf. 12 00:00:59,398 --> 00:01:07,226 So, and assembling of a void that's not void, that's the rule so that's what a 13 00:01:07,226 --> 00:01:11,965 Trie is. Now that seems kind of arbitrary, but 14 00:01:11,965 --> 00:01:19,204 you'll see, when we look at applications how these rules play a role. 15 00:01:19,205 --> 00:01:26,146 That actually for an exercise you might give a recursive definition of what a try 16 00:01:26,146 --> 00:01:30,176 is. So the most usual way that we think of 17 00:01:30,176 --> 00:01:33,841 tries is as representing a set of bitstrings. 18 00:01:33,841 --> 00:01:39,706 Each try corresponds to a set of bitstring where each non void external node 19 00:01:39,706 --> 00:01:44,916 represents one bitstring. And the, you get the bitstring by taking 20 00:01:44,916 --> 00:01:50,254 the path from the root to a node. Taking a zero when you go left, and one 21 00:01:50,254 --> 00:01:54,687 when you go right. For example, if we go zero, zero, left, 22 00:01:54,687 --> 00:02:00,291 left, right, right, left we get down to that non-void external node. 23 00:02:00,291 --> 00:02:05,182 Then we say that, that node represents the bitstring that we got. 24 00:02:05,182 --> 00:02:10,442 That defines the path that we got there 0, 0, 1, 1, 0. 25 00:02:10,443 --> 00:02:16,043 Or over here 0,0, 1 0, I'm sorry, 1, 0, 1, 0. 26 00:02:16,044 --> 00:02:21,276 That non-void node represents the bitstring 1, 0, 1, 0. 27 00:02:21,276 --> 00:02:25,394 The path from the root to a node defines the bit-string. 28 00:02:25,394 --> 00:02:31,448 So now, eh, the, non, the void nodes, have a different interpretation that derives 29 00:02:31,448 --> 00:02:36,757 right from this definition. For example if we go right, 4 times, and 30 00:02:36,757 --> 00:02:41,734 then left, we come to a void node. What that means is that no string with 31 00:02:41,734 --> 00:02:46,199 that prefix is in the set of strings represented by this trial. 32 00:02:46,200 --> 00:02:52,672 We're trying to represent in this case 1, 2, 3, 4, 5, 6, 7 bitstrings and then the 33 00:02:52,672 --> 00:02:59,101 void nodes represent the prefixes of all the bitstrings that aren't represented. 34 00:02:59,101 --> 00:03:04,027 So that's what we think of as a Trie corresponds to a set of bitstrings, or 35 00:03:04,027 --> 00:03:07,927 another way to look at it is it's all worked out here. 36 00:03:07,928 --> 00:03:13,759 So this Trie represents as I said, 7 different bitstrings. 37 00:03:13,760 --> 00:03:19,624 And those are shown at the top. Now, on the left is the bitstrings that 38 00:03:19,624 --> 00:03:24,422 from that set that start with 0. And on the right, the try on the right 39 00:03:24,422 --> 00:03:29,306 represents the bitstrings for that set that start with the 1 with the 1 stripped 40 00:03:29,306 --> 00:03:32,261 off. And so recursively going down, that's 41 00:03:32,261 --> 00:03:37,769 another way to see the sets of bitstrings that are represented Now this only works 42 00:03:37,769 --> 00:03:43,491 for bits, sets of bitstrings said to be prefix free So that is no member of this 43 00:03:43,491 --> 00:03:49,607 bit, this set of bitstrings is a prefix or another, of another one of that set. 44 00:03:49,608 --> 00:03:54,734 We can handle that by a using void and not void internal nodes. 45 00:03:54,734 --> 00:04:01,292 But in applications, I'm going to talk about that are typical with, it's okay to 46 00:04:01,292 --> 00:04:07,021 just work with prefix free set. That's so like, for example, fixed-length 47 00:04:07,022 --> 00:04:10,346 all the bits bitstrings are the same length. 48 00:04:10,346 --> 00:04:14,546 And it's prefix free because they're all, all different. 49 00:04:14,546 --> 00:04:17,781 They're all the same length and they're different. 50 00:04:17,781 --> 00:04:24,924 You can't have one be the prefix of another and that's a typical and useful 51 00:04:24,924 --> 00:04:31,104 application of Tries There's lots of applications of tries. 52 00:04:31,104 --> 00:04:37,620 If you look in our algorithms book, you'll find Trie code for sorting, for simple 53 00:04:37,620 --> 00:04:43,275 tables with string keys, and for suffix arrays, which I'll refer to in a minute. 54 00:04:43,275 --> 00:04:48,449 But they play a role in classic data compression algorithm and Huffman's code 55 00:04:48,449 --> 00:04:53,762 and Lempel-Ziv-Welch Compression. And we'll look at the use of tries to 56 00:04:53,762 --> 00:04:59,608 understand decision-making collision resolution leader election algorithms. 57 00:04:59,609 --> 00:05:04,642 They play a very important role nowadays in network systems, in bioinformatics, 58 00:05:04,642 --> 00:05:08,207 internet search all kinds of commercial data processing. 59 00:05:08,207 --> 00:05:11,889 Very important data structure that's often overlooked. 60 00:05:11,889 --> 00:05:16,935 That's why I'm taking the time to talk about now some of these applications to 61 00:05:16,935 --> 00:05:21,671 motivate the analysis, because they're not so easy to analyze as we'll see. 62 00:05:21,671 --> 00:05:27,696 So here's the, the basic application which is for symbol tables. 63 00:05:27,696 --> 00:05:33,755 So Trie represents a set of bitstrings. So what we have is, just going from the 64 00:05:33,755 --> 00:05:39,986 definition a search algorithm for determining whether a given bitstring is 65 00:05:39,986 --> 00:05:45,771 in the set represented by the Trie. And the basic idea is if the leading bit 66 00:05:45,771 --> 00:05:50,583 of your key is 0, go to the left. If it's 1, go to the right, then use the 67 00:05:50,583 --> 00:05:55,245 remainder of the string recursively. If you get to avoid external node, It 68 00:05:55,245 --> 00:05:59,805 means that the one you're looking for is not in the set represented by the tri. 69 00:05:59,805 --> 00:06:04,355 If you get to a non void external node, and you're at the end of your bitstring, 70 00:06:04,355 --> 00:06:07,489 then you report success. You did find the key. 71 00:06:07,490 --> 00:06:12,446 So for example, let's say we're going to search for the bitstring 0011 in this 72 00:06:12,446 --> 00:06:15,040 Trie. Start with the 0, go to the left. 73 00:06:15,040 --> 00:06:19,117 Next one is a 0, go to the left. Next one is a 1, go to the right. 74 00:06:19,117 --> 00:06:23,758 Next one is a 1, go to the right. We're at the end of our string and we're 75 00:06:23,758 --> 00:06:29,074 on a, non-void external node, so that. String is in the set of its string 76 00:06:29,074 --> 00:06:32,822 represented by our Trie. Let's look for 10110. 77 00:06:32,822 --> 00:06:38,348 So start with a 1, go to the right, 0, go to the left, 1 go to the right, 1 go to 78 00:06:38,348 --> 00:06:41,759 the right. We hit a void external node, so that 79 00:06:41,759 --> 00:06:45,361 string is not in the set represented by our Trie. 80 00:06:45,361 --> 00:06:49,803 It's a very natural search algorithm. Have the Trie represent a set of 81 00:06:49,803 --> 00:06:53,039 bitstrings. Of course, everything can be represented 82 00:06:53,039 --> 00:06:56,208 as a bitstring. So this is a natural algorithm for 83 00:06:56,208 --> 00:07:02,932 anything represented in a computer. So of course we're going to want to for an 84 00:07:02,932 --> 00:07:09,136 algorithm like this want to know what's the expected search time under a 85 00:07:09,136 --> 00:07:15,463 reasonable model for of randomness. That's a type of thing that we want to 86 00:07:15,463 --> 00:07:19,380 analyze. Now what about inserting new keys, or new 87 00:07:19,380 --> 00:07:23,159 bitstrings into the set represented by the Trie? 88 00:07:23,159 --> 00:07:29,557 Well, what we'll do is we'll insert by searching until we get to a void external 89 00:07:29,557 --> 00:07:33,017 node. So if we wind up at a, a, an internal node 90 00:07:33,017 --> 00:07:39,899 or non-void external node, that means that we'll have a prefix pre-evaluation and we 91 00:07:39,899 --> 00:07:46,316 can deal with that in some way, but insert a new key, it's going to wind up at a void 92 00:07:46,316 --> 00:07:50,663 external node. So to insert 0, 1, 1, 1, 0, we go left for 93 00:07:50,663 --> 00:07:56,536 the zero, one, right for the one, and now we're at a void external node. 94 00:07:56,537 --> 00:08:01,877 And so now, what we want to do is, if for each remaining bit in our key that we want 95 00:08:01,877 --> 00:08:07,749 to insert, we want to add a new internal node and, with one void, external child 96 00:08:07,750 --> 00:08:11,335 and then the other one corresponding to our bit. 97 00:08:11,335 --> 00:08:16,485 So in this case, our next bit is 1, so we put, if the key start at 0, 1, 0, then 98 00:08:16,485 --> 00:08:20,980 it's not in the set of strings, but 0, 1, 1, that could be this one. 99 00:08:20,981 --> 00:08:25,338 And then we do it again for another one, and then the next bit is 0. 100 00:08:25,338 --> 00:08:30,453 So we put the void external mode to the right and then non-void to the left. 101 00:08:30,453 --> 00:08:34,302 So that's how we would insert 0, 1, 1, 1, 0, into this Trie. 102 00:08:34,303 --> 00:08:40,440 Now, there are variants where you just keep track of the tail in someway with 103 00:08:40,440 --> 00:08:44,278 pointers and people in those are well studied. 104 00:08:44,278 --> 00:08:50,300 And there's lots of reasons to do that sort of thing, but the simplest version 105 00:08:50,300 --> 00:08:55,793 also is very effective that's what we'll stick with right now. 106 00:08:55,793 --> 00:09:01,329 So that's it, a search algorithm and an insertion algorithm that gives the basis 107 00:09:01,329 --> 00:09:06,148 for a simple table using the Trie data structure , which is a very useful 108 00:09:06,148 --> 00:09:10,282 algorithm. And then natural question that probably 109 00:09:10,282 --> 00:09:15,053 already occurred to many of you is what about these void external nodes. 110 00:09:15,053 --> 00:09:20,352 That seems kid of a waste to have all these void external nodes there in, in the 111 00:09:20,352 --> 00:09:24,800 scape structure. And so we're going to want to analyses how 112 00:09:24,800 --> 00:09:30,356 many there are to make sure that we understand how much space a Trie takes. 113 00:09:30,357 --> 00:09:37,018 But it's a very compact data structure and that analyses is certainly interesting 114 00:09:37,018 --> 00:09:43,280 and, and relevant in practice. Okay so, here's another application of 115 00:09:43,280 --> 00:09:46,879 Tries. What we want to do is, we have a, a given 116 00:09:46,879 --> 00:09:52,931 string, s, and just for an example I'll use a genova string made up of As, Cs, Ts, 117 00:09:52,931 --> 00:09:56,474 and Gs. And these things could be huge, it could 118 00:09:56,474 --> 00:10:01,050 be billions of letters. And we want to know, is a particular 119 00:10:01,050 --> 00:10:06,308 substring in, in our string. So like for this string, is ACCTA in 120 00:10:06,308 --> 00:10:09,756 there, and the answer is yes, starting at 0. 121 00:10:09,756 --> 00:10:14,155 What about CCT? Yeah, there's plenty of places where CCT 122 00:10:14,155 --> 00:10:17,081 occur in this string. What about TGA? 123 00:10:17,082 --> 00:10:21,925 No, there's no occurrence of TGA. If we have a specific string that's huge 124 00:10:21,925 --> 00:10:27,139 and we want to be able to do substring search, there's all kinds of applications 125 00:10:27,139 --> 00:10:32,919 in genomics, where it's important to be able to do an operation like this quickly. 126 00:10:32,919 --> 00:10:37,637 So search in genomic data. And this is also useable, useful in 127 00:10:37,637 --> 00:10:42,674 internet search. When you do a Google search you not only 128 00:10:42,674 --> 00:10:48,482 get to the page that you're looking for, but you get context you get where the 129 00:10:48,482 --> 00:10:54,630 substring is in that page. And that's uses a beta structure like this 130 00:10:54,630 --> 00:11:00,209 and many other applications. So the solution method that I'll talk 131 00:11:00,209 --> 00:11:06,528 about is the so called suffix multiway Trie generalizing the Trie for this 132 00:11:06,528 --> 00:11:10,627 problem. And so the idea is to if you have, if 133 00:11:10,627 --> 00:11:17,452 you're given string, what we're going to do is work with all the suffixes of the 134 00:11:17,452 --> 00:11:22,063 string. So the original string ACCTAG, GCCT, we 135 00:11:22,063 --> 00:11:26,136 leave off the A then we have CCTA and so forth. 136 00:11:26,137 --> 00:11:32,043 So if the string is of size N, we have N strings for all the suffixes. 137 00:11:32,044 --> 00:11:37,012 And we're going to treat those as different strings and just insert them 138 00:11:37,012 --> 00:11:40,083 into the Trie, that's called a suffix Trie. 139 00:11:40,084 --> 00:11:43,314 Now notice that's prefix tree, prefix free. 140 00:11:43,314 --> 00:11:49,528 None of these is a prefix of another. Because they're, they're all different 141 00:11:49,528 --> 00:11:52,409 lengths. It's a prefix free set. 142 00:11:52,409 --> 00:11:59,111 And they all end we have them all end with a character that isn't found anywhere else 143 00:11:59,111 --> 00:12:04,607 in the try. So then the idea is that every internal 144 00:12:04,607 --> 00:12:14,263 node of this Trie corresponds to some substring of, of our original string. 145 00:12:14,263 --> 00:12:18,689 So to answer the question is X a substring of X. 146 00:12:18,689 --> 00:12:24,342 We use the characters of our query to traverse the try. 147 00:12:24,342 --> 00:12:34,076 So for example, if we're looking for A, C CTA then we can when we get to a nonvoid 148 00:12:34,076 --> 00:12:42,524 external node that tells us that one is in there, and it tells us what position it 149 00:12:42,524 --> 00:12:46,844 is. So if built the try AC if we see something 150 00:12:46,844 --> 00:12:53,972 that starts with AC then we look starting at position zero and continue our search, 151 00:12:53,972 --> 00:13:00,009 and the ACCTA is there. If we encounter a void node then so for 152 00:13:00,009 --> 00:13:05,533 example, if we're looking for CCT. Then we find a void node. 153 00:13:05,534 --> 00:13:10,286 Sorry, CCT is there because we found it in an internal node. 154 00:13:10,286 --> 00:13:19,812 But something like TGA we end up at an void node in rather So this is a very 155 00:13:19,812 --> 00:13:29,052 simple algorithm to answer is this is x the substring of questions and a find 156 00:13:29,052 --> 00:13:34,822 application of Tries. And again the number of void nodes in what 157 00:13:34,822 --> 00:13:39,094 does it mean to be a random try and how long is the search and so forth? 158 00:13:39,094 --> 00:13:44,363 All of these kinds of questions are going to be important and relevant in practice. 159 00:13:44,363 --> 00:13:49,214 Here's another application of tries. Tries as a model for an algorithm so 160 00:13:49,214 --> 00:13:54,761 called, leader election algorithm. This is important in distributed systems. 161 00:13:54,762 --> 00:14:00,042 So the idea is you have a group of individuals and they would need to elect a 162 00:14:00,042 --> 00:14:03,851 leader and what they're going to do is each flip a coin. 163 00:14:03,851 --> 00:14:08,530 So it's distributed, there can be a large number of them that flip a coin. 164 00:14:08,530 --> 00:14:12,283 And we'll count ones as winners and zeroes as losers. 165 00:14:12,284 --> 00:14:17,688 And so everybody that gets a one when they flip a coin survives for the next round. 166 00:14:17,688 --> 00:14:22,274 And the first that got zero are gone. So now we just worry about the one is, 167 00:14:22,274 --> 00:14:25,234 that got one is and again they each flip a coin. 168 00:14:25,234 --> 00:14:30,674 In this case the 2 green one is get a 0 so they're the losers and they're eliminated 169 00:14:30,674 --> 00:14:34,449 and only the one is that got one continue to the next round. 170 00:14:34,449 --> 00:14:40,896 They each flip a coin, again two are eliminated and three are left, the ones 171 00:14:40,896 --> 00:14:47,101 that got 1s, they each flip a coin. In this case, that all get 1's so they all 172 00:14:47,101 --> 00:14:51,376 advance to the next round and then we have a void no. 173 00:14:51,376 --> 00:14:57,542 And then, again they nobody eliminated. Now they each flip a coin and only the 174 00:14:57,542 --> 00:15:03,472 blue one survives so that's the winner. So this is a very simple method for 175 00:15:03,473 --> 00:15:08,502 choosing a leader in its distributed banner among n people. 176 00:15:08,502 --> 00:15:13,578 Now there's a possible problem, and that is a procedure might fail. 177 00:15:13,578 --> 00:15:19,550 What if they all throw 0 then in that case they're all losers. 178 00:15:19,550 --> 00:15:26,110 There's no winner, procedure might fail. So obviously we're going to be interested 179 00:15:26,110 --> 00:15:31,319 in what's the chance of failure. Well, it's the probability that the 180 00:15:31,319 --> 00:15:34,999 rightmost path in a random try ends in a void no. 181 00:15:34,999 --> 00:15:39,756 What do I mean by a random Trie? Well, it turns out that the model that 182 00:15:39,756 --> 00:15:45,455 associates with this and also works for symbol tables is it's a try that you get 183 00:15:45,455 --> 00:15:50,915 by inserting infinite length random bitstring into an initially empty try. 184 00:15:50,915 --> 00:15:57,497 So there's 3 diverse applications of the Trie data structure for a symbol table. 185 00:15:57,497 --> 00:16:02,417 For sub-strain search and for distributed leader election. 186 00:16:02,417 --> 00:16:08,988 And all of this is to motivate studying this combinatorial structure. 187 00:16:08,989 --> 00:16:13,471 So for distributed leader what I want to know, what's the number of rounds? 188 00:16:13,471 --> 00:16:17,625 Well, it's the expected length of the rightmost path in a random Trie that 189 00:16:17,625 --> 00:16:22,929 somebody rounds, and then your probability of success from that you can calculate how 190 00:16:22,929 --> 00:16:32,884 effective this method is going to be. So that's a brief description of tries and 191 00:16:32,884 --> 00:16:40,717 next we'll look at analysis of Trie parameters.