Bon algorithme pour trouver toutes les paires de chaînes entre 2 ensembles afin que tous les mots de la 1ère chaîne soient tous contenus dans la 2ème chaîne ?

Question

J'ai 2 grands jeux de chaînes (en fait, ce sont des noms de produits)."Grand" signifie quelques millions de chaînes.

Exemple:

Ensemble 1 :

Some good product
Another product
Some name
Blah

Ensemble 2 :

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

L'ensemble 1 contient de « bons » noms.L'ensemble 2 contient des noms « sales ».

Je veux: pour chaque élément de l'ensemble 2 (en outre :item2) trouver l'élément le plus long de l'ensemble 1 (plus loin :item1) afin que tous les mots de item1 soient contenus dans item2.

Pour l’exemple donné, les paires seront les suivantes :

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

Jusqu'à présent, je n'ai rien trouvé de mieux qu'un algorithme de force brute :

1. Divisez chaque chaîne de l'ensemble 1 en mots = nous obtenons un ensemble de listes de mots, que ce soit l'ensemble 3
2. Divisez chaque chaîne de l'ensemble 2 en mots = nous obtenons un ensemble de listes de mots, que ce soit l'ensemble 4
3. Choisissez une liste de mots de l'ensemble 3 (plus loin :list3), comparez-le à toutes les listes de mots de l'ensemble 4 jusqu'à trouver une liste entièrement contenue dans la liste3.

Cependant, sa complexité est assez élevée et son fonctionnement est assez lent.Mon implémentation simple prend environ 1,8 s pour trouver 1 paire (l'ensemble 1 contient 3 millions d'éléments, l'ensemble 2 contient 4 millions d'éléments).Si j'implémente la même tâche en utilisant des index MySQL-fulltext (cela permet de rechercher des chaînes contenant tous les mots donnés), alors 1 recherche prend environ 0,4 s.Je me demande donc s'il existe de bonnes approches qui pourraient être appliquées ici avec du petit sang :)

Mon langage de programmation est PHP7.Les données sont stockées dans la base de données MySQL.

Answer 1

Je vais énumérer deux approches possibles qui pourraient être raisonnablement efficaces dans la pratique, bien que leur durée d'exécution dans le pire des cas ne soit pas meilleure que celle que vous avez indiquée.

Indices

Vous pouvez créer un index pour chaque mot.Construisez une table de hachage.Pour chaque mot qui apparaît dans un nom propre, la table de hachage mappe ce mot à une liste de tous les noms sales contenant ce mot.Cette table de hachage peut être construite une fois lors d'une analyse linéaire de l'ensemble des noms sales (Set2).

Ensuite, étant donné un nom propre, parcourez les mots du nom propre.Pour chaque mot, recherchez-le dans la table de hachage, parcourez tous les noms sales qui contiennent ce mot et vérifiez combien de mots il a en commun avec le nom propre.Gardez le meilleur match.

Cela peut être un peu optimisé.Si le nom propre contient un mot qui apparaît dans de nombreux noms sales, la gestion de ce mot sera lente.Ainsi, vous pouvez trouver le nombre de fois où chaque mot apparaît dans un nom sale (sa fréquence) et le stocker dans une table de hachage.Ensuite, étant donné un nom propre, vous pouvez parcourir les mots du nom propre par ordre de fréquence croissante, en gardant une trace de la meilleure correspondance que vous avez trouvée jusqu'à présent.Si vous avez trouvé une correspondance de longueur $\ell$, vous pouvez alors arrêter l'itération plus tôt sans répéter $\ell-1$ mots les plus fréquents dans le nom propre sans manquer aucune correspondance valide.

Essaie

L'ordre des mots dans un nom n'a pas d'importance, alors triez les mots dans chaque phrase.Par exemple, « un bon produit » devient « un bon produit en partie ».Faites ceci pour chaque nom de chaque ensemble.

Ensuite, créez un essai pour représenter l'ensemble des bons noms (Set1).Par exemple, dans votre exemple, le trie sera

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

Maintenant, choisis un sale nom.Nous voulons lui trouver une correspondance à partir du trie.Je vous suggère d'utiliser un algorithme récursif pour trouver toutes les correspondances :pour trouver une correspondance pour le nom $w_1 \cdots w_n$ dans l'essai $T$, vérifiez s'il y a une arête à la racine de $T$ étiqueté $w_1$, et si c'est le cas, recherchez récursivement toutes les correspondances pour $w_2 \cdots w_n$ dans le sous-trie pointé par ce bord ;trouver également de manière récursive toutes les correspondances pour $w_2 \cdots w_n$ dans $T$.Une fois que vous avez trouvé toutes les correspondances, conservez la plus longue.

Par exemple, pour « un autre nom de produit très long », après tri, cela devient « un autre nom de produit très long ».Vous recherchez cela dans le tri en recherchant de manière récursive toutes les correspondances pour « nom long du produit très » dans le sous-tri. +-- product --+, et en trouvant toutes les correspondances pour « nom long du produit très » dans le tri principal.

Ce processus de recherche peut être optimisé de diverses manières, par exemple en gardant une trace de la correspondance la plus longue trouvée jusqu'à présent et en s'arrêtant tôt s'il n'y a aucun moyen pour l'appel récursif de trouver une correspondance plus longue en fonction du nombre de mots que vous avez trouvés jusqu'à présent et de la manière dont il reste beaucoup de mots.

Il n'est pas nécessaire de trier par ordre lexicographique.Vous pouvez trier dans n’importe quel autre ordre, à condition qu’il soit cohérent.Par exemple, vous pouvez trier selon la fréquence des mots dans l'ensemble de données (en commençant par les mots les moins courants), ce qui pourrait contribuer à réduire le nombre d'appels récursifs.