有没有办法定量比较两个字符串的相似性

Question

我有两个字串说:

s_1 = "This is a bat"
s_2 = "This is a bag"

在定性方面它们可以是相似的(1)或不相似(0),在上面的情况下它们由于"g"而不相似,而在定量的方式中我可以看到一定量的不相似性我是如何计算这种不同的使用python从s_1到s_2的后一个"g"

我写下一个简单的代码:

Per_deff = float(((Number_of_mutated_sites)/len(s_1))*100)

此代码告诉我们两个相同长度的字符串之间的"per_deff",如果它们的长度不相同则会怎样.我怎样才能解决我的问题.

Answer 1

你想要的东西类似于Levenshtein Distance.即使它们的长度不相等,它也能给出两根弦之间的距离.

如果两个字符串完全相同,则距离将为0,如果它们相似则距离将更小.

维基百科的示例代码:

// len_s and len_t are the number of characters in string s and t respectively
int LevenshteinDistance(string s, int len_s, string t, int len_t)
{ int cost;

  /* base case: empty strings */
  if (len_s == 0) return len_t;
  if (len_t == 0) return len_s;

  /* test if last characters of the strings match */
  if (s[len_s-1] == t[len_t-1])
      cost = 0;
  else
      cost = 1;

  /* return minimum of delete char from s, delete char from t, and delete char from both */
  return minimum(LevenshteinDistance(s, len_s - 1, t, len_t    ) + 1,
                 LevenshteinDistance(s, len_s    , t, len_t - 1) + 1,
                 LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);
}