☰

ファイルAの各行について、ファイルBの一致するすべての行をパターンに置き換えます。

tag-icon • tag-icon awk sed perl
ファイルAの各行について、ファイルBの一致するすべての行をパターンに置き換えます。

fileAには約100,000個の文字列が含まれています（人名のみa-zA-Z）。

fileBには約1億行があります。

プログラム

プログラムは2つだけです。

  • 文字列を単一点に置き換える
  • 文字列を同じ長さの点に置き換える

演算

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

出力は各プログラムごとに1つずつ、2つのファイルでなければなりません。

$ 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#!出力ari.....#!だけで十分です。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()

160万個のファイルAと1,000個のファイルBの場合、約3分かかり、わずか10秒に短縮されましたgrep -iF -f fileA fileB > fileB.filtered。

@Ned64さんの言葉が正しいです。最速の方法は単純なCです。これはこのフォーラムのトピックではありません。

現在のPython実装では、fileBの2B行とfileAの35k文字列を処理するには52日かかります。純粋なCが1時間以内にこれを実行できるかどうかはもうわかりません。 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文字を超える行がないと仮定しています。これが間違っている場合は、より大きな数字を選択するか、必要に応じてコードを追加して計算できます。また、fileAの行がfileBで見つかった順序に興味がなく、正規表現比較ではなく文字列比較を実行したいとします。どちらも欲しいものではない場合はマイナーな調整です。

以下のコメントに応じて編集してください。 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ベースのアプローチを使用できます。

方法：

キーがfileAの小文字の行（改行なし）で、値が等しい点であるハッシュ％hを埋めます。

次に、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と43,000行を解析できました！fileA

ご意見ありがとうございます。

関連情報