☰

パス/ファイルのリストから共通パスを見つける方法

tag-icon • tag-icon linux command-line unix sed string-manipulation
パス/ファイルのリストから共通パスを見つける方法

前奏曲:

パス/ファイルのリストがソートされた入力が与えられた場合、それらの共通パスを見つけるにはどうすればよいでしょうか?

技術用語に翻訳すると、stdin からソートされた入力を供給する場合、stdin から最短の適切なプレフィックスを選択するにはどうすればよいでしょうか。

ここでの「プレフィックス」は通常の意味を持ちます。たとえば、文字列「abcde」には「abc」というプレフィックスがあります。これが私のサンプル入力です。

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

これは例です後続の適切な接頭辞を削除するstdin から次のコマンドを使用します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、は保持されますが、他の 2 つは保持されません。つまり、上記のコマンドとはまったく逆の動作になります。/home/dave/sub2/file2/home/dave/home/davesed

より詳しい情報：

  • 入力はすでにソートされている
  • もし私が/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

応用：

類似したコンテンツを含む 2 つのディスク ボリュームがあります。v1 にはあって v2 にはない内容を別のディスク ボリューム v3 にコピーします。、、および を使用してfind、sortコピーcomm対象のリストを取得できますが、そのリストをさらにクリーンアップする必要があります。つまり、リストに があれば/home/dave、他の 2 つは必要ありません。

ありがとう！

答え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

関連情報