.net Distinct()和复杂条件

本文关键字：复杂 条件 Distinct net | 更新日期: 2023-09-27 18:00:45

假设我有一个类

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

现在我想通过相似性（而不是完全匹配）条件来过滤这些音频列表中的重复项。Basicaly是通过字符串总长度校正的Levenstein距离。问题是，关于IEqualityComparer的一般提示是"始终同时实现GetHashCode和Compare"。我显然无法在GetHashCode中计算字符串之间的距离，因为它根本不是一个比较方法。然而，在这种情况下，即使是类似的音频也会返回不同的散列，Distinct（）会将其视为不同的对象，compare（）方法不会触发。

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

.net Distinct()和复杂条件

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

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

  1. 承认您将不得不使用Levenstein来比较实例对的整个三角形（O（n^2）复杂性）
  2. 尝试使用书中的每一个技巧来优化这一点：如何计算从空字符串到当前字符串的Levenstein距离声音（即针对音频的每个实例，可能针对两个字符串属性分别计算）

这可能最终（有人可能会说）得到一个非常好的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（）。如果你愿意，你可以编写自己的扩展方法，从用户程序员的角度来看，让整个事情看起来很好。

是的，对于"ab"answers"zy"这样的东西，绝对QuasiLevenstein是相等的，但在"ab"与"废话"之间会有很大的不同，至少你会对事情进行一些优化。（GetHashCode+Distinct方法带来了一个额外的问题-GetHashCode的严格性）。

BKTree的代码，带有简单的"c#互操作性"层，c#中的示例如下：

https://bitbucket.org/ptasz3k/bktree

这是VS 2012解决方案。

首先从所有对象构建树，传递选择器函数（示例中为x=>x.Key.ToLowerInvariant（）），然后搜索给定的键并计算距离，树返回所有匹配的对象。

所以，如果我正确理解你的问题：

var bk = BKTree.CSharp.CreateBK(x => x.artist, audios);
var allArtists = audios.Select(x => x.artist);
var possibleDuplicates = allArtists.Select(x => new 
    { Key = x, Similiar = BKTree.CSharp.FindInBk(bk, x, treshold).ToList());

希望这能有所帮助。

相关文章：