Явная нечеткая строка с именами

Ответ 1

Когда я смотрю на эту проблему, я замечаю несколько ключевых фактов, на которых основываются некоторые улучшения:

Факты и наблюдения

1. Макс итераций 1000.
2. 15 для Левенштейна расстояние звучит очень высоко для меня.
3. Вы знаете, эмпирически наблюдая за данными, как должно выглядеть ваше нечеткое соответствие (существует много случаев нечеткого соответствия, и каждый из них зависит от того, почему данные плохие).
4. Создавая этот API-интерфейс, вы можете подключить множество алгоритмов, в том числе свой и другие, такие как Soundex, вместо того, чтобы полагаться только на один.

Требования

Я интерпретировал вашу проблему как требующую следующих двух вещей:

1. У вас есть объекты PersonDO которые вы хотите просмотреть с помощью ключа, основанного на имени. Похоже, что вы хотите сделать это, потому что вам нужен уже существующий PersonDO один из которых существует для уникального имени, и одно и то же имя может PersonDO более одного раза в вашем цикле/рабочем процессе.
2. Вам нужно "нечеткое соответствие", потому что входящие данные не являются чистыми. Для целей этого алгоритма мы будем предполагать, что если имя "совпадает", оно всегда должно использовать один и тот же PersonDO (другими словами, уникальным идентификатором человека является его имя, что, очевидно, не так в реальной жизни, но кажется, работать для вас здесь).

Реализация

Далее, давайте посмотрим, как сделать некоторые улучшения в вашем коде:

1. Очистка: ненужные манипуляции с хеш-кодом.

Вам не нужно создавать хэш-коды самостоятельно. Это немного смущает проблему.

Вы просто генерируете хеш-код для комбинации имени и фамилии. Это именно то, что сделал бы HashMap, если бы вы дали ему сцепленную строку в качестве ключа. Итак, просто сделайте это (и добавьте пробел, на случай, если мы захотим выполнить обратный анализ первого/последнего ключа позже).

Map<String, PersonDO> personCache = Maps.newHashMap();

public String getPersonKey(String first, String last) {
  return first + " " + last;
}

...
// Initialization code
for(PersonDO p: dao.getPeople()) {
    personCache.put(getPersonKey(p.getFirstName(), p.getLastName()), p);
}

2. Очистка: создайте функцию поиска, чтобы выполнить поиск.

Так как мы изменили ключ на карте, нам нужно изменить функцию поиска. Мы создадим это как мини-API. Если бы мы всегда точно знали ключ (то есть уникальные идентификаторы), мы бы, конечно, просто использовали Map.get. Итак, начнем с этого, но так как мы знаем, что нам нужно будет добавить нечеткое соответствие, мы добавим обертку, где это может произойти:

public PersonDO findPersonDO(String searchFirst, String searchLast) {
  return personCache.get(getPersonKey(searchFirst, searchLast));
}

3. Создайте алгоритм нечеткого соответствия самостоятельно, используя скоринг.

Обратите внимание, что, поскольку вы используете Guava, я использовал здесь несколько удобств (Ordering, ImmutableList, Doubles и т.д.).

Во-первых, мы хотим сохранить работу, которую выполняем, чтобы выяснить, насколько близок матч. Сделайте это с POJO:

class Match {
   private PersonDO candidate;
   private double score; // 0 - definitely not, 1.0 - perfect match

   // Add candidate/score constructor here
   // Add getters for candidate/score here

   public static final Ordering<Match> SCORE_ORDER =
       new Ordering<Match>() {
     @Override
     public int compare(Match left, Match right) {
       return Doubles.compare(left.score, right.score);
     }
   };
}

Далее мы создаем метод для оценки общего имени. Мы должны забивать имена и фамилии отдельно, потому что это уменьшает шум. Например, нам не важно, совпадает ли имя с какой-либо частью фамилии - если только ваше имя не было случайно в поле фамилии или наоборот, что вы должны учитывать намеренно, а не случайно (мы рассмотрим это позже),

