Java模糊字符串与名称匹配

我有一个独立的CSV数据加载过程，我用Java编码，必须使用一些模糊的字符串匹配。 这绝对不是理想的，但我没有太多选择。 我使用名字和姓氏进行匹配，并在运行开始时缓存所有可能性。 找到匹配后，我需要该人在运行期间对多个位置。 我使用guava的Objects.hashCode()来创建firstname和lastname之外的哈希。

缓存机制如下所示：

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

大多数时候我会在firstname + lastname上点击，但是当它错过时我会使用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()的min值设置为15（即不超过15个字符）; 它大部分时间都有效，但我仍然发生了一些不匹配： Mike Thompson击中Mike Thomas等。

除了找出将主键放入正在加载的文件的方法之外，是否有人看到了改进此过程的方法？ 任何其他匹配的算法可以帮助吗？

Answer 1

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

事实和观察

1. 最大迭代次数为1000。
2. 莱文施泰因距离15对我来说真是太高了。
3. 你知道，通过经验观察数据，你的模糊匹配应该是什么样的（模糊匹配有很多种情况，每种情况都取决于数据不好的原因）。
4. 通过构建这样的API，你可以插入许多算法，包括你自己和其他像Soundex ，而不是只依赖一个。

要求

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

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

履行

接下来，让我们看一下代码的一些改进：

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

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

您只是为firstname + lastname的组合生成哈希码。 如果你把串联的字符串作为键给它，这正是HashMap会做的。 所以，就这样做（并添加一个空格，以防万一我们想要在以后从密钥中解析出第一个/最后一个）。

 Map 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.清理：构建检索function以执行查找。

由于我们已经更改了地图中的键，因此我们需要更改查找function。 我们将它构建为迷你API。 如果我们总是完全知道密钥（即唯一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 SCORE_ORDER = new Ordering() { @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 findMatches(String searchFirst, String searchLast) { List results = new ArrayList(); // 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 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 – 这样我们就可以修改程序来处理模糊匹配与精确匹配的不同。

你可能想要做的一些事情：

• 报告猜测：将基于模糊性匹配的所有名称保存到列表中，以便您可以报告这些名称，以后可以对其进行审核。
• 首先validation：您可能想要添加一个控件来打开和关闭它是否实际使用模糊匹配或只是报告它们，以便您可以在数据进入之前按摩数据。
• 数据缺失：您可能希望将模糊匹配上的任何编辑限定为“不确定”。 例如，如果匹配模糊，您可以禁止对Person记录进行任何“主要编辑”。

结论

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

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

Answer 2

1. 用db来执行搜索？ 在select中使用正则表达式，或使用LIKE运算符

2. 分析您的数据库并尝试构建或Huffman-tree或几个表来执行键值搜索。

Answer 3

没有最好的解决方案，无论如何你必须处理某种启发式方法。 但是你可以寻找另一个Levenshtein距离实现（或者自己实现）。 此实现必须为不同字符的不同字符操作（插入，删除）提供不同的分数。 例如，您可以为键盘上较近的字符对提供较低的分数。 此外，您可以根据字符串长度动态计算最大距离阈值。

我有一个性能提示给你。 每次计算Levenshtein距离时，都会执行n * m次运算，其中n和m是字符串的长度。 Levenshtein自动机可以构建一次，然后对每个字符串进行非常快速的评估。 请注意，因为评估NFA非常昂贵，所以首先需要将其转换为DFA。

也许你应该看看Lucene 。 我希望它包含您需要的所有模糊搜索function。 如果支持，你甚至可以使用你的DBMS全文搜索。 例如，PostgreSQL支持全文。

Answer 4

这就是我对类似用例所做的事情：

• 分别匹配名字和姓氏，这将进行更精确的匹配并消除一些误报：

距离（“ab”，“ac”）为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 ... 

这两个应该适合您的输入。