☰

对于文件 A 中的每一行，用模式替换文件 B 中所有匹配的行

tag-icon • tag-icon awk sed perl
对于文件 A 中的每一行，用模式替换文件 B 中所有匹配的行

fileA 包含约 100k 字符串（仅限人名a-zA-Z）

fileB 有约 100M 行

程式

只有两个程序：

  • 用单个点替换字符串
  • 用相同长度的点替换字符串

算法

for each lineB in fileB do
   for each lineA in fileA do
      if lineA matches with lineB; then
         replace the match in lineB with dots
         append the modified lineB' to file "res-length" or "res-single", depending on the program
      fi
   done
done

直接的解决方案非常慢。

匹配应该不区分大小写。

可以另外安装任何其他 Linux 应用程序（gawk 等）。

例子

$ cat fileA
agnes
Ari
Vika

$ cat fileB
12vika1991
ariagnes#!
ari45
lera56er

输出应该是两个文件，对应于每个程序：

$ cat res-single  # replace a string with a single dot
12.1991
.agnes#!
ari.#!
.45

$ cat res-length  # replace a string with dots of the same length
12...1991
...agnes#!
ari.....#!
...45

该任务的简化版本要求输出唯一的第一的匹配。所以对于程序#2 而不是...agnes#!andari.....#!只输出就足够了ari.....#!

简化的任务算法

for each lineB in fileB do
   find the first lineA in fileA that matches lineB
   if lineA is found; then
      replace the match in lineB with dots
      append the modified lineB' to file "res-length" or "res-single", depending on the program
   fi
done

Python实现

def create_masks(wordlist=WordListDefault.TOP1M.path, replace_char='.'):
    # fileA lowercase
    names = PATTERNS_PATH.read_text().splitlines()

    masks_length = []
    masks_single = []
    with codecs.open(wordlist, 'r', encoding='utf-8', errors='ignore') as infile:
        for line in infile:
            line_lower = line.lower()
            for name in names:
                i = line_lower.find(name)
                if i != -1:
                    ml = f"{line[:i]}{replace_char * len(name)}{line[i + len(name):]}"
                    ms = f"{line[:i]}{replace_char}{line[i + len(name):]}"
                    masks_length.append(ml)
                    masks_single.append(ms)

    with open(MASKS_LENGTH, 'w') as f:
        f.writelines(masks_length)
    with open(MASKS_SINGLE, 'w') as f:
        f.writelines(masks_single)


if __name__ == '__main__':
    create_masks()

对于 1.6M 文件 A 和 1k 文件 B，大约需要 3 分钟，随后减少到仅 10 秒grep -iF -f fileA fileB > fileB.filtered。

@Ned64 说得对，最快的方法就是简单的 C，这不是本论坛的主题。

当前的 python 实现需要 52 天才能处理 fileB 的 2B 行以及 fileA 中的 35k 字符串。我不再确定纯 C 能否在一小时内完成此操作。我想知道 CUDA 是否是一种可行的方法......

答案1

$ cat tst.awk
BEGIN {
    dots = sprintf("%*s",1000,"")
    gsub(/ /,".",dots)
    resSingle = "res-single"
    resLength = "res-length"
}
{ lc = tolower($0) }
NR==FNR {
    lgth = length($0)
    str2lgth[lc] = lgth
    str2dots[lc] = substr(dots,1,lgth)
    next
}
{
    for (str in str2lgth) {
        if ( s=index(lc,str) ) {
            bef = substr($0,1,s-1)
            aft = substr($0,s+str2lgth[str])
            print bef "." aft > resSingle
            print bef str2dots[str] aft > resLength
        }
    }
}

。

$ awk -f tst.awk fileA fileB

$ cat res-single
12.1991
ari.#!
.agnes#!
.45

$ cat res-length
12....1991
ari.....#!
...agnes#!
...45

上面假设 fileA 中的任何行都不会超过 1000 个字符，如果这是错误的，请选择一个更大的数字，或者我们可以在必要时添加代码来计算它。它还假设您不关心在 fileB 中查找 fileA 中的行的顺序，并且您想要进行字符串而不是正则表达式比较，如果这不是您想要的，那么这两者都是微不足道的调整。

编辑以回应您下面的评论，如果您无法静态定义 fileA 中的行的最大长度（甚至不是 100,000 个字符？），则以下是如何修改上述内容，因此需要计算出最大值，并且 fileA 中的行是全部小写：

NR==FNR {
    lgth = length($0)
    str2lgth[$0] = lgth
    maxLgth = (lgth > maxLgth ? lgth : maxLgth)
    next
}
FNR==1 {
    dots = sprintf("%*s",maxLgth,"")
    gsub(/ /,".",dots)
    for ( str in str2lgth ) {
        str2dots[str] = substr(dots,1,str2lgth[str])
    }
    resSingle = "res-single"
    resLength = "res-length"
}
{
    lc = tolower($0)
    for (str in str2lgth) {
        if ( s=index(lc,str) ) {
            bef = substr($0,1,s-1)
            aft = substr($0,s+str2lgth[str])
            print bef "." aft > resSingle
            print bef str2dots[str] aft > resLength
        }
    }
}

答案2

您可以在此处使用简单的基于 Perl 的方法。

方法：

填充一个散列 %h，其键是 fileA 的小写行（不带换行符），值是等效的点数。

然后，对于 fileB 的每一行，我们测试哈希 %h 的任何键是否以不区分大小写的方式存在。如果是，那么我们将匹配前、匹配和匹配后数据打印到 res-single 和 res-length 文件中。如果您只想要第一个匹配项，请取消注释“最后一个”语句。

$ perl -Mautodie -lne '
    BEGIN {
     open *{"FH$_"}, ">", qw[res-single res-length][$_] for 0..1;
     do{
       local @ARGV = pop;
       $h{do{chomp;lc;}} = s/././gr =~ tr/\n//dr while <>;
       @h = keys %h;
      };
    }
    for my $h ( @h ) {
      if ( /\Q$h/pi ) {
        my($p, $q) = (${^PREMATCH}, ${^POSTMATCH});
        print {*{"FH$_"}} $p, (".", $h{$h})[$_], $q for 0..1;
        #last;
      }
    }
' fileB fileA

$ more res-*

::::::::::::::
res-length
::::::::::::::
12....1991
ari.....#!
...agnes#!
...45

::::::::::::::
res-single
::::::::::::::
12.1991
ari.#!
.agnes#!
.45

答案3

优化的C解决方案https://github.com/dizcza/people-names-as-passwords/blob/master/src/create_masks.c

我使用了 trie 数据结构，它允许我在 12 分钟内解析 2B 行fileB和 43k 行！fileA

感谢大家的意见。

相关内容