Best way to compare strings using pre-built ngrams?

Question

I'm struggling with an n-gram problem and have been hunting the Web for examples to help me out and have noticed n-grams being discussed on this forum. I'm working on a system where we've got scraped titles and are trying to reduce the number of unrecognised texts. There are roughly 60,000 known good titles and about 6,000,000 unmatched titles. 1:100 is not a very impressive ratio. Some of the bad titles aren't in the list of canonical titles and can't ever be matched, but others are failing to be matched because of punctuation/positional/editing/spelling inconsistencies and errors. Typical dirty data.

To avoid confusion I'll clarify what I mean by n-gram as the term is used for two different things. I'm talking n-grams where you break a string into a series of n-length substrings. These are sometimes called "q-grams", for some reason. I'm not talking about something like Google's corpus of word combination "n-grams". So, with a length of 3 for n, the string "hello" breaks down into:

__h
_he
hel
ell
lo_
o__

(The padding before and after isn't always used but, based on my data set, I think that it will be helpful.)

There is a plug-in for MySQL that parses texts into 2-character blocks, but I'm very likely to need lengths of 3 and possibly other lengths. Testing will show what's most effective.

Despite being a programmer for a long time, I'm poor enough at SQL that I haven't sorted out how to build the n-grams or how to rank similarities based on the n-grams. If it comes to it, I can build the n-grams in another language without any trouble and load them all into MySQL. That leaves me with needing to figure out how to construct the SELECT to compare strings.

Do you happen to have or know of an example that you might be able to refer me to?

For background, the rest of the team has been trying to solve this using some code I provided with a variety of algoritms, phonetic and statistical:

• Soundex and metaphone: Not really appropriate for this data (too many languages) and not great on a good day anyway.

• Levenshtein distance, longest common subsequence, and Jaro-Winkler: Much higher quality, but too expensive to run on-the-fly for a data set of this size.

Thanks in advance for any help or suggestions.

Answer 1

I've done this in SQL Server using a modified version of Dice's Coefficient. Basically, you store a precomputed table of q-grams from your lookup data set. This table should have the primary key of the source record, the resulting q-gram, and the number of times that q-gram appears when breaking up the string.

Then when you want to do a lookup, break your input string into a similar list of q-grams (temporary table, subquery, etc.), and join those to your lookup table on the q-gram, grouping by the primary key from the lookup row (which, in the lookup table, is actually a foreign key rather than a primary key). For each matched q-gram, calculate the number of matches as the minimum cardinality between the input value and the lookup table row, e.g. the string 'aaaa' could have 'aa' * 3, and 'aaaaa' could have 'aa' * 4, thus you would have 3 matches. Double this number to get 6.

Once you've got this doubled number of matches, divide by the total number of q-grams obtained from both the input string, and the rows in the lookup table associated with a given primary key. So 'aaaa' would have 3 q-grams, and 'aaaaa' would have 4. You would calculate the similarity as 6/7. You can then filter this similarity quotient based on your desired threshold.

The nice part about this algorithm is that it's fast, since after splitting your input string, it's just a bunch of index lookups. The downside is that it doesn't put any emphasis on ordering of q-grams, so having two words out of order won't affect the match quality (assuming you're not letting q-grams cross word boundaries).

Following is some sample code from SQL Server to explain the concept, but it makes use of features not found in MySQL. You'd probably need to rewrite some of this using subqueries rather than common-table expressions.

CREATE PROCEDURE FuzzyCustomerLookup
    @name varchar(8000),
    @threshold decimal(10,4) = 0.0,
    @limit_results int = 2147483647
AS
WITH inp_q AS ( --Split input string into q-grams
    SELECT
        q.qgram,
        COUNT(*) AS cardinality
    FROM dbo.Qgrams(@name) q --Function to split string into q-grams
    GROUP BY q.qgram
),
matches AS ( --Count matches of input string against each lookup row
    SELECT
        c.row_id,
        SUM(CASE WHEN c.cardinality < i.cardinality THEN c.cardinality ELSE i.cardinality END) AS matches
    FROM CustomerQgrams c --Precomputed table of q-grams
        INNER JOIN inp_q i
            ON c.qgram = i.qgram
    GROUP BY c.row_id
),
dice AS ( --Calculate match quality
    SELECT
        matches.row_id,
        CAST(matches.matches * 2 AS decimal(10,4)) / (CAST(i.cardinality AS decimal(10,4)) + CAST(c.cardinality AS decimal(10,4))) AS similarity
    FROM matches
        INNER JOIN (
            SELECT row_id, SUM(cardinality) AS cardinality
            FROM CustomerQgrams
            GROUP BY row_id
        ) c
            ON matches.row_id = c.row_id
        CROSS JOIN (
            SELECT SUM(cardinality) AS cardinality FROM inp_q
        ) i
)
SELECT TOP (@limit_results)
    ch.CustomerNo,
    ch.CustomerName,
    dice.similarity
FROM dice
    INNER JOIN Customers ch
        ON dice.row_id = ch.row_id
WHERE dice.similarity >= @threshold
ORDER BY dice.similarity DESC