Инструменты Linux для обработки файлов как множеств и выполнения операций над ними

Кто-нибудь знает о инструменте для Linux, специально разработанном для обработки файлов как множеств и выполнения операций над множествами? Например, разность, пересечение и т.д.?

Предположим, что элементы представляют собой строки символов за исключением NUL и перевода строки (хотя стоит учитывать, что перевод строки допустим в именах файлов), вы можете представить множество как текстовый файл с одним элементом в строке и использовать некоторые стандартные утилиты Unix.

Принадлежность к множеству

$ grep -Fxc 'элемент' множество   # выводит 1, если элемент в множестве
                                   # выводит >1, если множество - мультимножество
                                   # выводит 0, если элемент не в множестве

$ grep -Fxq 'элемент' множество   # возвращает 0 (истина), если элемент в множестве
                                   # возвращает 1 (ложь), если элемент не в множестве

$ awk '$0 == "элемент" { s=1; exit }; END { exit !s }' множество
# возвращает 0, если элемент в множестве, 1 в противном случае.

$ awk -v e="элемент" '$0 == e { s=1; exit } END { exit !s }'

Пересечение множеств

$ comm -12 <(sort множество1) <(sort множество2)  # выводит пересечение множества1 и множества2

$ grep -xF -f множество1 множество2

$ sort множество1 множество2 | uniq -d

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

$ awk '!done { a[$0]; next }; $0 in a' множество1 done=1 множество2

Равенство множеств

$ cmp -s <(sort множество1) <(sort множество2) # возвращает 0, если множество1 равно множеству2
                                   # возвращает 1, если множество1 != множество2

$ cmp -s <(sort -u множество1) <(sort -u множество2)
# сводит мультимножества к множествам и делает то же самое, что и предыдущая

$ awk '{ if (!($0 in a)) c++; a[$0] }; END{ exit !(c==NR/2) }' множество1 множество2
# возвращает 0, если множество1 == множество2
# возвращает 1, если множество1 != множество2

$ awk '{ a[$0] }; END{ exit !(length(a)==NR/2) }' множество1 множество2
# то же самое, требует >= gnu awk 3.1.5

Кардинальность множеств

$ wc -l < множество     # выводит количество элементов в множестве

$ awk 'END { print NR }' множество

$ sed '$=' множество

Тест подмножества

$ comm -23 <(sort -u подмножество) <(sort -u множество) | grep -q '^'
# возвращает истину, если подмножество не является подмножеством множества (имеет элементы, не входящие в множество)

$ awk '!done { a[$0]; next }; { if !($0 in a) exit 1 }' множество done=1 подмножество
# возвращает 0, если подмножество является подмножеством множества
# возвращает 1, если подмножество не является подмножеством множества

Объединение множеств

$ cat множество1 множество2     # выводит объединение множества1 и множества2
                    # предполагается, что они не пересекаются

$ awk 1 множество1 множество2   # аналогично

$ cat множество1 множество2 ... множествоn   # объединение n множеств

$ sort -u множество1 множество2  # то же самое, но не предполагает, что они не пересекаются

$ sort множество1 множество2 | uniq

$ awk '!a[$0]++' множество1 множество2       # аналогично без сортировки

Дополнение множества

$ comm -23 <(sort множество1) <(sort множество2)
# выводит элементы в множестве1, которые не входят в множество2

$ grep -vxF -f множество2 множество1           # аналогично

$ sort множество2 множество2 множество1 | uniq -u    # аналогично

$ awk '!done { a[$0]; next }; !($0 in a)' множество2 done=1 множество1

Симметрическая разность множеств

$ comm -3 <(sort множество1) <(sort множество2) | tr -d '\t'  # предполагает отсутствие табуляции в множествах
# выводит элементы, которые находятся в множестве1 или в множестве2, но не в обоих

$ sort множество1 множество2 | uniq -u

$ cat <(grep -vxF -f множество1 множество2) <(grep -vxF -f множество2 множество1)

$ grep -vxF -f множество1 множество2; grep -vxF -f множество2 множество1

$ awk '!done { a[$0]; next }; $0 in a { delete a[$0]; next }; 1;
       END { for (b in a) print b }' множество1 done=1 множество2

Степенной набор

Все возможные подмножества множества, отображенные через пробел, по одному на строку:

$ p() { [ "$#" -eq 0 ] && echo || (shift; p "$@") |
        while read r; do printf '%s %s\n%s\n' "$1" "$r" "$r"; done; }
