很好的算法来找到2个集合之间的所有字符串对，以便来自第1个字符串的所有单词都包含在第2个字符串中？

Question

我有2大组字符串（实际上它们是产品名称）。"大"意味着几百万个字符串。

例子：:

第一组:

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

集合1包含"好"名称。集合2包含"脏"名称。

我要: 对于第2组中的每个项目（进一步:item2）从集合1中找到最长的项目（进一步:item1），以便item1中的所有单词都包含在item2中.

对于给定的示例，对将如下所示:

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. 将集合1中的每个字符串拆分为单词=我们得到一组单词列表，让它设置为3
2. 将集合2中的每个字符串拆分为单词=我们得到一组单词列表，让它设置为4
3. 从集合3中获取单词列表（进一步:列表3），将其与集合4中的所有单词列表进行比较，直到找到完全包含在列表3中的列表。

然而，它具有相当高的复杂性和工作相当缓慢。我的简单实现需要大约1.8s才能找到1对（Set1有3mln项，Set2有4mln项）。如果我使用MySQL-fulltext索引实现相同的任务（它允许搜索包含所有给定单词的字符串），那么1搜索大约需要0.4s。所以我想知道是否有一些好的方法可以在这里应用于小血:)

我的编程语言是PHP7。数据存储在MySQL DB中。

Answer 1

我将列出两种可能在实践中相当有效的方法，尽管它们的最坏情况运行时间并不比您列出的更好。

指数

您可以为每个单词建立索引。建哈希表。对于任何干净名称中出现的每个单词，哈希表将该单词映射到包含该单词的所有脏名称的列表。这个hashtable可以在一组脏名（Set2）的线性扫描中建立一次。

然后，给定一个干净的名称，迭代干净名称中的单词。对于每个单词，在哈希表中查找它，并遍历包含该单词的所有脏名称，并检查它与干净名称有多少个单词。保持最佳匹配。

这可以优化一下。如果干净名称包含在许多脏名称中出现的单词，则处理该单词会很慢。因此，您可以找到每个单词在某个脏名（其频率）中出现的次数，并将其存储在哈希表中。然后，给定一个干净的名称，您可以按频率增加的顺序迭代干净名称中的单词，跟踪迄今为止找到的最佳匹配。如果你找到了一个长度匹配的 $\ell$, ，那么你可以在不迭代的情况下提前停止迭代 $\ell-1$ 干净名称中的最高频率单词，不会丢失任何有效匹配项。

尝试

名称中单词的顺序无关紧要，因此对每个短语中的单词进行排序。例如，"一些好产品"变成"一些好产品"。对每个集合中的每个名称执行此操作。

接下来，构建一个trie来表示好名字集（Set1）。例如，在你的例子中，trie将是

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

现在，选择一个肮脏的名字。我们想从trie中找到一个匹配的。我建议你使用递归算法来查找所有匹配项:查找名称的匹配项 $w_1\cdots w_n$ 在trie $T$, ，检查根部是否有边缘 $T$ 贴上标签 $w_1$, ，如果是这样，递归地找到所有匹配 $w_2\cdots w_n$ 在那边缘指向的亚特里;也递归地找到所有匹配 $w_2\cdots w_n$ 在 $T$.一旦你找到了所有的比赛，保持最长的一个。

例如，对于"另一个很长的产品名称"，在排序后，这变成了"另一个很长的名称产品"。您可以在trie中通过递归查找子区域中"长名称产品非常"的所有匹配项来查找 +-- product --+, ，并通过在主trie中查找"长名称产品非常"的所有匹配项。

这个搜索过程可以通过各种方式进行优化，例如，通过跟踪迄今为止找到的最长匹配，如果递归调用无法根据您迄今为止匹配的单词和剩余的单词找到更长的匹配，则提前停止。

没有要求按字典顺序排序。您可以按照任何其他顺序进行排序，只要它是一致的。例如，您可以按整个数据集中单词的频率进行排序（首先进入最不常见的单词），这可能有助于减少递归调用的数量。