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

0

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

У меня есть текстовый файл с ~ 5000 строк.

Мне нужно найти строки в текстовом файле, которые не появляются где-либо еще в хранилище.

Есть ли инструмент или умный способ использовать grep, который может эффективно найти этот ответ?

Спасибо за любую помощь

Крис
источник
1
«Мне нужно найти строки в текстовом файле, которые больше нигде не появляются в хранилище». Мы говорим о целых строках или фрагментах в хранилище? Допустим, в вашем текстовом файле есть строка «foobar» и строка «foobar baz» в хранилище. Это появление? Или следует рассматривать только точную строку "foobar"?
Камиль Мачоровски
Фрагменты, строки, которые я пытаюсь сопоставить, могут быть частью любой строки в исходном коде.
Крис

Ответы:

0

Решение было разработано в bashUbuntu 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"
Камил Мачоровский
источник