java判断两个字符串是否“足够相似”的好指标是什么

Question

我正在研究一个非常粗略的初稿算法，以确定两个字符串的相似程度。我还使用Levenshtein Distance来计算字符串之间的编辑距离

我目前所做的基本上是将编辑的总数除以较大字符串的大小。如果该值低于某个阈值（当前随机设置为25%），则它们“足够相似”

然而，这完全是武断的，我认为这不是一个很好的计算相似性的方法。是否有某种数学方程或概率/统计方法来获取Levenshtein距离数据，并使用它来表示“是的，根据所做编辑的数量和字符串的大小，这些字符串足够相似”

另外，这里的关键是我使用了一个任意的阈值，我不希望这样做。我如何计算这个阈值而不是分配它，这样我就可以安全地说两个字符串“足够相似”

更新

我正在比较表示Java堆栈跟踪的字符串。我想这样做的原因是根据相似性对一堆给定的堆栈跟踪进行分组，并将其用作对“内容”进行排序的过滤器：）这种分组对于更高级别的原因很重要，我无法完全公开共享

---

到目前为止，我的算法（伪代码）大致如下：

/*
 * The input lists represent the Strings I want to test for similarity. The
 * Strings are split apart based on new lines / carriage returns because Java
 * stack traces are not a giant one-line String, rather a multi-line String.
 * So each element in the input lists is a "line" from its stack trace.
 */
calculate similarity (List<String> list1, List<String> list2) {

    length1 = 0;
    length2 = 0;
    levenshteinDistance = 0;

    iterator1 = list1.iterator();
    iterator2 = list2.iterator();

    while ( iterator1.hasNext() && iterator2.hasNext() ) {

        // skip blank/empty lines because they are not interesting
        str1 = iterator1.next();    length1 += str1.length();
        str2 = iterator2.next();    length2 += str2.length();

        levensteinDistance += getLevenshteinDistance(str1, str2);
    }

    // handle the rest of the lines from the iterator that has not terminated

    difference = levenshteinDistance / Math.max(length1, length2);

    return (difference < 0.25) ? true : false; // <- arbitrary threshold, yuck!
}

Answer 1

使用余弦相似性如何？这是评估两个文本之间相似性的通用技术。其工作原理如下：

从两个字符串中提取所有字母，构建如下表：

Letter | String1 | String2

这可以是一个简单的哈希表或任何东西

在“字母”列中，输入每个字母，在“字符串”列中，将其频率输入该字符串中（如果字符串中没有字母，则值为0）

之所以称为余弦相似性，是因为将两个字符串列中的每一列解释为向量，其中每个分量都是与字母关联的数字。接下来，计算向量之间“角度”的余弦，如下所示：

C = (V1 * V2) / (|V1| * |V2|)

分子是点积，即相应分量的乘积之和，分母是向量大小的乘积

C与1的接近程度说明了字符串的相似性

它可能看起来很复杂，但一旦你理解了这个想法，它只是几行代码

让我们看一个例子：考虑字符串

s1 = aabccdd
s2 = ababcd

该表如下所示：

Letter a b c d
s1     2 1 2 2
s2     2 2 1 1

因此：

C = (V1 * V2) / (|V1| * |V2|) = 
(2 * 2 + 1 * 2 + 2 * 1 + 2 * 1) / (sqrt(13) * sqrt(10)) = 0.877

所以他们“非常”相似

Answer 2

堆栈跟踪采用易于解析的格式。我将使用解析库解析堆栈跟踪，然后您可以提取您想要比较的任何语义内容

当字符串不像您期望的那样进行比较时，相似性算法将变得更慢，并且难以调试

Answer 3

这是我的观点——这只是一个很长的故事，不一定是对你的问题的回答：

我过去也做过类似的事情，我试图通过简单地重新排列句子，同时保持同样的信息来确定某人是否剽窃

1“孩子们应该在我们吃饭的时候玩耍”
2“我们吃饭的时候，孩子们应该玩”
3“我们应该边玩边吃孩子”

所以levenshtein在这里没有多大用处，因为它是线性的，每个都会有很大的不同。标准差将通过测试，学生将逍遥法外

因此，我将句子中的每个单词分解，重新组合成数组，然后相互比较，首先确定每个数组中是否存在单词，以及单词与最后一个数组的关系。然后每个单词都会检查数组中的下一个单词，以确定是否有连续的单词，就像我在第1行和第2行上面的示例句子中所示。 因此，如果有连续的单词，我将由每个数组共有的每个序列组成一个字符串，然后尝试找出剩余单词中的差异。剩下的单词越少，它们就越有可能只是填充词，从而减少抄袭

“我们吃饭的时候，我想孩子们应该玩”

然后，“我想”被评估，并被认为是基于关键词词典的填充词——这部分在这里很难描述

这是一个复杂的项目，不仅仅是我所描述的，而且不是一个简单的代码块，我可以轻松地共享，但是上面的想法并不难复制

祝你好运。我感兴趣的是其他成员对你的问题有什么看法

Answer 4

因为Levenshtein距离永远不会大于较长字符串的长度，所以我肯定会将分母从(length1 + length2)更改为Math.max(length1, length2)。这将使度量标准化为介于0和1之间

现在，根据提供的信息，不可能回答“足够相似”的需求。我个人尽量避免使用0.25截止值的阶跃函数，更喜欢已知区间的连续值。也许最好将连续的“相似性”（或“距离”）值输入到更高级别的算法中，而不是将这些值转换为二进制值