将路径规范分解为最长公共前缀+后缀

将路径规范分解为最长公共前缀+后缀

给定任意两个 Unix 绝对路径眼镜如图 1 所示,可以将每个规范分解为最长公共前缀和特定后缀的串联。例如,

/abc/bcd/cdf     -> /abc/bcd + cdf
/abc/bcd/chi/hij -> /abc/bcd + chi/hij

是否有 Unix 实用程序(或多个实用程序)来计算此类分解? (我添加了“或实用程序”,以防有单独的实用程序用于计算最长公共前缀和计算相对路径。)

(我意识到编写此类实用程序并不是非常困难,但只要有可能,我会尝试优先考虑或多或少标准的工具而不是定制的工具。)

1我写“路径规范”而不是“路径”来回避问题,例如给定文件系统中(路径)的存在、链接等。

答案1

您可以使用以下命令计算行列表的最长公共前导子字符串:

sed -e '1{h;d;}' -e 'G;s,\(.*\).*\n\1.*,\1,;h;$!d'

例如:

/abc/bcd/cdf
/abc/bcd/cdf/foo
/abc/bcd/chi/hij
/abc/bcd/cdd

返回:

/abc/bcd/c

要将其限制为路径组件:

sed -e 's,$,/,;1{h;d;}' -e 'G;s,\(.*/\).*\n\1.*,\1,;h;$!d;s,/$,,'

(返回/abc/bcd上面的示例)。

答案2

您可以在 shell 循环中执行此操作。下面的代码应该适用于带有额外斜杠的各种奇怪路径;如果你所有的路径都是这种形式/foo/bar,你可以使用更简单的东西。

split_common_prefix () {
  path1=$1
  path2=$2
  common_prefix=
  ## Handle initial // specially
  case $path1 in
    //[!/]*) case $path2 in
               //[!/]*) common_prefix=/ path1=${path1#/} path2=${path2#/};;
               *) return;;
             esac;;
    /*) case $path2 in
          /*) :;;
          *) return;;
        esac;;
    *) case $path2 in /*) return;; esac;;
  esac
  ## Normalize multiple slashes
  trailing_slash1= trailing_slash2=
  case $path1 in */) trailing_slash1=/;; esac
  case $path2 in */) trailing_slash2=/;; esac
  path1=$(printf %s/ "$path1" | tr -s / /)
  path2=$(printf %s/ "$path2" | tr -s / /)
  if [ -z "$trailing_slash1" ]; then path1=${path1%/}; fi
  if [ -z "$trailing_slash2" ]; then path2=${path2%/}; fi
  ## Handle the complete prefix case (faster, necessary for equality and
  ## for some cases with trailing slashes)
  case $path1 in
    "$path2")
      common_prefix=$path1; path1= path2=
      return;;
    "$path2"/*)
      common_prefix=$path2; path1=${path1#$common_prefix} path2=
      return;;
  esac
  case $path2 in
    "$path1"/*)
      common_prefix=$path1; path1= path2=${path2#$common_prefix}
      return;;
  esac
  ## Handle the generic case
  while prefix1=${path1%%/*} prefix2=${path2%%/*}
        [ "$prefix1" = "$prefix2" ]
  do
    common_prefix=$common_prefix$prefix1/
    path1=${path1#$prefix1/} path2=${path2#$prefix1/}
  done
}

或者,确定两个字符串的最长公共前缀并将其修剪到最后/一个字符(除非公共前缀仅由斜杠组成)。

答案3

据我所知,还没有这样的工具。但是,您可以轻松编写这样的程序,因为您必须确定最长的组件组。

“一行”示例:

echo /abc/bcd/cdf | awk -vpath=/abc/bcd/chi/hij -F/ '{ OFS="\n";len=0; split(path, components); for (i=1; i<=NF; i++) if($i == components[i])len+=1+length($i);else break;print substr($0, 1, len - 1), substr($0, len + 1), substr(path, len + 1);exit;}

带注释的格式化版本:

$ cat longest-path.awk
#!/usr/bin/awk -f
BEGIN {
    FS="/";   # split by slash
}
{
    len=0;                      # initially the longest path has length 1
    split(path, components);    # split by directory separator (slash)
    for (i=1; i<=NF; i++) {     # loop through all path components
        if ($i == components[i]) {
            len += 1 + length($i);
        } else {
            break;              # if there is a mismatch, terminate
        }
    }
    print substr($0, 1, len - 1);  # longest prefix minus slash
    print substr($0, len + 1);     # remainder stdin
    print substr(path, len + 1);   # remainder path
    exit;                          # only the first line is compared
}
$ echo  /abc/bcd/cdf | ./longest-path.awk -vpath=/abc/bcd/chi/hij
/abc/bcd
cdf
chi/hij

答案4

Stéphane Chazelas 已经展示了一个基于 sed 的解决方案。我遇到了一个略有不同的ack 的 sed 表达式我在下面定制来回答这个问题。具体来说,我将其限制为路径组件并处理路径组件中换行符的可能性。然后我演示如何使用它将路径规范分解为最长公共引导路径组件+剩余路径分量

我们将从ack 的 sed 表达式(我将其切换为ERE语法):

sed -E '$!{N;s/^(.*).*\n\1.*$/\1\n\1/;D;}' <<"EOF'
/abc/bcd/cdf
/abc/bcd/cdf/foo
/abc/bcd/chi/hij
/abc/bcd/cdd
EOF

/abc/bcd/c正如预期的那样。 ✔️

要将其限制为路径组件:

sed -E '$!{N;s|^(.*/).*\n\1.*$|\1\n\1|;D;};s|/$||' <<'EOF'
/abc/bcd/cdf
/abc/bcd/cdf/foo
/abc/bcd/chi/hij
/abc/bcd/cdd
EOF

