Linux-Tools zum Behandeln von Dateien als Mengen und Ausführen von Mengenoperationen

81

Kennt jemand ein Linux-Tool, das speziell dafür entwickelt wurde, Dateien als Mengen zu behandeln und Mengenoperationen an ihnen auszuführen? Wie Unterschied, Kreuzung usw.?

nilton
quelle

Antworten:

110

Angenommen, Elemente sind Zeichenfolgen, die nicht NUL und newline sind (beachten Sie jedoch, dass newline in Dateinamen gültig ist), können Sie eine Menge als Textdatei mit einem Element pro Zeile darstellen und einige der Standard-Unix-Dienstprogramme verwenden.

Mitgliedschaft festlegen

$ 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 }'

Schnittpunkt setzen

$ 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

Stellen Sie Gleichheit ein

$ 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

Stellen Sie die Kardinalität ein

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

$ awk 'END { print NR }' set

$ sed '$=' set

Teilmengen-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

Union einstellen

$ 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

Komplement setzen

$ 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

Stellen Sie den symmetrischen Unterschied ein

$ 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

Alle möglichen Teilmengen einer Menge werden durch Leerzeichen getrennt angezeigt, eine pro Zeile:

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

(setzt voraus, dass Elemente SPC, TAB (unter Annahme des Standardwerts von $IFS), Backslash und Platzhalterzeichen nicht enthalten ).

Kartesisches Produkt einstellen

$ 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

Leerset-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

Maximal

$ 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

Alles verfügbar unter http://www.catonmat.net/blog/set-operations-in-unix-shell-simplified/

llhuii
quelle
1
Ich denke, die Python-Version ist viel einfacher und intuitiver. ;-)
Keith
Ich denke, das ist die vollständigste Antwort. Leider ist es nicht immer intuitiv, welche Befehle oder welche Argumente (comm -12, -23, -13) als "Schnittmenge" oder "Differenz" auszuführen sind. Vielleicht erstelle ich einen Wrapper um sie herum, da ich diese Dinge immer benutze.
Nilton
Ich habe [pol @ localhost inst] $ grep -xc und INSTALL-BINARY 0 [pol @ localhost inst] $ ausgeführt, aber ich verstehe nicht, was das bedeutet. Das Wort "und" sollte in der Datei mehrmals vorkommen. Was mache ich falsch?
Vérace
1
Set-Schnittmenge: Funktioniert sort set1 set2 | uniq -dnicht für Multi-Sets. Erwägen Sie die Verwendung sort <(sort -u set1) <(sort -u set2) | uniq -d.
Neo
11

Art von. Sie müssen sich selbst mit dem Sortieren befassen, commkönnen dies aber auch tun, indem Sie jede Zeile als festes Element behandeln: -12für Schnittpunkte, -13für Differenzen. (Und -23gibt Ihnen gespiegelten Unterschied, das heißt, set2 - set1statt set1 - set2.) Union ist sort -uin diesem Setup.

Geekosaurier
quelle
1
In der Tat scheint comm die meisten Dinge zu tun. Obwohl die Argumente sehr uninteressant sind. Vielen Dank!
Nilton
7

Ich kenne kein bestimmtes Tool, aber Sie können Python, seine Set-Klasse und Operatoren verwenden, um ein kleines Skript dafür zu schreiben.

Zum Beispiel:

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

