5

Given a text file containing a sorted list of paths, how can I remove all the paths that are redundant due to having their parent (immediate or not) also in the list?

For example:

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

Should reduce to:

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

I've tried using substrings in awk but the parent paths are not guaranteed to be at the same level each time so I couldn't get it work.

  • Despite reading your question several times, I have no idea what paths you want removed and why. F.i. what makes /fff/ggg/hhh/iii "redundant"? – Satō Katsura May 2 '17 at 7:39
  • do you have a minimum level to compare? for ex, sort -t'/' -u -k1,2 will work for given sample... it uses first two columns as comparison to find unique entries and retain only first entry – Sundeep May 2 '17 at 7:41
  • @SatoKatsura, it's redunant because its grandparent is already in the list. The operation I need to do on these paths applies to all their children recursively, so there's no need to do it twice. – Esker May 2 '17 at 7:57
  • @Sundeep, every path is at least 9 levels deep in the list I'm actually acting on, but could be anywhere between that and 15 levels deep. – Esker May 2 '17 at 7:59
8

I think this should do it. Modified input file to add couple of more cases

$ 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

Using 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] is the reference with input line as key
  • for (i in paths) every line is compared against all saved keys
  • if (index($0,i"/")==1) next if input line matches with a saved key appended with / at start of line, then skip that line
    • / is used to avoid /aaa/bbbd matching against /aaa/bbb
  • The problem with this approach is that it's O(N^2) in the number of input paths. This may or may not be acceptable, depending on how many paths we're talking about. You could avoid the problem by looping over the components of the current path, rather than over the previous inputs. I posted another solution based on that idea. – Satō Katsura May 2 '17 at 8:35
5

And the mandatory sed solution:

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

The script collects paths in the hold space. For each new line, the hold space gets appended to the pattern space to check, whether it already occured.

This solutions assumes that the character # is not used in the file. Otherwise use a different character or, if you use GNU sed, use the short version at the bottom of the post.

Explanation in detail:

1s/^/#/

For portability, the # character is used to separate the paths in the hold space. For the first line we need to start with an initial #

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.*//

If the \_..._ address matches, the new path is a subpath of an earlier path, so remove it.

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

There is still a newline in our space, so the path is new and we add it to the list.

h;$! d

Save the new list to the hold space and start over, if this was not the last line.

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

For the last line, remove the # at beginning and end and replace the other # by newlines.

Alternative for GNU sed

This can be done more compact with GNU extensions on sed, if you don't mind if the order gets reverted:

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

Explanation as above, but using the newlines as separators instead of adding #.

  • when a path happens to have the octothorpe, aka, #, then the sed code doesn't produce the expected results. – user218374 May 2 '17 at 12:28
  • Of course. I added that remark to the answer. Unfortunally, the more elegant solution at the bottom, which has no such limitations, is not portable (as discussed a few days ago). Do you have an idea how to solve this the POSIX way without much overhead? – Philippos May 2 '17 at 12:37
  • You might want to take a look at my attempt. – user218374 May 2 '17 at 12:43
  • I see, same idea the other way around, than it works. Longer, but nice. – Philippos May 2 '17 at 13:02
  • Did you notice that it is POSIX compliant? – user218374 May 2 '17 at 13:04
4

Something like this:

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

On all but the first line (NR != 1), compare the prefix of this line to the line stored in prev (as many characters as the length of prev). If they match, skip to next line. Otherwise print it out and store this line to prev.

Assuming the file is sorted in the C locale, i.e. / comes before any of the letters, or if it's generated by a walk of the directory tree, it should be enough to test against the previous stored line. If the file is sorted in some other locale, the / might not affect the sorting, leading to ordering like /aaa/bbb, /aaaccc, /aaa/ddd. If the file isn't sorted at all, subdirectories could come before their parents, and the problem would be harded.

The first sub(...) removes a trailing slash from the line if there is one. When storing the line we add a trailing slash to avoid matching partial file names.

  • Thanks very much! I've marked the answer from @Sundeep due to their additional picking up of something I hadn't thought of either, but I still appreciate the response. – Esker May 2 '17 at 8:07
  • 1
    @Sundeep, yep, I noticed that from your answer. Added another way to work around that. – ilkkachu May 2 '17 at 8:13
4

A solution inspired by the one posted by @Sundeep:

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

The solution posted by @Sundeep is O(N^2) in the number N of input paths. The approach above is O(M) in the maximum depth D of input paths. This should be substantially faster for a large number of input paths.

If you know all paths are at least 9 levels deep you could of course improve the above, by changing --N > 1 to --N > 9.

On a side note: both my solution and the one posted by @Sundeep assume all paths are normalized (i.e. you don't have things like /foo/../../bar, nor /foo//bar/baz).

  • interesting approach.. I think this would be faster for large input file, especially for known cases like --N > 9... I know but not well versed to tell whether solution is O(N^2) or O(M)... but this solution has two loops as well isn't it? while and $0 in paths... – Sundeep May 2 '17 at 8:58
  • 1
    @Sundeep Yes, but the second loop always goes from ~15 to 9, so at worst you get ~6N comparisons. Yours does at worst N(N+1)/2 comparisons. It probably won't make any noticeable difference for <10k paths though. – Satō Katsura May 2 '17 at 9:58
3
perl -lne '$l=$_; grep $l =~ m|^\Q$_/|, @A or print, push @A, $_'
  • We accumulate all distinct paths in the array @A provided for a given line it does not match with what are already stored in it.
  • grep m|^\Q$_/| will quote the array elements and find a match.

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, strip current line
   y/\n_/_\n/                     # revert coordinate system
   h                              # update hold space
   $s/.//p                        # answer
'

Output

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.