1. ホーム
  2. string-matching

[解決済み] 可変長文字列に対するより良い類似性ランキングアルゴリズム

2022-04-26 22:26:36

質問

可変長の文字列に対して、通常提案されるもの(levenshtein距離、soundexなど)よりも良い結果をもたらす文字列類似性アルゴリズムを探しています。

例えば、こんな感じです。

与えられた文字列A: "Robert"。

次に文字列B: "Amy Robertson"

の方が、よりマッチしていると思います。

文字列C:"Richard"

また、できれば、このアルゴリズムは言語に依存しない(英語以外の言語でも動作する)ことが望ましいです。

解決方法は?

CatalysoftのSimon Whiteが、隣接する文字ペアを比較する非常に賢いアルゴリズムについて記事を書いていますが、私の目的にはとてもよく合っています。

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

SimonはJava版のアルゴリズムを持っていますが、私はPL/Ruby版を書きました(Mark Wong-VanHarenによる関連フォーラムのエントリコメントで示されたプレーンなRuby版から引用)。

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

とても効果的です。