Comment effectuer une comparaison inexacte dans les beans Java?

Question

J'ai une grande collection (plus de 100K objets) d'objets Java comme ci-dessous.

public class User 
{ 
    //declared as public in this example for brevity... 
    public String first_name; 
    public String last_name; 
    public String ssn; 
    public String email; 
    public String blog_url; 
    ... 
} 

Maintenant, je dois rechercher cette liste pour un objet dont au moins 3 (3 tout ou plus) les attributs correspondent à ceux de l'objet recherché.

Par exemple, si je suis à la recherche d'un objet qui a

first_name="John", 
last_name="Gault", 
ssn="000-00-0000", 
email="xyz@abc.com", 
blog_url="http://myblog.wordpress.com" 

La recherche devrait me retourner tous les objets où first_name,last_name and ssn allumette ou ceux où last_name, ssn, email and blog_url correspondent. De même, il pourrait y avoir d'autres combinaisons.

Je voudrais savoir quelle est la meilleure structure de données/algorithme à utiliser dans ce cas. Pour une recherche exacte, j'aurais pu utiliser un hashset ou une recherche binaire avec un comparateur personnalisé, mais je ne suis pas sûr de la manière la plus efficace d'effectuer ce type de recherche.

P.S.

• C'est pas un exercice de devoirs.

• Je ne suis pas sûr que le titre de la question soit approprié. S'il vous plaît, n'hésitez pas à modifier.

EDIT Certains d'entre vous ont souligné le fait que je pouvais utiliser ssn (par ex.) Pour la recherche car il est plus ou moins unique. L'exemple ci-dessus n'est qu'illustratif du scénario réel. En réalité, j'ai plusieurs objets où certains des champs sont nuls donc je voudrais chercher sur d'autres champs.

Answer 1

Je ne pense pas qu'il existe des structures de données spécifiques pour rendre ce type de correspondance/comparaison rapide.

Au niveau simple, de comparer deux objets, vous pourriez mettre en œuvre une méthode comme ceci:

public boolean closeEnough(User other) { 
    int count = 0; 
    count += firstName.equals(other.firstName) ? 1 : 0; 
    count += lastName.equals(other.lastName) ? 1 : 0; 
    count += ssn.equals(other.ssn) ? 1 : 0; 
    count += email.equals(other.email) ? 1 : 0; 
    ... 
    return count >= 3; 
} 

Pour faire une grande recherche à grande échelle, la seule façon que je peux penser à cela améliorerait sur un simple balayage linéaire (en utilisant la méthode ci-dessus) serait

1. créer une série de multimaps pour chacune des propriétés,
2. les remplir avec les dossiers de l'utilisateur

Ensuite, chaque fois que vous voulez faire une requête:

1. requête chaque multimap pour obtenir un ensemble de candidats possibles,
2. itérer tous les jeux utilisant closeEnough() pour trouver les matchs.

Vous pouvez améliorer cela en traitant différemment les propriétés SSN, adresse de messagerie et URL de blog des propriétés de nom. Plusieurs utilisateurs avec des correspondances sur les trois premières propriétés devraient être une occurrence rare, comparé à (disons) trouver plusieurs utilisateurs appelés "John". La façon dont vous avez posé la question nécessite au moins 1 de SSN, email ou URL pour correspondre (pour obtenir 3 correspondances), alors peut-être que vous ne pourriez pas déranger l'indexation des propriétés du nom du tout.

Answer 2

Fondamentalement, recherchez les résultats où ANY des attributs correspond à l'attribut dans la requête. Cela devrait réduire l'espace de recherche à un petit nombre d'entrées. À partir de ces résultats, recherchez les entrées correspondant à vos critères. Cela signifie que vous devez passer en revue et compter le nombre d'attributs qui correspondent, si c'est plus de 3, alors vous avez une correspondance. (Ce processus est relativement lent et vous ne voudrez pas le faire sur toute votre base de données.)

Dans ce cas, une optimisation potentielle serait d'enlever first_name et last_name de la phase de filtrage initiale, car ils sont beaucoup plus susceptibles de vous obtenir plusieurs résultats pour une requête que les autres attributs (par exemple, beaucoup de gens appelés "John").

Depuis trois attributs sont nécessaires pour correspondre, supprimer deux de la phase de filtrage n'affectera pas le résultat final.

Answer 3

Juste une pensée; Si vous cherchez quelqu'un avec SSN, vous devriez être en mesure de le réduire très rapidement, car une seule personne est censée avoir un SSN spécifique.