一种更好的变长字符串相似度排序算法 [英] A better similarity ranking algorithm for variable length strings

问题描述

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

I'm looking for a string similarity algorithm that yields better results on variable length strings than the ones that are usually suggested (levenshtein distance, soundex, etc).

例如

给定字符串 A:Robert"，

Given string A: "Robert",

然后是字符串 B:Amy Robertson"

Then string B: "Amy Robertson"

会比

字符串 C:理查德"

此外，该算法最好是语言不可知的(也适用于英语以外的语言).

Also, preferably, this algorithm should be language agnostic (also works in languages other than English).

推荐答案

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

Simon White of Catalysoft wrote an article about a very clever algorithm that compares adjacent character pairs that works really well for my purposes:

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

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

Simon has a Java version of the algorithm and below I wrote a PL/Ruby version of it (taken from the plain ruby version done in the related forum entry comment by Mark Wong-VanHaren) so that I can use it in my PostgreSQL queries:

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

就像一个魅力！

这篇关于一种更好的变长字符串相似度排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！