使用Levenstein Distance比较文件路径

本文关键字：文件 路径 比较 Distance Levenstein 使用 | 更新日期: 2023-09-27 18:27:43

我需要弄清楚特定文件路径有多近，Levenstein距离算法工作得很好，但我需要以某种方式给目录树上更高的目录赋予权重。

例如：

我的来源是"x:/t/c/d"

我的两个目标是：

  • "a:/t/c/d"
  • "x:/t/y/z"

我需要第二个目标识别为更近，即使"作为字符串"它的编辑距离更大（因为目标二与源在同一父目录"x"中，而第一个目标在目录"a"中

我该如何对字符串中较早出现的字符进行加权？

使用Levenstein Distance比较文件路径

在我看来，完整路径上的Levenstein距离不是您想要实现的正确算法。

我建议你把路径分成一个文件夹列表（最终在末尾有一个文件），然后我会比较相应位置的目录名（或驱动器），如果它是完美匹配的，我会给它一个高分，随着你沿着目录树走得更远，我会降低分数。

如果不匹配，那么你仍然可以在路径上应用Levenstein距离，并将其乘以一个权重，这个权重会随着你走得更远而减小。

而不是把它全部总结起来。

例如：

var source = "x:/t/c/d";
var targets = new[] { "a:/t/c/d", "x:/t/y/z" };
var separator = '/';
var sourceParts = source.Split(separator);
var weight = 10;
var match = 100;
var scores = targets.Select(target =>
{
    var score = sourceParts
        .Zip(target.Split(separator), (s, t) => new Tuple<string, string>(s, t))
        .Select(
            (tuple, i) => tuple.Item1 == tuple.Item2
                ? match * GetWeight(i)
                : LevenshteinDistance(tuple.Item1, tuple.Item2) * GetWeight(i)
        ).Sum();
    return new
    {
        Target = target,
        Score = score
    };
});

其中GetWeight（）类似于：

private static int MaxWeight = 10;
private static int GetWeight(int i) => i < MaxWeight ? MaxWeight - i : 1;

如何拆分源和目标usind"/"，然后分别比较它们中的每一个，这样第二个应该是更接近的

C#代码：

        var source = "x:/t/c/d";
        var sourceSplitted = source.Split('/');
        List<string> targets = new List<string>() { "a:/t/c/d", "x:/t/y/z" };
        for (int i = 0; i < sourceSplitted.Length; i++)
        {
            foreach (var item in targets)
            {
                var targetSplitted = item.Split('/');
                // Calculate levenshtein here using sourceSplitted[i] and targetSplitted[i]
            }
        }

建议将路径拆分，并从后面开始给它一个反向权重，伪码为：

currPath = null
currMin = int.Max

for (path in paths){ 
    var curr = 0
    var idx = 1;
    for ( x in Inverse( Split ( path ) ) ) { 
        curr+= idx * LevenshteinDistance( x )
        idx++;
    }
    if(idx < currMin)
        currPath = path;        
}

对于所有匹配的很长路径，它可能不起作用，但这是任何"猜测"算法都会遇到的问题，但类似的算法应该满足您的需求

相关文章：