.net Distinct() und komplex conditons

Question

Angenommen, ich habe eine Klasse

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

Jetzt mag ich Duplikate in Liste solchen Audio der durch Ähnlichkeit filtern (nicht Exact Match) Zustand. Grundlegend ist die Levendein-Distanz mit der Schwellwertkorrektur durch die Gesamtlänge der Saite. Das Problem ist, dass ein allgemeiner Hinweis zu IEqualityComparer lautet: "Implementiere immer GetHashCode und Compare". In GetHashCode kann ich den Abstand zwischen den Strings natürlich nicht berechnen, da es sich überhaupt nicht um eine Vergleichsmethode handelt. In diesem Fall werden jedoch ähnliche Audiodaten unterschiedliche Hashwerte zurückgeben und Distinct() behandelt sie als unterschiedliche Objekte und die compare() -Methode wird nicht ausgelöst.

Ich habe versucht, GetHashCode immer zu zwingen, gibt 0 zurück, also Compare für jedes-zu-jedem Objekt in der Sammlung aufgerufen, aber das ist langsam. So, endlich, eine Frage: Gibt es irgendetwas, was ich tun kann mit .net aus der Box oder sollte ich einen guten Algorithmus für die Filterung suchen?

Answer 1

würde ich (in erster Linie) legen nahe, nicht Distinct oder GetHashCode verwenden.

GetHashCode ist zu streng für Ihren Fall (wie @Gabe tadellos darauf hingewiesen). Was Sie tun können ist:

1. zugeben, dass Sie ein ganzes Dreieck (O (n^2) Komplexität) von Instanzen Paare unter Verwendung der Levenshtein
2. Versuche zu optimieren müssen vergleichen, die jeden Trick in der Verwendung Buch: Wie berechnet sich die Levenshtein Abstand von der leeren Zeichenfolge zum aktuellen Sound (das ist für jede Instanz von Audio und wahrscheinlich für beide String-Eigenschaften getrennt)?

, dass bis Ende könnte (man könnte sagen) mit einem verflixt gut GetHashCode. Aber man kann es nicht verwenden, wie ein GetHashCode, man sollte es eher wie so verwenden:

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; 
} 

Und dann würden Sie mit einem besseren oder schlechteren Algorithmus enden. Das war nur eine Idee und natürlich: Du kannst Distinct() nicht benutzen. Wenn Sie möchten, können Sie eine eigene Erweiterungsmethode schreiben, damit das Ganze aus der Sicht eines Anwenders gut aussieht.

Und ja der AbsoluteQuasiLevenshtein würde für Dinge wie gleich sein: „ab“ und „zy“, aber es wäre sehr zwischen „ab“ und „blahblahblahblah“ unterscheiden und zumindest würden Sie die Dinge ein wenig optimieren. (Die GetHashCode + Distinct Ansatz stellte ein zusätzliches Problem - die Strenge GetHashCode).

Answer 2

-Code für BKTree, mit einfachen "C# Interoperabilität" Schicht und Beispiel in C# ist hier:

https://bitbucket.org/ptasz3k/bktree

Es ist VS 2012-Lösung.

Sie beginnen mit dem Erstellen von Baum aus all Ihren Objekten, Übergabe Selektor-Funktion (x => x.Key.ToLowerInvariant() in Beispiel), dann suchen Sie nach einem gegebenen Schlüssel und Levenshtein Abstand und Baum liefert alle übereinstimmenden Objekte.

Also, wenn ich Ihr Problem richtig verstehen:

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

Hoffnung, das hilft.