1
00:00:00,350 --> 00:00:04,000
We can do considerably more to limit
our search for candidate matches.

2
00:00:04,000 --> 00:00:06,980
The next step is to consider not
only whether the prefixes of

3
00:00:06,980 --> 00:00:10,460
two strings have a symbol in,
a symbol in, in common.

4
00:00:10,460 --> 00:00:13,660
But, whether the first common symbol
appears close enough to the fronts of

5
00:00:13,660 --> 00:00:14,220
both strings.

6
00:00:14,220 --> 00:00:17,850
The fact that no symbols before
them are common to both strings,

7
00:00:17,850 --> 00:00:21,550
will put a lower bound on
the edit distance of the strings.

8
00:00:21,550 --> 00:00:24,970
And this lower bound in turn
will place a lower bound on

9
00:00:24,970 --> 00:00:27,370
the Jaccard distance between the strings.

10
00:00:27,370 --> 00:00:30,570
When we use a two-dimensional index
based on both the symbol edit,

11
00:00:30,570 --> 00:00:34,870
edit position and the position number
itself, we can cut down the total number

12
00:00:34,870 --> 00:00:39,190
of strings that become candidates for
comparison with a given probe string.

13
00:00:39,190 --> 00:00:40,796
Roughly, by a factor of two.

14
00:00:44,089 --> 00:00:45,980
Suppose, we have strings s and

15
00:00:45,980 --> 00:00:50,730
t and the first position of string s that
matches a symbol in t is at position i.

16
00:00:51,900 --> 00:00:52,980
Moreover, this symbol,

17
00:00:52,980 --> 00:00:57,270
which we shall suppose is a,
matches the symbol in position j of t.

18
00:00:58,520 --> 00:01:02,630
And the first thing we can conclude is
that s has i minus 1 symbols that do

19
00:01:02,630 --> 00:01:04,260
not appear in t.

20
00:01:04,260 --> 00:01:07,450
And t has j minus 1 symbols
that do not appear in s.

21
00:01:08,720 --> 00:01:15,035
Thus the edit distance between s and
t is at least i plus j minus 2.

22
00:01:20,530 --> 00:01:22,880
While we have a lower bound
on the edit distance,

23
00:01:22,880 --> 00:01:25,860
we can also see an upper bound on
the length of the longest common

24
00:01:25,860 --> 00:01:29,910
sub sequence in terms of
the length L of string s.

25
00:01:29,910 --> 00:01:34,430
That is the longest LCS we can
have is when every symbol of s

26
00:01:34,430 --> 00:01:36,510
following the a also appears in t.

27
00:01:37,570 --> 00:01:41,620
These symbols may not be consecutive in t,
but remember that there is

28
00:01:41,620 --> 00:01:46,180
a unique order to the symbols and they
appear in the same order in every string.

29
00:01:46,180 --> 00:01:47,930
so, if s is of length L,

30
00:01:47,930 --> 00:01:52,450
then the longest possible LCS
is of length L minus i plus 1.

31
00:01:53,910 --> 00:01:58,340
That is all but the i minus 1 symbols
of s that precede the symbol a.

32
00:02:03,930 --> 00:02:07,360
Now, we can use the lower bound on
edit distance and the upper bound on

33
00:02:07,360 --> 00:02:10,930
the length of the longest common
sub sequence to figure out for

34
00:02:10,930 --> 00:02:15,570
each position i what positions of j of
the other string could be the first match.

35
00:02:18,030 --> 00:02:21,470
Remember, we observed earlier that
the Jaccard distance of two strings can be

36
00:02:21,470 --> 00:02:25,010
expressed as E over E plus

37
00:02:26,580 --> 00:02:29,929
C where E is the edit distance and
C is the length of the LCS.

38
00:02:32,490 --> 00:02:34,680
So, if J is the upper
limit on Jaccard distance,

39
00:02:34,680 --> 00:02:38,640
we have E over E plus C is less than or
equal to J.

40
00:02:41,550 --> 00:02:45,310
From the previous slide, we know
that E is at least i plus j minus 2.

41
00:02:47,950 --> 00:02:53,880
And C is at most L minus i plus 1, where
L is the length of the probe string S.

42
00:02:53,880 --> 00:03:00,706
These two inequalities let us get
a lower bound on E over E plus C,

43
00:03:00,706 --> 00:03:06,028
which using this,
must be less than or equal to J.

44
00:03:06,028 --> 00:03:10,312
That is if we hold C fixed and
vary E, then E over E plus C

45
00:03:10,312 --> 00:03:15,670
is minimized when E is as small as
possible since C is not negative.

