Хороший алгоритм для поиска всех пар строк между двумя наборами, чтобы все слова из 1-й строки содержались во 2-й строке?

Question

У меня есть 2 больших набора строк (на самом деле это названия продуктов).«Большой» означает несколько миллионов строк.

Пример:

Набор 1:

Some good product
Another product
Some name
Blah

Набор 2:

Very long some product name with words blah
Another very long product name
asd asd sad sad asdsa
Blah blah blah

Набор 1 содержит «хорошие» имена.Набор 2 содержит «грязные» имена.

Я хочу: за каждый предмет из Набора 2 (далее:item2) найти самый длинный предмет из набора 1 (далее:элемент1), чтобы все слова из элемента1 содержались в элементе2..

Для данного примера пары будут следующими:

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

До сих пор я не мог придумать ничего лучше, чем алгоритм грубой силы:

1. Разбиваем каждую строку из Set 1 на слова = получаем набор списков слов, пусть это будет Set 3
2. Разбиваем каждую строку из Set 2 на слова = получаем набор списков слов, пусть это будет Set 4
3. Подберите список слов из набора 3 (далее:list3), сравниваем его со всеми списками слов из набора 4, пока не найдем какой-нибудь список, полностью содержащийся в списке list3.

Однако он имеет довольно высокую сложность и работает довольно медленно.В моей простой реализации поиск одной пары занимает около 1,8 с (набор 1 содержит 3 миллиона элементов, набор 2 — 4 миллиона элементов).Если я реализую ту же задачу с использованием полнотекстовых индексов MySQL (это позволяет искать строки, содержащие все заданные слова), то 1 поиск займет около 0,4 секунды.Вот мне и интересно, есть ли какие-нибудь хорошие подходы, которые можно было бы применить здесь малой кровью :)

Мой язык программирования — PHP7.Данные хранятся в базе данных MySQL.

Answer 1

Я перечислю два возможных подхода, которые могут быть достаточно эффективными на практике, хотя время их работы в худшем случае не лучше, чем то, что вы перечислили.

Индексы

Вы можете создать индекс для каждого слова.Постройте хеш-таблицу.Для каждого слова, которое встречается в любом чистом имени, хеш-таблица сопоставляет это слово со списком всех грязных имен, содержащих это слово.Эту хеш-таблицу можно создать один раз при линейном сканировании набора грязных имен (Set2).

Затем, получив чистое имя, переберите слова в чистом имени.Для каждого слова найдите его в хеш-таблице, переберите все грязные имена, содержащие это слово, и проверьте, сколько слов у него общего с чистым именем.Держите лучший матч.

Это можно немного оптимизировать.Если чистое имя содержит слово, которое встречается во многих грязных именах, обработка этого слова будет медленной.Итак, вы можете найти количество раз, когда каждое слово встречается в каком-то грязном имени (его частоту), и сохранить это значение в хеш-таблице.Затем, получив чистое имя, вы можете перебирать слова чистого имени в порядке возрастания частоты, отслеживая лучшее совпадение, которое вы нашли на данный момент.Если вы нашли совпадение длины $\элл$, то вы можете остановить итерацию раньше, не повторяя ее $\ell-1$ наиболее часто встречающиеся слова в чистом имени, не пропуская ни одного допустимого совпадения.

Пытается

Порядок слов в имени не имеет значения, поэтому сортируйте слова в каждой фразе.Например, «какой-то хороший продукт» становится «каким-то хорошим продуктом».Проделайте это с каждым именем в каждом наборе.

Затем создайте дерево, представляющее набор хороших имен (Set1).Например, в вашем примере дерево будет

+-- another --+-- product --+
|`-- blah --+
|`-- good --+-- product --+-- some --+
 `-- name --+-- some --+

Теперь выберите грязное имя.Мы хотим найти ему соответствие в дереве.Я предлагаю вам использовать рекурсивный алгоритм для поиска всех совпадений:найти соответствие имени $w_1 \cdots w_n$ в дереве $Т$, проверьте, есть ли ребро из корня $Т$ помеченный $w_1$, и если да, то рекурсивно найти все совпадения для $w_2 \cdots w_n$ в подтрие, на которое указывает это ребро;также рекурсивно найти все совпадения для $w_2 \cdots w_n$ в $Т$.Найдя все совпадения, сохраните самое длинное.

Например, для «еще одного очень длинного названия продукта» после сортировки оно становится «еще одним очень длинным названием продукта».Вы ищете это в дереве, рекурсивно находя все совпадения для «продукта с длинным названием» в подтрие. +-- product --+, а также найдя все совпадения для слова «очень длинное имя продукта» в главном дереве.

Этот процесс поиска можно оптимизировать различными способами, например, отслеживая самое длинное совпадение, найденное на данный момент, и останавливая его раньше, если рекурсивный вызов не может найти более длинное совпадение, основываясь на том, сколько слов вы уже сопоставили и как осталось много слов.

Сортировка по лексикографическому порядку не требуется.Вы можете сортировать в любом другом порядке, если он последователен.Например, вы можете выполнить сортировку по частоте слов во всем наборе данных (сначала на наименее распространенные слова), что может помочь уменьшить количество рекурсивных вызовов.