当我看这个问题时,我注意到一些关键事实可以作为改进的基础:
事实和观察
- 最大迭代次数为1000。
- Levenshtein距离的15听起来对我来说太高了。
- 通过经验观察数据,你可以知道你的模糊匹配应该是什么样子(对于模糊匹配有许多情况,每种情况都取决于数据存在的问题)。
- 通过构建类似API的东西,你可以插入许多算法,包括自己和其他人的算法Soundex,而不只是依赖于一个。
要求
我将您的问题解释为需要以下两个方面:
- 您有“PersonDO”对象,您希望通过基于名称的键查找这些对象。听起来像是因为您需要一个预先存在的“PersonDO”,每个唯一名称都存在一个,并且同一个名称可能会在您的循环/工作流程中出现多次。
- 由于输入数据不是纯净的,因此您需要“模糊匹配”。为了本算法的目的,我们将假设如果名称“匹配”,则始终应使用相同的
PersonDO
(换句话说,一个人的唯一标识符是他们的姓名,在现实生活中显然不是这样,但在这里似乎可以工作)。
实现
接下来,让我们看看如何改进代码:
1. 清理:不必要的哈希码操作。
您不需要自己生成哈希码。这会使问题有点混乱。
您只需为名字和姓氏的组合生成哈希码。如果将连接后的字符串作为键提供给HashMap
,那么这正是HashMap
会执行的操作。所以,只需这样做(并添加一个空格,以防我们稍后想从键中反向解析出名字/姓氏)。
Map<String, PersonDO> personCache = Maps.newHashMap();
public String getPersonKey(String first, String last) {
return first + " " + last;
}
...
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;
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)。
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);
double score =
(candidateName.length() - editDistance) / candidateName.length();
if (searchName.charAt(0) != candidateName.charAt(0)) {
score = Math.min(score, MAX_SCORE_FOR_NO_FIRST_LETTER_MATCH);
}
return Math.max(0.0, Math.min(score, 1.0));
}
如上所述,您可以插入第三方或其他单词匹配算法,并从所有算法的共享知识中获益。
现在,我们遍历整个列表并给每个姓名打分。注意,我添加了一个“调整”的选项。调整可能包括:
- 逆转:如果PersonDO是"Benjamin Franklin",但CSV表格可能包含"Franklin, Benjamin",则您需要对逆转的姓名进行纠正。在这种情况下,您可能需要添加一个
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>();
for(PersonDO person: personCache.values()) {
double scoreFirst = scoreName(searchFirst, person.getFirstName());
double scoreLast = scoreName(searchLast, person.getLastName());
double score = (scoreFirst + scoreLast)/2.0;
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);
person = match.getCandidate();
}
return person;
}
4. 以不同方式报告“模糊匹配”。
最后,您会注意到findClosestMatch
不仅返回人名,还返回Match
——这样我们就可以修改程序,以便将模糊匹配与精确匹配区别对待。
以下是您可能想要做的一些事情:
- 报告猜测:将所有基于模糊性匹配的名称保存到列表中,以便稍后报告和审核。
- 先验证:您可能希望添加一个控件来开关它是否实际使用模糊匹配或只是报告它们,以便在数据输入之前对数据进行调整。
- 数据保护:如果匹配是模糊的,您可能希望将任何对模糊匹配进行的编辑标记为“不确定”。例如,如果匹配是模糊的,则可以禁止对个人记录进行任何“重大编辑”。
结论
如您所见,自己编写此代码不太费力。毫无疑问,不会有库能够像您了解数据一样预测名称。
按上面示例所示逐步构建它将允许您轻松迭代和微调,甚至插入第三方库以提高评分,而不是完全依赖它们——包括它们的缺陷。
Mike Thompson
和Mike Thomas
都存在且都与CSV中的一个名称匹配时)。这样,你就可以手动修正这些错误并运行第二阶段,实际上修改数据库。 - Alexey Andreev