46
00:03:17,310 --> 00:03:18,655
If we hold E fixed and

47
00:03:18,655 --> 00:03:23,460
vary C, then E over E plus C is minimized
when C is as large as possible.

48
00:03:24,790 --> 00:03:27,390
If we let E be as low as possible,

49
00:03:27,390 --> 00:03:32,870
that is, i plus j minus 2, and
we let C be as large as possible.

50
00:03:34,050 --> 00:03:39,120
L minus i plus 1, then we can treat
these inequalities as equalities.

51
00:03:39,120 --> 00:03:44,790
Substitute i plus j minus 2 for
E in the inequality.

52
00:03:44,790 --> 00:03:49,410
E over E plus C is equal to or
less than J, which is this.

53
00:03:49,410 --> 00:03:55,610
And substitute C equals L minus
i plus 1 in the same inequality.

54
00:03:57,140 --> 00:04:00,690
And we get this messy formula.

55
00:04:00,690 --> 00:04:01,950
Trust me, that's what you get.

56
00:04:01,950 --> 00:04:03,720
You can work it out yourself.

57
00:04:03,720 --> 00:04:05,090
But there's more messy math.

58
00:04:05,090 --> 00:04:07,520
Our goal is to isolate little j.

59
00:04:07,520 --> 00:04:12,659
So, we can multiply both sides of
the inequality by L plus j minus 1.

60
00:04:14,508 --> 00:04:16,190
Rearrange the terms and voila.

61
00:04:18,790 --> 00:04:23,930
You get an, an upper limit on little j,
the position of the second string,

62
00:04:23,930 --> 00:04:28,370
such that i and j are the first
matching positions of the first string.

63
00:04:29,760 --> 00:04:36,980
The right side of
the inequality is messy in the,

64
00:04:36,980 --> 00:04:42,530
in the extreme, but for a given position i
of the first string, everything is known.

65
00:04:42,530 --> 00:04:48,880
We know the upper limit capital
J on the Jaccard distance and

66
00:04:48,880 --> 00:04:53,706
we know L,
the length of the first string, so

67
00:04:53,706 --> 00:04:58,410
we can calculate the value
of this formula.

68
00:04:58,410 --> 00:05:02,124
To take advantage of the limit on,
on little j that we derived on

69
00:05:02,124 --> 00:05:07,314
the previous slide, we're going to create
a more complicated index structure, where

70
00:05:07,314 --> 00:05:12,450
buckets correspond to pairs consisting
of a single symbol a and a position i.

71
00:05:17,820 --> 00:05:22,567
To index string s, we look at
all the positions in its prefix.

72
00:05:22,567 --> 00:05:25,124
The definition of
the prefix hasn't changed.

73
00:05:25,124 --> 00:05:32,261
It's still floor of J L plus 1.

74
00:05:35,701 --> 00:05:39,749
Where J is the upper limit
on the Jaccard distance and

75
00:05:39,749 --> 00:05:42,150
L is the length of the string s.

76
00:05:43,640 --> 00:05:47,660
We put string s into the bucket a i for
all positions i that

77
00:05:47,660 --> 00:05:52,900
are part of s's prefix where a is
the symbol that s has in its ith position.

78
00:05:56,680 --> 00:06:00,540
Incidentally, we still recommend
the B-tree index by keys a,

79
00:06:00,540 --> 00:06:04,660
i, ordered first by the symbol a,
and then by the position i.

80
00:06:04,660 --> 00:06:07,730
But, if there, there, but there are many
suitable forms of index structure.

81
00:06:07,730 --> 00:06:09,790
And the important thing is that,
given a and

82
00:06:09,790 --> 00:06:13,090
i, we can get to the bucket for
a and i quickly.

83
00:06:17,570 --> 00:06:21,890
To exploit our upper limit on the value
of little j, we're going to make use of

84
00:06:21,890 --> 00:06:27,400
the observation, that given a probe string
s, we only need to find a candidate string

85
00:06:27,400 --> 00:06:33,480
t that might be within Jaccard distance
capital J of string t one time.

86
00:06:33,480 --> 00:06:35,600
We’ll make sure we find
t in the bucket for

87
00:06:35,600 --> 00:06:38,930
the first symbol it has in common with s.

88
00:06:38,930 --> 00:06:42,870
But we may not look for t in buckets for
later symbols that s and

89
00:06:42,870 --> 00:06:48,200
t share even if those occurrences are both
within the prefixes of their strings.

90
00:06:48,200 --> 00:06:53,440
So, we're going to visit the positions i

