使用Levenshtein比較文件路徑距離

我需要弄清楚特定文件路徑的接近程度，Levenshtein距離算法的效果很好，但我需要以某種方式給目錄樹上更高的目錄加權。使用Levenshtein比較文件路徑距離

例如：

我的來源是「X：/ T/C/d」

和我的兩個目標是：

「A：/ T/C/d」
「X：/ T/Y/Z」

我還需要第二目標確定爲接近，即使「作爲一個字符串」這是編輯距離很大呃（因爲目標二與目標源在同一個父目錄「x」中，而第一個目標正在查看目錄「a」。

我該如何去衡量出現在字符串中較早出現的字符？

來源

2015-12-21 Ofek

爲什麼有人給這個投票呢？感覺這個問題很有意思，這個人擡起了Levenshtein的距離並應用了它，所以不確定downvote是什麼 – konkked

在我看來，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;

來源

2015-12-21 23:51:32 AleFranz

如何分割源和目標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] 
      } 
     }

來源

2015-12-21 23:56:55

建議分裂的道路，並給予它從後面開始反重，僞代碼將是：

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

對這裏的一切匹配，那麼它可能無法正常工作很長的路，但是這是一個問題你會遇到任何「猜測」算法，但類似的東西應該涵蓋您的需求

來源

2015-12-22 00:03:06 konkked

使用Levenshtein比較文件路徑距離

回答

相關問題