Je cherche à optimiser un algorithme assez simple qui est actuellement
o (n 2 sup>) em>. J'ai un fichier d'enregistrements, où chacun doit
être comparé à tous les autres dans le même fichier. Si les deux sont le
'idem' (la fonction de comparaison est assez compliquée), le
Les enregistrements sont la sortie. Notez qu'il peut y avoir plusieurs enregistrements correspondant
l'autre, et il n'y a pas de sens de l'ordre - uniquement si la correspondance est vraie ou fausse. em> b> pseudo code: p>
1,Joe Smith,Daniel Foster
2,Nate Johnson,Drew Logan
3,Nate Johnson, Jack Crank
4,Joey Smyth,Daniel Jack Foster
5,Joe Morgan Smith,Daniel Foster
Expected output:
Records 1,4,5 form a match set
End of output
10 Réponses :
En supposant que les fichiers ne soient pas ridiculement importants, je passerais dans le fichier dans son intégralité et calculez un hash pour la ligne et gardez une trace de combinaisons de hachage / ligne # (ou de pointeur de fichier). Trier ensuite la liste des hayes et identifiez ceux qui apparaissent plus d'une fois.
Cela ne fonctionnera pas dû aux collisions de hachage. Pourquoi ne pas simplement utiliser une table de hachage?
Le problème est de concevoir une fonction de hachage qui n'existe qu'un seul enregistrement n'est pas possible (au moins, je ne sais pas comment cela pourrait être fait). En outre, la fonction de comparaison peut retourner true quand les octets (A)! = BYTES (B).
Il s'agit d'un schéma de type MINHASH assez simple a bien fonctionné. Il n'atteint pas tous les «doublons» mais assez bon pour le travail gouvernemental ...
Venez simplement passer chaque enregistrement de votre fichier et insérez-les dans une table de hachage. À chaque étape, vérifiez si l'enregistrement est déjà dans la table de hachage. Si c'est le cas, alors la sortie. Cela peut être fait dans O (n).
+1. L'OP devra programmer une fonction de hachage appropriée (en fonction des détails de la comparaison). Mais la fonction de hachage n'a pas besoin d'être parfaite; Même s'il y a des collisions, cela devrait toujours être une amélioration.
Il y a le frottement. Je ne pense pas qu'il existe un moyen de créer une fonction de hachage ... Si vous regardez les données, je ne sais pas comment le hachage peut être généré pour tomber dans une situation de type «proche proximité».
Oh, quand j'ai lu la "même", j'ai supposé que c'était une relation d'équivalence et une transitivité implicite. Si ce n'est pas une relation d'équivalence, alors il devient très délicat ...
Divisez chaque ligne en noms, appliquez une transformation canonicalisation comme Soundex sur chaque nom et indexez la ligne sous chaque nom.
Nous devrions en savoir plus sur votre fonction de comparaison. Votre comparaison est-elle transitive? (C'est-à-dire que a == b et b == c implique a == C?) Est-ce réflexif? (Est-ce que a == b implique B == A?)
Si votre fonction de comparaison est transitive et réflexe, et que de nombreux enregistrements étant égaux sont courants, vous pouvez inclure vos enregistrements en groupes en les comparant à un "échantillon représentatif" du groupe. Qui pourrait approcher O (n) dans le meilleur cas.
Notez que le hachage Les enregistrements supposent hachage (a) == hachage (b) <=> comparer (A, B) == vrai, mais si la comparaison (A, B) peut être vraie même lorsque les octets (A)! = octets (b) Il pourrait être délicat de concevoir un algorithme de hachage approprié.
La fonction est transitive et réflexive. Le problème est que la fonction de comparaison peut retourner true quand des octets (A)! = Bytes (B). En fait, l'idée est d'identifier «similaire» A et B.
@CBannerjee: Êtes-vous certain que c'est transitif? Les mesures de la similitude de chaîne ne sont généralement pas. Par exemple, si joey est similaire à joesy , et joesy est similaire joshy et joshy < / code> est similaire à josh , est-ce que joey est similaire à josh ?
Je recommanderais quelque chose basé sur le groupement alors. Voici une autre suggestion de regroupement: définissez un entier 32 ou 64 bits en tant qu'ensemble d'indicateurs de bits indiquant la présence d'une caractéristique distinctive susceptible de signifier que les enregistrements sont similaires. Ensuite, décidez des enregistrements de comparer d'abord en fonction des similitudes de leurs masques de bit. (Comparez dans l'ordre de BitCount (masque (a) et masque (B)).) C'est comme le hachage, mais flou. EDIT: Vous voudrez peut-être examiner les techniques d'AI ou les techniques de données plutôt que de le former comme un problème d'algorithmes.
@Steve Jessop: Vous avez raison. Ce n'est pas transitif, mais c'est réflexif. Je pense avoir répondu réflexe
Je ne suis pas sûr des propriétés de votre comparateur et du jeu de données, mais en supposant que votre comparateur définit une relation d'équivalence sur vos lignes, voici rien:
Notez que dans le pire des cas, selon votre description de votre problème, vous ne pouvez pas obtenir de mieux que O (n ^ 2), simplement parce qu'il peut y avoir o (n ^ 2) résultats d'enregistrements correspondants que vous devez produire!
Hmmm..Intriguer la possibilité. Je vais faire la recherche ça!
Une carte sera soit basée sur un arbre ou une table de hachage, et le problème ne se prête pas à une fonction de commande ou à une fonction de hachage.
@Mark Ransom: Je cherchais juste les implémentations de la carte et je suis sûr que vous avez raison - ma fonction de comparaison ne renvoie que t ou f - pas une commande.
@cbannerjee mais est-ce que c'est hachable? C'est une propriété différente pour commander.
Fyi Mapreduce sera Pour améliorer votre temps mural, la chose n ° 1 à faire est de trouver des moyens d'éviter de devoir exécuter la comparaison. Toute façon de faire ça sera une victoire. Et même si votre logique de comparaison est complexe, vous pouvez toujours utiliser le tri pour aider.
Par exemple, supposons que vous ayez une dimension que ces données sont étendues. Les données qui varient en trop dans cette dimension est garantie de ne pas comparer égale, bien que la dimension ne garantit pas l'égalité. Ensuite, ce que vous pouvez faire est de trier vos données par cette dimension, puis n'exécutez que des comparaisons entre les éléments proches de cette dimension. Voilà! La plupart des comparaisons O (n * n) sont maintenant parties.
Rendons-le plus complexe. Supposons que vous puissiez identifier deux de ces dimensions indépendantes les unes des autres. Trier vos données le long des premières dimensions. Divisez les données dans la première dimension en bandes. (Faites que les bandes se chevauchent au maximum, elles peuvent varier dans cette dimension et comparer encore égale.) Prenez maintenant chaque bande et triez-la par la deuxième dimension. Puis exécutez des comparaisons entre paires d'éléments qui sont acceptablement à proximité de cette dimension et comprennent la paire de votre réponse si elle se compare égale, et c'est la première bande qu'il pourrait apparaître. (Cette logique dédénagée est nécessaire car le chevauchement peut signifier que le chevauchement peut signifier qu'un La paire qui se compare peut apparaître dans plusieurs bandes.) Ceci est probablement encore meilleur que la première approche car vous avez réussi à réduire les choses de sorte que vous comparez seulement des lignes avec un petit nombre de lignes "à proximité". / p>
Si vous souhaitez utiliser moins de ressources, vous devez vous concentrer sur les moyens d'éviter de faire des comparaisons individuelles. Tout ce que vous proposez sur ce chemin aidera.
Trier purement les données ne permettra pas de ne pas aider les données à cause de la quantité énorme de variabilité dans les données entrantes. Ce qui serait idéal, c'est peut-être l'alphabet Trier les champs et assigner Quelques type de fonction de hachage à chaque ligne, puis trier sur ce hachage. Malheureusement, j'ai du mal à trouver un hachage intelligent pour faire cela.
@CBannerjee: Si les données ont une variabilité de cela, et vous avez quelque chose que vous pouvez trier et dire définitivement «cette ligne ne doit pas nécessairement être comparée à rien de plus loin que celui-ci», puis triez aidera beaucoup. Sinon, il existe une multitude d'autres variations de l'astuce qui pourrait aider. Mais il n'ya aucun point dans mes possibilités énumérables sans avoir à savoir quoi que ce soit utile de votre fonction de comparaison.
Comme vous l'avez déjà mentionné, vous n'aurez pas la chance que cela va être meilleur que O (n ^ 2), mais vous pouvez paralliser cela.
J'ai une solution de travail qui fonctionnera avec HDFS, vous pouvez l'étendre avec l'utilisation de cache distribuée. p> à l'aide de l'entrée dans la source.txt: p> et cible.txt p> john meat john
C'est exactement ce que je pensais - merci encore une fois! Je vais examiner la séquencefile pour la cible afin que l'itération soit plus rapide que possible. Une note connexe, je suis toujours intriguée pour essayer de mapperduire le fichier cible pour essayer de parallémenter la solution.
Si vous avez besoin d'aide, n'hésitez pas à revenir avec une autre question connexe. Je serai heureux de vous aider.
Merci! Je vais mettre en œuvre mon réducteur personnalisé et je devrais être défini. Si je découvre comment mapper le fichier cible, je vous le ferai certainement de savoir!
Vous n'avez pas mentionné quel pourcentage de l'entrée est censé correspondre, ou à quelle fréquence vous pourriez obtenir un match exact par rapport à une correspondance inexacte. Si vous pouvez faire un petit pré-traitement pour réduire la taille du problème, cela pourrait être une grande aide.
Si vous triez simplement l'entrée et exécutez votre fonction de comparaison sur des entrées adjacentes, vous risquez de faire suffisamment de doublons pour rendre le N ^ 2 seconds passe supportable.
J'essaie de revenir à la source pour que les données sont plus petites, et voir également s'il y a des moyens intelligents, nous pouvons trier d'abord pour rendre le nombre de comparaisons plus petites ...
Si vous vraiment ne peut rien faire mieux qu'une relation d'équivalence opaque, votre pire des cas sera toujours O (n ^ 2) - par exemple, pour le cas où il n'y a pas de correspondances , vous devrez comparer chaque paire pour vous assurer de cela. (Comme les gens l'ont mentionné, vous pouvez paralleller cela, mais cela ne sera toujours pas particulièrement difficile pour des centaines de millions de documents; cela ne vaut peut-être pas le coût des ressources nécessaires pour le faire de cette façon).
généralement, cependant, il y a un meilleur moyen de le faire.
Si vous avez vraiment une relation d'équivalence (c'est-à-dire que si vous avez une garantie logique que si correspondez (A, B) = correspondez (B, C) = true, puis correspondez (A, C) est également vrai) est également vrai) , il y a probablement des forme canonique que vous pouvez convertir vos enregistrements en hachage et / ou commande.
Dans votre exemple, vous semblez correspondre à des variantes de "Joe Smith". Si tel est le cas, vous pouvez probablement augmenter vos critères de comparaison pour choisir un membre particulier de la classe d'équivalence pour représenter le tout. E.G., choisissez "Joseph" de représenter tous les noms équivalents à "Joe", "Smith" pour représenter tous les noms équivalents à "Smythe", etc.
Une fois que vous avez apporté cette transformation, vous pouvez utiliser une table de hachage pour réduire votre opération à O (N), plutôt que O (n ^ 2).
La question est que la fonction n'est pas transitive. J'essaie de réduire la taille du problème (en revenant au client et en expliquant la nature de la croissance N ^ 2), puis de fusionner ultérieurement les résultats. J'essaie également de trouver une sorte de fonction de hachage, ce qui me permettra de "rayer" des données triées et de comparer une gamme prédéfinie du hachage.
Merci à toutes les grandes suggestions.
Après avoir suivi des options, il semble que la meilleure approche compte tenu de ma chronologie consiste à utiliser un cadre MapReduce pour parallementer le problème et à lancer plus de matériel. Je me rends compte que cela ne réduit pas la complexité O (n 2 ).
La seule solution possible que je puisse penser consiste à exécuter un type de minuscule sur les données, à rayer les données dans des sections qui se chevauchent et à comparer dans les rayures et les chevauchements. Cela devrait réduire le nombre de comparaisons, mais je ne suis pas sûr à quel point la course au hasard sera chère.
Comme indiqué par Btille, vous n'avez pas besoin de transitivité pour classer les enregistrements. Dans le cas des noms d'anglais, vous pouvez représenter chaque nom par deux initiales et chaque enregistrement par une liste triée des initiales. Ensuite, il vous suffit d'exécuter la comparaison complète O (n ^ 2) entre des enregistrements de la même classe. Il y a le problème supplémentaire que la même paire d'enregistrements peut apparaître dans plusieurs classes, mais il est facile de détecter en maintenant une collection séparée de paires d'enregistrements correspondants (identifiés par des indices d'enregistrement).
Dans l'exemple, vous mettriez record 1 en classe "DF, JS", record 2 en classe "DL, NJ", record 3 en classe "JC, NJ", record 4 en classes "DJ, JS" , "JF, JS" et "DF, JS", et record 5 dans les classes "DF, JM", "DF, JS" et "DF, MS". Vous obtenez un total de 7 cours: "DF, JM", "DF, MS", "DF, JS", "DJ, JS", "DL, NJ", "JC, NJ", "JF, JS", dont Seule classe "DF, JS" contient plusieurs enregistrements, nommément enregistrements 1, 4 et 5. Ainsi, dans cet exemple, il suffit d'exécuter la fonction de comparaison complète deux fois.
D'autre part, il y a le problème que les gens ont des noms bizarres. Cette entrée de blog sur le sujet mérite un look si vous Je ne l'ai pas vu auparavant. ce que vous faites, vous allez manquer quelques matchs.
Donnez-moi un exemple d'enregistrement. pls. Vous devez savoir que vous peut trier vos données de toutes les données, et ce sera O (n * journal (n));
Vous ne pouvez pas lire le fichier entier dans une collection? Vous pouvez alors simplement trier la collection et le surtout pour voir quels éléments adjacents sont des duplicats. Il le changerait de
O (n * n) àO (n * journal (n))S'il n'y a vraiment aucun moyen de trier votre collection (en utilisant toutes les techniques - hachage, etc.), il restera toujours O (N ^ 2) puisque vous devrez comparer chaque élément à tous les autres éléments. Cela signifie que vous aurez une complexité de "N choisissez 2" = n! / (2! * (N-2)!) = N * (N-1) / 2 = 0,5 * N ^ 2 - 0.5 * N == O (n ^ 2)
Nous avons besoin de plus de détails sur le comparateur. Les détails de la fonction comparateur détermineront à quel point cela peut être optimisé. Par exemple, s'il s'agit d'une identité d'octet-pour-octet, vous pouvez utiliser le hachage. S'il y a des champs dont la commande n'a pas d'importance, vous pouvez utiliser un hachage après avoir tri des champs. Si les fichiers sont équivalents si un programme qu'elles décrivent ne s'arrêtent pas après un million de marches lorsqu'il est donné l'autre fichier ... pas si facile à optimiser.
La fonction comparateur renvoie basciellement vrai si deux enregistrements correspondent. Et n'est pas une fonction triviale ...
Les fichiers seront énormes. Je ne peux pas les lire dans une collection en mémoire. «Tri» (si cela est possible) Les enregistrements ne produisent pas de duplicats à se retirer facilement. Les résultats peuvent être un match «proche» ou «flou».
Compte tenu de vos échantillons de données, vous pouvez trier / hacher les enregistrements en fonction de la première lettre du nom de famille de chaque personne. Bien sûr, vous auriez toujours des éléments qui sont égaux dans le tri / hachage, mais pas égaux selon le comparateur, et dans chaque classe d'équivalence, vous devez comparer toutes les couples les uns contre les autres. Donc, c'est toujours O (n ^ 2), mais au moins vous (probablement) n'a pas
4 * 10 ^ 16 paires à faire.Donc, la comparaison n'est même pas transitive?
Le problème en utilisant MapReduce ici, est que vous avez besoin d'une clé commune pour nourrir votre réducteur. Comment est le comparète ()?
Pour Mapreduce, je prévoyais d'utiliser un TextInputformat, de sorte que les clés seraient les numéros de ligne et les valeurs seraient les enregistrements. Je vais itération sur l'ensemble des enregistrements cible (dans l'espoir de briser cela à l'aide d'une carte différente) et d'émettre l'enregistrement de la source comme clé et enregistrez de la cible comme valeur. La réduction prendra les enregistrements source sous forme de clés et émettra une liste des enregistrements cibles. Devrait fonctionner, oui? Ma principale préoccupation est également d'essayer de diviser également le fichier cible, car ce serait comme avoir deux «intrants» dans MapReduce.
Avec le piratage de l'INPORTFORMAT et RecordReader, cela sonne bien. Je pourrais éventuellement avoir une meilleure façon si vous pouvez expliquer comment fonctionne la logique de comparaison.
La logique Comparaison vérifie un certain nombre de choses comme une correspondance exacte et une correspondance floue sur plusieurs champs dans l'enregistrement. Il n'entraîne que T / F lorsque la correspondance de l'enregistrement de la source et de la cible. Après avoir pensé un peu à ce sujet, je ne sais pas comment je vais gérer les deux fichiers d'entrée (source et cible). La pensée initiale consiste à placer la cible dans la liaison distribuée et itérairez-la avec les enregistrements du fichier source, qui sera divisé par l'entrée de TextInpuPormat.
Je vous recommanderais de mettre en œuvre vos propres classes d'écriture et de valeur, et dans la touche, laissez le comparète () faire la même logique que votre fonction Comparer (). Si c'est faux, vous retournez -1 au lieu de 0. C'est un hack nifty, mais cela fonctionne. Ensuite, vous pouvez soumettre tous vos fichiers dans un seul emploi. Je peux configurer une réponse pour cela.
En fait, cela ne fonctionnera pas ... juste essayé pour moi-même. Principalement parce que chaque sortie de fichier est triée en soi, et ensuite, elle est fusionnée. La fusion ne vous donnera pas le bon résultat. Désolé, n'a pas attrapé ça. Si cela ne vous dérange pas, je vous fournirais une implémentation similaire à l'aide de HDFS et itérant sur le fichier plus tard.
Merci. Je pouvais juste le digérer et je suis arrivé à une conclusion similaire. Je pense que la question est de savoir comment distinguer la source et le fichier cible. Comme je l'ai dit qu'une option consiste à placer la cible dans le cache-cache et à transmettre la source sous forme de textinputformat sur le mappeur (il doit diviser le fichier source et itérer sur la cible dans le cache). Je suis à peu près sûr que cela fonctionnera, mais il semble que des déchets ne soient pas en mesure de mapper le fichier cible en plus petits morceaux, puis de réduire les travaux sur des morceaux de la source et de la cible.
@Thomasjungblut, laissez-nous Continuer cette discussion en chat
J'ai fourni une nouvelle réponse.