Нечеткое сравнение со взвешенными полями (предложить похожие случаи)

Question

Сегодня я столкнулся с определенной задачей и получил удовольствие от ее решения с помощью чистого кода, поэтому решил, что было бы здорово поделиться ею с остальными членами класса - но, эй, давайте оставим это в формате вопроса.

Задание:

Учитывая экземпляр типа T (источник) и коллекция экземпляров типа T (возможные предложения), Предоставьте предложения, которые похожи на источник, упорядочены по сходству и полностью исключают предложения, у которых их сходство ниже определенного порога.

Сходством будет сравнение нечетких строк нескольких полей экземпляра, каждое из которых имеет вес важности.

Пример ввода:

Исходный экземпляр:

{A = "Hello", B = "World", C = "and welcome!"}

Возможные предложения:

{A = "Hola", B = "World", C = "Welcome!"}
{A = "Bye", B = "world", C = "and fairwell"}
{A = "Hell", B = "World", C = "arrives..."}
{A = "Hello", B = "Earth", C = "and welcome!"}
{A = "Hi", B = "world", C = "welcome!"}

Важность полей:

• A: 30%
• B: 50%
• С: 20%

Пример вывода:

[0] = {A = "Hell", B = "World", C = "arrives..."}
[1] = {A = "Hola", B = "World", C = "Welcome!"}
[2] = {A = "Hello", B = "Earth", C = "and welcome!"}
[3] = {A = "Hi", B = "world", C = "welcome!"}

Обратите внимание, что возможное предложение Bye;world;and fairwell здесь вообще нет, так как не соответствует минимальному порогу подобия (скажем, порог по крайней мере 50% Взвешенный-подобия)

Первый результат наиболее похож на источник, хотя C поле совсем не похоже на источник, потому что мы дали C вес всего 20%и два других поля с более тяжелым весом очень похожи (или точно совпадают) с источником.

Примечание нечеткого сравнения

Алгоритм, который будет использоваться для сравнения string a а также string b это может быть любой из известных алгоритмов нечеткого сравнения, здесь не совсем так.

Итак, как можно превратить этот список возможных предложений в реальный список заказанных предложений? (Господи, пожалуйста, помогите, и т. Д.)

Answer 1

Для нашего случая, давайте использовать удивительный алгоритм расстояния Левенштейна.

Предположим, у нас есть функция со следующей сигнатурой:

private static int CalcLevenshteinDistance(string a, string b)

И на самом деле получить сходство между a а также bвместо расстояния мы будем использовать:

private static decimal CalcLevenshteinSimilarity(string a, string b)
{
    return 1 - ((decimal)CalcLevenshteinDistance(a, b) /
                Math.Max(a.Length, b.Length));
}

Это вернется точно 1 если строки точно такие же, 0 если строки не похожи вообще или где-то между. Например, 0.89 было бы что a а также b являются 89% похоже (не плохо!)

Чтобы помочь нам с взвешенными полями, давайте создадим небольшой вспомогательный класс:

public class SuggestionField
{
    public string SourceData { get; set; }
    public string SuggestedData { get; set; }
    public decimal Importance { get; set; }
}

Это будет представлять всю информацию, необходимую для соответствия одного поля типа T к источнику T пример.

Теперь вычислить взвешенное сходство между одним предложением и источником довольно просто:

private static decimal RateSuggestion(IEnumerable<SuggestionField> fields)
{
    return fields.Sum(x =>
        x.Importance * CalcLevenshteinSimilarity(x.SourceData,
                                                 x.SuggestedData));
}

Теперь давайте обернем его в функцию, которая получает все возможные предложения, а также SuggestionFieldдействительно классным и простым в использовании способом:

public static IEnumerable<T> Suggest<T>
    (IEnumerable<T> possibleSuggestions,
     params Func<T, SuggestionField>[] fieldSelectors)
{
    return possibleSuggestions
        .Select(x => new
                     {
                         Suggestion = x,
                         Similarity = RateSuggestion(fieldSelectors.Select(f => f(x)))
                     })
        .OrderByDescending(x => x.Similarity)
        .TakeWhile(x => x.Similarity > 0.5m) // <-- Threshold here!
        .Select(x => x.Suggestion);
}

Ладно, ладно, этот кусок кода может на первый взгляд немного запутать, но расслабьтесь. Основное замешательство, вероятно, происходит от params Func<T, SuggestionField>[] fieldSelectors и, следовательно, из Similarity = RateSuggestion(fieldSelectors.Select(f => f(x))) также.

Тем из вас, кто силен в Linq и во всех тех играх с селекторами, уже может быть понятно, как можно использовать эту функцию. В любом случае, это будет понятно в одно мгновение!

Использование:

// I'll be using anonymous types here, but you don't have to be lazy about it
var src = new {A = "Hello", B = "World", C = "and welcome!"};
var possibleSuggestions =
    new[]
    {
        new {A = "Hola", B = "World", C = "Welcome!"},
        new {A = "Bye", B = "world", C = "and fairwell"},
        new {A = "Hell", B = "World", C = "arrives..."},
        new {A = "Hello", B = "Earth", C = "and welcome!"},
        new {A = "Hi", B = "world", C = "welcome!"}
    };

var suggestions =
    Suggest(possibleSuggestions,
            x => new SuggestionField
                 {
                     SourceData = src.A,
                     SuggestedData = x.A,
                     Importance = 0.3m // 30%
                 },
            x => new SuggestionField
                 {
                     SourceData = src.B,
                     SuggestedData = x.B,
                     Importance = 0.5m // 50%
                 },
            x => new SuggestionField
                 {
                     SourceData = src.C,
                     SuggestedData = x.C,
                     Importance = 0.2m // 20%
                 }).ToArray();

Это может показаться вам хорошим, как есть, или его можно изменить, чтобы использовать его по своему вкусу, но я надеюсь, что идея ясна, и кто-то найдет ее полезной;)

PS

Конечно, порог сходства может быть передан в качестве параметра. Не стесняйтесь добавлять любые идеи и комментировать, как сделать это лучше или более читабельным!