I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings.
Some good product Another product Some name Blah
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.