WEBVTT
Kind: captions
Language: en

1
00:00:00.120 --> 00:00:02.190
When you put English text into a computer,

2
00:00:02.190 --> 00:00:05.930
it is saving every individual character as
eight bits of data.

3
00:00:05.930 --> 00:00:06.930
Eight ones and zeros.

4
00:00:06.930 --> 00:00:09.019
I mean, they're not actually ones and zeros,

5
00:00:09.020 --> 00:00:11.520
they're particular positions
of atoms on a disk

6
00:00:11.520 --> 00:00:13.790
or a few electrons going over a wire,

7
00:00:13.790 --> 00:00:16.290
but as far as we're concerned
in the computer science world,

8
00:00:16.290 --> 00:00:18.420
they are ones and zeros. Bits.

9
00:00:18.420 --> 00:00:22.720
And yes, a modern phone or computer might
store a few quadrillion of them(!)

10
00:00:22.720 --> 00:00:25.300
But every time you've had to wait a long time
for a download,

11
00:00:25.300 --> 00:00:27.670
or your phone's complained
that its storage is full,

12
00:00:27.670 --> 00:00:31.680
you're running up against the same question
that computer scientists have been working on

13
00:00:31.680 --> 00:00:35.000
since before these things here
were state of the art:

14
00:00:35.000 --> 00:00:38.160
can we please not use so many bits?

15
00:00:40.540 --> 00:00:43.260
So, let’s run through
how computers compress text.

16
00:00:43.260 --> 00:00:45.460
Images and video are different —
that's lossy compression,

17
00:00:45.460 --> 00:00:48.260
where it doesn't matter if you lose
a little bit of detail.

18
00:00:48.260 --> 00:00:50.480
But text has to be losslessly compressed:

19
00:00:50.480 --> 00:00:52.640
you can't just lose a bit of detail,

20
00:00:52.640 --> 00:00:55.010
otherwise you end up sending the wrong worms.

21
00:00:55.010 --> 00:00:56.339
So the first thing we need to know

22
00:00:56.339 --> 00:00:59.880
is how text is stored on disk before it's
compressed.

23
00:00:59.880 --> 00:01:00.880
To make this easier,

24
00:01:00.880 --> 00:01:03.089
I am just going to talk about
English text here:

25
00:01:03.089 --> 00:01:06.400
I know only too well that it gets
more complicated than this,

26
00:01:06.400 --> 00:01:09.840
but hey, the series is called "the basics",
so deal with it.

27
00:01:09.840 --> 00:01:12.500
On a modern computer,
each English character takes up

28
00:01:12.500 --> 00:01:16.690
exactly eight ones and zeros on disk -
eight bits, or one byte.

29
00:01:16.690 --> 00:01:19.850
And there are 256 possible combinations of
those ones and zeros,

30
00:01:19.850 --> 00:01:23.310
so you can have 256 possible characters.

31
00:01:23.310 --> 00:01:26.100
That's enough for the English alphabet, numbers,
some punctuation, and...

32
00:01:26.100 --> 00:01:29.201
well, then it gets complicated depending on
which country you’re in

33
00:01:29.201 --> 00:01:31.580
and oh my god that's a whole separate video

34
00:01:31.580 --> 00:01:34.080
we do not want to get into right now.

35
00:01:34.080 --> 00:01:35.390
Why eight bits?

36
00:01:35.390 --> 00:01:37.540
Because it was big enough to store all the
characters

37
00:01:37.540 --> 00:01:41.610
that American computers usually needed,
but no bigger,

38
00:01:41.610 --> 00:01:45.410
so the text doesn't take up any more space
than it absolutely has to.

39
00:01:45.410 --> 00:01:48.000
Eight is also a power of two, which means
it's easy to deal with

40
00:01:48.000 --> 00:01:50.520
at the really low levels of programming.

41
00:01:50.520 --> 00:01:54.340
It's also helpful to have a fixed number of
bits per character

42
00:01:54.340 --> 00:01:56.630
because it makes searching through text
really fast.

43
00:01:56.630 --> 00:01:59.800
If you want to go to the 100,000th character
in some text,

44
00:01:59.800 --> 00:02:03.120
you know exactly where the ones and zeros
are going to be without

45
00:02:03.120 --> 00:02:07.150
having to count the number of bits in every
single character before it.

46
00:02:07.150 --> 00:02:09.539
If you want to know how long
a string of text is,

47
00:02:09.539 --> 00:02:12.549
you just count the bits
and you divide by eight.

