.net Четкие() и сложные условия использования

Question

Предположим, у меня есть класс

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

Теперь я хочу, чтобы отфильтровать дубликаты в списке таких аудио-х по сходству (не Четк.совп) условия. В основном это расстояние Левенштейна с коррекцией treshold по общей длине строки. Проблема в том, что общий совет о IEqualityComparer - «Всегда применять как GetHashCode, так и Compare». Я obviuosly не могу рассчитать расстояние между строками в GetHashCode, потому что это не метод сравнения вообще. Однако в этом случае даже аналогичные звуковые сигналы возвращают разные хэши, а Distinct() будут обрабатывать его как разные объекты, а метод compare() не запускается.

Я попытался заставить GetHashCode всегда возвращать 0, поэтому Compare вызывает каждый объект в коллекции, но это медленно. Итак, наконец, вопрос: есть ли что-нибудь, что я могу сделать с .net из коробки, или мне нужно найти хороший алгоритм фильтрации?

Answer 1

Я хотел бы предложить (в первую очередь) не используется Distinct или GetHashCode.

GetHashCode слишком строг для вашего случая (как @Gabe указал отлично). Что вы можете сделать, это:

1. Признайтесь, что вы должны сравнить весь треугольник (O (N^2) сложность) экземпляры пара с помощью Левенштейн
2. Try оптимизировать, что использование каждого трюка в книга: Как вычисляется расстояние Левенштейна от пустой строки до текущей звук (то есть для каждого экземпляра аудио и, возможно, отдельно для обоих свойств строки)?

Это может закончиться (можно сказать) с проклятой 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» и «З.Ы.», но это будет значительно отличаться от «AB» и «blahblahblahblah» и, по крайней мере, вы бы оптимизировать вещи немного. (GetHashCode + Отличительный подход поставил дополнительную проблему - строгость GetHashCode).

Answer 2

Код для 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()); 

Надеется, что это помогает.