☰

查找存储库中未出现的字符串

tag-icon • tag-icon unix regex grep unix-utils egrep
查找存储库中未出现的字符串

问题：我有一个中等大小的存储库（数千个文件，数十万行）。

我有一个约有 5000 行的文本文件。

我需要在文本文件中找到未在存储库其他任何地方出现的行。

是否有一个工具，或者一种巧妙使用 grep 的方法，可以有效地找到这个答案？

谢谢你的帮助

答案1

该解决方案是在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开始。正如我之前所说，当返回时，您的结果在。0wc0$patterns

最后删除临时文件：

rm "$tmpf1" "$tmpf2"

效率

我有 20 万个文本文件，4.5M 行，总共 300 MiB。这些是 HTML 文档，标题和格式都很简单，正文几乎都是纯英文文本。我选取了 3k 个最常见的英文单词作为模式，并添加了几行胡言乱语。

首先grep需要几分钟从 HDD 读取数据并开始工作，然后大约需要两分钟sort。但由于缓存的存在，每次后续迭代都只需几秒钟，并且$patterns时间越来越短。

我的硬件是 Core i7 和 8 GiB RAM。您的模式和文件可能有很大差异，并会影响您的执行时间。不过，我认为您有机会在几分钟内完成任务。

剧本

这是上述算法的实现。一个附加功能是：它从中获取模式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"

相关内容