单词比较算法

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 Company”和“ Acme Comp”。即使角色数量不同，也应该具有较小的差异索引。此外，“Acme Company”和“Company Acme”应返回 0。

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

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

Answer 1

您可能要检查出 Levenshtein距离算法为出发点。它会率的“距离”两个词之间。

这SO线程上实现谷歌式“你的意思是...？”系统可以提供一些思路以及

Answer 2

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

的的Levenshtein（） ：返回字符的最小数量就得替换，插入或删除，将一个字符串转换为另一种。结果 的同音（） ：返回四一句话，这应该是相同的任何发音相似的单词的关键字符的soundex键。结果 的音位（） ：在到同音相似，并可能更有效的为您服务。它比同音（），因为它知道英文发音的基本规则更准确。变音位生成的密钥的长度是可变的。结果 的 similar_text（） ：类似于的Levenshtein（），但它可以返回一个百分比值来代替。

Answer 3

我已经取得了一些成功 编辑距离 算法，还有 声音指数.

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

Answer 4

我已经实际执行了类似的系统。我用Levenshtein距离（如其他海报已经建议），有一些修改。与未改性的编辑距离（适用于整个字符串）的问题是，它是单词重新排序敏感，所以“Acme的数码股份有限公司世界公司”将很少能匹配针对“数码股份有限公司世公司的Acme”和这样的重新排序在我的数据是相当普遍的。

我修改了它，这样，如果整个字符串的编辑距离太大，算法回落至匹配相互话找一个好词对词匹配（二次成本，但有一个截止，如果有太多的话，那么它的工作确定）。

Answer 5

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

完整的博文在这里.

Answer 6

有很多种算法来做到这一点，和大多数数据库，甚至还包括一个默认。它实际上是一个相当普遍关注的问题。

如果它只是关于英文单词，例如SQL Server包括SOUNDEX其可用于对所得到的单词的声音进行比较。

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

Answer 7

我实现它在PHP中，和我现在写一段代码，这将打破2串字和使用莱文斯坦从第一串和第二串的话比较每个单词和接受洛斯可能值。生病后它，当我完成了。

非常感谢。

更新：这里是我想出：

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;
}