91
00:06:53,440 --> 00:06:58,230
of string s from the left that is 4i
equals 1, 2, 3, and so on in that order.

92
00:07:00,320 --> 00:07:06,160
and, suppose we find a symbol a in
position i, then we're going to look

93
00:07:06,160 --> 00:07:12,287
in certain buckets a,

94
00:07:12,287 --> 00:07:20,920
j to find candidate strings
t to compare with string s.

95
00:07:20,920 --> 00:07:22,650
When we decide which buckets to look in,

96
00:07:22,650 --> 00:07:25,730
we can assume that none of
the earlier positions of s, that is

97
00:07:25,730 --> 00:07:30,440
the positions less than i, have matched
anything in the candidate string t.

98
00:07:30,440 --> 00:07:33,790
If this assumption is wrong then
t is already a candidate, so

99
00:07:33,790 --> 00:07:41,290
we don't need to worry about missing t for
this value of position i.

100
00:07:42,530 --> 00:07:45,183
That assumption lets us
use the upper bound on j

101
00:07:45,183 --> 00:07:47,367
that we derived two slides previous.

102
00:07:53,405 --> 00:07:57,990
Here's the pseudocode for how we find
candidate matches for probe string s.

103
00:07:59,590 --> 00:08:04,790
First, we do a loop on the positions of i
that are part of the, of the prefix of s.

104
00:08:04,790 --> 00:08:08,412
This loop is just like the simple
form of lookup we described earlier.

105
00:08:08,412 --> 00:08:16,750
In particular this limits i to be only the
positions in the prefix of the string s.

106
00:08:21,550 --> 00:08:27,126
First thing we do is determine the symbol
a in the position i of x of, of string s.

107
00:08:27,126 --> 00:08:34,608
We need that to limit the buckets we
search to only with the right symbol.

108
00:08:34,608 --> 00:08:39,784
again, that's just like
the earlier lookup.

109
00:08:39,784 --> 00:08:41,826
What's new is the inner loop on j,

110
00:08:41,826 --> 00:08:46,135
the position of the target string that
might match the ith position of s.

111
00:08:50,562 --> 00:08:53,824
Notice that the loop limit
is exactly the formula for

112
00:08:53,824 --> 00:08:57,393
the upper bound on j that we de,
de, we derived earlier.

113
00:09:04,521 --> 00:09:08,900
And for each value of j within its limit,
we look in the bucket for symbol a and

114
00:09:08,900 --> 00:09:10,630
position j.

115
00:09:10,630 --> 00:09:12,790
Any string there becomes a candidate for

116
00:09:12,790 --> 00:09:17,010
being within Jaccard distance,
capital J, of string s.

117
00:09:22,330 --> 00:09:22,830
Okay.

118
00:09:22,830 --> 00:09:24,520
So let's take an example of a lookup.

119
00:09:24,520 --> 00:09:28,854
We'll assume J, the upper limit
on Jaccard distances is 0.2.

120
00:09:30,860 --> 00:09:32,160
And here's our probe string.

121
00:09:33,990 --> 00:09:34,930
Its length is ten.

122
00:09:38,290 --> 00:09:39,759
And, how long is its prefix?

123
00:09:39,759 --> 00:09:43,800
Well, JL is 0.2 times 10 or 2.

124
00:09:43,800 --> 00:09:46,400
Add 1, and take the floor and you get 3.

125
00:09:46,400 --> 00:09:50,126
That is, the prefix is ade.

126
00:09:54,497 --> 00:09:56,160
Here's the upper bound on J.

127
00:09:56,160 --> 00:10:00,520
The positions in the buckets in
which we have to look for a given i.

128
00:10:00,520 --> 00:10:04,059
Since, we know everything but i,
we simplify the expression to this.

129
00:10:10,192 --> 00:10:12,649
Remember, j has to be an integer.

130
00:10:12,649 --> 00:10:17,085
So, for i equals 1,

131
00:10:17,085 --> 00:10:22,507
we get 3.8 minus 1, or

132
00:10:22,507 --> 00:10:28,598
2.8 divided by 0.8.

133
00:10:28,598 --> 00:10:30,586
That's 3 and a half.

134
00:10:30,586 --> 00:10:34,770
So, j is equal to or less than 3.

135
00:10:34,770 --> 00:10:36,642
'Kay.

136
00:10:36,642 --> 00:10:45,020
For i equals 2, we get 1.8 divided
by 0.8 or 2 and a quarter.

137
00:10:45,020 --> 00:10:49,050
Thus j j has to be 1 or 2.

