字符串匹配 – 可变长度字符串的更好的相似性排名算法

发布时间：2020-12-14 03:11:48 所属栏目：大数据来源：网络整理

导读：我正在寻找一个字符串相似性算法，在可变长度字符串上产生比通常建议的更好的结果(levenshtein distance，soundex等)。例如，给定字符串A：“Robert”，然后字符串B：“Amy Robertson” 会比一个更好的匹配字符串C：“Richard” 此外，优选地，该算法应

我正在寻找一个字符串相似性算法，在可变长度字符串上产生比通常建议的更好的结果(levenshtein distance，soundex等)。

例如，

给定字符串A：“Robert”，

然后字符串B：“Amy Robertson”

会比一个更好的匹配

字符串C：“Richard”

此外，优选地，该算法应当是语言不可知的(也在除英语之外的语言中工作)。

解决方法

Catalysoft的Simon White写了一篇关于一个非常聪明的算法的文章，比较了相邻的字符对，这对我的目的非常有用：

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

Simon有一个Java版本的算法，下面我写了一个PL / Ruby版本(取自普通ruby版本，在相关论坛条目评论由Mark Wong-VanHaren完成)，以便我可以在我的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';

奇迹般有效！

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!