C#如何计算含SID的注册表键字符串相似度（排除Levenshtein距离）

核心逻辑 #

不要直接对全串计算编辑距离，注册表键为固定层级结构，SID仅出现在HKEY_USERS的下一级节点位置，先做结构归一化处理排除SID的干扰，再计算相似度即可满足需求。

具体实现步骤 #

1. 编写SID匹配规则 #

Windows SID的标准格式为S-数字-数字段串，仅包含数字和短横线，用正则即可快速识别：
^S-\d-(?:\d+-)+\d+$

2. 实现注册表键归一化方法 #

将输入的注册表键按\分割为层级片段，遍历所有片段，将符合SID格式的片段统一替换为占位符{SID}，排除不同SID带来的无意义差异。

3. 相似度计算 #

• 若两个键归一化后的结果完全相等，直接判定为100%相似
• 若仍有差异，可对归一化后的字符串计算莱文斯坦距离，或按层级加权计算相似度（根节点、系统级节点权重高于自定义子节点，结果更贴合业务逻辑）

完整代码示例 #

using System;
using System.Linq;
using System.Text.RegularExpressions;

public static class RegistryKeySimilarity
{
    // SID匹配正则
    private static readonly Regex SidRegex = new Regex(@"^S-\d-(?:\d+-)+\d+$", RegexOptions.Compiled | RegexOptions.IgnoreCase);

    // 归一化注册表键
    private static string NormalizeRegistryKey(string key)
    {
        if (string.IsNullOrWhiteSpace(key)) return string.Empty;
        var segments = key.Split('\\');
        for (int i = 0; i < segments.Length; i++)
        {
            if (SidRegex.IsMatch(segments[i]))
            {
                segments[i] = "{SID}";
            }
        }
        return string.Join('\\', segments);
    }

    // 计算相似度（返回0-1的浮点数，1为完全相同）
    public static double GetSimilarity(string key1, string key2)
    {
        var normalized1 = NormalizeRegistryKey(key1);
        var normalized2 = NormalizeRegistryKey(key2);

        if (normalized1 == normalized2) return 1.0;

        // 归一化后仍有差异则计算莱文斯坦距离
        int distance = LevenshteinDistance(normalized1, normalized2);
        int maxLength = Math.Max(normalized1.Length, normalized2.Length);
        return maxLength == 0 ? 1.0 : 1 - (double)distance / maxLength;
    }

    // 莱文斯坦距离实现
    private static int LevenshteinDistance(string a, string b)
    {
        int[,] matrix = new int[a.Length + 1, b.Length + 1];
        for (int i = 0; i <= a.Length; i++) matrix[i, 0] = i;
        for (int j = 0; j <= b.Length; j++) matrix[0, j] = j;

        for (int j = 1; j <= b.Length; j++)
        {
            for (int i = 1; i <= a.Length; i++)
            {
                int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
                matrix[i, j] = Math.Min(Math.Min(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1), matrix[i - 1, j - 1] + cost);
            }
        }
        return matrix[a.Length, b.Length];
    }
}

// 调用示例
public class Program
{
    public static void Main()
    {
        string key1 = @"Computer\HKEY_USERS\S-1-5-21-123456789-1234567890-123456789-1001\SomethingHere\SomethingHere";
        string key2 = @"Computer\HKEY_USERS\S-1-5-21-987654321-0987654321-987654321-1002\SomethingHere\SomethingHere";
        
        double similarity = RegistryKeySimilarity.GetSimilarity(key1, key2);
        Console.WriteLine($"相似度：{similarity:P0}"); // 输出：相似度：100%
    }
}

效果说明 #

你提到的两个仅SID不同的注册表键，经过归一化后会变成完全相同的字符串，相似度为100%，符合预期。如果还有其他层级的差异，也能通过编辑距离计算得到准确的相似度结果。

内容的提问来源于stack exchange，提问作者rlnnclt