Como encontrar os caminhos comuns a partir de uma lista de caminhos / arquivos

Question

Prelúdio:

Dada uma entrada classificada de uma lista de caminhos / arquivos, como encontrar seus caminhos comuns?

Traduzindo para o termo técnico, se alimentando a entrada classificada de stdin, como escolher o prefixo mais curto adequado do stdin?

Aqui, o "prefixo" tem o significado normal, por exemplo, a string 'abcde' tem um prefixo 'abc'. Aqui está a minha entrada de amostra

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

Este é um exemplo para remover o prefixo apropriado sucessivo do stdin, usando o comando sed :

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

Pergunta:

Minha pergunta é como preservar o prefixo adequado , e remover todas as linhas que têm esse prefixo. Tanto o /home/dave/file1 quanto o /home/dave/sub2/file2 têm o prefixo /home/dave , o /home/dave será preservado enquanto os outros dois não. Ou seja, fará o oposto do que o comando sed faz.

Mais informações:

• A entrada já seria classificada
• Se eu tiver /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' ), esperaria que /home/dave e /home/phil fossem a resposta.

Aplicação:

Eu tenho dois volumes de disco contendo conteúdo semelhante. Eu quero copiar o que está na v1, mas falta de v2 em outro volume de disco, v3. Usando find , sort e comm , posso obter uma lista do que copiar, mas preciso limpar ainda mais essa lista. Ou seja, desde que eu tenha /home/dave na lista, não preciso dos outros dois.

Obrigado!

    

Answer 1

Esta resposta usa Python. Como o OP queria remover os diretórios cobertos por seus pais, como eu tinha visto como uma possibilidade, comecei a escrever um programa diferente para remover coberturas:

Exemplo:

$ 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

Código do comando 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

Esta resposta usa Python. Ele também faz um prefixo comum componente-sábio em vez de string-wise. Melhor para caminhos, pois o prefixo comum de /ex/ample e /exa/mple deve ser / não /ex . Isso pressupõe que o que é desejado é o maior prefixo comum e não uma lista de prefixos com seus revestimentos removidos. Se você tem /home/dave /home/dave/file1 /home/phil /home/phil/file2 e espera /home/dave /home/phil em vez de /home . Esta não é a resposta que você estaria procurando.

Exemplo:

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

Código do comando 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())

    

Answer 2

Dado que a entrada está classificada, o pseudo código seria:

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

Traduzindo para o código Perl (Yes Perl, a linguagem de script mais bonita de todas):

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

Crédito: Ben Bacarisse @ bsb.me.uk, de comp.lang.perl.misc. Obrigado Ben, isso funciona muito bem!

    

Answer 3

E a versão de um liner da resposta do xpt. Novamente, assumindo entrada classificada:

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

Executar na entrada de exemplo

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

usando

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 = $_; }'

dá

/home/dave
/home/phil

A mágica está nos argumentos da linha de comando para perl: -e nos permite dar um script na linha de comando, -n itera sobre as linhas do arquivo (colocando cada linha em $_ ), e -l lida com novas linhas para nós.

O script funciona usando l para rastrear o último prefixo visto. O bloco BEGIN é executado antes da primeira linha ser lida e inicializa a variável em uma sequência que não será vista (sem novas linhas). A condicional é executada em cada linha do arquivo (mantida por $_ ). A condicional é executada em todas as linhas do arquivo e diz "se a linha não tiver o valor atual de l como um prefixo, imprima a linha e salve-a como o valor de l ." Por causa dos argumentos da linha de comando, isso é essencialmente idêntico ao outro script.

O problema é que ambos os scripts assumem que o prefixo comum existe como sua própria linha, portanto, não encontre o prefixo comum para entrada como

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