I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings.
Example:
Set 1:
Some good product
Another product
Some name
Blah
Set 2:
Very long some product name with words blah
Another very long product name
asd asd sad sad asdsa
Blah blah blah
Set 1 contains "good" names. Set 2 contains "dirty" names.
I want: for every item from Set 2 (further: item2) find the longest item from Set 1 (further: item1) so that all words from item1 are contained in item2.
For the given example the pairs will be the following:
Very long SOME product NAME with words blah => Some name
ANOTHER very long PRODUCT name => Another product
asd asd sad sad asdsa => none
BLAH blah blah => blah
So far I couldn't think of anything better than brute force algorithm:
- Split every string from Set 1 into words = we get a set of lists of words, let it be Set 3
- Split every string from Set 2 into words = we get a set of lists of words, let it be Set 4
- Pick up a list of words from Set 3 (further: list3), compare it to all the lists of words from Set 4 until find some list which is fully contained in the list3.
However it has pretty high complexity and works quite slow. My simple implementation takes about 1.8s to find 1 pair (Set 1 has 3mln items, Set 2 has 4mln items). If I implement same task using MySQL-fulltext indexes (it allows to search for strings which contain all given words) then 1 search takes about 0.4s. So I'm wondering whether there are some good approaches which could be applied here with small blood :)
My programming language is PHP7. The data is stored in MySQL DB.
name product some
would be considered to contain the good namesome name
? $\endgroup$