在文件和目录列表中查找公共父路径

问题描述 投票：0回答：8

我得到了文件和目录的列表

List<string> pathes
。现在我想计算每条路径彼此共享的最深公共分支。

我们可以假设它们都有一条共同的路径，但这在开始时是未知的。

假设我有以下三个条目：

  • C:/Hello/World/This/Is/An/Example/Bla.cs
  • C：/你好/世界/这个/是/不是/一个/示例/
  • C：/你好/地球/Bla/Bla/Bla

这应该得到结果：C:/Hello/，因为地球正在打破这个子目录“链”。

第二个例子：

  • C:/Hello/World/This/Is/An/Example/Bla.cs
  • C：/你好/世界/这个/是/不是/一个/示例/

-> C:/Hello/World/这/是/

你将如何进行？我尝试使用 string.split(@"/") 并从第一个字符串开始，检查该数组的每个部分是否包含在其他字符串中。然而，这将是一个非常昂贵的调用，因为我正在迭代 (list_of_entries)^list_of_entries。有没有更好的解决方案？

我当前的尝试类似于以下内容（C# + LINQ）：

    public string CalculateCommonPath(IEnumerable<string> paths)
    {
        int minSlash = int.MaxValue;
        string minPath = null;
        foreach (var path in paths)
        {
            int splits = path.Split('\\').Count();
            if (minSlash > splits)
            {
                minSlash = splits;
                minPath = path;
            }
        }

        if (minPath != null)
        {
            string[] splits = minPath.Split('\\');
            for (int i = 0; i < minSlash; i++)
            {
                if (paths.Any(x => !x.StartsWith(splits[i])))
                {
                    return i >= 0 ? splits.Take(i).ToString() : "";
                }
            }
        }
        return minPath;
    }
c# string url utility-method
8个回答
10
投票

获取最长公共前缀的函数可能如下所示：

public static string GetLongestCommonPrefix(string[] s)
{
    int k = s[0].Length;
    for (int i = 1; i < s.Length; i++)
    {
        k = Math.Min(k, s[i].Length);
        for (int j = 0; j < k; j++)
            if (s[i][j] != s[0][j])
            {
                k = j;
                break;
            }
    }
    return s[0].Substring(0, k);
}

那么你可能需要剪掉右手的前缀。例如。我们想要返回 

c:/dir
而不是 
c:/dir/file
for 

c:/dir/file1
c:/dir/file2

您可能还想在处理之前规范化路径。请参阅在 C# 中标准化目录名称。

7
投票

我不知道这是否是性能最好的解决方案（可能不是），但它肯定很容易实现。

  • 按字母顺序对列表进行排序
  • 逐个字符地比较该排序列表中的第一个条目与该列表中的最后一个条目，并在发现差异时终止（终止之前的值是这两个字符串中最长的共享子字符串）

小提琴样本

示例代码：

List<string> paths = new List<string>();

paths.Add(@"C:/Hello/World/This/Is/An/Example/Bla.cs");
paths.Add(@"C:/Hello/World/This/Is/Not/An/Example/");
paths.Add(@"C:/Hello/Earth/Bla/Bla/Bla");

List<string> sortedPaths = paths.OrderBy(s => s).ToList();

Console.WriteLine("Most common path here: {0}", sharedSubstring(sortedPaths[0], sortedPaths[sortedPaths.Count - 1]));

当然还有这个功能：

public static string sharedSubstring(string string1, string string2)
{
    string ret = string.Empty;

    int index = 1;
    while (string1.Substring(0, index) == string2.Substring(0, index))
    {
        ret = string1.Substring(0, index);
        index++;
    }

    return ret;
} // returns an empty string if no common characters where found
2
投票

首先使用要检查的路径对列表进行排序。然后，您可以拆分并比较第一个和最后一个项目 - 如果它们相同，则继续到下一个维度，直到找到差异。

所以你只需要排序一次，然后检查两项。

2
投票

返回 

c:/dir

c:/dir/file1
c:/dir/file2

我会这样编码：

public static string GetLongestCommonPrefix(params string[] s)
{
    return GetLongestCommonPrefix((ICollection<string>)s);
}

