Comparaison efficace des valeurs des lignes de base de données

Question

Je souhaite parcourir une base de données de documents et calculer un score de comparaison par paire.

Une méthode simpliste et naïve imbrique une boucle dans une autre boucle. Cela permettrait au programme de comparer deux fois les documents et de comparer chaque document à lui-même.

Y a-t-il un nom pour l'algorithme pour effectuer cette tâche efficacement? Y a-t-il un nom pour cette approche?

Merci.

Answer 1

Supposons que tous les éléments ont un nombre ItemNumber

solution simple - ont toujours le 2ème ItemNumber de l'élément supérieur au premier élément.

par exemple

for (firstitem = 1 to maxitemnumber) 
    for (seconditem = firstitemnumber+1 to maxitemnumber) 
    compare(firstitem, seconditem) 

Note visuelle: si vous pensez de la comparaison comme matrice (numéro d'article d'un sur un élément de l'axe de l'autre sur l'autre axe) cela ressemble à l'un des triangles.

........ 
x....... 
xx...... 
xxx..... 
xxxx.... 
xxxxx... 
xxxxxx.. 
xxxxxxx. 

Answer 2

Vous pouvez garder une trace des documents que vous avez déjà comparés, par ex. (Avec des chiffres;))

compared = set() 

for i in [1,2,3]: 
    for j in [1,2,3]: 
     pair = frozenset((i,j)) 
     if i != k and pair not in compared: 
      compare.add(pair) 
      compare(i,j) 

Une autre idée serait de créer la combinaison de documents premier et itérer sur eux. Mais pour générer ceci, vous devez parcourir à nouveau les deux listes et le itérer de nouveau sur la liste des résultats, donc je ne pense pas que cela ait un quelconque avantage.

Mise à jour:
Si vous avez les documents déjà dans une liste, puis la réponse de Hogan est en effet mieux. Mais je pense qu'il a besoin d'un meilleur exemple:

docs = [1,2,3] 
l = len(docs) 
for i in range(l): 
    for j in range(i+1,l): 
     compare(l[i],l[j]) 

Answer 3

Je ne pense pas que ce soit assez compliqué pour se qualifier pour un nom.

Vous pouvez éviter les doublons simplement en forçant une comparaison sur n'importe quelle valeur qui pourrait être différente entre différentes lignes - la clé primaire est un choix évident, par ex.

appariements uniques:

SELECT a.item as a_item, b.item as b_item 
FROM table AS a, table AS b 
WHERE a.id<b.id 

il Potentiellement ya beaucoup de façons dont le l'opération de comparaison peut être utilisé pour générer des données summmaries et donc d'identifier les éléments potentiellement similaires - pour un seul mot soundex est un choix évident - Cependant, vous ne dites pas quelle est votre métrique de comparaison.

C.

Answer 4

Quelque chose comme ça?

src = [1,2,3] 
for i, x in enumerate(src): 
    for y in src[i:]: 
     compare(x, y) 

Ou vous pourriez vouloir générer une liste de paires à la place:

pairs = [(x, y) for i, x in enumerate(src) for y in src[i:]]