$ p $(cat множество)

(предполагает, что элементы не содержат SPC, TAB (принимая значение по умолчанию для $IFS), обратную косую черту, подстановочные символы).

Декартово произведение множеств

$ while IFS= read -r a; do while IFS= read -r b; do echo "$a, $b"; done < множество1; done < множество2

$ awk '!done { a[$0]; next }; { for (i in a) print i, $0 }' множество1 done=1 множество2

Тест на непересекаемость множеств

$ comm -12 <(sort множество1) <(sort множество2)  # ничего не выводит, если множества непересекаются

$ awk '++seen[$0] == 2 { exit 1 }' множество1 множество2 # возвращает 0, если непересекаются
                                             # возвращает 1, если нет

Тест на пустое множество

$ wc -l < множество            # выводит 0  если множество пусто
                         # выводит >0, если множество не пусто

$ grep -q '^' множество        # возвращает истину (0 код выхода), если множество не пусто

$ awk '{ exit 1 }' множество   # возвращает истину (0 код выхода) если множество пусто

Минимальное значение

$ sort множество | head -n 1   # выводит минимальный (лексикографически) элемент в множестве

$ awk 'NR == 1 { min = $0 }; $0 < min { min = $0 }; END { print min }'
# аналогично, но выполняет числовое сравнение, когда элементы числовые

Максимальное значение

$ sort тест | tail -n 1    # выводит максимальный элемент в множестве

$ sort -r тест | head -n 1

$ awk 'NR == 1 || $0 > max { max = $0 }; END { print max }'
# аналогично, но выполняет числовое сравнение, когда элементы числовые

Все доступно по http://www.catonmat.net/blog/set-operations-in-unix-shell-simplified/

В некоторой степени да. Вам нужно самостоятельно заниматься сортировкой, но comm можно использовать для этого, рассматривая каждую строку как элемент множества: -12 для пересечения, -13 для разности. (А -23 даст вам перевернутую разность, то есть множество2 - множество1, а не множество1 - множество2.) Объединение – это sort -u в этой настройке.

Крошечный консольный инструмент “setop” теперь доступен в Debian Stretch и в Ubuntu с 16.10. Вы можете установить его через

sudo apt install setop


Вот несколько примеров. Множества, с которыми предстоит работать, указаны в виде различных входных файлов:

setop input # эквивалентно "sort input --unique"
setop file1 file2 --union # опция --union является стандартной и может быть опущена
setop file1 file2 file3 --intersection # допускается более двух входов
setop file1 - --symmetric-difference # - обозначает стандартный ввод
setop file1 -d file2 # все элементы, содержащиеся в 1, но не в 2

Логические запросы возвращают только EXIT_SUCCESS в случае истины и EXIT_FAILURE вместе с сообщением в противном случае. Таким образом, setop может использоваться в оболочке.

setop inputfile --contains "value" # содержится ли элемент value в входах?
setop A.txt B.txt --equal C.txt # объединение A и B равно C?
setop bigfile --subset smallfile # аналогично --superset
setop -i file1 file2 --is-empty # пересечение 1 и 2 пустое (непересекаются)?


Также возможно точно описать, как потоки ввода будут разбираются, на самом деле с помощью регулярных выражений:

• setop input.txt --input-separator "[[:space:]-]" означает, что пробел (т.е. \v \t \n \r \f или пробел) или знак минус интерпретируются как разделитель между элементами (по умолчанию – перенос строки, т.е. каждая строка входного файла соответствует одному элементу)
• setop input.txt --input-element "[A-Za-z]+" означает, что элементы представляют собой только слова, состоящие из латинских символов, все другие символы считаются разделителями между элементами

Кроме того, вы можете

• --count все элементы выходного множества,
• --trim все входные элементы (т.е. удалить все нежелательные предшествующие и последующие символы, такие как пробел, запятая и т.д.),
• считать пустые элементы действительными с помощью --include-empty,
• --ignore-case,
• установить --output-separator между элементами выходного потока (по умолчанию \n),
• и так далее.

Смотрите man setop или github.com/phisigma/setop для получения дополнительной информации.

Не знаю о конкретном инструменте, но вы можете использовать Python и его класс множеств и операторы, чтобы написать небольшой скрипт для этого.

Например:

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

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

Если рассматривать файл как множество строк, и файлы отсортированы, то существует comm.

