字比较算法

我正在为我正在处理的项目做一个CSV导入工具。客户端需要能够在Excel中输入数据，将它们导出为CSV并将其上传到数据库。例如，我有这个CSV记录：字比较算法

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

当然，这两家公司都保存在一个单独的表，并与外键链接，所以我需要在插入之前发现正确的公司ID。我打算通过将数据库中的公司名称与CSV中的公司名称进行比较来实现此目的。如果字符串完全相同，则比较应返回0，并且返回某些值随着字符串变得更加不同而返回更大值，但strcmp不会在此处将其切换，因为：

“Acme Company”和“Acme Comapny “应该有一个非常小的差异指数，但 ”Acme公司“和”Cmea Mpnyaco“应该有非常大的差异指数或”Acme公司“和”Acme Comp。“。即使字符数不同，也应该有一个很小的差异指数。此外，“Acme公司”和“公司Acme”应返回0.

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

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

来源

2009-01-23 disc0dancer

对于库：http://stackoverflow.com/questions/83777/are-there-any-fuzzy-search-or-string-similarity-functions-libraries-written-for – nawfal 2013-06-06 05:25:11

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

This SO thread实施谷歌风格的“你的意思是......？”系统也可以提供一些想法。

来源

2009-01-23 16:25:23 MattK

你打我吧:) – 2009-01-23 16:27:03

这非常有用。我看到PHP甚至有一个levenshtein（）函数。谢谢。 – disc0dancer 2009-01-23 16:30:39

我发现了mySQL的levensthein函数，快速谷歌应该找到它。 – 2009-01-23 16:32:15

我用Levenshtein Distance算法取得了一些成功，也有Soundex。

你在使用哪种语言？我们可能会指出具体的例子

来源

2009-01-23 16:26:44

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

如果它只是英文单词，例如SQL Server就包含SOUNDEX，它可以用来比较单词所产生的声音。

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

来源

2009-01-23 16:29:13 Loki

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

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

来源

2009-01-23 16:32:06

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

我对它进行了修改，以便如果整个字符串的编辑距离过大，算法会回到匹配的单词之间以找到一个好的单词匹配匹配（二次成本，但是如果if有太多的话，所以它工作确定）。

来源

2009-01-23 16:35:33

我在PHP中实现它，现在我正在编写一段代码，它将分解单词中的两个字符串，并使用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; 
}

来源

2009-01-23 16:48:53 disc0dancer

我已经采取的SoundEx，莱文斯坦，PHP相似，双音位和一组对字符串扩展方法包装起来的C＃。

Entire blog post here。

来源

2009-01-26 18:40:38 plinth