使用编辑距离比较文件路径

Question

我需要弄清楚特定文件路径有多接近，Levenshtein 距离算法效果很好，但我需要以某种方式为目录树中较高的目录赋予权重。

例如：

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

我的两个目标是：

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

我需要第二个目标识别为更近，即使 "as a string" 它的编辑距离更大（因为目标二与源位于同一父目录 "x"，而第一个目标正在查看目录 "a"。

我将如何为字符串中较早出现的字符赋予权重？

Answer 1

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

我建议你把路径拆分成一个文件夹列表（最后是一个文件），然后我会比较相应位置的目录名（或驱动器）并给它一个高分如果它是完美匹配，则随着目录树的向下移动降低分数。

如果不匹配，您仍然可以在路径上应用 Levenshtein 距离并将其乘以权重，随着您进一步向下移动，权重会减小。

总结一下。

例如：

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;

Answer 2

如何使用“/”拆分源和目标，然后分别比较它们，这样第二个应该更接近

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]
            }
        }

Answer 3

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

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;        
}

对于所有内容都匹配的很长的路径，它可能无法工作，但这是一个问题，你将运行进入任何 "guessing" 算法，但类似的东西应该满足你的需求

使用编辑距离比较文件路径

Comparing file paths using Levenshtein Distance

java

c#

algorithm

comparison

string-comparison