48
00:02:12.549 --> 00:02:14.909
Computers don't have the luxury of spaces,
remember:

49
00:02:14.909 --> 00:02:18.620
it's just one long string of 1s and 0s.

50
00:02:18.620 --> 00:02:20.569
But let's say we're not worried about speed
right now,

51
00:02:20.569 --> 00:02:22.760
we just want to fit as much text as possible

52
00:02:22.760 --> 00:02:26.240
into as small a number of 1s and 0s as possible.

53
00:02:26.240 --> 00:02:27.400
Compression.

54
00:02:27.400 --> 00:02:30.020
A good plan would be to assign
the most common characters

55
00:02:30.030 --> 00:02:32.060
to smaller arrangements of bits.

56
00:02:32.060 --> 00:02:34.810
So those researchers, way way back,
could have said:

57
00:02:34.810 --> 00:02:37.150
well, the space bar is generally
used most often.

58
00:02:37.150 --> 00:02:38.829
Just give that the code "0".

59
00:02:38.829 --> 00:02:41.010
Then it's the lowercase e.
Give that the code "1".

60
00:02:41.010 --> 00:02:43.740
Then it's lowercase t: give that two zeros...

61
00:02:43.740 --> 00:02:46.319
...and immediately, we've hit a problem.

62
00:02:46.319 --> 00:02:49.340
Because the computer running through that text later
has no way of knowing

63
00:02:49.340 --> 00:02:52.769
whether "00" is a t, or the space bar twice.

64
00:02:52.769 --> 00:02:54.799
And if we keep on assigning letters like that,

65
00:02:54.799 --> 00:02:56.620
the problems keep getting worse:

66
00:02:56.620 --> 00:02:58.909
is three zeros a lowercase n?

67
00:02:58.909 --> 00:03:00.859
Or a t followed by a space? Or three spaces?

68
00:03:00.859 --> 00:03:04.469
Remember, there are no gaps here, no actual
space separators,

69
00:03:04.469 --> 00:03:08.440
all the computer can see is a constant stream
of 1s and 0s.

70
00:03:08.440 --> 00:03:10.719
There's no way to know which is meant.

71
00:03:10.719 --> 00:03:16.939
Except. In 1952, a very clever mathematician
called David Huffman invented Huffman coding.

72
00:03:16.939 --> 00:03:19.590
You invent something like that,
your name gets put on it.

73
00:03:19.590 --> 00:03:21.029
Yes, there are much better,

74
00:03:21.029 --> 00:03:23.980
more modern, more complicated,
mathematical ways to do this,

75
00:03:23.980 --> 00:03:28.090
but Huffman coding is the basic foundation
of modern text compression.

76
00:03:28.090 --> 00:03:30.549
And here is how it works.

77
00:03:30.549 --> 00:03:31.909
Let's say we want to compress...

78
00:03:31.909 --> 00:03:34.319
let's go with the lyrics to
Will Smith's "Wild Wild West".

79
00:03:34.319 --> 00:03:39.700
Uncompressed, that is 3,684 characters
taking up nearly 30,000 bits.

80
00:03:39.700 --> 00:03:43.240
First up: you count how many times
each character is used,

81
00:03:43.240 --> 00:03:44.760
and you put that in a list in order.

82
00:03:44.760 --> 00:03:47.139
Now that'll be different for each block of
text you're compressing:

83
00:03:47.139 --> 00:03:49.980
this has way more Ws than usual.

84
00:03:49.980 --> 00:03:52.239
Now take the two least used characters.

85
00:03:52.239 --> 00:03:55.829
Those two are going to be the bottom branches
on your “Huffman tree”.

86
00:03:55.829 --> 00:03:58.269
Write them down, with how often they're used
next to them.

87
00:03:58.269 --> 00:03:59.950
That’s called their frequency.

88
00:03:59.950 --> 00:04:04.340
Then connect them together, one level up,
with the sum of their frequencies.

89
00:04:04.340 --> 00:04:07.049
Now add that new sum back into your list,

90
00:04:07.049 --> 00:04:09.069
wherever it sits, higher up.

91
00:04:09.069 --> 00:04:10.540
And repeat!

92
00:04:10.540 --> 00:04:12.400
Take the bottom two off your list,
connect them up,

93
00:04:12.400 --> 00:04:14.260
add the result back in your list.

94
00:04:14.260 --> 00:04:15.260
Keep that going.

