string-matching - 一种更好的变长字符串相似度排序算法

Question

我正在寻找一种字符串相似度算法，它可以在可变长度字符串上产生比通常建议的算法(编辑距离、soundex 等)更好的结果。

例如，

给定字符串 A:“Robert”，

然后字符串 B:“Amy Robertson”

会比

更好的匹配

字符串 C:“理查德”

此外，最好该算法应该与语言无关(也适用于英语以外的语言)。

Answer 1

Catalysoft 的 Simon White 写了一篇关于一种非常聪明的算法的文章，该算法比较相邻字符对，该算法非常适合我的目的:

http://www.catalysoft.com/articles/StrikeAMatch.html

Simon 有一个 Java 版本的算法，下面我编写了一个 PL/Ruby 版本(取自 Mark Wong-VanHaren 在相关论坛条目评论中完成的普通 ruby​​ 版本)，以便我可以在我的应用程序中使用它。 PostgreSQL 查询:

CREATE FUNCTION string_similarity(str1 varchar, str2 varchar)
RETURNS float8 AS '

str1.downcase! 
pairs1 = (0..str1.length-2).collect {|i| str1[i,2]}.reject {
  |pair| pair.include? " "}
str2.downcase! 
pairs2 = (0..str2.length-2).collect {|i| str2[i,2]}.reject {
  |pair| pair.include? " "}
union = pairs1.size + pairs2.size 
intersection = 0 
pairs1.each do |p1| 
  0.upto(pairs2.size-1) do |i| 
    if p1 == pairs2[i] 
      intersection += 1 
      pairs2.slice!(i) 
      break 
    end 
  end 
end 
(2.0 * intersection) / union

' LANGUAGE 'plruby';

工作起来就像一个魅力!