.net Distinct()和复杂的条件

Question

假设我有一堂课

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

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

我试图强制GetHashCode总是返回0,所以Compare调用集合中的每个对象,但这很慢.所以,最后,一个问题:我可以用.net开箱即用,或者我应该搜索一些好的过滤算法？

Answer 1

我建议（首先）不要使用Distinct或GetHashCode。

GetHashCode对于您的情况来说过于严格（正如 @Gabe 完美指出的那样）。你可以做的是：

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

（有人可能会说）这最终可能会得到一个非常好的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的严格性）。