Je cherche un algorithme pour résoudre ce qui suit dans une durée raisonnable.
donné un ensemble d'ensembles, trouvez tous ces ensembles sous-ensembles d'un ensemble donné.
Par exemple, si vous avez un ensemble de termes de recherche tels que ["Overflow de pile", "Foo Bar", ...], puis donné un document D, trouver tous les termes de recherche dont les mots apparaissent tous dans d.
J'ai trouvé deux solutions adéquates:
Utilisez une liste des vecteurs de bits comme index. Pour interroger pour un superset donné, créez un vecteur de bit pour cela, puis itérer sur la liste effectuant un bitwise ou pour chaque vecteur de la liste. Si le résultat est égal au vecteur de recherche, le jeu de recherche est un surset de l'ensemble représenté par le vecteur actuel. Cet algorithme est Utilisez un arbre de préfixe (Trie). Trier les ensembles avant de les insérer dans la trie. Lorsque vous recherchez un ensemble donné, triez-la en premier. Itérate sur les éléments du jeu de recherche, activer des nœuds correspondant s'ils sont soit des enfants du nœud racine, soit d'un nœud précédemment activé. Tous les chemins, à travers des nœuds activés à une feuille, représentent des sous-ensembles du jeu de recherche. La complexité de cet algorithme est Quelle est votre solution?
O (n) où n est le nombre d'ensembles dans l'index, et le bit bit ou est très rapide. L'insertion est o (1) . CAVEAT: Pour soutenir tous les mots de la langue anglaise, les vecteurs de bits devront être de plusieurs millions de bits longs et il faudra exister une commande totale pour les mots, sans lacunes.
O (un journal A + AB) où a est la taille du jeu de recherche et B est le nombre de ensembles indexés.
3 Réponses :
Le préfixe Trie ressemble à quelque chose que j'essayais si les ensembles étaient clairsemés par rapport au vocabulaire total. N'oubliez pas que si le suffixe défini de deux préfixes différents est identique, vous pouvez partager le sous-programme représentant l'ensemble de suffixe (ceci peut être atteint par la consommation de hachage plutôt que la minimisation de la DFA arbitraire), donnant un dag plutôt qu'un arbre. Essayez de commander vos mots les moins ou les plus fréquents en premier (je parierai que l'un ou l'autre est meilleur qu'un ordre aléatoire ou alphabétique).
Pour une variation de votre première stratégie, où vous représentez chaque ensemble par un très grand nombre d'entiers (vecteur de bits), utilisez un ensemble de cartographe commandé de manière clairsemétrique / carte des entiers (une trie sur la séquence des bits qui saute des courses consécutives) - http://citeeerx.ist.psu.edu/viewdoc /summary?diofoI=10.1.1.37.5452 (implémenté dans http://www.scala-lang.org/docu/files/aPI/scala/collection/immutable/intmap.html ).
Si votre ensemble de référence (d'ensembles) est corrigé et que vous souhaitez trouver pour de nombreux ensembles contenant les autres, je calculerais la relation de confinement immédiate (un graphique acyclique dirigé avec un chemin de A-> B IFF B est contenu dans A, et sans les arcs redondants A-> C où A-> B et B-> C). Le facteur de ramification n'est pas plus que le nombre d'éléments dans un ensemble. Les sommets accessibles à partir de l'ensemble donné sont exactement ceux qui sont sous-ensembles de celui-ci.
D'abord, je construirais 2 structures de données, s et E.
s est une matrice d'ensembles (Set S a les sous-ensembles N). P>
for i in C:
if C[i] == S[i].Count()
// S[i] subset exists in D
Pouvez-vous créer un index pour vos documents? C'est-à-dire une cartographie de chaque mot à ces documents contenant ce mot. Une fois que vous avez construit cela, la recherche devrait être assez rapide et vous pouvez simplement définir l'intersection pour trouver les documents correspondant à tous les mots.
Voici wiki sur Recherche en texte intégral .
EDIT: OK, j'ai eu ça en arrière.
Vous pouvez convertir votre document en un ensemble (si votre langue dispose d'un type de données défini), faites de même avec vos recherches. Ensuite, cela devient une simple question de tester si on est un sous-ensemble de l'autre.
Dans les coulisses, c'est effectivement la même idée: cela impliquerait probablement de construire une table de hachage pour le document, de haquer les requêtes et de vérifier chaque mot dans la requête à son tour. Ce serait O (nm) où n est le nombre de recherches et m le nombre moyen de mots dans une recherche.
Je fais l'inverse. Compte tenu d'un million de recherches et d'un document, trouvez toutes les recherches correspondant au document donné votre méthode.
Passez-vous une commande sur vos séries? En d'autres termes, est l'ensemble {A, B} identique à la série {B, A}? Aussi, pour (2)? Qu'est-ce que vous triez réellement dans la première ligne? Il semble que vous devez d'abord résoudre le problème pour appliquer votre algorithme. (Bien que je suis probablement mal compris).
Êtes-vous préoccupé par des multisets? Le document ("défini") peut-il contenir plusieurs instances du même élément? Que diriez-vous de l'un des ensembles de recherche (membre de l'ensemble des ensembles)? C'est à dire. Si le document indique "Je ne lirai pas un livre que j'ai déjà lu", la recherche "Lire la lecture de livre" correspondrait, mais "Lire la lecture de livre de lecture" ne serait pas.
Non, pas préoccupé par les multisets du tout.
La 2e approche a très bien fonctionné pour moi pour résoudre un problème similaire. J'ai réduit 14 heures de temps d'exécution de l'approche naïve à 2 minutes (!) Avec la trie.