检查两个字符串是否非常相似(相似的字符、模式等)

Question

我习惯于在Ruby中对许多字符串进行精确匹配检查，但是我想知道是否有一种方法可以使这个过程更有效。

例如，我从一个区域获取数据，并将其与活动记录中的数据进行比较。如果www.domain.com在一个位置，但domain.com在另一个位置，我可以确定这一点的唯一方法是在一个地方删除www或在另一个地方添加它。

是否有一种方法能够聪明地确定两个数据是否相似?

在上面的例子中，14个字符中有10个(或71.42%)是相似的，所以我认为可以安全地假设这两个记录属于链接，因为它们只是略有不同。

是否有一种宝石或方法能够明智地做出这种决定?

Answer 1

Damerau-Levenshtein距离模糊匹配

任何类型的模糊匹配将在一定程度上取决于如何选择查看数据。对于这样的东西，你可以看看Levenshtein距离的许多变体之一，比如Damerau-Levenshtein。您可以调整MIN_SIMILARITY_PERCENT来调整相似度索引，该索引使用编辑距离作为在对中最长的单词中找到的字符的百分比来计算。

require 'damerau-levenshtein'
class SimilarityIndex
MIN_SIMILARITY_PERCENT = 70.0
attr_reader :similarity_idx, :words
def initialize word1, word2
@words = word1, word2
similar?
end

def edit_distance
DamerauLevenshtein.distance *@words
end
def longest_word_length
@words.max_by(&:length).size
end
def similar?
e = edit_distance
l = longest_word_length.to_f
@similarity_idx = ((1 - (e/l)) * 100).round 2
@similarity_idx >= MIN_SIMILARITY_PERCENT
end
end

您可以用一些测试数据验证这一点。例如:

word_pairs = %w[
www.domain.com
domain.com
www.example.com
foobarbaz.example.com
]
word_pairs.each_slice(2).map do |word1, word2|
s = SimilarityIndex.new word1, word2
{ words: s.words, similarity_idx: s.similarity_idx, similar?: s.similar? }
end

该测试数据生成以下结果:

[{:words=>["www.domain.com", "domain.com"],
:similarity_idx=>71.43,
:similar?=>true},
{:words=>["www.example.com", "foobarbaz.example.com"],
:similarity_idx=>57.14,
:similar?=>false}]