Linux tools to treat files as sets and perform set operations on them

Question

Does anyone know of any linux tool specifically designed to treat files as sets and perform set operations on them? Like difference, intersection, etc?

Answer 1

Assuming elements are strings of characters other than NUL and newline (beware that newline is valid in file names though), you can represent a set as a text file with one element per line and use some of the standard Unix utilities.

Set Membership

$ grep -Fxc 'element' set   # outputs 1 if element is in set
                            # outputs >1 if set is a multi-set
                            # outputs 0 if element is not in set

$ grep -Fxq 'element' set   # returns 0 (true)  if element is in set
                            # returns 1 (false) if element is not in set

$ awk '$0 == "element" { s=1; exit }; END { exit !s }' set
# returns 0 if element is in set, 1 otherwise.

$ awk -v e='element' '$0 == e { s=1; exit } END { exit !s }'

Set Intersection

$ comm -12 <(sort set1) <(sort set2)  # outputs intersect of set1 and set2

$ grep -xF -f set1 set2

$ sort set1 set2 | uniq -d

$ join -t <(sort A) <(sort B)

$ awk '!done { a[$0]; next }; $0 in a' set1 done=1 set2

Set Equality

$ cmp -s <(sort set1) <(sort set2) # returns 0 if set1 is equal to set2
                                   # returns 1 if set1 != set2

$ cmp -s <(sort -u set1) <(sort -u set2)
# collapses multi-sets into sets and does the same as previous

$ awk '{ if (!($0 in a)) c++; a[$0] }; END{ exit !(c==NR/2) }' set1 set2
# returns 0 if set1 == set2
# returns 1 if set1 != set2

$ awk '{ a[$0] }; END{ exit !(length(a)==NR/2) }' set1 set2
# same as previous, requires >= gnu awk 3.1.5

Set Cardinality

$ wc -l < set     # outputs number of elements in set

$ awk 'END { print NR }' set

$ sed '$=' set

Subset Test

$ comm -23 <(sort -u subset) <(sort -u set) | grep -q '^'
# returns true iff subset is not a subset of set (has elements not in set)

$ awk '!done { a[$0]; next }; { if !($0 in a) exit 1 }' set done=1 subset
# returns 0 if subset is a subset of set
# returns 1 if subset is not a subset of set

Set Union

$ cat set1 set2     # outputs union of set1 and set2
                    # assumes they are disjoint

$ awk 1 set1 set2   # ditto

$ cat set1 set2 ... setn   # union over n sets

$ sort -u set1 set2  # same, but doesn't assume they are disjoint

$ sort set1 set2 | uniq

$ awk '!a[$0]++' set1 set2       # ditto without sorting

Set Complement

$ comm -23 <(sort set1) <(sort set2)
# outputs elements in set1 that are not in set2

$ grep -vxF -f set2 set1           # ditto

$ sort set2 set2 set1 | uniq -u    # ditto

$ awk '!done { a[$0]; next }; !($0 in a)' set2 done=1 set1

Set Symmetric Difference

$ comm -3 <(sort set1) <(sort set2) | tr -d '\t'  # assumes not tab in sets
# outputs elements that are in set1 or in set2 but not both

$ sort set1 set2 | uniq -u

$ cat <(grep -vxF -f set1 set2) <(grep -vxF -f set2 set1)

$ grep -vxF -f set1 set2; grep -vxF -f set2 set1

$ awk '!done { a[$0]; next }; $0 in a { delete a[$0]; next }; 1;
       END { for (b in a) print b }' set1 done=1 set2

Power Set

All possible subsets of a set displayed space separated, one per line:

$ p() { [ "$#" -eq 0 ] && echo || (shift; p "$@") |
        while read r; do printf '%s %s\n%s\n' "$1" "$r" "$r"; done; }
$ p $(cat set)

