Testing phrases to see if they match each other

Question

I have a large number of phrases (~ several million), each less than six or seven words and the large majority less than five, and I would like to see if they "phrase match" each other. This is a search engine marketing term - essentially, A phrase matches B if A is contained in B. Right now, they are stored in a db (postgres), and I am performing a join on regexes (see this question). It is running impossibly slowly even after trying all basic optimization tricks (indexing, etc) and trying the suggestions provided.
Is there an easier way to do this? I am not averse to a non-DB solution. Is there any reason to think that regexes are overkill and are taking way longer than a different solution?

Answer 1

It would be great to get a little more context as to why you need to see which phrases are subsets of others: for example, it seems strange that the DB would be built in such a way anyway: you're having to do the work now because the DB is not in an appropriate format, so it makes sense that you should 'fix' the DB or the way in which it is built, instead.

It depends massively on what you are doing with the data and why, but I have found it useful in the past to break things down into single words and pairs of words, then link resources or phrases to those singles/pairs.

For example to implement a search I have done:

Source text:

Testing phrases to see

Entries:

• testing
• testing phrases
• phrases
• phrases to
• to
• to see
• see

To see if another phrase was similar (granted, not contained within) you would break down the other phrase in the same way and count the number of phrases common between them.

It has the nice side effect of still matching if you were to use (for example) "see phases to testing": because the individual words would match.. but because the order is different the pairs wouldn't, so it's taking phrases (consecutive words) into account at the same time, the number of matches wouldn't be as high, good for use as a 'score' in matching.

As I say that -kind- of thing has worked for me, but it would be great to hear some more background/context, so we can see if we can find a better solution.

Answer 2

When you have the 'cleaned column' from MaasSQL's previous answer, you could, depending on the way "phrase match" works exactly (I don't know), sort this column based on the length of the containing string.

Then make sure you run the comparison query in a converging manner in a procedure instead of a flat query, by stepping through your table (with a cursor) and eliminating candidates for comparison through WHERE statements and through deleting candidates that have already been tested (completely). You may need a temporary table to do this.

What do I mean with 'WHERE' statement previously? Well, if the comparison value is in a column sorted on length, you'll never have to test whether a longer string matches inside a shorter string.

And with deleting candidates: starting with the shortest strings, once you've tested all strings of a certain length, you'll can remove them from the comparison table, as any next test you'll do will never get a match.

Of course, this requires a bit more programming than just one SQL statement. And is dependent on the way "phrase match" works exactly.

DTS or SSIS may be your friend here as well.

Answer 3

An ideal algorithm for doing sub-string matching is AhoCorsick.

Although you will have to read the data out of the database to use it, it is tremendously fast, when compared to more naive methods.

See here for a related question on substring matching:

And here for an AhoCorsick implementation in Java: