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




расстояние левенштейна python (3)

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

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


  1. Используете ли вы БД для выполнения поиска? Используя регулярное выражение в вашем выборе, или используйте оператор LIKE

  2. Проанализируйте свою базу данных и попробуйте построить или дерево Хаффмана, или несколько таблиц, чтобы выполнить поиск по значению ключа.


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

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

  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 балл на счет «Ник / Николас» или аналогичный.
  • Распространенные псевдонимы : Вы можете добавить набор известных псевдонимов («Роберт -> Боб, Роб, Бобби, Робби»), а затем сравнить поисковое имя со всеми из них и набрать наибольшее количество очков. Если он соответствует любому из них, вы, вероятно, дали бы ему 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, если совпадение было нечетким.

Заключение

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

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


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

  • Сопоставьте имя и фамилию отдельно, это сделает более точное совпадение и устранит некоторые ложные срабатывания:
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
...

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





levenshtein-distance