Filtrage des paths d'un file text qui sont plus profonds que leur prédécesseur immédiat

Étant donné un file text contenant une list sortingée de paths, comment puis-je supprimer tous les paths qui sont redondants en raison de leur parent (immédiat ou non) également dans la list?

Par exemple:

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

Devrait être réduit à:

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

J'ai essayé d'utiliser des sous-strings dans awk, mais les paths parents ne sont pas garantis d'être au même niveau à chaque fois, donc je ne pouvais pas le faire fonctionner.

Je pense que cela devrait le faire. Fichier d'input modifié pour append quelques cas supplémentaires

 $ 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 

Utiliser 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] est la reference avec la ligne d'input comme key
  • for (i in paths) chaque ligne est comparée à toutes les keys sauvegardées
  • if (index($0,i"/")==1) next si la ligne d'input correspond à une key enregistrée avec / au début de la ligne, puis sauter cette ligne
    • / est utilisé pour éviter /aaa/bbbd matching contre /aaa/bbb

Et la solution sed obligatoire:

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

Le script collecte les paths dans l'espace de stockage. Pour chaque nouvelle ligne, l'espace de maintien est ajouté à l'espace de motif pour vérifier s'il s'est déjà produit.

Cette solution suppose que le caractère # n'est pas utilisé dans le file. Sinon, utilisez un caractère différent ou, si vous utilisez GNU sed , utilisez la version courte au bas du post.

Explication en détail:

 1s/^/#/ 

Pour la portabilité, le caractère # est utilisé pour séparer les paths dans l'espace de cale. Pour la première ligne, nous devons commencer par un #

 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\1/_s/\n.*// 

Si l'adresse \_..._ correspond, le nouveau path est un sous-path d'un path antérieur, alors supprimez-le.

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

Il y a toujours une nouvelle ligne dans notre espace, donc le path est nouveau et nous l'ajoutons à la list.

 h;$! d 

Enregistrez la nouvelle list dans l'espace de réserve et recommencez, si ce n'était pas la dernière ligne.

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

Pour la dernière ligne, supprimez le # au début et à la fin et remplacez l'autre # par des returns à la ligne.

Alternative pour GNU sed

Cela peut être fait plus compact avec les extensions GNU sur sed , si cela ne vous dérange pas si l'ordre est returnné:

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

Explication comme ci-dessus, mais en utilisant les nouvelles lignes comme séparateurs au lieu d'append # .

Quelque chose comme ça:

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

Sur tout sauf la première ligne ( NR != 1 ), comparez le préfixe de cette ligne à la ligne stockée dans prev (autant de caractères que la longueur de prev ). S'ils correspondent, passez à next ligne next . Sinon, print -le et stockez cette ligne sur prev .

En supposant que le file est sortingé dans la locale C, c'est-à / dire avant une des lettres ou s'il est généré par une marche de l'arborescence, il devrait suffire de tester la ligne stockée précédente. Si le file est sortingé dans un autre environnement local, le / pourrait ne pas affecter le sorting, conduisant à la command comme /aaa/bbb , /aaaccc , /aaa/ddd . Si le file n'est pas sortingé du tout, les sous-directorys pourraient venir avant leurs parents, et le problème serait dur.

Le premier sub(...) supprime une barre oblique de la ligne s'il y en a une. Lors du stockage de la ligne, nous ajoutons une barre oblique pour éviter de faire correspondre les noms de files partiels.

Une solution inspirée de celle postée par @Sundeep:

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

La solution postée par @Sundeep est O(N^2) dans le nombre N de paths d'input. L'approche ci-dessus est O(M) dans la profondeur maximale D des paths d'input. Cela devrait être sensiblement plus rapide pour un grand nombre de paths d'input.

Si vous savez que tous les paths ont au less 9 niveaux de profondeur, vous pouvez bien sûr améliorer ce qui précède, en changeant --N > 1 à --N > 9 .

Sur une note de côté: à la fois ma solution et celle postée par @Sundeep supposent que tous les paths sont normalisés (ie vous n'avez pas de choses comme /foo/../../bar , ni /foo//bar/baz ).

 perl -lne '$l=$_; grep $l =~ m|^\Q$_/|, @A or print, push @A, $_' 
  • Nous array @A tous les paths distincts dans le array @A fournis pour une ligne donnée, il ne correspond pas à ce qui y est déjà stocké.
  • grep m|^\Q$_/| va citer les éléments du tableau et find une correspondance.

 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\}\1/|s/\(.*\)_.*/\1/ # match yes, ssortingp current line y/\n_/_\n/ # revert coordinate system h # update hold space $s/.//p # answer ' 

Sortie

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