public static string GetLongestCommonPrefix(ICollection<string> paths)
{
    if (paths == null || paths.Count == 0)
        return null;


    if (paths.Count == 1)
        return paths.First();

    var allSplittedPaths = paths.Select(p => p.Split('\\')).ToList();

    var min = allSplittedPaths.Min(a => a.Length);
    var i = 0;
    for (i = 0; i < min; i++)
    {
        var reference = allSplittedPaths[0][i];
        if (allSplittedPaths.Any(a => !string.Equals(a[i], reference, StringComparison.OrdinalIgnoreCase)))
        {
            break;
        }
    }

    return string.Join("\\", allSplittedPaths[0].Take(i));
}

这里有一些测试：

[TestMethod]
public void GetLongestCommonPrefixTest()
{
    var str1 = @"C:\dir\dir1\file1";
    var str2 = @"C:\dir\dir1\file2";
    var str3 = @"C:\dir\dir1\file3";
    var str4 = @"C:\dir\dir2\file3";
    var str5 = @"C:\dir\dir1\file1\file3";
    var str6 = @"C:\dir\dir1\file1\file3";


    var res = Utilities.GetLongestCommonPrefix(str1, str2, str3);

    Assert.AreEqual(@"C:\dir\dir1", res);

    var res2 = Utilities.GetLongestCommonPrefix(str1, str2, str3, str4);

    Assert.AreEqual(@"C:\dir", res2);

    var res3 = Utilities.GetLongestCommonPrefix(str1, str2, str3, str5);

    Assert.AreEqual(@"C:\dir\dir1", res3);

    var res4 = Utilities.GetLongestCommonPrefix(str5, str6);

    Assert.AreEqual(@"C:\dir\dir1\file1\file3", res4);

    var res5 = Utilities.GetLongestCommonPrefix(str5);

    Assert.AreEqual(str5, res5);

    var res6 = Utilities.GetLongestCommonPrefix();

    Assert.AreEqual(null, res6);

    var res7 = Utilities.GetLongestCommonPrefix(null);

    Assert.AreEqual(null, res7);
}
1
投票

我将迭代第一个路径中的每个字符，将其与路径集合中每个路径（第一个路径除外）中的每个字符进行比较：

public string FindCommonPath(List<string> paths)
{
    string firstPath = paths[0];
    bool same = true;

    int i = 0;

    string commonPath = string.Empty;

    while (same && i < firstPath.Length)
    {
        for (int p = 1; p < paths.Count && same; p++)
        {
            same = firstPath[i] == paths[p][i];
        }

        if (same)
        {
            commonPath += firstPath[i];
        }
        i++;
    }

    return commonPath;
}

您可以首先迭代列表以找到最短路径，并可能稍微改进它。

1
投票

为您提供最长的公共目录路径和尽可能复杂的功能：

private static string GetCommonPath(IEnumerable<string> files)
{
    // O(N, L) = N*L; N  - number of strings, L - string length

    // if the first and last path from alphabetic order matches, all paths in between match
    string first = null;//smallest string
    string last = null;//largest string

    var comparer = StringComparer.InvariantCultureIgnoreCase;
    // find smallest and largest string:
    foreach (var file in files.Where(p => !string.IsNullOrWhiteSpace(p)))
    {
        if (last == null || comparer.Compare(file, last) > 0)
        {
            last = file;
        }

        if (first == null || comparer.Compare(file, first) < 0)
        {
            first = file;
        }
    }

    if (first == null)
    {
        // the list is empty
        return string.Empty;
    }

    if (first.Length > last.Length)
    {
        // first should not be longer
        var tmp = first;
        first = last;
        last = tmp;
    }

    // get minimal length
    var count = first.Length;
    var found = string.Empty;

    const char dirChar = '\\';
    var sb = new StringBuilder(count);
    for (var idx = 0; idx < count; idx++)
    {
        var current = first[idx];
        var x = char.ToLowerInvariant(current);
        var y = char.ToLowerInvariant(last[idx]);

        if (x != y)
        {
            // first and last string character is different - break
            return found;
        }

        sb.Append(current);

        if (current == dirChar)
        {
            // end of dir character
            found = sb.ToString();
        }
    }

    if (last.Length >= count && last[count] == dirChar)
    {
        // whole first is common root:
        return first;
    }

    return found;
}
0
投票

这比通过斜杠分割路径并比较它们要优化得多：