138
00:10:50,150 --> 00:10:55,430
And for i equals 3, we get 0.8 divided
by 0.8, so only j equals 1 will do.

139
00:10:56,910 --> 00:10:59,650
Of course, i can't be higher
than 3 because the prefix of

140
00:10:59,650 --> 00:11:02,430
the probe string is only 3 positions long.

141
00:11:02,430 --> 00:11:07,530
But even if we were unaware of that
we'd get a negative upper bound on j for

142
00:11:07,530 --> 00:11:09,060
i equals 4 or greater.

143
00:11:11,230 --> 00:11:13,740
As a result, suppose again
that this is the probe string.

144
00:11:16,610 --> 00:11:18,360
And consider i equals 1.

145
00:11:18,360 --> 00:11:22,920
The first symbol of the string is a,
and if you remember the previous slide,

146
00:11:22,920 --> 00:11:27,230
we determined that for i equals 1,
we need to look at buckets for j up to 3.

147
00:11:27,230 --> 00:11:29,810
Thus, we need to look in these 3 buckets

148
00:11:32,450 --> 00:11:36,890
for possible matches at
Jaccard distance up to 0.2.

149
00:11:36,890 --> 00:11:42,074
For i equals 2, the upper limit on j is 2,
so we look at these 2 buckets.

150
00:11:45,632 --> 00:11:49,971
And finally, for i equals 3,
we look in the bucket, e, 1,

151
00:11:49,971 --> 00:11:55,680
because e is the third symbol of s, and
for i equals 3, the upper limit on j is 1.

152
00:11:55,680 --> 00:11:57,760
No other buckets have to be searched.

153
00:12:03,970 --> 00:12:07,560
We want to convince ourselves that when t
is in none of these six buckets then it

154
00:12:07,560 --> 00:12:10,780
can't be a distance 0.2 or
less from string s.

155
00:12:12,810 --> 00:12:15,485
Then, the edit distance between s and
t is at least 3.

156
00:12:16,610 --> 00:12:21,600
To see why, consider what the first
symbol t has in common with s can be.

157
00:12:21,600 --> 00:12:27,180
If it is an a, then that a is at
least four positions back in t,

158
00:12:27,180 --> 00:12:33,800
because the we would search for
and find t if

159
00:12:33,800 --> 00:12:37,710
a were any of the first three positions,
because we look at those buckets.

160
00:12:37,710 --> 00:12:41,600
If a is at least t,
at least four positions back in t,

161
00:12:41,600 --> 00:12:47,629
then there are three symbols in t that
precede a in the first symbol of s and

162
00:12:47,629 --> 00:12:51,020
therefore there must be

163
00:12:52,040 --> 00:12:57,049
these three symbols of t must
be deleted to convert t into s.

164
00:12:58,910 --> 00:13:01,000
okay.
If the first symbol that t and

165
00:13:01,000 --> 00:13:05,560
s share is d, then it must be at
least three positions back into e and

166
00:13:05,560 --> 00:13:09,500
therefore, there are at least three
symbols not shared by s and t.

167
00:13:09,500 --> 00:13:11,600
Namely a, which is in s but

168
00:13:11,600 --> 00:13:17,300
not in t, and the two symbols
in positions one and two of t.

169
00:13:17,300 --> 00:13:21,040
And similarly, if f, s, and
t share e, but not a or

170
00:13:21,040 --> 00:13:25,570
d, then e is at least two symbols
back in t and we can identify a,

171
00:13:25,570 --> 00:13:29,870
d, and the first symbol of
t as symbols not shared.

172
00:13:29,870 --> 00:13:33,100
And of course, if the first symbol s and
t share is after e,

173
00:13:33,100 --> 00:13:35,350
then a, d, and e are not shared.

174
00:13:38,660 --> 00:13:39,470
And the LCS of s and

175
00:13:39,470 --> 00:13:44,030
t cannot be longer than ten,
because that is the entire length of s.

176
00:13:45,750 --> 00:13:48,160
Therefore, the Jaccard
distance between s and t,

177
00:13:48,160 --> 00:13:53,649
which is e over e plus c is at least
three thirteenths, which is about 0.23.

178
00:13:55,020 --> 00:13:58,059
And surely, greater than
the minimum distance between s and

179
00:13:58,059 --> 00:14:00,364
t that we will accept, which is 0.2.

180
00:14:00,364 --> 00:14:03,568
Thus there's no reason why we
should compare s with any t

181
00:14:03,568 --> 00:14:06,720
that is not in one of six
buckets we actually do search.