Обратите внимание, что нам больше не нужно "максимальное расстояние Левенштейна". Это потому, что мы нормализуем их по длине, и мы выберем наиболее близкое соответствие позже. 15 символов добавляет/редактирует/удаляет кажется очень высоким, и, поскольку мы свели к минимуму проблему с пустым именем/фамилией, забивая имена по отдельности, мы могли бы теперь выбрать максимум 3-4, если хотите, (забив что-либо еще как 0).

// Typos on first letter are much more rare.  Max score 0.3
public static final double MAX_SCORE_FOR_NO_FIRST_LETTER_MATCH = 0.3;

public double scoreName(String searchName, String candidateName) {
  if (searchName.equals(candidateName)) return 1.0

  int editDistance = StringUtils.getLevenshteinDistance(
      searchName, candidateName);

  // Normalize for length:
  double score =
      (candidateName.length() - editDistance) / candidateName.length();

  // Artificially reduce the score if the first letters don't match
  if (searchName.charAt(0) != candidateName.charAt(0)) {
    score = Math.min(score, MAX_SCORE_FOR_NO_FIRST_LETTER_MATCH);
  }

  // Try Soundex or other matching here.  Remember that you don't want
  // to go above 1.0, so you may want to create a second score and
  // return the higher.

  return Math.max(0.0, Math.min(score, 1.0));
}

Как отмечалось выше, вы можете подключить сторонние или другие алгоритмы сопоставления слов и воспользоваться общими знаниями обо всех них.

Теперь мы просматриваем весь список и оцениваем каждое имя. Обратите внимание, что я добавил место для "твиков". Твики могут включать в себя:

• Сторнирование: Если PersonDO - "Бенджамин Франклин", но в листе CSV может содержаться "Франклин, Бенджамин", то вы захотите исправить обратные имена. В этом случае вы, вероятно, захотите добавить метод checkForReversal который будет checkForReversal имя в обратном порядке и принимать этот показатель, если он значительно выше. Если бы он точно совпадал, вы бы дали 1,0 балл.
• Сокращения: Вы можете захотеть повысить балл за счет, если имя или фамилия совпадают, а другое полностью содержится в кандидате (или наоборот). Это может указывать на сокращение, как "Саманта/Сэм".
• Распространенные псевдонимы: Вы можете добавить набор известных псевдонимов ("Роберт → Боб, Роб, Бобби, Робби"), а затем сравнить поисковое имя со всеми из них и набрать наибольшее количество очков. Если он соответствует любому из них, вы, вероятно, дали бы ему 1,0 балл.

Как вы можете видеть, построение этого в виде серии API дает нам логические места, чтобы легко настроить это для нашего сердца.

На с алогритом:

public static final double MIN_SCORE = 0.3;

public List<Match> findMatches(String searchFirst, String searchLast) {
  List<Match> results = new ArrayList<Match>();

  // Keep in mind that this doesn't scale well.
  // With only 1000 names that not even a concern a little bit, but
  // thinking ahead, here are two ideas if you need to:
  // - Keep a map of firstnames.  Each entry should be a map of last names.
  //   Then, only iterate through last names if the firstname score is high
  //   enough.
  // - Score each unique first or last name only once and cache the score.
  for(PersonDO person: personCache.values()) {
    // Some of my own ideas follow, you can tweak based on your
    // knowledge of the data)

    // No reason to deal with the combined name, that just makes things
    // more fuzzy (like your problem of too-high scores when one name
    // is completely missing).
    // So, score each name individually.

    double scoreFirst = scoreName(searchFirst, person.getFirstName());
    double scoreLast = scoreName(searchLast, person.getLastName());

    double score = (scoreFirst + scoreLast)/2.0;

    // Add tweaks or alternate scores here.  If you do alternates, in most
    // cases you'll probably want to take the highest, but you may want to
    // average them if it makes more sense.

    if (score > MIN_SCORE) {
      results.add(new Match(person, score));
    }
  }

  return ImmutableList.copyOf(results);
}

Теперь мы модифицируем ваш findClosestMatch, чтобы получить только самое высокое значение из всех совпадений (выдает NoSuchElementException если его нет в списке).

Возможные настройки:

• Возможно, вы захотите проверить, были ли набраны несколько имен очень близко, и либо сообщить о победителях (см. Ниже), либо пропустить строку для ручного выбора позже.
• Вы можете сообщить, сколько было других совпадений (если у вас очень жесткий алгоритм подсчета очков).

Код:

public Match findClosestMatch(String searchFirst, String searchLast) {
  List<Match> matches = findMatch(searchFirst, searchLast);

  // Tweak here

  return Match.SCORE_ORDER.max(list);
}

.. а затем измените наш оригинальный получатель:

public PersonDO findPersonDO(String searchFirst, String searchLast) {
  PersonDO person = personCache.get(getPersonKey(searchFirst, searchLast));
  if (person == null) {
    Match match = findClosestMatch(searchFirst, searchLast);
    // Do something here, based on score.
    person = match.getCandidate();
  }
  return person;
}

4. Сообщать о "нечеткости" по-другому.

Наконец, вы заметите, что findClosestMatch не просто возвращает человека, он возвращает Match - это так, чтобы мы могли изменить программу так, чтобы нечеткие совпадения отличались от точных совпадений.

Некоторые вещи, которые вы, вероятно, хотите сделать с этим:

• Предположения об отчете: сохраните все имена, которые совпадают на основе нечеткости, в список, чтобы вы могли сообщать о них, и они могут быть проверены позже.
• Сначала проверьте: вы можете захотеть добавить элемент управления для включения и выключения, использует ли он на самом деле нечеткие совпадения или просто сообщает о них, чтобы вы могли массировать данные до их поступления.
• Защита данных. Возможно, вы захотите квалифицировать любые изменения, сделанные в нечетком совпадении, как "неопределенные". Например, вы можете запретить любые "основные изменения" записи Person, если совпадение было нечетким.

Заключение

Как видите, не так уж много кода, чтобы сделать это самостоятельно. Сомнительно, что когда-нибудь будет библиотека, которая будет предсказывать имена, а вы сами сможете знать данные.

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

Ответ 2

• Используете ли вы db для выполнения поиска? Используя регулярное выражение в вашем выборе или используйте оператор LIKE

• Проанализируйте свою базу данных и попытайтесь создать или таблицу Huffman-tree или несколько, чтобы выполнить поиск по ключевым словам.

Ответ 3

Нет лучшего решения, так или иначе вы должны иметь дело с какой-то эвристикой. Но вы можете искать другую реализацию расстояния Левенштейна (или реализовать ее самостоятельно). Эта реализация должна давать разные оценки для различных операций с символами (вставка, удаление) для разных символов. Например, вы можете дать более низкие баллы для пар символов, которые находятся на клавиатуре. Кроме того, вы можете динамически вычислять максимальный порог расстояния на основе длины строки.

И у меня есть подсказка для вас. Каждый раз, когда вы вычисляете расстояние Левенштейна, выполняются n * m операций, где n и m - длины строк. Существует автомат Levenshtein, который вы создаете один раз, а затем оцениваете очень быстро для каждой строки. Будьте осторожны, так как NFA очень дорого оценить, вам нужно сначала преобразовать его в DFA.

Возможно, вам стоит взглянуть на Lucene. Надеюсь, он включает в себя все возможности нечеткого поиска, которые вам нужны. Вы даже можете использовать полнотекстовый поиск СУБД, если он поддерживается. Например, PostgreSQL поддерживает полный текст.

Ответ 4

Это то, что я сделал с аналогичным вариантом использования:

• Сопоставьте имя и фамилию отдельно, это будет более точное совпадение и устранить некоторые ложные срабатывания:

distance("a b", "a c")                        is   33%
max(distance("a", "a"), distance("b", "c"))   is   100%

• Настройте критерии расстояния min по длине входных строк, т.е. 0 для строк короче, чем 2 символа, 1 для строк короче 3 символов.

int length = Math.min(s1.length(), s2.length);

int min;

if(length <= 2) min = 0; else
if(length <= 4) min = 1; else
if(length <= 6) min = 2; else
...

Эти два должны работать для вашего ввода.