set(['awk',
     'basename',
     'chroot', ...
Keith
quelle
Ja, schöne Antwort. Warum awk verwenden, wenn Python verfügbar ist?
Guettli
Sie haben vergessen:Python> import os
James Bowery
7

Das winzige Konsolenwerkzeug "setop" ist seit 16.10 in Debian Stretch und in Ubuntu verfügbar. Sie können es über erhalten sudo apt install setop

Hier sind einige Beispiele. Die zu bearbeitenden Sets werden als unterschiedliche Eingabedateien angegeben: 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

Boolesche Abfragen werden nur EXIT_SUCCESSim Fall von true zurückgegeben und EXIT_FAILUREauch eine andere Nachricht. Auf diese Weise kann setop in der Shell verwendet werden. 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)?

Es ist auch möglich, genau zu beschreiben, wie die Eingabeströme analysiert werden sollen, und zwar durch reguläre Ausdrücke:

  • setop input.txt --input-separator "[[:space:]-]"bedeutet, dass ein Leerzeichen \v \t \n \r \foder ein Minuszeichen als Trennzeichen zwischen Elementen interpretiert wird (Standard ist eine neue Zeile, dh jede Zeile der Eingabedatei ist ein Element)
  • setop input.txt --input-element "[A-Za-z]+" Bedeutet, dass Elemente nur Wörter sind, die aus lateinischen Zeichen bestehen. Alle anderen Zeichen gelten als Trennzeichen zwischen Elementen

Darüber hinaus können Sie

  • --count alle Elemente der Ausgabemenge,
  • --trim alle Eingabeelemente (dh alle unerwünschten vorhergehenden und nachfolgenden Zeichen wie Leerzeichen, Komma usw. löschen),
  • leere Elemente als gültig betrachten über --include-empty,
  • --ignore-case,
  • Setze die --output-separatorzwischen den Elementen des Ausgabestreams (Standard ist \n),
  • und so weiter.

Weitere Informationen finden Sie unter man setopoder unter github.com/phisigma/setop .

Frank
quelle
3

Wenn Sie eine Datei als eine Reihe von Zeilen sehen und die Dateien sortiert sind, gibt es comm.

Wenn Sie eine Datei als (Mehrfach-) Satz von Linien sehen und die Linien nicht sortiert sind, grepkann dies zu Unterschieden und Schnittmengen führen. Union ist gerecht cat.

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

Ich habe ein Python-Dienstprogramm erstellt, das die Vereinigung, Schnittmenge, Differenz und das Produkt mehrerer Dateien in Zeilenrichtung ausführen kann. Es heißt SetOp und ist auf PyPI zu finden ( hier ). Die Syntax sieht folgendermaßen aus:

$ setop -i file1 file2 file3  # intersection
$ setop -d file1 file2 file3  # difference
Tigr
quelle
1

Ich habe dazu ein kleines Tool geschrieben, das mir an verschiedenen Stellen sehr geholfen hat. Die Benutzeroberfläche ist unpoliert und ich bin mir nicht sicher über die Leistungsmerkmale für sehr große Dateien (da die gesamte Liste in den Speicher eingelesen wird), aber "es funktioniert für mich". Das Programm finden Sie unter https://github.com/nibrahim/lines . Es ist in Python. Sie können es mit bekommen pip install lines.

Derzeit werden Vereinigung, Schnittmenge, Differenz und symmetrische Differenz zweier Dateien unterstützt. Jede Zeile der Eingabedatei wird als Element einer Menge behandelt.

Es hat auch zwei zusätzliche Operationen. Eine Möglichkeit, leere Zeilen in einer Datei auszudrücken, und die zweite (die für mich sehr nützlich war) besteht darin, die Datei zu durchsuchen und sie in Sätze ähnlicher Zeichenfolgen zu unterteilen. Ich brauchte dies, um nach Dateien in einer Liste zu suchen, die nicht dem allgemeinen Muster entsprachen.

Ich würde mich über Feedback freuen.

Noufal Ibrahim
quelle
0

Das Dateisystem behandelt Dateinamen (ganze Dateinamen, einschließlich Pfade) als eindeutig.

Operationen?

Sie können die Dateien in a / und b / in das leere Verzeichnis c / kopieren, um einen neuen Vereinigungssatz zu erhalten.

Mit Datei-Tests wie -e nameund Schleifen oder Finden können Sie nach Dateien suchen, die in zwei oder mehr Verzeichnissen vorhanden sind, um die Schnittmenge oder den Unterschied zu ermitteln.

Benutzer unbekannt
quelle
1
Ich meinte, den Inhalt von Dateien als Elemente einer Menge zu behandeln (sagen wir, ein Element pro Zeile) und die Dateien selbst als Mengen.
Nilton
0

Beste Antwort hier: Setdown (ein spezielles Tool)

Ich habe ein Programm namens setdown geschrieben, das Set-Operationen über das CLI ausführt.

Es kann Mengenoperationen ausführen, indem es eine Definition schreibt, die derjenigen in einem Makefile ähnelt:

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

Es ist ziemlich cool und du solltest es dir ansehen. Ich persönlich empfehle nicht, Ad-hoc-Befehle zu verwenden, die nicht für den Job erstellt wurden, um Set-Vorgänge auszuführen. Es funktioniert nicht gut, wenn Sie wirklich viele Set-Vorgänge ausführen müssen oder wenn Sie Set-Vorgänge haben, die voneinander abhängig sind . Darüber hinaus können Sie mit setdown Mengenoperationen schreiben, die von anderen Mengenoperationen abhängen!

Ich finde es jedenfalls ziemlich cool und du solltest es dir unbedingt ansehen.

Robert Massaioli
quelle
0

Beispielmuster für mehrere Dateien (Schnittmenge in diesem Fall):

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

Erweitert um:

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

Testdateien:

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

Ausgabe:

0
6
12
18
bsb
quelle
0

Mit zshArrays ( zshArrays können eine beliebige Folge von Bytes enthalten, sogar 0).

(Beachten Sie auch, dass Sie dafür sorgen können typeset -U array, dass die Elemente einzigartig sind).

Mitgliedschaft festlegen

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

(Verwenden des IArray-Index-Flags, um den Index des letzten Vorkommens $elementim Array abzurufen (oder 0, wenn nicht gefunden). Entfernen e(für exact) $element, um als Muster verwendet zu werden.)

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

${array:#pattern}Dies ist eine Variation von kshs ${var#pattern}, bei der die Elemente entfernt werden, die dem Muster entsprechen, und nicht nur der führende Teil, der dem Muster entspricht. Das (M)(für übereinstimmende ) kehrt die Bedeutung um und entfernt alle Elemente mit Ausnahme der übereinstimmenden Elemente (wird $~elementals Muster verwendet).

Kreuzung setzen

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

${set1:*set2}führt die Array-Schnittmenge aus, die "${(@)...}"Syntax ist jedoch erforderlich, um leere Elemente beizubehalten.

Stellen Sie die Gleichheit ein

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

Testet, ob die Arrays identisch sind (und in derselben Reihenfolge). Das qParametererweiterungsflag setzt die Elemente in Anführungszeichen (um Probleme mit Dingen wie a=(1 "2 3")vs zu vermeiden b=("1 2" 3)) und (j: :)verbindet sie mit Leerzeichen, bevor ein Zeichenfolgenvergleich durchgeführt wird.

Verwenden Sie das oFlag, um zu überprüfen, ob sie unabhängig von der Reihenfolge dieselben Elemente haben. Siehe auch das uFlag (einzigartig) zum Entfernen von Duplikaten.

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

Set Kardinalität

n=$#array

Teilmengen-Test

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

Union

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

(siehe typeset -Uoben oder das uParametererweiterungs-Flag, um Duplikate zu erfassen). Wenn die leere Zeichenfolge nicht zu den möglichen Werten gehört, können Sie Folgendes vereinfachen:

union=($array1 $array2)

ergänzen

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

denn die Elemente $array1davon sind nicht in $array2.

Minimum / Maximum (lexikalischer Vergleich)

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

Minimum / Maximum (Dezimalzahlvergleich)

min=${${(no)array}[1]} max=${${(no)array}[-1]}
Stéphane Chazelas
quelle