单词比对算法

Question

我正在为我所在的项目开发一个CSV导入工具。 客户需要能够在Excel中输入数据，将其导出为CSV并上传到数据库。 例如，我有这条CSV记录：

   1,   John Doe,     ACME Comapny   (the typo is on purpose)

当然，公司名称被放在一个单独的表中，并与外键链接，因此在插入之前我需要找到正确的公司ID。 我计划通过比较数据库中的公司名称和CSV中的公司名称来实现这一点。 如果字符串完全相同，则比较应该返回0，如果字符串不同则返回一个值，该值随着字符串差异的增加而变大。但是strcmp函数在这里无法胜任，因为：

"Acme Company"和"Acme Comapny"应该具有非常小的差异索引，但是 "Acme Company"和"Cmea Mpnyaco"应该具有非常大的差异索引， 或者"Acme Company"和"Acme Comp."也应该具有小的差异索引，即使字符数不同。 此外，"Acme Company"和"Company Acme"应返回0。

因此，如果客户在输入数据时出现错误，我可以提示他选择最可能要插入的名称。

是否有已知的算法可以实现此目的，或者我们可以发明一个算法 :)？

- Discodancer

---

关于库：https://dev59.com/1HVD5IYBdhLWcg3wHnsX - nawfal

Answer 1

你可能想要查看Levenshtein Distance算法作为起点。它将评估两个单词之间的“距离”。

在实现类似谷歌的“您是不是要找...？”系统方面，这个SO线程也许可以提供一些思路。

- MattK

---

非常有用。我甚至看到PHP还有一个levenstein()函数。谢谢。 - disc0dancer

我也找到了一个针对MySQL的Levenshtein函数，快速谷歌应该能找到它。 - Neil Aitken

Answer 2

我不知道你正在使用哪种编程语言，但如果是PHP的话，你应该考虑以下算法：

levenshtein()：返回将一个字符串转换成另一个字符串所需替换、插入或删除的最小字符数。
soundex()：返回单词的四位soundex键，与任何类似发音的单词的键应该相同。
metaphone()：类似于soundex，可能对你更有效。它比soundex()更准确，因为它了解英语发音的基本规则。metaphone生成的键长度可变。
similar_text()：类似于levenshtein()，但它可以返回百分比值。

- Phantom Watson

---

我已经检查了你推荐的所有这些函数，但我只发现levenstein有用，因为我不是比较它们的声音，而是比较打字错误和缩写。 similar_text()听起来很有前途，但是similar_text('Acme Company', 'Company Acme')返回58%，而我需要100% :) - disc0dancer

我可能有些荒谬，这样做计算速度会很慢，但你可以使用levenshtein()函数将一个查询中的每个单词与另一个查询中的每个单词进行比较，仅计算最接近的匹配项作为“预期单词”。 - Phantom Watson

哦，那基本上就是你已经在做的事情了。没关系。:-J - Phantom Watson

Soundex在姓名方面更有用。 - Hank

Answer 3

我用Levenshtein Distance算法取得了一些成功，还有Soundex。你使用的是什么语言实现的呢？我们可以指出具体的例子。

- Neil Aitken

Answer 4

我实际上已经实现了一个类似的系统。我使用了Levenshtein距离（就像其他帖子中已经建议的那样），并进行了一些修改。未经修改的编辑距离（应用于整个字符串）的问题在于它对单词重新排序非常敏感，因此“Acme Digital Incorporated World Company”将与“Digital Incorporated World Company Acme”匹配较差，而这种重新排序在我的数据中非常常见。

我对其进行了修改，以便如果整个字符串的编辑距离太大，算法会回退到将单词彼此匹配以找到良好的单词对单词匹配（二次成本，但如果有太多单词，则有一个截止点，所以它工作得很好）。

- Rafał Dowgird

---

我喜欢这种方法。非常聪明。 - Phantom Watson

Answer 5

我已将SoundEx、Levenshtein、PHP相似性和双重metaphone算法打包到C#中的String扩展方法中。 完整博客文章请点击此处。

- plinth

Answer 6

有多种算法可以做到这一点，大多数数据库甚至默认包含其中一个。实际上，这是一个非常常见的问题。

如果只涉及英语单词，例如 SQL Server 包括 SOUNDEX，可用于比较单词的结果音。

http://msdn.microsoft.com/en-us/library/aa259235%28SQL.80%29.aspx

- Loki

Answer 7

我正在使用PHP实现它，现在正在编写一段代码，将2个字符串分解成单词，并使用Levenshtein算法比较第一个字符串的每个单词与第二个字符串的单词，并接受最低可能值。完成后我会发布它。

非常感谢。

更新：这是我想出来的：

function myLevenshtein( $str1, $str2 )
{
  // prepare the words
  $words1 = explode( " ",  preg_replace( "/\s+/", " ", trim($str1) ) );
  $words2 = explode( " ",  preg_replace( "/\s+/", " ", trim($str2) ) );

  $found = array(); // array that keeps the best matched words so we don't check them again
  $score = 0;       // total score
  // In my case, strings that have different amount of words can be good matches too
  // For example, Acme Company and International Acme Company Ltd. are the same thing
  // I will just add the wordcount differencre to the total score, and weigh it more later if needed
  $wordDiff = count( $words1 ) - count( $words2 );
  foreach( $words1 as $word1 )
  {
    $minlevWord = "";
    $minlev = 1000;
    $return = 0;
    foreach( $words2 as $word2 )
    {
      $return = 1;
      if( in_array( $word2, $found ) )
        continue;
      $lev = levenshtein( $word1, $word2 );
      if( $lev < $minlev )
      {
        $minlev = $lev;
        $minlevWord = $word2;
      }
    }
    if( !$return )
      break;
    $score += $minlev;
    array_push( $found, $minlevWord );
  }

  return $score + $wordDiff;
}

- Discodancer