algorithm - 词比较算法

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。

因此，如果客户在输入数据时输入了一个类型，我可以提示他选择他最可能想要插入的名称。

有没有一种已知的算法可以做到这一点，或者我们可以发明一个:)？

score 18 · Accepted Answer

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

这个关于实现谷歌风格“你的意思是......？”的SO线程系统也可以提供一些想法。

score 9 · Accepted Answer

我不知道你在用什么语言编码，但如果是 PHP，你应该考虑以下算法：

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

score 2 · Accepted Answer

我在Levenshtein Distance算法上取得了一些成功，还有Soundex。

你用什么语言实现这个？我们也许可以指出具体的例子

score 2 · Accepted Answer

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

我修改了它，如果整个字符串的编辑距离太大，算法会退回到相互匹配的单词以找到一个好的单词到单词匹配（二次成本，但如果有太多的话会有一个截止话，所以它工作正常）。

score 2 · Accepted Answer

我采用了 SoundEx、Levenshtein、PHP 相似性和双变音位，并在 C# 中将它们打包到 String 上的一组扩展方法中。

整个博客文章在这里。

score 0 · Accepted Answer

有多种算法可以做到这一点，大多数数据库甚至默认包含一种。这实际上是一个相当普遍的问题。

如果它只是关于英语单词，例如 SQL Server 包括 SOUNDEX，可用于比较单词的结果声音。

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

score 0 · Accepted Answer

我正在用 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;
}

algorithm - 词比较算法

7 回答 7

Related

Reference