Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

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

share|improve this question

7 Answers 7

up vote 36 down vote accepted

Set Membership

$ grep -xc '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 -xq '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 insersect of set1 and set2

$ grep -xF -f set1 set2

$ sort set1 set2 | uniq -d

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

$ awk 'NR==FNR { a[$0]; next } $0 in a' set1 set2

Set Equality

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

$ diff -q <(sort set1 | uniq) <(sort set2 | uniq)
# 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 | cut -d' ' -f1    # outputs number of elements in set

$ wc -l < set

$ awk 'END { print NR }' set

Subset Test

$ comm -23 <(sort subset | uniq) <(sort set | uniq) | head -1
# outputs something if subset is not a subset of set
# does not putput anything if subset is a subset of set

$ awk 'NR==FNR { a[$0]; next } { if !($0 in a) exit 1 }' set 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

$ cat set1 set2 | sort -u  # same, but assumes they are not disjoint

$ sort set1 set2 | uniq

# sort -u set1 set2

$ awk '!a[$0]++'           # ditto

Set Intersection

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

$ grep -xF -f set1 set2

$ sort set1 set2 | uniq -d

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

$ awk 'NR==FNR { a[$0]; next } $0 in a' set1 set2

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 'NR==FNR { a[$0]; next } !($0 in a)' set2 set1

Set Symmetric Difference

$ comm -3 <(sort set1) <(sort set2) | sed 's/\t//g'
# outputs elements that are in set1 or in set2 but not both

$ comm -3 <(sort set1) <(sort set2) | tr -d '\t'

$ 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 'NR==FNR { a[$0]; next } $0 in a { delete a[$0]; next } 1;
       END { for (b in a) print b }' set1 set2

Power Set

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

Set Cartesian Product

$ while read a; do while read b; do echo "$a, $b"; done < set1; done < set2

$ awk 'NR==FNR { a[$0]; next } { for (i in a) print i, $0 }' set1 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

$ awk '{ exit 1 }' set   # returns 0 if set is empty, 1 otherwise

Minimum

$ head -1 <(sort set)    # outputs the minimum element in the set

$ awk 'NR == 1 { min = $0 } $0 < min { min = $0 } END { print min }'

Maximum

$ tail -1 <(sort set)    # outputs the maximum element in the set

$ awk '$0 > max { max = $0 } END { print max }'

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

share|improve this answer
    
Welcome to Unix and Linux! Please don't just post a link as an answer, both because the linked site may be unavailable, and because as it is your answer doesn't show what it's about. Summarize the essential parts of the answer here, and provide the link for reference. –  Gilles Apr 20 '11 at 7:20
    
Thank you.Get it. –  llhuii Apr 21 '11 at 12:25
    
Now that's a very nice list. Thank you! –  Gilles Apr 21 '11 at 18:44
    
I think the Python version is much simpler and more intuitive. ;-) –  Keith Apr 22 '11 at 23:37
    
I think this is the most complete answer. Unfortunately which commands to run or which arguments (comm -12, -23, -13) in each case is not always intuitive as "intersection" or "difference". Maybe'll create a wrapper around them, since I'm always using these things. –  nilton Apr 25 '11 at 22:08

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 difference, -13 for intersection. (And -23 gives you flipped difference, that is, set2 - set1 instead of set1 - set2.) Union is sort -u in this setup.

share|improve this answer
1  
Indeed, comm seems to do most of the stuff. Although the arguments are very unintuitive. Thanks! –  nilton Apr 25 '11 at 22:09

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', ...

share|improve this answer

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
share|improve this answer

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
share|improve this answer

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.

share|improve this answer
    
I meant treating the contents of files as the elements of a set (let's say, one element per line), and the files themselves as sets. –  nilton Apr 25 '11 at 22:04

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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