WEBVTT 00:00:00.046 --> 00:00:03.284 Suppose I secretly choose one of these eight letters. 00:00:03.367 --> 00:00:06.723 You may ask only questions whose answer is yes or no. 00:00:06.920 --> 00:00:09.974 Your job is to identify my letter with certainty. 00:00:10.170 --> 00:00:12.110 How many answers do you need? 00:00:13.023 --> 00:00:15.285 Because the letters are equally likely, 00:00:15.368 --> 00:00:19.537 the sensible first question cuts the possibilities into equal halves. 00:00:19.850 --> 00:00:22.672 Ask whether the letter lies in A through D. 00:00:22.775 --> 00:00:25.237 One answer leaves the upper four; 00:00:25.341 --> 00:00:27.292 the other leaves the lower four. 00:00:27.996 --> 00:00:31.492 The first answer has taken us from eight candidates to four. 00:00:31.596 --> 00:00:36.589 It has not named the symbol, but it has removed exactly half of the uncertainty. 00:00:37.385 --> 00:00:40.811 Ask another balanced question inside the surviving half. 00:00:41.008 --> 00:00:43.040 Four candidates become two. 00:00:43.237 --> 00:00:45.292 The same yes-or-no answer has again 00:00:45.292 --> 00:00:48.056 divided the remaining possibilities by two. 00:00:48.759 --> 00:00:51.512 A third question separates the final pair. 00:00:51.708 --> 00:00:54.261 Eight leaves now stand at the ends of the tree, 00:00:54.344 --> 00:00:57.723 and every letter is reached by exactly three answers. 00:00:58.427 --> 00:01:00.401 The count is not an accident. 00:01:00.598 --> 00:01:04.184 Three binary answers can form eight distinct answer strings, 00:01:04.267 --> 00:01:07.565 because two choices made three times give two cubed. 00:01:08.478 --> 00:01:10.417 Turn that relation around. 00:01:10.521 --> 00:01:12.379 The number of binary questions needed 00:01:12.379 --> 00:01:18.010 to choose among eight equal possibilities is log base two of eight, which is three. 00:01:18.923 --> 00:01:24.171 We give one balanced binary answer a unit of information and call that unit a bit. 00:01:24.484 --> 00:01:27.840 A bit is not merely a zero stored in memory. 00:01:27.943 --> 00:01:30.115 It is the distinction between two alternatives 00:01:30.115 --> 00:01:32.065 that were both still possible. 00:01:32.862 --> 00:01:37.449 With q binary answers there are two to the q possible answer strings. 00:01:37.552 --> 00:01:42.497 Therefore identifying one of N equally likely outcomes requires log base two 00:01:42.580 --> 00:01:43.997 of N bits. 00:01:44.793 --> 00:01:47.859 Next we will make the letters unequally likely. 00:01:48.172 --> 00:01:53.407 That one change will lead us first to entropy, the ideal average question count, 00:01:53.490 --> 00:01:55.171 and then to Huffman coding, 00:01:55.254 --> 00:01:59.295 a way to build an actual binary description close to that ideal. 00:02:00.444 --> 00:02:03.835 Keep the same eight symbols, but change their likelihoods. 00:02:04.031 --> 00:02:06.586 A now occurs forty percent of the time. 00:02:06.783 --> 00:02:08.815 B occurs twenty percent. 00:02:08.919 --> 00:02:11.308 C and D each occur ten percent, 00:02:11.392 --> 00:02:14.620 and the final four symbols each occur five percent. 00:02:15.324 --> 00:02:19.237 A alone occupies forty percent of the probability bar. 00:02:19.341 --> 00:02:24.264 It is twice as likely as B, and four times as likely as either C or D. 00:02:24.805 --> 00:02:28.661 C and D together occupy another twenty percent. 00:02:28.857 --> 00:02:33.571 They are less common individually, but they still matter much more often than any 00:02:33.571 --> 00:02:36.045 one of the four symbols at the narrow end. 00:02:36.586 --> 00:02:39.590 The final four slices are equal and rare. 00:02:39.674 --> 00:02:42.914 Each accounts for only one twentieth of the messages. 00:02:43.711 --> 00:02:48.457 If we keep the old balanced tree, every outcome still costs three questions. 00:02:48.541 --> 00:02:52.465 That treats a five-percent event exactly like the event that appears forty percent 00:02:52.465 --> 00:02:53.546 of the time. 00:02:54.157 --> 00:02:58.925 Instead, ask the most useful question first: is the symbol A? 00:02:59.009 --> 00:03:02.385 When the answer is yes, which happens forty percent of the time, 00:03:02.469 --> 00:03:04.815 the search ends after one bit. 00:03:05.519 --> 00:03:08.991 If it was not A, the next question can separate B. 00:03:09.443 --> 00:03:11.592 B then takes two answers. 00:03:11.696 --> 00:03:16.491 The commonest sixty percent of all symbols have received the two shortest paths. 00:03:17.288 --> 00:03:21.085 The price is that C and D now require four questions. 00:03:21.282 --> 00:03:22.974 That sounds worse than the old three, 00:03:23.058 --> 00:03:26.367 but each of those symbols appears only one time in ten. 00:03:27.164 --> 00:03:30.601 The four rarest outcomes take five questions each. 00:03:30.705 --> 00:03:32.235 Long answers are not free, 00:03:32.319 --> 00:03:35.512 but we pay for them on only twenty percent of the symbols. 00:03:36.123 --> 00:03:39.595 Now average the question counts using their probabilities. 00:03:39.699 --> 00:03:42.150 A contributes point four times one. 00:03:42.602 --> 00:03:45.180 B contributes point two times two. 00:03:45.376 --> 00:03:49.019 C and D together contribute point two times four, 00:03:49.103 --> 00:03:52.192 and the rare group contributes point two times five. 00:03:52.989 --> 00:03:56.054 The result is two point six questions per symbol. 00:03:56.251 --> 00:03:58.860 Some individual outcomes became more expensive, 00:03:58.944 --> 00:04:02.312 but the outcomes we see most often became much cheaper. 00:04:03.109 --> 00:04:06.615 The equal-depth plan cost exactly three questions. 00:04:06.812 --> 00:04:11.317 Exploiting likelihood saves point four of a question per symbol on average. 00:04:11.630 --> 00:04:12.919 Over a million symbols, 00:04:12.919 --> 00:04:16.693 that becomes roughly four hundred thousand fewer binary answers. 00:04:17.786 --> 00:04:19.375 For eight equal outcomes, 00:04:19.458 --> 00:04:24.892 three halvings isolate one outcome because one eighth equals one over two cubed. 00:04:25.344 --> 00:04:29.339 Now replace one eighth by a general probability p. 00:04:30.135 --> 00:04:34.327 Imagine a very large collection of equally detailed possibilities. 00:04:34.524 --> 00:04:39.065 An event with probability p occupies the fraction p of them. 00:04:39.261 --> 00:04:44.336 To isolate that fraction by balanced binary questions, we keep halving. 00:04:45.248 --> 00:04:47.220 After q balanced questions, 00:04:47.303 --> 00:04:51.286 one answer path identifies about one part in two to the q. 00:04:51.483 --> 00:04:57.509 To match an event occupying fraction p, two to the q must be about one over p. 00:04:58.201 --> 00:05:03.845 Solve for q. The ideal question count is log base two of one over p. 00:05:04.030 --> 00:05:07.920 Equivalently, it is minus log base two of p. 00:05:08.705 --> 00:05:11.074 This quantity measures surprise. 00:05:11.178 --> 00:05:15.392 A likely event has a large p and a small information value. 00:05:15.589 --> 00:05:20.733 A rare event has a small p and needs a longer answer path to distinguish it. 00:05:21.530 --> 00:05:24.047 For A, p is point four, 00:05:24.130 --> 00:05:27.997 so the ideal length is about one point three two two bits. 00:05:28.194 --> 00:05:33.361 For a five-percent symbol, it is about four point three two two bits. 00:05:33.674 --> 00:05:37.123 These are not yet legal single-symbol code lengths. 00:05:38.519 --> 00:05:42.291 A single binary question cannot be split into a fraction. 00:05:42.374 --> 00:05:48.072 But across a long stream, common and rare symbols can share a description strategy, 00:05:48.155 --> 00:05:51.105 and a fractional average becomes meaningful. 00:05:52.018 --> 00:05:56.592 To find the ideal average, weight each symbol's question count by the probability 00:05:56.592 --> 00:05:59.077 of seeing that symbol, then add. 00:05:59.274 --> 00:06:02.828 This weighted average is the quantity we call entropy. 00:06:03.624 --> 00:06:06.061 Now calculate it for our distribution. 00:06:06.144 --> 00:06:10.113 A contributes about point five two nine bits per source symbol. 00:06:10.196 --> 00:06:12.285 That is its ideal length multiplied 00:06:12.285 --> 00:06:15.432 by the forty-percent frequency with which we pay it. 00:06:16.229 --> 00:06:19.307 B contributes about point four six four. 00:06:19.503 --> 00:06:23.544 C and D together contribute about point six six four. 00:06:24.341 --> 00:06:27.845 The four five-percent symbols each carry more surprise, 00:06:27.928 --> 00:06:31.691 and together they contribute about point eight six four bits. 00:06:31.887 --> 00:06:33.803 Adding every group gives an entropy 00:06:33.803 --> 00:06:36.927 of about two point five two two bits per symbol. 00:06:38.324 --> 00:06:40.879 Here is another way to read the same number. 00:06:41.075 --> 00:06:44.140 In a long block of n symbols, the probability 00:06:44.140 --> 00:06:50.004 pattern concentrates most messages among roughly two to the n H typical sequences. 00:06:50.917 --> 00:06:55.094 Distinguishing that many likely messages needs about the log of their count, 00:06:55.177 --> 00:06:57.825 which is n H binary answers. 00:06:58.022 --> 00:07:01.471 Entropy is therefore not an arbitrary formula. 00:07:01.667 --> 00:07:05.732 It is the question count forced by the number of likely messages. 00:07:06.746 --> 00:07:10.787 Huffman coding turns the probability list into a binary tree. 00:07:11.402 --> 00:07:13.699 Begin with one leaf for every symbol. 00:07:13.782 --> 00:07:17.544 The only repeated instruction is to merge the two smallest weights. 00:07:18.341 --> 00:07:22.730 The first two rarest leaves are E and F, each with weight five. 00:07:22.834 --> 00:07:25.761 Join them under a new node of weight ten. 00:07:26.673 --> 00:07:29.275 G and H are the next equal pair. 00:07:29.471 --> 00:07:33.257 Merge their five-percent weights into a second node of weight ten. 00:07:34.053 --> 00:07:36.399 C and D each have weight ten. 00:07:36.596 --> 00:07:39.615 Merge those two leaves into a node of weight twenty. 00:07:40.412 --> 00:07:44.987 The two ten-weight branches made from E through H are now the smallest pair. 00:07:45.300 --> 00:07:47.738 Their merge produces another weight twenty. 00:07:48.651 --> 00:07:50.893 Three weights of twenty are available. 00:07:51.089 --> 00:07:54.562 Ties may be resolved consistently in more than one way. 00:07:54.758 --> 00:07:57.720 Merge these two compound branches to make forty. 00:07:58.423 --> 00:08:02.255 B has weight twenty and the compound branch has weight forty. 00:08:02.359 --> 00:08:07.236 They are the two smallest remaining items, so their parent has weight sixty. 00:08:08.033 --> 00:08:12.748 Finally merge A, with weight forty, and the remaining weight sixty. 00:08:12.944 --> 00:08:17.090 Their root has weight one hundred, and the Huffman tree is complete. 00:08:18.486 --> 00:08:23.259 Assign zero to the upper branch and one to the lower branch at each split. 00:08:23.455 --> 00:08:28.262 A codeword is the sequence encountered while walking from the root to a leaf. 00:08:29.175 --> 00:08:35.050 A is reached immediately by code zero, so the most likely symbol costs only one bit. 00:08:35.363 --> 00:08:39.102 B follows one then zero, so it costs two bits. 00:08:39.899 --> 00:08:45.960 C and D sit deeper, with codes one one zero zero and one one zero one. 00:08:46.156 --> 00:08:48.340 Each requires four bits. 00:08:49.136 --> 00:08:52.783 The four rarest symbols lie one level deeper still. 00:08:52.979 --> 00:08:58.379 Their codes share the prefix one one one, then use two more bits to select the leaf. 00:08:59.431 --> 00:09:02.462 No codeword is the beginning of another codeword. 00:09:02.658 --> 00:09:06.360 That prefix property lets a decoder read the stream from left to right 00:09:06.443 --> 00:09:09.253 and know exactly when each symbol ends. 00:09:09.957 --> 00:09:11.685 Compute the average length. 00:09:11.768 --> 00:09:14.428 A pays one bit forty percent of the time. 00:09:14.624 --> 00:09:17.794 B pays two bits twenty percent of the time. 00:09:18.107 --> 00:09:22.368 C and D pay four, and the final four symbols pay five. 00:09:23.072 --> 00:09:27.682 The Huffman code therefore uses two point six bits per symbol on average. 00:09:27.786 --> 00:09:31.290 The merging rule has recovered the likelihood-aware question plan, 00:09:31.373 --> 00:09:35.715 and it has guaranteed that no other binary prefix code has a smaller average length 00:09:35.715 --> 00:09:37.678 for these individual symbols. 00:09:38.805 --> 00:09:41.055 Put the two numbers on one scale. 00:09:41.139 --> 00:09:45.037 Entropy for our source is about two point five two two bits per symbol. 00:09:45.121 --> 00:09:48.094 The Huffman code uses two point six. 00:09:48.890 --> 00:09:52.444 The gap is only point zero seven eight of a bit per symbol. 00:09:52.640 --> 00:09:56.589 Huffman coding is not merely better than the fixed three-bit code. 00:09:56.785 --> 00:09:59.898 It is very close to the information-theoretic target. 00:10:00.694 --> 00:10:02.367 Two questions remain. 00:10:02.564 --> 00:10:07.673 Why can no lossless prefix code move the green point to the left of entropy? 00:10:07.776 --> 00:10:12.618 And if the bound is unbeatable, why is Huffman allowed to sit slightly above it? 00:10:13.922 --> 00:10:19.287 A binary prefix code is a set of nonoverlapping leaves in a binary tree. 00:10:19.483 --> 00:10:25.591 A codeword of length l occupies one part in two to the l of the tree's capacity. 00:10:26.387 --> 00:10:29.732 Add those occupied fractions over all symbols. 00:10:29.835 --> 00:10:31.354 They cannot exceed one. 00:10:31.438 --> 00:10:36.535 This is the tree-capacity inequality, often called Kraft's inequality. 00:10:37.448 --> 00:10:41.860 Now compare the actual average length L with entropy H. 00:10:42.057 --> 00:10:46.203 Their difference can be written as this weighted logarithmic ratio. 00:10:46.906 --> 00:10:48.648 The log-sum inequality says 00:10:48.648 --> 00:10:52.805 that weighted ratio is at least minus the log of the tree capacity. 00:10:53.001 --> 00:10:57.728 Since the capacity is at most one, that quantity is nonnegative. 00:10:58.640 --> 00:11:03.448 Therefore every binary prefix code has average length at least H. 00:11:03.644 --> 00:11:05.188 Shorter paths for some outcomes 00:11:05.188 --> 00:11:10.065 consume more tree capacity and force compensating longer paths elsewhere. 00:11:10.169 --> 00:11:13.130 The average cannot cross the entropy bound. 00:11:14.043 --> 00:11:18.677 Entropy supplies ideal lengths such as one point three two two bits. 00:11:18.873 --> 00:11:21.262 Real codewords have whole-number lengths. 00:11:21.346 --> 00:11:25.166 Huffman chooses those integers optimally, and its average is always 00:11:25.166 --> 00:11:29.253 less than one bit above entropy for a memoryless symbol source. 00:11:30.166 --> 00:11:35.051 When probabilities are exact powers of one half, the ideal lengths are integers 00:11:35.135 --> 00:11:37.898 and Huffman can meet entropy exactly. 00:11:38.095 --> 00:11:40.113 Otherwise it rounds through the tree, 00:11:40.197 --> 00:11:43.703 as our small point zero seven eight gap demonstrates. 00:11:44.407 --> 00:11:48.634 There is also a way to make the rounding cost per symbol smaller. 00:11:48.738 --> 00:11:51.165 Encode blocks of symbols together. 00:11:51.268 --> 00:11:55.541 One possible extra bit is then shared by the whole block rather than charged 00:11:55.541 --> 00:11:57.109 to every symbol. 00:11:57.906 --> 00:11:59.752 Now return to files. 00:11:59.856 --> 00:12:02.353 Typical English text is structured. 00:12:02.550 --> 00:12:06.543 Spaces and common letters occur more often than rare punctuation, 00:12:06.543 --> 00:12:09.446 so even the one-byte distribution is uneven. 00:12:10.243 --> 00:12:13.413 English also has dependencies across positions. 00:12:13.610 --> 00:12:15.534 After the letters q and u, 00:12:15.618 --> 00:12:18.556 some next letters are far more plausible than others. 00:12:18.869 --> 00:12:25.105 Words, phrases, indentation, and repeated substrings create further predictability. 00:12:25.901 --> 00:12:29.745 A compressor turns that predictability into short descriptions. 00:12:29.941 --> 00:12:33.611 Huffman coding exploits a probability distribution. 00:12:33.808 --> 00:12:37.836 More advanced compressors also exploit context, repeated strings, 00:12:37.836 --> 00:12:40.031 and predictions from earlier data. 00:12:40.944 --> 00:12:43.731 Independent random bytes are different. 00:12:43.928 --> 00:12:48.258 Each of the two hundred fifty-six byte values has probability one over two 00:12:48.258 --> 00:12:52.915 hundred fifty-six, and the next byte is not predicted by the bytes before it. 00:12:53.712 --> 00:12:56.627 There is no statistical redundancy to exploit. 00:12:56.823 --> 00:12:59.201 The entropy is eight bits per byte, 00:12:59.285 --> 00:13:02.583 exactly the size already used by an ordinary byte. 00:13:03.379 --> 00:13:08.024 There are two hundred fifty-six possible byte values, which is two to the eighth. 00:13:08.220 --> 00:13:12.366 If they are equally likely, identifying one requires eight bits. 00:13:13.418 --> 00:13:18.144 For an n-byte file there are two to the eight n possible inputs. 00:13:18.340 --> 00:13:22.064 There are not enough shorter binary strings to give every input a unique 00:13:22.148 --> 00:13:24.308 shorter lossless description. 00:13:25.523 --> 00:13:30.280 Some individual random-looking file may shrink by chance, but most will not, 00:13:30.364 --> 00:13:33.430 and compressor metadata can make them larger. 00:13:33.743 --> 00:13:37.177 Already compressed or encrypted files often behave similarly 00:13:37.261 --> 00:13:41.081 because their byte patterns have been deliberately made difficult to predict. 00:13:41.785 --> 00:13:44.525 The whole story now fits into four steps. 00:13:44.629 --> 00:13:47.892 First, a bit is one resolved binary choice. 00:13:48.689 --> 00:13:54.108 Second, repeated halving says an event of probability p carries about log base two 00:13:54.192 --> 00:13:56.131 of one over p bits. 00:13:56.328 --> 00:13:58.836 Averaging that surprise gives entropy. 00:13:59.633 --> 00:14:03.427 Third, Huffman coding repeatedly merges rare events 00:14:03.511 --> 00:14:06.263 so likely symbols end near the root. 00:14:06.460 --> 00:14:10.476 Its integer code lengths approach the entropy limit without ever beating 00:14:10.476 --> 00:14:11.940 that lower bound. 00:14:12.737 --> 00:14:17.172 Finally, compression is possible when data contains predictable structure. 00:14:17.369 --> 00:14:20.365 English supplies redundancy and context. 00:14:20.562 --> 00:14:23.094 Independent random bytes do not. 00:14:23.290 --> 00:14:25.215 Entropy measures that difference, 00:14:25.299 --> 00:14:29.525 and coding turns the available predictability into fewer stored bits.