Filtre os caminhos de um arquivo de texto que é mais profundo do que o predecessor imediato

Question

Dado um arquivo de texto contendo uma lista ordenada de caminhos, como posso remover todos os caminhos que são redundantes devido a ter seu pai (imediato ou não) também na lista?

Por exemplo:

/aaa/bbb
/aaa/bbb/ccc
/ddd/eee
/fff/ggg
/fff/ggg/hhh/iii
/jjj/kkk/lll/mmm
/jjj/kkk/lll/mmm/nnn

Deve reduzir para:

/aaa/bbb
/ddd/eee
/fff/ggg
/jjj/kkk/lll/mmm

Eu tentei usar substrings no awk, mas não é garantido que os caminhos pai estejam no mesmo nível a cada vez, então não consegui fazê-lo funcionar.

    

Answer 1

Eu acho que isso deveria ser feito. Arquivo de entrada modificado para adicionar mais casos

$ cat ip.txt 
/aaa/bbb
/aaa/bbbd
/aaa/bbb/ccc
/ddd/eee
/fff/ggg
/fff/ggg/hhh/iii
/jjj/kkk/lll/mmm
/jjj/kkk/lll/mmm/nnn
/jjj/kkk/xyz

Usando awk

$ awk '{for (i in paths){if (index($0,i"/")==1) next} print; paths[$0]}' ip.txt 
/aaa/bbb
/aaa/bbbd
/ddd/eee
/fff/ggg
/jjj/kkk/lll/mmm
/jjj/kkk/xyz

• paths[$0] é a referência com linha de entrada como chave
• for (i in paths) cada linha é comparada com todas as chaves salvas
• if (index($0,i"/")==1) next se a linha de entrada corresponder a uma chave salva anexada com / no início da linha e, em seguida, pular essa linha
  • / é usado para evitar /aaa/bbbd de correspondência em relação a /aaa/bbb

Answer 2

E a obrigatória sed solution:

sed '1s/^/#/;x;G;\_#\([^#]*\)#.*\n/_s/\n.*//;s/\n\(.*\)/#/;h;$! d;x;s/^#//;s/#$//;y/#/\n/'

O script coleta caminhos no espaço de armazenamento. Para cada nova linha, o espaço de espera é anexado ao espaço padrão para verificar se já ocorreu.

Esta solução assume que o caractere # não é usado no arquivo. Caso contrário, use um caractere diferente ou, se você usar o GNU sed , use a versão curta na parte inferior da postagem.

Explicação detalhada:

1s/^/#/

Para portabilidade, o caractere # é usado para separar os caminhos no espaço de armazenamento. Para a primeira linha, precisamos começar com um # inicial

x;G

By exchanging the spaces and appending the hold space, we have the list of already occured buffers first, then the new path.

\_#\([^#]*\)#.*\n/_s/\n.*//

Se o endereço \_..._ corresponder, o novo caminho será um subcaminho de um caminho anterior, portanto, remova-o.

s/\n\(.*\)/#/

Ainda há uma nova linha no nosso espaço, então o caminho é novo e nós o adicionamos à lista.

h;$! d

Salve a nova lista no espaço de espera e comece de novo, se esta não for a última linha.

x;s/^#//;s/#$//;y/#/\n/

Para a última linha, remova o # no início e no final e substitua o outro # por novas linhas.

Alternativa para o% GNUsed

Isso pode ser feito de forma mais compacta com as extensões GNU em sed , se você não se importar se o pedido for revertido:

sed 'G;\_^\([^\n]*\)/.*\n\n_s/[^\n]*\n//;h;$! d;x;s/^\n//;s/\n$//'

Explicação como acima, mas usando as novas linhas como separadores em vez de adicionar # .

    

Answer 3

Algo parecido com isto:

$ awk '{sub(/\/$/, "")} 
    NR != 1 && substr($0, 0, length(prev)) == prev {next}; 
    {print; prev = $0"/" }  ' paths 

Em todos exceto na primeira linha ( NR != 1 ), compare o prefixo dessa linha com a linha armazenada em prev (tantos caracteres quanto o comprimento de prev ). Se eles corresponderem, pule para next line. Caso contrário, use print e armazene esta linha em prev .

Supondo que o arquivo esteja classificado na localidade C, ou seja, / vem antes de qualquer uma das letras, ou se for gerado por uma caminhada da árvore de diretórios, deve ser suficiente para testar a linha armazenada anterior. Se o arquivo estiver classificado em outra localidade, o / talvez não afete a classificação, o que levará à solicitação como /aaa/bbb , /aaaccc , /aaa/ddd . Se o arquivo não for classificado, os subdiretórios podem chegar antes de seus pais e o problema será difícil.

O primeiro sub(...) remove uma barra à direita da linha, se houver uma. Ao armazenar a linha, adicionamos uma barra à direita para evitar a correspondência de nomes de arquivos parciais.

    

Answer 4

Uma solução inspirada na postada pelo @Sundeep:

awk -F / -v OFS=/ '
{                  
    p = $0         
    while(--NF > 1) {
        if ($0 in paths) next
    }              
    print p        
    paths[p]       
}' file

A solução postada pelo @Sundeep é O(N^2) no número N dos caminhos de entrada. A abordagem acima é O(M) na profundidade máxima D dos caminhos de entrada. Isso deve ser substancialmente mais rápido para um grande número de caminhos de entrada.

Se você souber que todos os caminhos têm pelo menos 9 níveis de profundidade, você pode melhorar o acima, alterando --N > 1 para --N > 9 .

Em uma nota lateral: tanto a minha solução quanto a postada pelo @Sundeep assumem que todos os caminhos estão normalizados (ou seja, você não tem coisas como /foo/../../bar , nem /foo//bar/baz ).

    

Answer 5

perl -lne '$l=$_; grep $l =~ m|^\Q$_/|, @A or print, push @A, $_'

• Nós acumulamos todos os caminhos distintos no array @A fornecido para uma determinada linha que não corresponde ao que já está armazenado nele.
• grep m|^\Q$_/| irá citar os elementos da matriz e encontrar uma correspondência.

sed -ne '
   H                              # append current line into hold space
   g                              # pattern space = hold space \n current line
   y/\n_/_\n/                     # change coordinate system
   \|_\([^_]*\)_\(.*_\)\{0,1\}/|s/\(.*\)_.*// # match yes, strip current line
   y/\n_/_\n/                     # revert coordinate system
   h                              # update hold space
   $s/.//p                        # answer
'

Saída

/aaa/bbb
/ddd/eee
/fff/ggg
/jjj/kkk/lll/mmm