Как выполнить неточное сравнение в бинах Java?

Question

У меня есть большая (более 100 тыс. Объектов) коллекция объектов Java, как показано ниже.

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;
   ...
}

Теперь мне нужно найти в этом списке объект, в котором как минимум 3 (любые 3 или более) атрибута соответствуют атрибутам искомого объекта.

Например, если я ищу объект с

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

Поиск должен вернуть мне все объекты, где first_name,last_name and ssn соответствует или те, где last_name, ssn, email and blog_url соответствуют. Точно так же могут быть и другие комбинации.

Я хотел бы знать, какую структуру данных / алгоритм лучше использовать в этом случае. Для точного поиска я мог бы использовать хэш-набор или двоичный поиск с пользовательским компаратором, но я не уверен, каков наиболее эффективный способ выполнить этот тип поиска.

P.S.

• Это , а не домашнее задание.

• Я не уверен, подходит ли название вопроса. Пожалуйста, не стесняйтесь редактировать.

EDIT Некоторые из вас отметили тот факт, что я мог бы использовать ssn (например,) для поиска, так как он более или менее уникален. Пример выше является только иллюстрацией реального сценария. На самом деле, у меня есть несколько объектов, некоторые поля которых не заданы, поэтому я хотел бы выполнить поиск по другим полям.

Answer 1

Я не думаю, что есть какие-то конкретные структуры данных, которые бы делали такой тип сравнения / сравнения быстрым.

На простом уровне сравнения двух объектов вы можете реализовать такой метод:

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;
}

Чтобы выполнить крупномасштабный поиск, я могу придумать, что при простом линейном сканировании (с использованием описанного выше метода) было бы лучше

1. создать серию мультикарт для каждого из свойств,
2. заполнить их записями пользователей

Затем каждый раз, когда вы хотите выполнить запрос:

3. запросить каждую мультикарту, чтобы получить набор возможных кандидатов,
4. итерация всех наборов с использованием closeEnough() для поиска совпадений.

Вы можете улучшить это, обрабатывая свойства SSN, адреса электронной почты и URL-адреса блога иначе, чем свойства имени. Несколько пользователей с совпадениями в первых трех свойствах должны быть редким явлением по сравнению с (скажем) поиском нескольких пользователей по имени «Джон». Для того, чтобы вы задали вопрос, требуется как минимум 1 SSN, адрес электронной почты или URL для сопоставления (чтобы получить 3 совпадения), поэтому, возможно, вы вообще не сможете индексировать свойства имени.

Answer 2

В основном, ищите результаты, где ЛЮБОЙ из атрибутов соответствует атрибуту в запросе.Это должно сузить пространство поиска до довольно небольшого количества записей.Из этих результатов ищите записи, которые соответствуют вашим критериям.Это означает, что вам нужно пройти и посчитать, сколько атрибутов совпадают, если это больше 3, то у вас есть совпадение.(Этот процесс является относительно медленным, и вы не захотите делать это по всей вашей базе данных.)

В этом случае потенциальная оптимизация будет заключаться в удалении first_name и last_name из начальной фазы фильтра, так как онигораздо более вероятно, что вы получите несколько результатов для запроса, чем другие атрибуты (например, множество людей, называемых «Джон»).

Поскольку три атрибуты должны совпадать, удаляя два изфаза фильтра не повлияет на конечный результат.

Answer 3

Просто мысль; если вы ищете кого-то с SSN, вы сможете очень быстро сузить его, так как только один человек должен иметь один конкретный SSN.