We can be even more restrictive in the set
of candidates that we look for and, and
matches to a given probe string.
In fact, much more restrictive.
We're going to reintroduce the idea we
started with, that the length of strings
are an important similarity clue when
the Jaccard distance must be small.
however, we look not at the length
of the string as a whole but rather,
we build an index structure that takes in
to account both the position of the symbol
in the string's prefix and the length of
the portion of the string that follows it.
We call this length the suffix length.
And it changes as the position varies.
We're now going to see an even
more powerful scheme for indexing.
Here we're going to index on three things.
The first component of the index key or
bucket name is a character at some
position in the prefix of the string.
Remember that the prefix is the position
up to the floor of J L plus one,
that's our usual, function.
Where J is the upper bound
of the car distance and
L is the length of the string.
The second component of the key is the
number of the position in the prefix that
holds the character.
Points one and two are exactly the things
we indexed using the previous method.
And the third component of the key is
the length of the suffix of the string.
That is, the suffix is portion of the
string to the right of the index position.
The addition of the suffix
length as a component of
the index key gives us
the additional advantage that we do
not have to compare two strings if
their lengths are rather different.
Even if they have identical or
almost identical prefixes.
Let's see how we can exploit the fact
that buckets contain only strings with
a particular suffix length to
put a stronger lower bound on
the edit distance between strings.
That will enable us to put a lower
bound on the decard distance.
And for some index buckets,
the lower bound will be so
great that we know we can't
find any matches in the bucket.
So let's consider a probe string S.
And suppose we think we need to
compare S with another string T
because the I'th position of S.
Is the first position of s that
matches any position of t, and
this position is the jth position of t.
Okay, then we can derive a lower bound
on the edit distance between s and
t as follows.
Okay, first, take i plus j minus 2.
This is what we used before as
a lower bound on edit distance.
And is justification is that none of
the first i minus one positions of
s matches any of the first
j minus one positions of t.
So we need to do one edit on each of those
positions to convert s to t or visa versa.
But if we know the suffix lengths for
the two strings involved.
And there is an additional
minimum number of edits equal to
the difference between
the lengths of the two suffixes.
Notice that since the index doesn't
tell us exactly what symbols are in
the suffix of t.
We can't tell for certain where the edits
are needed if we want to convert s to
t by inserts and deletes.
But the strings s and
t may look nothing like each other.
And in fact many edits may be needed.
But we know for certain that only an edit
can chain to the length of a string,
and it changes it by one.
So, we need at least as
many edits in the suffix of
S as the difference in their suffix
lengths if we are to turn S into T.
And an important point to observe is
that because the positions of S and T.
Just before their
suffixes are the same and
all strings have their symbols in sorted
order.The only way we can change s
into t by the least number edits would
be the suffix of s into the suffix of t.
We also have to rethink our upper-bound
on the longest common subsequence, probe
string s and some other string t when
we take into account the suffix length.
So again, we suppose that the first match
between s and t occurs at s's position i.
And it matches the jth position of t.
And let's let a be the symbol
in those positions.
Then the LCS of s and t consists of the a.
And as long as sub-sequences we
can make out of it two suffixes.
We don't know what these suffixes are.
But we're sure that they cannot
have more symbols in common.
And the shorter of the two suffixes.
That's where we get one plus
the length of the shorter
as an upper bound on the length of
the longest common subsequence.
As we did for the second variation where
we considered positions but not suffixes.
We can start with the fact that E over
E plus C is less than or equal to J.
Again, remember that E over E plus
C has its minimum value when E,
the edit distance,
is as low as possible and C,
the, length of the LCS,
is as high as possible.
Thus, we can set E to its lower bound and
C to its upper bound.
And we have a lower bound on J.
But we'll make one more change, writing
E over E plus C equal to or less than J,
which is, of course that,
as E is equal to or
less than J times E plus C.
Simple arithmetic there.
So here's what we get.
Here you can see the lower bound
on E twice that’s that’s this.
And here’s the upper bound on C.
' Kay.
This is
just rearranging the terms
from the line above.
Trust me it, it works.
We now build an index.
Where the keys are triples
consisting of a symbol.
A position holding that symbol.
And a suffix-length.
For each such triple there is a bucket.
And we put into the bucket a, i, k,
those strings s that have symbol
a in position i, and i is a position
in the prefix of s, and the length
of the portion of the string after
position i, that is the suffix, is k.
Here is a simple example.
The string s is a b c d e,
and the lower bound on the Jaccard
distance is cap J is 0.2.
And the prefix of s is
the first 2 positions.
That's because JL is 1, and
the floor of JL + 1 is 2.
So for the first position of s,
the symbol is a,
the position is 1, and
suffix of s after position 1 has length 4.
Okay.
That gives us this bucket.
And we in to that bucket of course,
we'll put string s.
For the second position
the symbol is b and
the suffix length after
position two is three.
That explains this bucket.
There are no more buckets
in to which we put s.
The lookup algorithm is similar
to what we've seen before, but
there are more buckets.
Each probably contains
many fewer strings and
we have a stronger condition that lets us
rule out a larger fraction of the buckets.
So suppose we're given probe string S.
And we want to find strings T that might
be within Jaccard distance J of S.
We look at certain buckets for
each position of the prefix of S.
Here's what we do for position I of S.
First, suppose that eh,
that position contains the symbol A.
Also suppose that the suffix of
the after position i is length k, and
for certain values of j, the position
of string t and m, which is the suffix
of a length of t after its g position
we must look in the bucket a,
j, m, if and only if the following
inequality is satisfied.
Ok this is the inequality we
derived a few slides ago.
It gives us limits on j and
m since I k and
the Jacquard distance
capital J are already known.
Its not all that easy to see what values
are j and m satisfy this inequality but
there’s actually a nice pattern which
we we will show you in a few slides.
So let's see an example of Lookup
with the string abcde again.
And again we'll have j is 0.2.
Okay, here again is the inequality that j
and m have to satisfy for each i and k.
And here are all the buckets
that must be searched.
We'll explain why in, in a minute.
Most of action is when i equals one.
That is, we're considering the por-,
position one of string s.
This position holds a, of course.
When i equals one k,
the suffix length of, of s is four.
If we substitute these values for i and k.
As well as substitute 0.2 for
the Jaccard distance capital J.
Our inequality becomes this.
I'm not going to do all the details here.
But when J equals 1.
It turns out.
That you need m equals 3 4 or
5 in order to satisfy the inequality.
That is m must be pretty close
to 4 the suffix-length of s.
In order to make
the magnitude of 4 minus m.
Be small enough.
' Kay.
The case j equals 1 that's gives rise to
these three buckets.
Which must be searched.
Then consider j equals 2.
Now it turns out that m must be exactly 4.
In order to make the magnitude
of 4-m small enough.
So we get only this bucket for J equals 2.
There is one more bucket, B 1 3.
This comes from the second position
of string S which holds symbol B.
When i equals 2, we have k,
the surface length equal to 3.
And here's what the inequality becomes.
It turns out that we have
only one way to satisfy it.
J has to be 1 and m has to be 3.
So here's my attempt at a picture of the
region in three dimensional space where
the buckets we have to search lie.
One dimension is i,
the position of the probe string
s where we find the first match.
So we'll look at slices for
each value of i starting with i
equals one as we have done here.
The position and the other string
t is the vertical dimension and
the length of the suffix of t
is the horizontal dimension.
The pairs of j and
m that satisfy the inequality.
Form a triangle with peak at k the length
of the suffix for the probe string s.
The reason for the peak is that
there is a term magnitude of
m minus k that obviously grows
with the difference between m and
k and it doesn't matter which is larger.
So what we see is that
the lower the position j,
the bigger the difference between m and
k can be.
Eventually j grows too large.
And there's no value of m equal e,
even m equals k.
That satisfies the inequality
to be satisfied.
When i equals 2 the value.
Of j and the difference between m and
k are more limited so
the triangle is smaller.
Notice also that the value of k has
changed when we increase i the position in
the probe string we decrease k the length
of the suffix by the same amount.
The same change happens for i equals 3.
The triangle gets smaller.
And the value of k shifts to the left.
So that the left sides of
the triangles continue to line up.
Eventually the triangles
become a single point.
And then for the next hirer value
of i there is no triangle at all.
And we can stop our search.
I want to leave with,
with one observation.
We saw three different index schemes with
one, two and three dimensional indices.
The schemes with higher numbers of
dimensions involve searching more
buckets for more matches.
But the total sum of the sizes
of all the buckets, searched or
not, is the same for each scheme.
The reason is that each stream
is placed in the same number of
buckets regardless of the scheme.
That number is our old friend,
floor of JL plus one.
the, length of the prefix of the string.
I claim that the expected number of
strings in all the buckets that we have to
search, given a probe string, goes down
by a factor of two when we add position
information because we search a triangle
instead of the containing rectangle.
When we add suffix length,
we can get a large reduction
in the number of candidates.
Depending on the distribution
of string lengths.
If lengths can vary widely,
the third scheme can eliminate almost all
the false positive candidates we have to
consider using the first two schemes.