最佳字符串比较方法swift

Question

用于获取两个字符串之间相似度百分比的最佳算法是什么。到目前为止我一直在使用 Levenshtein，但这还不够。Levenshtein 给了我差异的数量，然后我必须尝试通过执行以下操作将其计算为相似度：

100 - (no.differences/no.characters_in_scnd_string * 100)

例如，如果我测试与"ab"的相似度"abc"，我会得到大约 66% 的相似度，这是有道理的，因为与"ab"的相似度为 2/3 "abc"。

我遇到的问题是，当我测试 时"abcabc"，"abc"我得到 100% 的相似度，正如"abc"中完全存在的那样"abcabc"。然而，我希望答案是 50%，因为 50% 与..."abcabc"相同。"abc"

我希望这是有道理的......第二个字符串是不变的，我想测试不同字符串与该字符串的相似度。我所说的相似，是指"cat dog"尽管"dog cat"词序不同，但具有极高的相似性。

有任何想法吗？

Answer 1

使用 Levenstein 算法和输入：

case1 - distance(abcabc, abc)
case2 - distance(cat dog, dog cat)

输出是：

distance(abcabc, abc) = 3 // what is ok, if you count percent from `abcabc`
distance(cat dog, dog cat) = 6 // should be 0

abcabc因此，在和 的情况下，abc我们得到 3，它是最大单词 的 50% abcabc。正是您想要实现的目标。

第二种情况是catsand dogs：我的建议是将此字符串拆分为单词并比较它们的所有可能组合并选择最小的结果。

更新：

第二种情况我会用伪代码来描述，因为我对Swift.

get(cat dog) and split to array of words ('cat' , 'dog') //array1
get(dog cat) and split to array of words ('dog' , 'cat') //array2

var minValue = 0;

for every i-th element of `array1`
   var temp = maxIntegerValue // here will be storred all results of 'distance(i, j)'
   index = 0 // remember index of smallest temp
   for every j-th element of `array2` 
      if (temp < distance(i, j))
         temp = distance(i, j)
         index = j
   // here we have found the smallest distance(i, j) value of i in 'array2'
   // now we should delete current j from 'array2'  
   delete j from array2

   //add temp to minValue
   minValue = minValue + temp 

工作流程将是这样的：

在第一个for语句（对于值 'cat' array1）的第一次迭代之后，我们将得到 0，因为i = 0和j = 1是相同的。然后j = 1将从中删除array2，之后array2将只有 elem dog。

第二个语句的第二次迭代for（对于值 'dog' ）我们也将得到 0，因为它与fromarray1相同dogarray2

至少从现在起你知道如何处理你的问题。现在取决于您将如何具体实现它，可能您会采用另一种数据结构。