mysql - 我可以使用 ActiveRecord 根据最近匹配（levenshtein 距离）查找行吗

Question

我的数据库中有一个字符串表。我选择其中一个，A。

如何搜索表的其余部分以找到与A最相似的字符串？

Answer 1

我认为您正在寻找莱文斯坦距离。2个字符串之间的levenstein距离，是需要多少添加/删除/修改字符才能使字符串相等。

这是Ruby中的一个实现

Answer 2

如果您在寻找两个字符串之间的语音相似性，您可以使用 SQL soundex 函数（Oracle 中也有 metaphone）。

这会将传递给它的字符串转换为 4 位代码（1 个字母，3 个数字 iirc），代表单词的语音。

如果您对要比较的两个字符串都这样做，如果它们在语音上相似，那么您可以匹配代码。

Answer 3

这是 Ruby 中 Levenshtein 距离算法的简单实现：

def levenshtein(a, b)
  case
    when a.empty?: b.length
    when b.empty?: a.length
    else [(a[0] == b[0] ? 0 : 1) + levenshtein(a[1..-1], b[1..-1]),
          1 + levenshtein(a[1..-1], b),
          1 + levenshtein(a, b[1..-1])].min
  end
end

两个字符串之间的 Levenshtein 距离由将一个字符串转换为另一个字符串所需的最小操作数给出，其中操作是单个字符的插入、删除或替换。