单词比较算法

我正在为我正在进行的项目执行CSV导入工具.客户端需要能够在excel中输入数据,将它们导出为CSV并将它们上传到数据库.例如,我有这个CSV记录:

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

当然,这些公司被保存在一个单独的表中并与外键相关联,因此我需要在插入之前发现正确的公司ID.我计划通过将数据库中的公司名称与CSV中的公司名称进行比较来实现此目的.如果字符串完全相同,则比较应返回0,并返回一些随着字符串变得更大而变大的值,但是strcmp不会在此处删除它,因为:

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

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

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

您可能希望查看Levenshtein距离算法作为起点.它将评估两个单词之间的"距离".

这个SO线程实现了Google风格的"你的意思是......？" 系统也可以提供一些想法.

我不知道你编写的语言是什么,但如果它是PHP,你应该考虑以下算法:

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