Java模糊字符串与名称匹配

Question

我有一个独立的 CSV 数据加载过程，我用 Java 编码，它必须使用一些模糊字符串匹配。这绝对不理想，但我没有太多选择。我使用名字和姓氏进行匹配，并在运行开始时缓存所有可能性。找到匹配项后，我需要该人在运行期间对象多个位置。我用的是 Guava 的 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;
}

这适用于简单的拼写错误、拼写错误和缩短的名称(即 Mike->Michael)，但是当我完全丢失缓存中的传入名称之一时，我最终会返回一个误报匹配。为了防止这种情况发生，我在 findClosetMatch() 中设置了最小值。到 15(即不超过 15 个字符)；它大部分时间都可以工作，但我仍然有一些不匹配的情况发生:Mike Thompson点击 Mike Thomas等等。

除了找出一种将主键添加到正在加载的文件中的方法之外，有没有人看到改进此过程的方法？任何其他匹配算法可以在这里提供帮助？

Answer 1

当我看到这个问题时，我注意到一些关键事实可以作为一些改进的基础:

事实和观察

最大迭代次数为 1000。

Levenshtein 距离 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.清理:构建一个检索函数来执行查找。

由于我们更改了 map 中的键，因此我们需要更改查找功能。我们将像一个迷你 API 一样构建它。如果我们总是准确地知道 key (即唯一 ID)，我们当然会使用 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 分 .

缩写 :如果名字/姓氏中的一个完全匹配并且另一个完全包含在候选人中(反之亦然)，您可能希望给分数一个额外的奖励。这可能表示缩写，例如“Samantha/Sam”。

常用昵称 :您可以添加一组已知的昵称(“Robert -> Bob, Rob, Bobby, Robby”)，然后根据所有昵称对搜索名称进行评分并取最高分。 如果它与其中任何一个匹配，您可能会给它 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);
}

.. 然后修改我们原来的 getter:

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 记录进行任何“主要编辑”。

结论

正如您所看到的，自己编写代码并不多。令人怀疑的是，是否会出现一个可以预测名称以及您自己可以了解数据的库。

像我在上面的例子中所做的那样分块构建它会 允许您轻松迭代和调整 甚至插入第三方库来提高你的得分，而不是完全依赖它们——错误等等。