Соответствие нечеткой строки Java именам

Question

Соответствие нечеткой строки Java именам

У меня есть автономный процесс загрузки данных CSV, который я написал в Java, который должен использовать нечеткое сопоставление строк. Это определенно не идеально, но у меня нет большого выбора. Я сопоставляю, используя имя и фамилию, и я кеширую все возможности в начале прогона. После нахождения совпадения мне нужно, чтобы этот человек возражал против нескольких мест во время пробега. Я использовал гуаву Objects.hashCode() создать хэш из имени и фамилии.

Механизм кеширования выглядит так:

Map<Integer,PersonDO> personCache = Maps.newHashMap();
for(PersonDO p: dao.getPeople()) {
    personCache.put(Objects.hashCode(p.getFirstName(),p.getLastName()), p);
}

Большую часть времени я получаю хиты по имени + фамилии, но когда он пропускает, я отступаю, используя Apache StringUtils.getLevenshteinDistance() чтобы попытаться соответствовать Вот как проходит логический поток:

    person = personCache.get(Objects.hashCode(firstNameFromCSV,lastNameFromCSV));
    if(person == null) {//fallback to fuzzy matching
        person = findClosetMatch(firstNameFromCSV+lastNameFromCSV);

    }

Это findClosetMatch() метод:

private PersonDO findClosetMatch(String name) {
    int min = 15;//initial value
    int testVal=0;
    PersonDO matchedPerson = null;
    for(PersonDO person: personCache.values()) {
        testVal = StringUtils.getLevenshteinDistance(name,person.getFirstName()+person.getLastName());
        if( testVal < min ) {
            min = testVal;
            matchedPerson = person;
        }
    }
    if(matchedPerson == null) {
        throw new Exception("Unable to find person: " + name) 
    }
    return matchedPerson;
}

Это прекрасно работает с простыми орфографическими ошибками, опечатками и сокращенными именами (например, Майк-> Майкл), но когда я полностью пропускаю одно из входящих имен в кеше, я получаю ложное положительное совпадение. Чтобы не допустить этого, я установил минимальное значение в findClosetMatch() до 15(т.е. не более 15 символов); это работает большую часть времени, но у меня все еще было несколько несовпадений: Mike Thompson хиты на Mike Thomas и т.п.

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

24

java string levenshtein-distance

Источник

user772385 11 янв '14 в 02:07

4 ответа

Решение

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

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

расстояние ("a b", "a c") составляет 33%
max(расстояние ("a", "a"), расстояние ("b", "c")) составляет 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
...

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

2

Источник

user1851024 13 янв '14 в 10:28

Используете ли вы БД для выполнения поиска? Используя регулярное выражение в вашем выборе, или используйте LIKE оператор
Проанализируйте свою базу данных и попробуйте построить или дерево Хаффмана, или несколько таблиц, чтобы выполнить поиск по значению ключа.

2

Источник

user2365185 11 янв '14 в 09:26

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

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

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

2

Источник

user1109309 13 янв '14 в 08:07

Другие вопросы по тегам java string levenshtein-distance

user143295 13 янв '14 в 09:23 2014-01-13 09:23 · Accepted Answer · 2014-01-13 09:23

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

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

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

Требования

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

У тебя есть PersonDO объекты, которые вы хотите найти с помощью ключа, который основан на имени. Похоже, вы хотите сделать это, потому что вам нужно предварительно существующий PersonDO из которых одно существует для уникального имени, и одно и то же имя может появляться более одного раза в вашем цикле / рабочем процессе.
Вам нужно "нечеткое соответствие", потому что входящие данные не являются чистыми. Для целей этого алгоритма мы будем предполагать, что если имя "совпадает", оно всегда должно использовать одно и то же 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 это приведет к обратному результату в названии и получит этот показатель, если он значительно выше. Если бы он точно совпадал, вы бы дали 1,0 балл.
Сокращения: Вы можете захотеть увеличить балл, если одно или другое имя совпадает, а другое полностью содержится в кандидате (или наоборот). Это может указывать на сокращение. Возможно, вы захотите дать Левенштейну 1 балл на счет "Ник / Николас" или аналогичный.
Распространенные псевдонимы: Вы можете добавить набор известных псевдонимов ("Роберт -> Боб, Роб, Бобби, Робби"), а затем сравнить поисковое имя со всеми из них и набрать наибольшее количество очков. Если он соответствует любому из них, вы, вероятно, дали бы ему 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's 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, если совпадение было нечетким.

Заключение

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

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