Если рассматривать файл как (мультимножество) строк, и строки не отсортированы, grep может выполнить разность и пересечение (он достигает разности и пересечения множеств, но не учитывает количество для мультимножеств). Объединение просто cat.

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

Я создал утилиту на Python, которая может выполнять по строкам объединение, пересечение, разность и произведение нескольких файлов. Она называется SetOp, и вы можете найти ее в PyPI (здесь). Синтаксис выглядит так:

$ setop -i file1 file2 file3  # пересечение
$ setop -d file1 file2 file3  # разность

С массивами zsh (zsh массивы могут содержать любую произвольную последовательность байтов, включая 0).

принадлежность к множеству

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

(используя флаг индексации массива I, чтобы получить индекс последнего вхождения $element в массив (или 0, если не найдено). Удалите e (для exact), чтобы $element рассматривался как шаблон)

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

${array:#pattern} — это вариант на ${var#pattern} в ksh, который удаляет элементы, соответствующие шаблону, в отличие от простого удаления начальной части, которая соответствует шаблону. Флаг (M) (для matched) меняет значение и удаляет все, кроме совпадающих элементов (используйте $~element, чтобы это было воспринято как шаблон).

пересечение множеств

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

${set1:*set2} выполняет пересечение массивов, но синтаксис "${(@)...}" необходим для сохранения пустых элементов.

равенство множеств

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

Проверяет, идентичны ли массивы (и в одном и том же порядке). Флаг расширения параметров q экранирует элементы (чтобы избежать проблем с такими вещами, как a=(1 "2 3") против b=("1 2" 3)), и (j[ ]) объединяет их с пробелом перед выполнением строкового сравнения.

Чтобы проверить, имеют ли они одинаковые элементы, независимо от порядка, используйте флаг o для их упорядочивания. Смотрите также флаг u (уникальный) для удаления дубликатов.

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

кардинальность множеств

n=$#array

тест на подмножество

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

(предполагая массивы с уникальными значениями)

объединение

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

(смотрите typeset -U выше или флаг расширения параметров u, чтобы позаботиться о дубликатах). Если пустая строка не является одним из возможных значений, вы можете упростить до:

union=($array1 $array2)

дополнение

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

для элементов $array1, которые не входят в $array2.

Минимальное/максимальное (лексикографическое сравнение)

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

Минимальное/максимальное (сравнение целых чисел с плавающей запятой)

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

Я написал инструмент на Go для этого вопроса. Исходный код можно найти здесь на GitHub.

Вы можете использовать homebrew для установки его на macOS:

brew install suzaku/homebrew-rose/rose

Использование очень простое:

• rose and file1 file2 для пересечения.
• rose or file1 file2 для объединения.
• rose sub file1 file2 для вычитания.

Используя Raku (ранее известный как Perl_6)

Raku имеет два выбора типов объектов, когда дело доходит до операций, связанных с множествами. Они:

1. Set тип объекта (неизменяемый),
2. SetHash тип объекта (изменяемый).

Можно использовать символы Unicode, например, инфикс ∩ для пересечения, или его ASCII эквивалент, например, инфикс (&) для пересечения. Обратите внимание, что для результатов множества ниже первые две строки идентичны; в третьей (и последней) строке только оператор множества меняется.

Ниже, произведя сравнение множеств, берем (известное, 72-словное) предложение “Мы считаем эти истины самоочевидными…” из Декларации независимости США, и выполняем сравнение с (также известным, 38-словным) Преамбулой Конституции США:

Пересечение: инфикс (&), инфикс ∩

~$ raku -e 'my Set $a .= new(.comb(/<alpha>+/)>>.lc) given "declaration.txt".IO.words; 
            my Set $b .= new(.comb(/<alpha>+/)>>.lc) given "preamble.txt".IO.words; 
           .sort>>.keys.put given $a (&) $b; #returns 10 words'
и форма в свободе людей, обеспечивающих

Объединение: инфикс (|), инфикс ∪

~$ raku -e 'my Set $a .= new(.comb(/<alpha>+/)>>.lc) given "declaration.txt".IO.words; 
            my Set $b .= new(.comb(/<alpha>+/)>>.lc) given "preamble.txt".IO.words; 
           .sort>>.keys.put given $a (|) $b; #returns 100 words'
все создать, благословения по определенному общему согласованию, основы со стороны общего правительства, которое защищает и поддерживает

Симметрическая разность множеств: $a (^) $b, или воспользуйтесь инфиксом ⊖

~$ raku -e 'my Set $a .= new(.comb(/<alpha>+/)>>.lc) given "declaration.txt".IO.words; 
            my Set $b .= new(.comb(/<alpha>+/)>>.lc) given "preamble.txt".IO.words; 
           .sort>>.keys.put given $a (^) $b; #returns 90 words'
все, что является преступлением и недопустимым, остается

Асимметрическая разность множеств: $a (-) $b, или воспользуйтесь инфиксом ∖

~$ raku -e 'my Set $a .= new(.comb(/<alpha>+/)>>.lc) given "declaration.txt".IO.words; 
            my Set $b .= new(.comb(/<alpha>+/)>>.lc) given "preamble.txt".IO.words; 
           .sort>>.keys.put given $a (-) $b; #returns 62 words'
все, что лишено общепринятых обычных и обязательных условий

Асимметрическая разность множеств: $b (-) $a, или воспользуйтесь инфиксом ∖

~$ raku -e 'my Set $a .= new(.comb(/<alpha>+/)>>.lc) given "declaration.txt".IO.words; 
            my Set $b .= new(.comb(/<alpha>+/)>>.lc) given "preamble.txt".IO.words; 
           .sort>>.keys.put given $a (-) $b; #returns 28 words'
все внешниепы, которые имеют какое-либо основание, в котором

Операторы множеств, возвращающие Boolean

(Как и выше, символы Unicode можно использовать, но многие из них имеют легко печатаемые ASCII варианты):

1. инфикс (elem), инфикс ∈
2. инфикс ∉
3. инфикс (cont), инфикс ∋
4. инфикс ∌
5. инфикс (<=), инфикс ⊆
6. инфикс ⊈
7. инфикс (<), инфикс ⊂
8. инфикс ⊄
9. инфикс (>=), инфикс ⊇
10. инфикс ⊉
11. инфикс (>), инфикс ⊃
12. инфикс ⊅
13. инфикс (==), инфикс ≡
14. инфикс ≢

https://www.archives.gov/founding-docs/declaration-transcript
https://www.archives.gov/founding-docs/constitution
https://docs.raku.org/language/setbagmix#Sets,_bags,_and_mixes
https://raku.org

Я написал небольшой инструмент для этого, который оказался весьма полезным мне в разных местах. Интерфейс не отполирован, и я не уверенно на счет его производительности при работе с очень большими файлами (так как он читает весь список в память), но “он работает для меня”. Программа доступна по адресу https://github.com/nibrahim/lines. Она написана на Python. Вы можете установить ее с помощью pip install lines.

В настоящее время она поддерживает объединение, пересечение, разность и симметрическую разность двух файлов. Каждая строка входного файла рассматривается как элемент множества.

Также есть две дополнительные операции. Одна из них позволяет удалить пустые строки из файла, а вторая (которая оказалась весьма полезной для меня) – просмотреть файл и разделить его на множества схожих строк. Мне это нужно было, чтобы искать файлы в списке, которые не соответствуют общему шаблону.

Я буду рад получить ваши отзывы.

Файловая система рассматривает имена файлов (полные имена файлов, включая пути) как уникальные.

Операции?

Вы можете скопировать файлы из a/ и b/ в пустую директорию c/, чтобы получить новое объединенное множество.

С помощью тестов файлов, таких как -e name, и циклов или поиска, вы можете проверить, существуют ли файлы в двух или более директориях, чтобы получить пересечение или разницу.

Лучший ответ по этому поводу: Setdown (посвященный инструмент)

Я написал программу под названием setdown, которая выполняет операции над множествами из командной строки.

Она может выполнять операции над множествами, записывая определение, аналогичное тому, что вы написали бы в Makefile:

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

Это довольно круто, и вам стоит обратить на это внимание. Лично я не рекомендую использовать разрозненные команды, которые не предназначены для этой работы, для выполнения операций над множествами. Это не будет хорошо работать, когда вам действительно нужно выполнить много операций над множествами или если у вас есть операции, которые зависят друг от друга. Не только это, но setdown позволяет записывать операции над множествами, которые зависят от других операций над множествами!

В любом случае, я думаю, что это довольно круто, и вам определенно стоит обратить на это внимание.

Пример шаблона для нескольких файлов (в данном случае пересечение):

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

Расширяется до:

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

Тестовые файлы:

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

Вывод:

0
6
12
18