Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems. It only takes a minute to sign up.
Sign up to join this community
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.
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 keyfor (i in paths) every line is compared against all saved keysif (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
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.
May 2 '17 at 8:35
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 #.
octothorpe, aka, #, then the sed code doesn't produce the expected results.
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.
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).
--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...
6N comparisons. Yours does at worst N(N+1)/2 comparisons. It probably won't make any noticeable difference for <10k paths though.
May 2 '17 at 9:58
perl -lne '$l=$_; grep $l =~ m|^\Q$_/|, @A or print, push @A, $_'
array @A provided for a given line it does not match with what are already stored in it.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
'
/aaa/bbb
/ddd/eee
/fff/ggg
/jjj/kkk/lll/mmm
/fff/ggg/hhh/iii"redundant"?sort -t'/' -u -k1,2will work for given sample... it uses first two columns as comparison to find unique entries and retain only first entry