We can do considerably more to limit
our search for candidate matches.
The next step is to consider not
only whether the prefixes of
two strings have a symbol in,
a symbol in, in common.
But, whether the first common symbol
appears close enough to the fronts of
both strings.
The fact that no symbols before
them are common to both strings,
will put a lower bound on
the edit distance of the strings.
And this lower bound in turn
will place a lower bound on
the Jaccard distance between the strings.
When we use a two-dimensional index
based on both the symbol edit,
edit position and the position number
itself, we can cut down the total number
of strings that become candidates for
comparison with a given probe string.
Roughly, by a factor of two.
Suppose, we have strings s and
t and the first position of string s that
matches a symbol in t is at position i.
Moreover, this symbol,
which we shall suppose is a,
matches the symbol in position j of t.
And the first thing we can conclude is
that s has i minus 1 symbols that do
not appear in t.
And t has j minus 1 symbols
that do not appear in s.
Thus the edit distance between s and
t is at least i plus j minus 2.
While we have a lower bound
on the edit distance,
we can also see an upper bound on
the length of the longest common
sub sequence in terms of
the length L of string s.
That is the longest LCS we can
have is when every symbol of s
following the a also appears in t.
These symbols may not be consecutive in t,
but remember that there is
a unique order to the symbols and they
appear in the same order in every string.
so, if s is of length L,
then the longest possible LCS
is of length L minus i plus 1.
That is all but the i minus 1 symbols
of s that precede the symbol a.
Now, we can use the lower bound on
edit distance and the upper bound on
the length of the longest common
sub sequence to figure out for
each position i what positions of j of
the other string could be the first match.
Remember, we observed earlier that
the Jaccard distance of two strings can be
expressed as E over E plus
C where E is the edit distance and
C is the length of the LCS.
So, if J is the upper
limit on Jaccard distance,
we have E over E plus C is less than or
equal to J.
From the previous slide, we know
that E is at least i plus j minus 2.
And C is at most L minus i plus 1, where
L is the length of the probe string S.
These two inequalities let us get
a lower bound on E over E plus C,
which using this,
must be less than or equal to J.
That is if we hold C fixed and
vary E, then E over E plus C
is minimized when E is as small as
possible since C is not negative.
If we hold E fixed and
vary C, then E over E plus C is minimized
when C is as large as possible.
If we let E be as low as possible,
that is, i plus j minus 2, and
we let C be as large as possible.
L minus i plus 1, then we can treat
these inequalities as equalities.
Substitute i plus j minus 2 for
E in the inequality.
E over E plus C is equal to or
less than J, which is this.
And substitute C equals L minus
i plus 1 in the same inequality.
And we get this messy formula.
Trust me, that's what you get.
You can work it out yourself.
But there's more messy math.
Our goal is to isolate little j.
So, we can multiply both sides of
the inequality by L plus j minus 1.
Rearrange the terms and voila.
You get an, an upper limit on little j,
the position of the second string,
such that i and j are the first
matching positions of the first string.
The right side of
the inequality is messy in the,
in the extreme, but for a given position i
of the first string, everything is known.
We know the upper limit capital
J on the Jaccard distance and
we know L,
the length of the first string, so
we can calculate the value
of this formula.
To take advantage of the limit on,
on little j that we derived on
the previous slide, we're going to create
a more complicated index structure, where
buckets correspond to pairs consisting
of a single symbol a and a position i.
To index string s, we look at
all the positions in its prefix.
The definition of
the prefix hasn't changed.
It's still floor of J L plus 1.
Where J is the upper limit
on the Jaccard distance and
L is the length of the string s.
We put string s into the bucket a i for
all positions i that
are part of s's prefix where a is
the symbol that s has in its ith position.
Incidentally, we still recommend
the B-tree index by keys a,
i, ordered first by the symbol a,
and then by the position i.
But, if there, there, but there are many
suitable forms of index structure.
And the important thing is that,
given a and
i, we can get to the bucket for
a and i quickly.
To exploit our upper limit on the value
of little j, we're going to make use of
the observation, that given a probe string
s, we only need to find a candidate string
t that might be within Jaccard distance
capital J of string t one time.
We’ll make sure we find
t in the bucket for
the first symbol it has in common with s.
But we may not look for t in buckets for
later symbols that s and
t share even if those occurrences are both
within the prefixes of their strings.
So, we're going to visit the positions i
of string s from the left that is 4i
equals 1, 2, 3, and so on in that order.
and, suppose we find a symbol a in
position i, then we're going to look
in certain buckets a,
j to find candidate strings
t to compare with string s.
When we decide which buckets to look in,
we can assume that none of
the earlier positions of s, that is
the positions less than i, have matched
anything in the candidate string t.
If this assumption is wrong then
t is already a candidate, so
we don't need to worry about missing t for
this value of position i.
That assumption lets us
use the upper bound on j
that we derived two slides previous.
Here's the pseudocode for how we find
candidate matches for probe string s.
First, we do a loop on the positions of i
that are part of the, of the prefix of s.
This loop is just like the simple
form of lookup we described earlier.
In particular this limits i to be only the
positions in the prefix of the string s.
First thing we do is determine the symbol
a in the position i of x of, of string s.
We need that to limit the buckets we
search to only with the right symbol.
again, that's just like
the earlier lookup.
What's new is the inner loop on j,
the position of the target string that
might match the ith position of s.
Notice that the loop limit
is exactly the formula for
the upper bound on j that we de,
de, we derived earlier.
And for each value of j within its limit,
we look in the bucket for symbol a and
position j.
Any string there becomes a candidate for
being within Jaccard distance,
capital J, of string s.
Okay.
So let's take an example of a lookup.
We'll assume J, the upper limit
on Jaccard distances is 0.2.
And here's our probe string.
Its length is ten.
And, how long is its prefix?
Well, JL is 0.2 times 10 or 2.
Add 1, and take the floor and you get 3.
That is, the prefix is ade.
Here's the upper bound on J.
The positions in the buckets in
which we have to look for a given i.
Since, we know everything but i,
we simplify the expression to this.
Remember, j has to be an integer.
So, for i equals 1,
we get 3.8 minus 1, or
2.8 divided by 0.8.
That's 3 and a half.
So, j is equal to or less than 3.
'Kay.
For i equals 2, we get 1.8 divided
by 0.8 or 2 and a quarter.
Thus j j has to be 1 or 2.
And for i equals 3, we get 0.8 divided
by 0.8, so only j equals 1 will do.
Of course, i can't be higher
than 3 because the prefix of
the probe string is only 3 positions long.
But even if we were unaware of that
we'd get a negative upper bound on j for
i equals 4 or greater.
As a result, suppose again
that this is the probe string.
And consider i equals 1.
The first symbol of the string is a,
and if you remember the previous slide,
we determined that for i equals 1,
we need to look at buckets for j up to 3.
Thus, we need to look in these 3 buckets
for possible matches at
Jaccard distance up to 0.2.
For i equals 2, the upper limit on j is 2,
so we look at these 2 buckets.
And finally, for i equals 3,
we look in the bucket, e, 1,
because e is the third symbol of s, and
for i equals 3, the upper limit on j is 1.
No other buckets have to be searched.
We want to convince ourselves that when t
is in none of these six buckets then it
can't be a distance 0.2 or
less from string s.
Then, the edit distance between s and
t is at least 3.
To see why, consider what the first
symbol t has in common with s can be.
If it is an a, then that a is at
least four positions back in t,
because the we would search for
and find t if
a were any of the first three positions,
because we look at those buckets.
If a is at least t,
at least four positions back in t,
then there are three symbols in t that
precede a in the first symbol of s and
therefore there must be
these three symbols of t must
be deleted to convert t into s.
okay.
If the first symbol that t and
s share is d, then it must be at
least three positions back into e and
therefore, there are at least three
symbols not shared by s and t.
Namely a, which is in s but
not in t, and the two symbols
in positions one and two of t.
And similarly, if f, s, and
t share e, but not a or
d, then e is at least two symbols
back in t and we can identify a,
d, and the first symbol of
t as symbols not shared.
And of course, if the first symbol s and
t share is after e,
then a, d, and e are not shared.
And the LCS of s and
t cannot be longer than ten,
because that is the entire length of s.
Therefore, the Jaccard
distance between s and t,
which is e over e plus c is at least
three thirteenths, which is about 0.23.
And surely, greater than
the minimum distance between s and
t that we will accept, which is 0.2.
Thus there's no reason why we
should compare s with any t
that is not in one of six
buckets we actually do search.