如果父目录也在列表中，则从列表中删除路径

Question

我的标题可能用词有点奇怪，所以这是我的情况：我有一堆目录路径，例如

/a/b
/a/b/c
/a/b/c/d
/a/e/f/g/h
/a/e/f/g/h/i/j/k/l
/a/e/f/g/m/n/o
/a/e/f/g/m/n/p

我想过滤掉列表中已经存在的条目的子路径的所有行，例如

/a/b
/a/e/f/g/h
/a/e/f/g/m/n/o
/a/e/f/g/m/n/p

目录路径是从 获得的find，因此它们应该可靠地按自上而下的顺序排列。解析为数组或多行字符串的解决方案都是受欢迎的。

Answer 1

我假设路径名列表可能没有排序，并且生成的路径名列表应该与输入中的顺序相同。我还假设没有路径名包含嵌入的换行符。

使用/bin/sh：

#!/bin/sh

set --
while IFS= read -r pathname; do
        for p do
                case $pathname in ("$p"/*) continue 2 ;; esac
        done

        set -- "$@" "$pathname"
done <list

printf '%s\n' "$@"

这将从文件中读取路径名list，一次一行。接受的路径名（最初是一个空列表）针对每个读取路径名进行测试，在内部循环中一次一个。如果接受的路径名是当前路径名的目录路径前缀，则丢弃当前路径名（内循环使用 跳到外循环的下一次迭代continue 2）。如果没有发现可接受的路径名是当前路径名的目录路径前缀，则接受当前路径名。

接受的路径名列表保存在位置参数中。

该bash外壳显然是能够运行上面的脚本，但如果你想要的东西专门为壳写的，你可以说

#!/bin/bash

accepted=()
while IFS= read -r pathname; do
        for p in "${accepted[@]}"; do
                [[ $pathname == "$p"/* ]] && continue 2
        done

        accepted+=("$pathname")
done <list

printf '%s\n' "${accepted[@]}"

使用awk与上述相同的方法：

$ awk '{ for (i=1; i<=n; ++i) if (index($0, accepted[i] "/") == 1) next; accepted[++n]=$0 } END { for (i=1; i<=n; ++i) print accepted[i] }' list
/a/b
/a/e/f/g/h
/a/e/f/g/m/n/o
/a/e/f/g/m/n/p

该awk代码，nicified：

{
        for (i = 1; i <= n; ++i)
                if (index($0, accepted[i] "/") == 1)
                        next

        accepted[++n] = $0
}

END {
        for (i = 1; i <= n; ++i)
                print accepted[i]
}

您应该能够在开始时看到此awk程序与 shell 代码变体之间的明显相似之处。

这用于index()测试接受的路径名是否是当前路径名的前缀。您可以if ($0 ~ "^" acceped[i] "/")改用，但这样做的一个缺点是路径名本身被用作正则表达式的一部分。这开始重要，一旦你有一个包含类似字符的路径名.和*等。

Answer 2

如果我没记错的话，一个标准化（*）或至少一致呈现的路径列表，按照通常的字典排序，在该目录之后立即出现一个目录的子目录（递归）。因此，仅查看前一条（未删除的）行就足够了。

_{（* 规范化，我的意思是/foo/baror /foo/bar/，而不是 eg /foo/asdf/../bar或/foo///bar//。输出find不会有问题，因为如果给定非规范化的起始目录，它确实会提供非规范化的输出，但输出至少是一致的。）}

一个路径仍然可以是另一个的前缀，而只是一个兄弟而不是父，例如/fooand /foobar。为了处理这种情况，我们可以在每一行还没有的行中添加一个尾部斜杠。

因此（添加/foo并/foobar添加到测试中，并且没有尝试打高尔夫球）：

$ sort paths.txt | awk '! /\/$/ { $0 = $0 "/" } 
                        last && last == substr($0, 1, length(last)) { next; } 
                        { last = $0; sub(/\/$/, "", $0); print }' 
/a/b
/a/e/f/g/h
/a/e/f/g/m/n/o
/a/e/f/g/m/n/p
/foo
/foobar

$0如果需要，第一行将斜线添加到当前行；last如果有，则第二个将行与最后存储的行 (in )进行比较，并删除匹配的行；第三个存储并打印任何未删除的行，删除尾部斜杠。（删除sub(...)以保留它们。）

Answer 3

一个简短的awk解决方案：

<infile sort -u |awk 'NR==1 || index($0, pre"/")!=1{print; pre=$0}'

Answer 4

使用 perl（和排序过程替换以保证输入已排序）：

$ perl -lne '
    unless (defined($paths) && m:^($paths)/:) {
      $paths{$_}++;
      $paths=join("|", map +( "\Q$_\E" ), keys %paths);
    };

    END { print join("\n", sort keys %paths) }' <(sort input.txt)
/a/b
/a/e/f/g/h
/a/e/f/g/m/n/o
/a/e/f/g/m/n/p

它逐步构建一个正则表达式匹配它已经看到的路径。如果之前未见过路径，则将其添加到%paths哈希中，哈希用于构建正则表达式并包含需要在脚本末尾打印的路径列表。

每个路径是通过\ Q和。\ E当加到正则表达式，以确保任何包围perlre元字符（如.，?，*，等）被禁用。