c# - .net Distinct() 和复杂条件

Question

假设我有一个类

public class Audio
{
    public string artist   { get; set; }
    public string title    { get; set; }
    // etc.
}

现在我想通过相似性(非完全匹配)条件过滤此类音频列表中的重复项。基本上它是 Levenstein 距离，通过字符串总长度进行阈值校正。问题是，关于 IEqualityComparer 的一般提示是“始终同时实现 GetHashCode 和比较”。我显然无法计算 GetHashCode 中字符串之间的距离，因为它根本不是比较方法。然而，在这种情况下，即使是相似的音频也会返回不同的哈希值，并且 Distinct() 会将其视为不同的对象，并且不会触发 compare() 方法。

我试图强制 GetHashCode 始终返回 0，因此对集合中的每个对象调用 Compare，但这很慢。所以，最后，一个问题:开箱即用的 .net 有什么我可以做的，还是我应该搜索一些好的过滤算法？

Answer 1

我建议(首先)不要使用 Distinct 或 GetHashCode。

GetHashCode 对您的情况来说太严格了(正如@Gabe 完美指出的那样)。你可以做的是:

1. 承认您必须使用 Levenshtein 比较实例对的整个三角形(O(n^2) 复杂度)
2. 尝试使用书中的每一个技巧来优化它:如何计算从空字符串到当前字符串的编辑距离声音(即针对音频的每个实例，并且可能分别计算对于两个字符串属性)？

这可能最终(有人可能会说)得到一个非常好的 GetHashCode。但是您不能像使用 GetHashCode 那样使用它，您应该像这样使用它:

bool AreSimilar(Audio me, Audio you) {
  int cheapLevenshtein = Math.Abs(me.AbsoluteQuasiLevenshtein - you.AbsoluteQuasiLevenshtein);

  if (cheapLevenshtein < THRESHOLD) {

    int expensiveLevenshtein = Audio.LevenshteinBetween(me, you);
    var result = (expensiveLevenshtein < LIMIT);
    return result;

  } else
    return false;
}

然后你会得到一个更好或更差的算法。这只是一个想法，当然:您不能使用 Distinct()。如果您愿意，您可以编写自己的扩展方法，使整个事情从用户程序员的角度来看看起来不错。

是的，AbsoluteQuasiLevenshtein 对于诸如“ab”和“zy”之类的东西来说是相等的，但在“ab”和“blahblahblahblah”之间会有很大的不同，至少你会稍微优化一下. (GetHashCode + Distinct 方法带来了另一个问题 - GetHashCode 的严格性)。