(assumes elements don't contain SPC, TAB (assuming the default value of $IFS), backslash, wildcard characters).

Set Cartesian Product

$ while IFS= read -r a; do while IFS= read -r b; do echo "$a, $b"; done < set1; done < set2

$ awk '!done { a[$0]; next }; { for (i in a) print i, $0 }' set1 done=1 set2

Disjoint Set Test

$ comm -12 <(sort set1) <(sort set2)  # does not output anything if disjoint

$ awk '++seen[$0] == 2 { exit 1 }' set1 set2 # returns 0 if disjoint
                                             # returns 1 if not

Empty Set Test

$ wc -l < set            # outputs 0  if the set is empty
                         # outputs >0 if the set is not empty

$ grep -q '^' set        # returns true (0 exit status) unless set is empty

$ awk '{ exit 1 }' set   # returns true (0 exit status) if set is empty

Minimum

$ sort set | head -n 1   # outputs the minimum (lexically) element in the set

$ awk 'NR == 1 { min = $0 }; $0 < min { min = $0 }; END { print min }'
# ditto, but does numeric comparison when elements are numerical

Maximum

$ sort test | tail -n 1    # outputs the maximum element in the set

$ sort -r test | head -n 1

$ awk '$0 > max { max = $0 }; END { print max }'
# ditto, but does numeric comparison when elements are numerical

All available at http://www.catonmat.net/blog/set-operations-in-unix-shell-simplified/

Answer 2

Sort of. You need to deal with sorting yourself, but comm can be used to do that, treating each line as a set member: -12 for intersection, -13 for difference. (And -23 gives you flipped difference, that is, set2 - set1 instead of set1 - set2.) Union is sort -u in this setup.

Answer 3

The tiny console tool “setop” is now availible in Debian Stretch and in Ubuntu since 16.10. You can get it via sudo apt install setop

Here are some examples. The sets to be operated on are given as different input files: setop input # is equal to "sort input --unique" setop file1 file2 --union # option --union is default and can be omitted setop file1 file2 file3 --intersection # more than two inputs are allowed setop file1 - --symmetric-difference # ndash stands for standard input setop file1 -d file2 # all elements contained in 1 but not 2

Boolean queries return only EXIT_SUCCESS in case of true, and EXIT_FAILURE as well as a message otherwise. This way, setop can be used in the shell. setop inputfile --contains "value" # is element value contained in input? setop A.txt B.txt --equal C.txt # union of A and B equal to C? setop bigfile --subset smallfile # analogous --superset setop -i file1 file2 --is-empty # intersection of 1 and 2 empty (disjoint)?

It is also possible to precisly describe how the input streams shall be parsed, actually by regular expressions:

• setop input.txt --input-separator "[[:space:]-]" means that a whitespace (i. e. \v \t \n \r \f or space) or a minus sign is interpreted as a separator between elements (default is new line, i. e. every line of the input file is one element)
• setop input.txt --input-element "[A-Za-z]+" means that elements are only words consisting of latin characters, all other characters are considered to be separators between elements

Furthermore, you can

• --count all elements of the output set,
• --trim all input elements (i. e. erase all unwanted preceding and succeeding characters like space, comma etc.),
• consider empty elements as valid via --include-empty,
• --ignore-case,
• set the --output-separator between elements of the output stream (default is \n),
• and so on.

See man setop or github.com/phisigma/setop for more information.

Answer 4

I don't know of a specific tool but you can use Python, and its set class and operators, to write a little script to do that.

For exampe:

Python> s1 = set(os.listdir("/bin"))
Python> s2 = set(os.listdir("/usr/bin"))
Python> s1 & s2

set(['awk',
     'basename',
     'chroot', ...

Answer 5

If you see a file as a set of lines, and the files are sorted, there's comm.

If you see a file as a (multi)set of lines, and the lines aren't sorted, grep can do difference and intersection (it achieves set difference and intersection, but doesn't respect count for multisets). Union is just cat.

grep -xF -f small large >intersection
grep -vxF -f small large >difference
cat small large >union

Answer 6

I've made a Python utility that can do line-wise union, intersection, difference and product of multiple files. It's called SetOp, you can find it on PyPI (here). Syntax looks like this:

$ setop -i file1 file2 file3  # intersection
$ setop -d file1 file2 file3  # difference

Answer 7

I've written a command tool in Go for this question. The source code is here on GitHub.

You can use homebrew to install it on macOS:

brew install suzaku/homebrew-rose/rose

Usage is simply:

• rose and file1 file2 for intersection.
• rose or file1 file2 for union.
• rose sub file1 file2 for subtraction.

Answer 8

With zsh arrays (zsh arrays can contain any arbitrary sequence of bytes, even 0).

set membership

if ((${array[(Ie)$element]})); then
  echo '$element is in $array'
fi

(using the I array subscript flag, to get the index of the last occurrence of $element in the array (or 0 if not found). Remove e (for exact) for $element to be taken as a pattern)

if ((n = ${(M)#array:#$element})); then
  echo "\$element is found $n times in \$array'
fi

${array:#pattern} being a variation on ksh's ${var#pattern} that removes the elements that match the pattern as opposed to just remove the leading part that matches the pattern. The (M) (for matched) reverses the meaning and removes all but the matched elements (use $~element for it to be taken as a pattern).

set intersection

common=("${(@)set1:*set2}")

${set1:*set2} does the array intersection, but the "${(@)...}" syntax is needed to preserve empty elements.

set equality

[[ ${(j: :)${(q)array1}} = ${(j: :)${(q)array2}} ]]

Tests whether the arrays are identical (and in the same order). The q parameter expansion flag quotes the elements (to avoid problems with things like a=(1 "2 3") vs b=("1 2" 3)), and (j: :) joins them with space before doing a string comparison.

To check that they have the same elements, irrespective of order, use the o flag to order them. See also the u flag (unique) to remove duplicates.

[[ ${(j: :)${(qo)array1}} = ${(j: :)${(qo)array2}} ]]

set cardinality

n=$#array

subset test

if ((${#array1:*array2} == ${#array2})); then
  echo '$array2 is included in $array1'
fi

(assuming arrays with unique values)

union

union=("$array1[@]" "$array2[@]")

(see typeset -U above or the u parameter expansion flag to take care of duplicates). Again if the empty string is not one of the possible values, you can simplify to:

union=($array1 $array2)

complement

complement=("${(@)array1:|array2}")

for the elements of $array1 that are not in $array2.

minimum/maximum (lexical comparison)

min=${${(o)array}[1]} max=${${(o)array}[-1]}

minimum/maximum (decimal integer comparison)

min=${${(no)array}[1]} max=${${(no)array}[-1]}

Answer 9

I wrote a little tool to do this which has been quite useful to me in various places. The UI is unpolished and I'm not sure about the performance characteristics for very large files (since it reads the whole list into memory) but "it works for me". The program is at https://github.com/nibrahim/lines. It's in Python. You can get it using pip install lines.

It currently supports union, intersection, difference and symmetric difference of two files. Each line of the input file is treated as an element of a set.

It also has two extra operations. One of squeeze out blank lines in a file and the second (which has been very useful to me) is to look through the file and divide it into sets of similar strings. I needed this to look for files in a list that didn't match the general pattern.

I'd welcome feedback.

Answer 10

The filesystem treats filenames (whole filenames, including paths) as unique.

Operations?

You may copy the files in a/ and b/ to the empty directory c/, to get a new, union set.

With file-tests like -e name and loops or find, you may check for files existing in two or more directories, to get the intersection, or the difference.

Answer 11

Best answer here: Setdown (a dedicated tool)

I wrote a program called setdown that performs Set operations from the cli.

It can perform set operations by writing a definition similar to what you would write in a Makefile:

someUnion: "file-1.txt" \/ "file-2.txt"
someIntersection: "file-1.txt" /\ "file-2.txt"
someDifference: someUnion - someIntersection

Its pretty cool and you should check it out. I personally don't recommend using ad-hoc commands that were not built for the job to perform set operations.It won't work well when you really need to do many set operations or if you have any set operations that depend on each other. Not only that but setdown lets you write set operations that depend on other set operations!

At any rate, I think that it's pretty cool and you should totally check it out.

Answer 12

Sample pattern for multiple files (intersection in this case):

eval `perl -le 'print "cat ",join(" | grep -xF -f- ", @ARGV)' t*`

Expands to:

cat t1 | grep -xF -f- t2 | grep -xF -f- t3

Test files:

seq 0 20 | tee t1; seq 0 2 20 | tee t2; seq 0 3 20 | tee t3

Output:

0
6
12
18