95
00:04:15.260 --> 00:04:17.930
And when one of the sums reaches the bottom
two of the list,

96
00:04:17.930 --> 00:04:19.389
you connect it up like that.

97
00:04:19.389 --> 00:04:23.660
And eventually, you're going to be down to
one thing in your list,

98
00:04:23.660 --> 00:04:24.660
right at the top.

99
00:04:24.660 --> 00:04:27.750
You now have a Huffman tree,
and it looks like this,

100
00:04:27.750 --> 00:04:31.860
and it tells you how to convert your text
into ones and zeros.

101
00:04:31.860 --> 00:04:36.620
Our first letter is the first uppercase W
in 'wiki-wiki-wild-wild-West'.

102
00:04:36.620 --> 00:04:38.960
Uppercase W is here, there’s 141 of them.

103
00:04:38.960 --> 00:04:41.229
So go the top, follow the path down.

104
00:04:41.229 --> 00:04:43.340
Each time you take the left hand side, write
a 0;

105
00:04:43.340 --> 00:04:45.910
each time you take the right hand side, write
a 1.

106
00:04:45.910 --> 00:04:48.740
So W is this: only 5 bits instead of 8.

107
00:04:48.740 --> 00:04:49.820
Next, lowercase i.

108
00:04:49.820 --> 00:04:52.949
Follow the code down, only four bits
this time, it’s more common.

109
00:04:52.949 --> 00:04:55.960
Then the k, which is less common; that actually
takes up seven bits.

110
00:04:55.960 --> 00:04:56.960
And you keep going.

111
00:04:56.960 --> 00:04:59.580
Some of the letters will take up more than
8 bits,

112
00:04:59.580 --> 00:05:03.030
but that’s fine, because they’re not used
very often.

113
00:05:03.030 --> 00:05:06.810
Now, you do have to also store this tree to
provide a translation table

114
00:05:06.810 --> 00:05:08.930
between your new symbols
and the uncompressed ones -

115
00:05:08.930 --> 00:05:11.699
so this is not efficient for
short bits of text.

116
00:05:11.699 --> 00:05:14.380
If you’re ever asked to do this
in a computer science exam,

117
00:05:14.380 --> 00:05:16.590
then they’ll ignore all that
and just ask you

118
00:05:16.590 --> 00:05:18.960
to do one easy word from a tree by hand.

119
00:05:18.960 --> 00:05:22.419
But for Will Smith's magnum opus,
we have compressed it down

120
00:05:22.419 --> 00:05:26.559
to just over 20,000 bits: about a 30% saving.

121
00:05:26.559 --> 00:05:29.430
To uncompress the resulting stream of bits,
it works the other way:

122
00:05:29.430 --> 00:05:32.450
just read across, take the left fork every
time you see a 0

123
00:05:32.450 --> 00:05:35.050
and the right fork every time you see a 1.

124
00:05:35.050 --> 00:05:37.080
When you reach a letter, that's it, you know
that’s the end,

125
00:05:37.080 --> 00:05:41.190
and you know that there is no other path you
could have possibly taken.

126
00:05:41.190 --> 00:05:43.520
You start again with the next bit.

127
00:05:43.520 --> 00:05:46.900
Now in practice, computers might do this working
backwards from the bottom up sometimes,

128
00:05:46.900 --> 00:05:50.180
but this is a pretty good way to at least
understand what's going on.

129
00:05:50.180 --> 00:05:52.050
And here's the really clever part:

130
00:05:52.050 --> 00:05:55.490
Huffman proved that this is
the most efficient way

131
00:05:55.490 --> 00:05:57.810
to assign 0s and 1s to single characters.

132
00:05:57.810 --> 00:06:02.009
It is mathematically impossible to beat this.

133
00:06:02.009 --> 00:06:04.770
Unless, as you might already
have figured out,

134
00:06:04.770 --> 00:06:08.260
you start working on blocks
bigger than one character.

135
00:06:08.260 --> 00:06:10.889
Clever tricks like that are basically how
zip files work...

136
00:06:10.889 --> 00:06:13.889
but then, this is just the basics.

137
00:06:13.889 --> 00:06:16.530
Thank you to all my proofreaders who helped
with that script,

138
00:06:16.530 --> 00:06:17.599
thank you to my graphics team,

139
00:06:17.599 --> 00:06:20.849
and also thank you to the
Centre for Computing History in Cambridge

140
00:06:20.849 --> 00:06:22.419
for letting me film with their old kit.