☰

如何从路径/文件列表中找到常用路径

tag-icon • tag-icon linux command-line unix sed string-manipulation
如何从路径/文件列表中找到常用路径

序幕：

给定一个已排序的路径/文件列表输入，如何找到它们的公共路径？

翻译成技术术语，如果从标准输入提供已排序的输入，如何从标准输入中选择最短的正确前缀？

这里的“前缀”具有正常含义，例如字符串“abcde”的前缀为“abc”。这是我的示例输入

$ echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2'
/home/dave
/home/dave/file1
/home/dave/sub2/file2

这是一个例子删除连续的正确前缀从标准输入，使用以下命令sed：

$ echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2' | sed "N; /^\(.*\)\n\1\//D; P; D" 
/home/dave/file1
/home/dave/sub2/file2

问题：

我的问题是如何保留正确的前缀相反，删除所有带有该前缀的行。由于和都/home/dave/file1带有/home/dave/sub2/file2前缀/home/dave，因此/home/dave将保留，而其他两个则不会保留。即，它将sed执行与上述命令完全相反的操作。

更多信息：

  • 输入已经排序
  • 如果我有/home/dave /home/dave/file1 /home/phil /home/phil/file2（echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2\n/home/phil\n/home/phil/file2'），我会期望/home/dave和/home/phil是答案。

应用：

我有两个磁盘卷，它们包含类似的内容。我想将 v1 中有但 v2 中缺少的内容复制到另一个磁盘卷 v3 中。使用find、sort和comm，我能够获得要复制的内容的列表，但我需要进一步清理该列表。也就是说，只要/home/dave列表中有，我就不需要另外两个。

谢谢！

答案1

此答案使用 Python。由于 OP 想要删除其父级所覆盖的目录（我认为这是可能的），因此我开始编写另一个程序来删除覆盖物：

例子：

$ echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2\n/home/phil\n/home/phil/file1' | removecoverings 
/home/phil
/home/dave

命令代码removecoverings：

#!/usr/bin/env python2

import sys

def list_startswith(a, b):
    if not len(a) >= len(b):
        return False
    return all(x == y for x,y in zip(a[:len(b)],b))

def removecoverings(it):
    g = list(it)
    g.sort(key=lambda v: len(v.split('/')), reverse=True)
    o = []
    while g:
        c = g.pop()
        d = []
        for v in g:
            if list_startswith(v.split('/'), c.split('/')):
                d.append(v)
        for v in d:
            g.remove(v)
        o.append(c)
    return o

for o in removecoverings(l.strip() for l in sys.stdin.readlines()):
    print o

此答案使用 Python。它还执行组件式而非字符串式公共前缀。对于路径来说，更好的选择是，和的公共前缀/ex/ample不应/exa/mple是/。/ex这假设想要的是最大公共前缀，而不是删除其覆盖物的前缀列表。如果您有/home/dave /home/dave/file1 /home/phil /home/phil/file2和期望/home/dave /home/phil而不是/home。这不是您想要的答案。

例子：

$ echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2' | commonprefix 
/home/dave

命令代码commonprefix：

#!/usr/bin/env python2

import sys

def commonprefix(l):
    # this unlike the os.path.commonprefix version
    # always returns path prefixes as it compares
    # path component wise
    cp = []
    ls = [p.split('/') for p in l]
    ml = min( len(p) for p in ls )

    for i in range(ml):

        s = set( p[i] for p in ls )         
        if len(s) != 1:
            break

        cp.append(s.pop())

    return '/'.join(cp)

print commonprefix(l.strip() for l in sys.stdin.readlines())

答案2

假设输入已经排序，伪代码将是：

$seen = last_line;
if current_line begins exactly as $seen then next
else { output current_line; $seen = current_line }

翻译成 Perl 代码（是的，Perl，最漂亮的脚本语言）：

perl -e '
my $l = "\n";
while (<>) {
    if ($_ !~ /^\Q$l/) {
        print;
        chomp;
        $l = $_;
    }
}
'

信用：Ben Bacarisse @bsb.me.uk，来自 comp.lang.perl.misc。谢谢 Ben，它运行得很好！

答案3

还有 xpt 答案的单行版本。同样，假设输入已排序：

perl -lne 'BEGIN { $l="\n"; }; if ($_ !~ /^\Q$l/) { print $_; $l = $_; }'

在示例输入上运行

/home/dave
/home/dave/file1
/home/dave/sub2/file2
/home/phil
/home/phil/file2

使用

echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2\n/home/phil\n/home/phil/file2' | perl -lne 'BEGIN { $l="\n"; }; if ($_ !~ /^\Q$l/) { print $_; $l = $_; }'

给出

/home/dave
/home/phil

魔法在于 perl 的命令行参数：-e允许我们在命令行上给出一个脚本，-n遍历文件的各行（将每一行放在中$_），并-l为我们处理换行符。

该脚本通过使用l来跟踪最后看到的前缀来工作。该BEGIN块在读取第一行之前运行，并将变量初始化为不会看到的字符串（没有换行符）。条件在文件的每一行上运行（由 保存）$_。条件在文件的所有行上执行，并表示“如果该行没有 的当前值l作为前缀，则打印该行并将其保存为 的值l。”由于命令行参数，这与其他脚本基本相同。

问题是，这两个脚本都假设公共前缀作为其自己的行存在，因此不会找到类似输入的公共前缀

/home/dave/file1
/home/dave/file2

相关内容