private static string FindCommonPath(string[] paths) {
    var firstPath = paths[0];
    var commonPathLength = firstPath.Length;

    for (int i = 1; i < paths.Length; i++)
    {
        var otherPath = paths[i];
        var pos = -1;
        var checkpoint = -1;

        while (true)
        {
            pos++;

            if (pos == commonPathLength)
            {
                if (pos == otherPath.Length
                    || (pos < otherPath.Length
                        && (otherPath[pos] == '/' || otherPath[pos] == '\\')))
                {
                    checkpoint = pos;
                }
                break;
            }

            if (pos == otherPath.Length)
            {
                if (pos == commonPathLength
                || (pos < commonPathLength
                    && (firstPath[pos] == '/' || firstPath[pos] == '\\')))
                {
                    checkpoint = pos;
                }
                break;
            }

            if ((firstPath[pos] == '/' || firstPath[pos] == '\\')
                && (otherPath[pos] == '/' || otherPath[pos] == '\\'))
            {
                checkpoint = pos;
                continue;
            }

            var a = char.ToLowerInvariant(firstPath[pos]);
            var b = char.ToLowerInvariant(otherPath[pos]);

            if (a != b)
                break;
        }

        if (checkpoint == 0 && (firstPath[0] == '/' || firstPath[0] == '\\'))
            commonPathLength = 1;
        else commonPathLength = checkpoint;

        if (commonPathLength == -1 || commonPathLength == 0)
            return "";
    }

    return firstPath.Substring(0, commonPathLength);
}
0
投票

这是我提出的一种方法，该方法本质上将路径集合展平为唯一段变体的堆栈，并使用计数方法通过在最大段变体计数发散时终止解析来找出公共基本父路径，这表明存在超过某一点就没有普通孩子了。

注意：这仅适用于 Windows/NTFS 样式路径。

它在 PowerShell 中，但转换为其他 .Net 语言并不困难。

在 PowerShell 脚本应用程序中进行测试，该应用程序在每次运行中处理数十个或数千个路径。它的性能相对较好，（尽管很复杂）线性时间复杂度为 O(nm + xy)，其中 m 和 y 在每次迭代中都会变化：n 是路径数，m 是每条路径的路径段数，x是 n 个路径集合中任何给定路径中路径段的最大数量，y 是 n 个路径集合中给定段索引的唯一路径段变体的数量。从大约 8600 个目录路径字符串（平均每毫秒大约 32 个路径）解析公共基本路径大约需要 225 毫秒。因此，如果您有一百万条路径的列表，它的性能可能不够（推测约为 32 秒）。

它适用于已排序的数组，以最大程度地减少需要调整数组大小的次数。我认为在最坏的情况下，它可能是一个平均优化，平均情况下，它可能是一个小的优化，而最好的情况下，它可能会使其变慢或可以忽略不计。我不确定，因为我没有做过性能测试，但这是我的感觉。

function resolveCommonBase {
    param(
        [array]$from
    )

    Write-Host "Resolving a common base path from $($from.Length) paths";

    $pathSegments = $null;
    foreach ($dir in ($from | Sort-Object -Property Length -Descending)) {
        $segments = $dir.Split("\", [System.StringSplitOptions]::RemoveEmptyEntries);
        if (-not $pathSegments) {
            $pathSegments = [array]::CreateInstance([hashtable], $segments.Length);
        }

        if ($segments.Length -gt $pathSegments.Length) {
            [array]::Resize([ref] $pathSegments, $segments.Length);
        }

        for ($i = 0; $i -lt $segments.Length; $i += 1) {
            if (-not $pathSegments[$i]) {
                $pathSegments[$i] = @{$segments[$i] = 1};
            }
            elseif (-not $pathSegments[$i][$segments[$i]]) {
                $pathSegments[$i][$segments[$i]] = 1;
            }
            else {
                $pathSegments[$i][$segments[$i]] += 1;
            }
        }
    }

    $commonBase = "";
    $candidateSegmentKey = "[\candidate\]";

    for ($i = 0; $i -lt $pathSegments.Length; $i += 1) {
        $candidateSegment = $null;

        foreach ($segment in $pathSegments[$i].GetEnumerator()) {
            if (-not $candidateSegment -or $segment.Value -gt $candidateSegment.Value) {
                $candidateSegment = $segment;
            }
        }
        $pathSegments[$i][$candidateSegmentKey] = $candidateSegment;

        if (-not $commonBase) {
            $commonBase = $candidateSegment.Key;
        }
        elseif ($candidateSegment.Value -eq $pathSegments[$i - 1][$candidateSegmentKey].Value) {
            $commonBase = "$commonBase\$($candidateSegment.Key)";
        }
        else {
            break;
        }
    }

    Write-Host "Found common base path $commonBase";

    if ($commonBase -match "^[a-zA-Z]:`$") {
        return "$commonBase\";
    }
    return $commonBase;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.