/abc/bcd正如预期的那样。 ✔️

使用换行符处理路径组件

出于测试目的,我们将使用以下路径规范数组:

a=(
  $'/a\n/b/\nc  d\n/\n\ne/f'
  $'/a\n/b/\nc  d\n/\ne/f'
  $'/a\n/b/\nc  d\n/\ne\n/f'
  $'/a\n/b/\nc  d\n/\nef'
)

通过检查我们可以看到最长公共引导路径组件是:

$'/a\n/b/\nc  d\n'

这可以通过以下方式计算并捕获在变量中:

longest_common_leading_path_component=$(
  printf '%s\0' "${a[@]}" \
    | sed -zE '$!{N;s|^(.*/).*\x00\1.*$|\1\x00\1|;D;};s|/$||' \
    | tr \\0 x # replace trailing NUL with a dummy character ②
)
# Remove the dummy character
longest_common_leading_path_component=${longest_common_leading_path_component%x} 
# Inspect result
echo "${longest_common_leading_path_component@Q}" # ③

结果:

$'/a\n/b/\nc  d\n'

正如预期的那样。 ✔️


继续我们的测试用例,我们现在说明如何将路径规范分解为最长公共引导路径组件+剩余路径分量具有以下内容:

for e in "${a[@]}"; do
  remainder=${e#"$longest_common_leading_path_component/"}
  printf '%-26s -> %s + %s\n' \
    "${e@Q}" \
    "${longest_common_leading_path_component@Q}" \
    "${remainder@Q}"
done

结果:

$'/a\n/b/\nc  d\n/\n\ne/f' -> $'/a\n/b/\nc  d\n' + $'\n\ne/f'
$'/a\n/b/\nc  d\n/\ne/f'   -> $'/a\n/b/\nc  d\n' + $'\ne/f'
$'/a\n/b/\nc  d\n/\ne\n/f' -> $'/a\n/b/\nc  d\n' + $'\ne\n/f'
$'/a\n/b/\nc  d\n/\nef'    -> $'/a\n/b/\nc  d\n' + $'\nef'

① 我总是-E向 sed 和 grep 添加选项以将它们切换到埃雷语法以便与我使用的其他工具/语言(例如 awk、bash、perl、javascript 和 java)更好地保持一致。

② 为了保留此命令替换中的任何尾随换行符,我们使用了常用技术添加一个随后被砍掉的虚拟字符。我们x使用 一步将删除尾随 NUL 与添加虚拟字符(我们选择的)结合起来tr \\0 x

${parameter@Q}扩展结果是“一个字符串,它是以可重复用作输入的格式引用的参数值”。 –bash 参考手册。需要 bash 4.4+ (讨论)。否则,您可以使用以下方法之一检查结果:

printf '%q' "$longest_common_leading_path_component"
printf '%s' "$longest_common_leading_path_component" | od -An -tc
od -An -tc < <(printf %s "$longest_common_leading_path_component")
od -An -tc <<<$longest_common_leading_path_component # ④

④ 注意here-strings添加换行符(讨论)。

相关内容