J'ai un corpus de 900 000 cordes. Ils varient en longueur, mais ont un nombre moyen de caractères d'environ 4 500. J'ai besoin de trouver le moyen le plus efficace de calculer le coefficient de dés de chaque chaîne en ce qui concerne chaque autre chaîne. Malheureusement, cela se traduit par l'algorithme de coefficients de dés utilisé quelque 810 000 000 000 $.
Quelle est la meilleure façon de structurer ce programme pour une efficacité accrue? Évidemment, je peux empêcher de calculer les dés des sections A et B, puis B et A - mais cela ne fait que réduire à moitié le travail requis. Devrais-je envisager de prendre des raccourcis ou de créer une sorte d'arbre binaire? P>
J'utilise la mise en œuvre suivante de l'algorithme de coefficient de dés en Java: P>
public static double diceCoefficient(String s1, String s2) {
Set<String> nx = new HashSet<String>();
Set<String> ny = new HashSet<String>();
for (int i = 0; i < s1.length() - 1; i++) {
char x1 = s1.charAt(i);
char x2 = s1.charAt(i + 1);
String tmp = "" + x1 + x2;
nx.add(tmp);
}
for (int j = 0; j < s2.length() - 1; j++) {
char y1 = s2.charAt(j);
char y2 = s2.charAt(j + 1);
String tmp = "" + y1 + y2;
ny.add(tmp);
}
Set<String> intersection = new HashSet<String>(nx);
intersection.retainAll(ny);
double totcombigrams = intersection.size();
return (2 * totcombigrams) / (nx.size() + ny.size());
}
4 Réponses :
Vous devez trouver une sorte d'inégalité comme: D (x1, x2)> 1-p, d (x1, x3) <1-q et p d (x2, x3) <1-q + p. Ou quelque chose comme ça. Maintenant, si 1-q + p <0,9 0,9, alors vous n'avez probablement pas à évaluer d (x2, x3).
PS: Je ne suis pas sûr de cette inégalité exacte, mais j'ai un incitateur que cela pourrait avoir raison (mais je n'ai pas assez de temps pour faire les dérivations maintenant). Recherchez certaines des inégalités avec d'autres mesures de similitude et voyez si l'un d'entre eux est valable pour les dés co-efficaces.
=== aussi ===
S'il y a un élément dans la définition A, et si votre seuil est R (= 0,9), puis réglez B doit avoir le nombre d'éléments B devrait être tel que: R * A / (2-R) <= = B < = (2-r) * A / R. Cela devrait éliminer le besoin de beaucoup de comparaisons IMHO. Vous pouvez probablement trier les cordes en fonction de la longueur et utiliser la fenêtre décrit ci-dessus pour limiter les comparaisons.
Leur Charset Limited est-il en quelque sorte? Si tel est le cas, vous pouvez calculer le nombre de caractères par code dans chaque chaîne et comparer ces chiffres. Après un tel pré-calcul (il occupera 2 * 900K * S octets de mémoire [si nous supposons que aucun caractère ne se trouve plus de 65k temps dans la même chaîne], où S est un nombre de caractères différent). Ensuite, calculer le coefficent prendrait une heure (s). Bien sûr, cela serait utile s'il serait <4500.
Le Charset est limité à tous les caractères alphanumériques et à l'espace. Je suis un peu incertain sur la manière de mettre en œuvre votre méthode.
Il est similaire à ce que Xavier Holt a dit dans l'article 3: vous calculez le nombre de chaque bigram (j'ai commis une erreur et pensais que vous n'avez besoin que des lettres seulement, mais cela ne change pas la nature de l'algorithme) dans chaque chaîne, stockez-la à un tableau , alors vous comparez uniquement ces numéros de comptage Bigram. L'inconvénient est qu'il faut beaucoup d'espace.
Fabriquez une seule passe sur toutes les chaînes et accumulez un hashmap qui correspond à chaque bigram à un ensemble d'index des cordes qui contiennent ce bigram. (Vous construisez actuellement le groupe Bigram 900 000 fois, redondant, pour chaque chaîne.)
Passez ensuite à tous les ensembles et construisez une hache de [index, index] à des couples commun-bigram. (La dernière carte ne doit pas contenir de paires de touches redondantes, telles que [1,2] et [2,1] - stocker simplement l'une ou l'autre.)
Ces deux étapes peuvent facilement être paralléléées. Si vous avez besoin d'un exemple de code, merci de me le faire savoir.
Je vous suggère de continuer à rechercher des algorithmes pour déterminer la similitude entre les chaînes, essayez de la mettre en œuvre quelques-uns, et de les exécuter sur un jeu de chaînes plus petit pour voir à quel point ils fonctionnent.
Disclaimer d'abord: cela va pas réduire le nombre de comparaisons que vous devrez faire. Mais cela devrait faire une comparaison de dés plus rapide.
1) Ne construisez pas vos hashsets à chaque fois que vous faites un appel dicecoeFIFIER ()! Il devrait accélérer considérablement les choses si vous le faites simplement une fois pour chaque chaîne et gardez le résultat autour.
2) Puisque vous ne vous souciez que si un BIGRAM particulier est présent dans la chaîne, vous pouvez vous éloigner avec un bitset avec un peu pour chaque bigram possible, plutôt qu'un hashmap complet. Le calcul du coefficient serait alors simplifié pour anding deux jeux de bits et compter le nombre de bits définis dans le résultat.
3) ou, si vous avez un grand nombre de bigrams possibles (Unicode, peut-être?) - ou des cordes monotones avec une poignée de bigrams chacune - une gamme triée de bigrams pourrait fournir des comparaisons plus rapides et plus spatiales. < / p>
Le lien entre / l'explication du coefficient de dés serait bon pour la postérité.
Quelle sortie voulez-vous? Voulez-vous n articles avec le coefficient le plus élevé?
Merci pour le conseil. J'ai édité mon message original pour inclure les deux détails.
Quelle est la gamme de caractères autorisée?
Si vous souhaitez trouver des chaînes / documents similaires, je suis sûr que vous pourrez trouver des objets similaires beaucoup plus rapidement que O (n ^ 2) en faisant quelque chose d'intelligent comme une hachage SIM.
C'est dommage que Dice ne satisfait pas l'inégalité du triangle. N'est-il pas possible d'utiliser une métrique de distance qui fait? Cela réduirait certainement le temps de traitement. Bien sûr, si vous voulez seulement un résultat approximatif, vous pouvez prétendre que c'est une distance réelle.
Cet article présente une méthode qui trouve 90% des 50 meilleurs voisins les plus proches pour chaque enregistrement à l'aide de Jacard (similaire à des dés) pour un ensemble de données de la taille de 900k d'enregistrements de bibliographie en examinant moins de 3% des paires. www2011india.com/proceding/proceedings/p577.pdf
La plage de caractères autorisée est tous des caractères alphanumériques et l'espace. Je ne cherche pas à se cluster - juste pour localiser près de cordes en double. Je ne suis pas non plus défini sur le coefficient de dés et je suis ouvert aux suggestions concernant les alternatives.
L'utilisation d'un hashset dans la méthode DicecoEfficIFIFIERE semble me survenir. Vous pouvez vous permettre un éventail de booléens indexés par tous les digrams (1369 d'entre eux dans votre cas). Deux baies de ce type vous aideront à compter les digrams distincts ainsi que les digrams communs à deux cordes, de manière beaucoup plus efficace.
Compte tenu de la longueur de vos cordes, on peut craindre que le coefficient de dés sur les bigrams ne soit pas très discriminant ici. Je recommanderais d'utiliser des N-grammes d'ordre supérieur, éventuellement après un premier filtrage sur les dés bigram. La distance d'édition de chaîne irait bien, mais trop coûteuse ici.