模糊比较与加权字段(建议类似的实例)

本文关键字：实例 比较 加权 字段 模糊 | 更新日期: 2023-09-27 18:17:20

今天我遇到了一个特定的任务，并喜欢用一个干净的代码来解决它，所以决定与班上的其他同学分享它会很酷-但是，嘿，让它以问题的形式存在。

任务:

给定一个类型为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!"}

字段的重要性:

  • : 30%
    • <
  • B: 50%/gh><
  • C: 20%/gh>

示例输出:

[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的算法可以是任何已知的模糊比较算法，这不是这里真正的重点。

那么如何将可能的建议列表转换为有序建议的实际列表呢?(哦，上帝，请帮助等)

模糊比较与加权字段(建议类似的实例)

对于我们的例子，让我们使用令人敬畏的Levenshtein距离算法。

那么假设我们有一个签名如下的函数:

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%相似(不错!)

为了帮助我们处理加权字段，让我们创建一个小helper类:

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

这对你来说可能看起来很好，或者它可以被修改成更符合你的喜好的用法，但我希望这个想法是清晰的，有人会发现它有用;)

p。S

当然，相似度阈值可以作为参数传入。请随意添加任何想法和评论，如何使这更好或更可读!

相关文章：