Distinct на основе входимости

#c_sharp #linq

Есть признаки документа и введенные вручную примечания к документу. Признак документа
содержит текстовое описание, которое может пересекаться с примечанием. Хочется (и требуется
по ТЗ) печатать что-то одно. В идеале - то, что длиннее, но для начала - хотя бы чтобы
остался только один.

Пример: в комментарии введено "поставить печать", в признаке - "Поставить печать!!!".

Описан следующий компарер:  

internal class StringIncludeComparer:IEqualityComparer
{
    public bool Equals(string x, string y)
    {
        if (x.ToUpper().Contains(y.ToUpper())) {return true;}
        if (y.ToUpper().Contains(x.ToUpper())) {return true;}
        return false;
    }

    public int GetHashCode(string obj)
    {
        return obj.GetHashCode();
    }
}


Собрав в итоге комментарии из документов и комментарии из признаков документов в
один List<{ID, Comment}> делаю следующее:  

from trp in tmpPostReport
group trp.Comment by trp.Id
into CommPers
select new { Id= CommPers.Key, Comment = string.Join("; ", 
    CommPers.Distinct(new StringIncludeComparer()).ToArray()) };


Но в итоге получаю строку "поставить печать; Поставить печать!!!"

Вопрос:  


Что не так с компарером?  
Как сделать так, чтобы при сравнении строк "поставить печать" и "Поставить печать!!!"
выбиралась всегда большая по длине, т.е. "Поставить печать!!!"

    

Ответы

Ответ 1

Ваша проблема в том, что GetHashCode не согласован с Equals. так делать нельзя. Должно
выполняться условие: если Equals возвращает true, то и хэшкоды должны быть равны.

Например, вы можете вернуть 0 в GetHashCode.



Для того, чтобы выбрать самую короткую строку, можно попробовать использовать groupby:

CommPers.GroupBy(s => s, new StringIncludeComparer())
        .Select(g => g.OrderBy(s => s.Length).First());


Но учтите, что для EqualityComparer'а ваше отношение равенства должно быть транзитивно,
как это отмечено в другом ответе. Поэтому код имеет право и не сработать.



Для того, чтобы ваше сравнение гарантировано работало несмотря на то, что оно нетранзитивно,
применим тяжёлую артиллерию. Откажемся от IEqualityComparer'а (так как мы всё равно
не можем удовлетворить его инвариант), и сделаем группировку, которая вычисляет транзитивное
замыкание вашего равенства: если Equals(a, b) и Equals(b, c) оба равны true, то мы
считаем элементы a и c равными вне зависимости от Equals(a, c) (и так далее). Заметьте,
что нам теперь придётся сравнивать (почти) каждый элемент с каждым, так что производительность
пострадает.

static class EnumerableExtensions
{
    class TransitiveGrouping : List, IGrouping
    {
        public TransitiveGrouping(K key) { Key = key; }
        public K Key { get; private set; }
        internal List EqualKeys = new List();
    }

    public static IEnumerable> TransitiveGroupBy(
            this IEnumerable sequence,
            Func keySelector,
            Func keyComparer)
    {
        var result = new List>();
        foreach (T curr in sequence)
        {
            K currKey = keySelector(curr);
            var containingGroups = result
                    .Where(tg => tg.EqualKeys.Any(kk => keyComparer(kk, currKey)))
                    .ToList();
            if (containingGroups.Count == 0)
            {
                // add a new group
                var newGroup = new TransitiveGrouping(currKey);
                newGroup.Add(curr);
                newGroup.EqualKeys.Add(currKey);
                result.Add(newGroup);
            }
            else
            {
                var targetGroup = containingGroups.First();
                targetGroup.Add(curr);
                // merge the groups (transitive closure)
                foreach (var group in containingGroups.Skip(1))
                {
                    targetGroup.AddRange(group);
                    targetGroup.EqualKeys.AddRange(group.EqualKeys);
                    result.Remove(group);
                }
            }
        }
        return result;
    }
}


Теперь ваш запрос должен работать так:

CommPers.TransitiveGroupBy(s => s, new StringIncludeComparer().Equals)
        .Select(g => g.OrderByDescending(s => s.Length).First());


Вот рабочий пример: http://ideone.com/OT2GqM

Я сильно не отлаживал, так что возможны баги. Если что, сообщайте, пофиксим.


Ответ 2

Ответ на вторую часть вопроса - это нельзя сделать в терминах сравнения, потому что
сравнение транзитивно ((a == b, a == c) => a == c), а ваш механизим сравнения - нет:

"поставить печать" == "Поставить печать!!!"
"поставить печать" == "Поставить печать???"
но
"Поставить печать!!!" != "Поставить печать???"


Кстати, из-за этого вы будете получать разные результаты при разном порядке входных
данных (ес-но, после того, как почините компарер вставив return 0; вGetHashCode):

var values = new List 
{ 
    "поставить печать",
    "Поставить печать!!!",
    "Поставить печать??"
};


var values2 = new List 
{ 
    "Поставить печать!!!",
    "Поставить печать??",
    "поставить печать"
};

// 1
Console.WriteLine(values.Distinct(new StringIncludeComparer()).Count());

// 2!
Console.WriteLine(values2.Distinct(new StringIncludeComparer()).Count());