.net biệt() và phức tạp điều kiện ở

Question

Giả sử tôi có một lớp

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

Bây giờ tôi muốn lọc các bản sao trong danh sách của âm thanh như vậy bởi sự giống nhau (trận đấu không chính xác) điều kiện. Về cơ bản, nó là khoảng cách Levenstein với hiệu chỉnh ngưỡng bằng tổng chiều dài chuỗi. Vấn đề là, mẹo chung về IEqualityComparer là "Luôn triển khai cả GetHashCode và So sánh". Tôi obviuosly không thể calc khoảng cách giữa các chuỗi trong GetHashCode vì nó không phải là một phương pháp so sánh ở tất cả. Tuy nhiên trong trường hợp này, ngay cả âm thanh tương tự sẽ trả về các hash khác nhau và Distinct() sẽ coi nó là các đối tượng khác nhau và phương thức compare() không được kích hoạt.

Tôi đã cố gắng bắt buộc GetHashCode luôn trả về 0, vì vậy So sánh được gọi cho từng đối tượng trong bộ sưu tập, nhưng điều này là chậm. Vì vậy, cuối cùng, một câu hỏi: là có bất cứ điều gì tôi có thể làm với .net ra khỏi hộp hoặc tôi nên tìm kiếm một số thuật toán tốt để lọc?

Answer 1

tôi sẽ đề nghị (trước hết) không sử dụng biệt hoặc GetHashCode.

GetHashCode quá nghiêm ngặt đối với trường hợp của bạn (như @Gabe đã chỉ ra một cách hoàn hảo). gì bạn có thể làm là:

1. Hãy thừa nhận rằng bạn sẽ phải so sánh toàn bộ một tam giác (O (n^2) phức tạp) của cặp trường hợp sử dụng Levenshtein
2. Cố gắng tối ưu hóa rằng việc sử dụng mọi thủ đoạn trong sách: Cách tính khoảng cách Levenshtein từ chuỗi rỗng sang âm thanh hiện tại (nghĩa là cho mỗi và mọi thể hiện của Âm thanh và có thể là riêng biệt cho cả hai thuộc tính chuỗi)?

Điều đó có thể kết thúc (có thể nói) với darn tốt GetHashCode. Nhưng bạn không thể sử dụng nó như một GetHashCode, bạn thay vì nên sử dụng nó như vậy:

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

Và sau đó bạn muốn kết thúc với một thuật toán tốt hơn hoặc tồi tệ hơn. Đây chỉ là một ý tưởng và, tất nhiên: bạn không thể sử dụng Distinct(). Nếu bạn muốn, bạn có thể viết cho bạn phương thức mở rộng rất riêng để làm cho toàn bộ điều trông đẹp hơn từ góc nhìn của người lập trình người dùng.

Và có những AbsoluteQuasiLevenshtein sẽ là bình đẳng cho những thứ như: "ab" và "ZY" nhưng nó sẽ khác biệt lớn giữa "ab" và "blahblahblahblah" và ít nhất bạn sẽ tối ưu hóa mọi thứ một chút. (GetHashCode + Cách tiếp cận khác biệt đặt ra một vấn đề bổ sung - mức độ nghiêm ngặt của GetHashCode).

Answer 2

Mã cho BKTree, với lớp đơn giản "C# khả năng tương tác" và ví dụ trong C# là ở đây:

https://bitbucket.org/ptasz3k/bktree

Đó là VS giải pháp năm 2012.

Bạn bắt đầu với việc xây dựng cây từ tất cả các đối tượng của bạn, chuyển chức năng chọn (x => x.Key.Ví dụ ToLowerInvariant()), khi đó bạn tìm kiếm một khóa và khoảng cách và khoảng cách của cây được trả về cho tất cả các đối tượng phù hợp.

Vì vậy, nếu tôi hiểu vấn đề của bạn một cách chính xác:

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

Hope this helps.