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

当我看到这个问题时,我注意到一些关键事实可以基于一些改进:

事实和观察

1. 最大迭代次数为1000.
2. Levenshtein距离15对我来说真的很高.
3. 要知道,通过经验观察的数据,您的模糊匹配应该是什么样子(也有很多情况下,模糊匹配和每个取决于为什么数据是坏的).
4. 通过构建这样的API,你可以插入许多算法,包括你自己和其他像Soundex,而不是只依赖一个.

要求

我把你的问题解释为需要以下两件事:

1. 您有PersonDO想要通过基于名称的键查找的对象.这听起来像你想要这样做,因为你需要预先PersonDO存在每个唯一名称存在的名称,并且在循环/工作流程中可能会出现相同的名称.
2. 您需要"模糊匹配",因为传入的数据不纯.出于这个算法的目的,我们假设如果名称"匹配",它应该总是使用相同的PersonDO(换句话说,一个人的唯一标识符是他们的名字,这在现实生活中显然不是这样,但似乎在这里为你工作).

履行

接下来,让我们看一下代码的一些改进:

1.清理:不必要的哈希码操作.

您不需要自己生成哈希码.这有点混淆了这个问题.

您只是为firstname + lastname的组合生成哈希码.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.如果我们总是完全知道密钥(即唯一ID),我们当然会使用Map.get.所以我们从那开始,但是因为我们知道我们需要添加模糊匹配,所以我们将添加一个包装器,这可能发生:

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

3.使用评分自己构建模糊匹配算法.

请注意,由于您使用的是番石榴,我在这里使用了一些便利(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);
     }
   };
}

接下来,我们创建一个评估通用名称的方法.我们应该分别对名和姓进行评分,因为它可以降低噪音.例如,我们不关心名字是否匹配姓氏的任何部分 - 除非你的名字可能意外地在姓氏字段中,反之亦然,你应该故意而不是偶然地解释(我们稍后会解决).

请注意,我们不再需要"max levenshtein distance".这是因为我们将它们标准化为长度,我们将在稍后选择最接近的匹配. 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是"Benjamin Franklin",但CSV表格中可能包含"Franklin,Benjamin",那么您需要更正反向名称.在这种情况下,您可能希望添加一个方法checkForReversal,该方法将反向对该名称进行评分,并在该分数显着更高时获取该分数. 如果它完全相反,你会得到1.0分.
• 缩写:如果第一个/最后一个名字匹配相同而另一个完全包含在候选者中(或者反之亦然),您可能希望给予分数奖励.这可能表示缩写.你可能想给Levenshtein津贴1来说明"尼克/尼古拉斯"或类似情况.
• 常见昵称:您可以添加一组已知的昵称("Robert - > Bob,Rob,Bobby,Robby"),然后对所有昵称进行搜索,并获得最高分.如果它匹配其中任何一个,你可能会得到1.0分.

正如您所看到的,将其构建为一系列API,为我们提供了逻辑位置,可以轻松地将其调整为我们内心的内容.

与alogrithm:

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记录进行任何"主要编辑".

结论

正如你所看到的那样,自己做的并不是太多的代码.令人怀疑的是,有一个库可以预测名称,也可以自己了解数据.

正如我在上面的示例中所做的那样构建它将允许您轻松地迭代和调整,甚至插入第三方库以改善您的得分而不是完全依赖它们 - 故障和所有.