Найти строки, которые не отображаются в хранилище

Решение было разработано в bash на Ubuntu 16.04.2 LTS.

Алгоритм

Этот раздел является образовательным. Вы можете найти весь сценарий в конце моего ответа.

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

patterns="/path/to/your/text/copy"
repository="/path/to/your/repository/"

Вам понадобится несколько временных файлов.

tmpf1=`mktemp`
tmpf2=`mktemp`

Следующая команда сохранит все (ну, почти все, прочитайте вместе) шаблоны, которые появятся в хранилище, в первый временный файл. Увидеть man grep расшифровать команду. Также решите, нужно ли вам добавить -i возможность grep , Первый uniq не является обязательным, он используется для предварительного сокращения данных, которые sort ,

grep -rhoIFf "$patterns" "$repository" | uniq | sort | uniq | tee "$tmpf1" | wc -l

Если вышеприведенная команда печатает 0 , $patterns файл является вашим окончательным результатом, независимо от ошибок, указанных ниже, и вы должны удалить только временные файлы.

Есть подводные камни с grep , вы будете иметь дело с ними в данный момент. Хорошо знать, кто они.

1. Если есть foobar а также foo как шаблоны, foobar в репозитории будет совпадать foobar только.
2. Если есть foobar а также barbaz как шаблоны, foobarbaz в репозитории будет совпадать foobar только.
3. Если есть foobarbaz а также bar как шаблоны, foobarbaz в репозитории будет совпадать foobarbaz только.

Из-за этих ловушек $tmpf1 может не содержать все шаблоны, которые действительно появляются в хранилище (т. е. он может не содержать barbaz от второй ловушки).

Теперь вам нужно выбрать все эти строки из $patterns которые якобы не были найдены в хранилище. Обратите внимание, что вы должны соответствовать целые строки, следовательно, -x ,

grep -vxFf "$tmpf1" "$patterns" > "$tmpf2"

В этот момент $tmpf2 будет вашим окончательным результатом, но из-за этих ошибок он может содержать слишком много строк (например, barbaz от второй ловушки). Хитрость заключается в использовании $tmpf2 как новый файл шаблона и повторите процесс! Призовите:

cp "$tmpf2" "$patterns"

затем перейдите к первому grep , Повторяйте эту процедуру, пока не получите 0 от wc там. Как я уже говорил, когда 0 возвращается ваш результат в $patterns ,

В конце удалите временные файлы:

rm "$tmpf1" "$tmpf2"

КПД

У меня есть 200 тыс. Текстовых файлов, 4,5 млн строк, всего 300 мегабайт. Это HTML-документы с простыми заголовками и форматированием, почти простой текст на английском языке. Я взял 3k самых распространенных английских слов в качестве шаблонов и добавил несколько строк мумбо-юмбо.

Первый grep Потребовалось несколько минут, чтобы прочитать данные с жесткого диска и работать, затем около двух минут для sort , Но каждая последующая итерация занимала считанные секунды благодаря кешированию и $patterns сокращается все больше и больше.

Мое оборудование - Core i7 и 8 ГБ оперативной памяти. Ваши шаблоны и файлы могут значительно отличаться и влиять на время выполнения. Тем не менее, я думаю, что есть шанс, что вы решите задачу за несколько минут.

Сценарий

Это реализация вышеуказанного алгоритма. Еще одна особенность: он берет шаблоны из stdin , выводит результат на stdout , В этом случае вам не нужно копировать ваш текстовый файл. Сценарий не является надежным.

Сохраните следующий код как findUnused.sh , затем chmod a+x findUnused.sh ,

#!/bin/bash

patterns=`mktemp`
cat > "$patterns"
repository="$1"
tmpf1=`mktemp`
tmpf2=`mktemp`

while [ `grep -rhoIFf "$patterns" "$repository" | uniq | sort | uniq | tee "$tmpf1" | wc -l` -ne 0 ]
do
  grep -vxFf "$tmpf1" "$patterns" > "$tmpf2"
  cp "$tmpf2" "$patterns"
done
cat "$patterns"
rm "$patterns" "$tmpf1" "$tmpf2"

Использование (обратите внимание, есть перенаправления):

./findUnused.sh "/path/to/your/repository/" < "/path/to/your/text/file" > "/path/to/store/the/result"