5

假设我有一堂课

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

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

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

4

2 回答 2

3

我建议（首先）不要使用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的严格性）。

于 2013-02-24T20:11:17.993 回答
1

BKTree 的代码，带有简单的“c# 互操作性”层和 c# 中的示例在这里：

https://bitbucket.org/ptasz3k/bktree

这是VS 2012的解决方案。

您首先从所有对象构建树，传递选择器函数（例如 x => x.Key.ToLowerInvariant()），然后搜索给定的键和 levenshtein 距离，然后树返回所有匹配的对象。

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

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());

希望这可以帮助。

于 2013-02-24T22:16:28.163 回答