목록의 어떤 개체가 동일한 유형의 다른 개체와 가장 공통점이 있는지 어떻게 알 수 있습니까?

Question

내가하고 싶은 것은 속성이있는 개체 컬렉션을 갖고 쿼리 템플릿 역할을하는 개체를 전달하는 것입니다. 동일한 유형의 주어진 입력 객체와 속성 값이 가장 공통점이있는 객체를 정렬하거나 우선 순위를 매길 수 있습니까?

자세한 내용 :이 예제는 세 번째 항목에 일치하지만, 부동산 c이 null 또는 "f" 인 경우에, 그것은 첫 번째와 세 번째 항목을 반환해야하고 싶습니다

 List<A> myList = new List<A>() {new A() {b="x"}, 
             new A() {c="r"}, 
             new A() {b="x",c="r"},}; 

     var myTemplate = new A() {b = "x", c="r"}; 

. c 속성이 "r"이고 bisnull 또는 "f" 인 경우 c과 일치하므로 두 번째 및 세 번째 항목을 반환해야합니다.

Answer 1

두 개체가 얼마나 유사한 지 결정하기 위해 기본적으로 수식을 만들어야합니다. 각 속성에 대한 가중치를 선택한 다음 간단한 비교를 사용하여 해당 속성을 같은 것으로 집계해야하는지 여부를 말하십시오. 일부 유형의 퍼지 매칭이 사용될 수 있지만 더 복잡 할 것입니다. 간단한

뭔가 수 :

I는 0 ~ 100 사이의 숫자를 반환 정의하고 간단한 방법이다

public byte Similarity(SomeType other) 
{ 
    byte similarity = 0; 
    if (this.Property1 == other.Property1) 
     similarity += 25; 
    if (this.Property2 == other.Property2) 
     similarity += 13; 
    if (this.Property3 == other.Property3) 
     similarity += 12; 
    if (SomeFuzzyComparisonReturnsVerySimilar(this.Property4, other.Property4)) 
     similarity += 50; 
    return similarity; 
} 

; 100은 동일하고 0은 완전히 상이하다.

일단 그렇게했다면 고려해야 할 정도로 유사한 항목을 선택하는 것이 매우 간단합니다. 예 :

var similarObjects = ListOfSomeTypes.Where(s => s.Similarity(templateObject) > 75); 

또는 그들을 정렬하려면 : 궁극적으로

var sortedBySimilarity = ListOfSomeTypes.OrderByDescending(s => s.Similarity(templateObject)); 

를 내 포인트는 것을 일단 당신이, "공통점 가장을 가진"자신 만의 정의를 마련 할 필요가 있다는 것입니다하지만 나머지는 아마 꽤 쉬울 것입니다. 그 일이 반드시 쉬워지는 것은 아닙니다. 귀하의 질문에 자세한 내용과 함께

는 가능한 공식은 다음과 같습니다

public byte Similarity(A other) 
{ 
    byte similarity = 0; 
    if (this.b == null | other.b == null) 
     similarity += 25; 
    else if (this.b == other.b) 
     similarity += 50; 
    if (this.c == null | other.c == null) 
     similarity += 25; 
    else if (this.c == other.c) 
     similarity += 50; 
    return similarity; 
} 

이 가중치는 정확히 하나의 객체 약간 덜에서 가장 높은, null 값을 일치와 차이가 전혀.

Answer 2

나는 엄청난 양의 퍼지 (fuzzy) 매칭을 거대한 데이터 세트에 걸쳐 수행했으며, 고려해야 할 많은 시나리오가있다. 당신은 단순하거나 일반적인 경우에 접근하고있는 것처럼 보입니다. 그리고 많은 양의 데이터가없는 경우에는 일종의 일반적인 문자열 거리 비교가 적절 해 보입니다.

성능 측면에서 중요한 것은 "귀하의 데이터를 잘 알고 있습니다"입니다. 위에서 제안한대로 자신의 점수를 씁니다.

그런데, 우리는 퍼지 문자열 매칭을 위해 Levenshtein distance을 사용합니다. 두 문자열 간의 "거리"측면에서 매우 특정 적이 지 않으므로 주어진 문제에 대해 적절할 수도 있고 그렇지 않을 수도 있습니다. 다음은 C#에서 알고리즘의 빠른 복사/붙여 넣기입니다. 그것은 매우 쉽게 대부분의 언어로 포트. 이렇게하면 null 입력에 대한 예외가 발생하므로 적절하다고 생각되는 특별한 케이스 처리를 추가하십시오.

public static int LevenshteinDistance(string s, string t) 
{ 
    var sLen = s.Length; 
    var tLen = t.Length; 

    var d = new int[sLen + 1, tLen + 1]; 

    for (var i = 0; i <= sLen; d[i, 0] = i++) { } 
    for (var j = 0; j <= tLen; d[0, j] = j++) { } 

    for (var i = 1; i <= sLen; i++) 
    { 
     for (var j = 1; j <= tLen; j++) 
     { 
      var cost = (t[j - 1] == s[i - 1]) ? 0 : 1; 
      d[i, j] = Math.Min(
       Math.Min(d[i - 1, j] + 1, // a deletion 
       d[i, j - 1] + 1),   // an insertion 
       d[i - 1, j - 1] + cost); // a substitution 
     } 
    } 

    return d[sLen, tLen]; 
}