4

ルックアップ ファイルの長い行で grep がパターン ファイルから短いパターンを検出する場合、長いパターン内にあるルックアップ ファイルの短い行を抽出できるツールが必要です。

言い換えれば、1 行に 1 文のシェイクスピアの作品があり、フランス語の辞書を例にとると、シェイクスピアのどの行にどのフランス語の単語が含まれているかを調べて、シェイクスピアの行に複数の文が含まれている可能性があるという事実を検出できるようにする必要があります。フランス語の単語が 1 つ以上あること、およびフランス語の単語がシェイクスピアの複数の行に出現する可能性があること。

例えば：

pattern_file={
"The sun is shining!"
"It is a beautiful day!"}

lookup_file={
"Rain"
"Sun"
"Cloud"
"Beautiful"
"Shining"}

私が欲しいのは

function file pattern

複数の一致が検出された状態で、長いパターンで見つかった線と長いパターン自体の両方をカンマで区切って指定します。

ideal_result_file={
"Sun","The sun is shining!"
"Beautiful","It is a beautiful day!",
"Shining", "The sun is shining!"}

現在、grep を使用してルックアップ ファイル全体を 1 行ずつループ処理しています。

    while read line
    do
      grep  -is $line pattern_file | sed 's/^/'"$line"'\,/g' >> result_file.csv
    done < lookup_file

これは信じられないほど遅いです！私のlookup_fileには50,000行以上が含まれていますが、私のpattern_fileには500行が含まれています.grepを使用してlookup_fileでさらに短いパターンを見つけるのに数秒かかるのに対し、ループアプローチを使用した単一のパスには数日/数週間かかります.

任意の言語でのソリューションをいただければ幸いです。

大規模なデータセットで grep または fgrep を使用した
非常に遅いループ
Perl は bash より高速ですか?

ソリューションは、GB サイズのループアップおよびパターン ファイルと互換性がある必要があります。

4

9 に答える 9

6

-fスイッチを使用して、grep で「パターン ファイル」を使用できます。

egrep -i -f lookup_file pattern_file >> result_file

これは、各行に対して各パターンを個別にチェックするのではなく、すべての一致を同時にチェックする単一のステート マシンにgrepコンパイルされるため、高速になります。lookup_file

lookup_file が正規表現ではなくテキストで構成されている場合は、fgrep を使用するとさらに高速になります。

理想的な出力を得るには、-n および -o スイッチを使用して、各行に一致するパターンのリストを取得します。

于 2013-03-29T13:31:42.330 に答える
3

任意の言語が受け入れられることを示したので、まったく異なるアプローチを投稿します。シェル スクリプトを使用すると、インメモリ ツールやデータベースのパフォーマンスに勝るものはありません。大量のデータがある場合は、これらの種類の操作を目的としたデータベースを使用する必要があり、スケーリングがはるかに優れています。

ここでは、sqlite ( www.sqlite.org ) を使用した簡単な例を示します。

たとえば、次のように、パターンとデータをテーブルにインポートする必要があります (必要に応じて、これをスクリプト化できます)。

CREATE TABLE patterns (pattern TEXT);
CREATE TABLE data (sentence TEXT);

BEGIN;

INSERT INTO patterns VALUES ('Sun');
INSERT INTO patterns VALUES ('Rain');
INSERT INTO patterns VALUES ('Cloud');
INSERT INTO patterns VALUES ('Beautiful');

INSERT INTO data VALUES ('The sun is shining');
INSERT INTO data VALUES ('It is a beautiful day');
INSERT INTO data VALUES ('It is cloudy and the sun shines');

COMMIT;

次に、selectクエリを実行して目的の出力を取得します。

select pattern, group_concat(sentence) as doesmatch from (
    select pattern, sentence, lower(pattern) as lpattern, lower(sentence) as lsentence
    from patterns left outer join data
    where like('%' || lpattern || '%', lsentence)
) group by pattern;

コマンドラインでこれを使用して、最初のスニペットを保存しdata.sql、2番目のスニペットを保存する場合:query.sql

sqlite3 sentences.db < data.sql    # this imports your data, run once
sqlite3 sentences.db < query.sql

これにより、以下が得られます。

Beautiful|It is a beautiful day
Cloud|It is cloudy and the sun shines
Sun|The sun is shining,It is cloudy and the sun shines

それがあなたが望むものだと私は信じています。より洗練されたものにするために、お気に入りのより高度なツールをデータベース ライブラリと共に使用します。これにはpythonを選択します。

さらに改善するための提案:

  • regex単語全体をフィルタリングする代わりに使用likeします (つまり、パターン "sun" は "sun" に一致しますが、"sunny" には一致しません)。

  • インポートユーティリティ、

  • 出力フォーマット、

  • クエリの最適化。

于 2013-04-02T18:15:54.733 に答える
2

「パターン」ファイルと「ルックアップ」ファイルの意味を交換し、grep の-oスイッチを使用する必要があります。

$ cat patterns 
The sun is shining!
It is a beautiful day!

$ cat lookup 
Rain
Sun
Cloud
Beautiful

$ grep -iof lookup patterns 
sun
beautiful
于 2013-03-29T14:31:43.473 に答える
2

編集: 申し訳ありませんが、前の例は機能しませんでした。

これは、perl に完全に一致するようです。皮切りに

#!/usr/bin/perl

open PATTERNS, "patterns";
open LOOKUP, "lookup";

my @l = <LOOKUP>;

while (chomp(my $re = <PATTERNS>)) {
     print "$re\n" if grep(/$re/, @l); 
}

ここで、パターンとルックアップの意味を入れ替えたことに注意してください。パターンはパターンです。線ではなくパターンを印刷したい場合は、それで問題ありませんが、名前は変更しません。

于 2013-03-29T16:03:51.207 に答える
0

上記のアイデアのいくつかを組み合わせて、次のようgrepに使用して結果をマージする 2 パス システムを考え出しました。join

パターン

The sun is shining!
It is a beautiful day!

調べる

Rain
Sun
Cloud
Beautiful
Is

脚本

grep -i -o -n -f lookup patterns > tmp1
grep -i -n -f lookup patterns > tmp2
join -t ':' -o 1.2,2.2 tmp1 tmp2 | sed -e 's/:/,/'

次の結果を生成します

sun,The sun is shining!
is,The sun is shining!
is,It is a beautiful day!
beautiful,It is a beautiful day!

ルックアップ マッチとコンマ区切りのパターンの出力が必要な場合は、動作する小さな python 2.x スクリプトを次に示します。ルックアップをバッファに読み込み、パターンを 1 回通過します。

script.py

import sys, re

lookups = [re.compile(l.strip(),re.I) for l in open(sys.argv[1])]
for line in open(sys.argv[2]):
    for lookup in lookups:
        if lookup.search(line):
            print "{0},{1}".format(lookup.pattern, line),

歩留まりpython script.py lookup patterns:

Sun,The sun is shining!
Is,The sun is shining!
Beautiful,It is a beautiful day!
Is,It is a beautiful day!
于 2013-04-08T18:20:25.030 に答える
0

接尾辞配列や接尾辞配列のようなものを使用するのはどうですか? grep のようなオプションに固執する利点がある実装をここで見つけることができますが、私はそれを使用したことがなく、その効率と使いやすさを証明することはできません。

接尾辞ツリー/配列は、O(n) から O(n log n) 時間 (n はルックアップ ファイルの長さ) で検索されるファイルを前処理する必要があり、接尾辞ツリー/配列自体は、元のファイル (定数係数) ですが、ディスクにバインドされたアルゴリズムがあり、ヒトゲノム全体を頻繁に検索するために使用されます (数 GB)。ファイル内の文字列の検索には、O(m) 時間しかかかりません。ここで、m は文字列の長さです。これは、たとえば grep (O(n log m)?) よりもはるかに高速です。同じファイルを何度も検索することになると思われるので、接尾辞ツリー/配列に必要な前処理ステップへの投資は価値があるかもしれません。

于 2013-04-04T18:47:51.450 に答える
-1

これは速くはないかもしれませんが、試すことができます：

for i in `cat lookup_file`; 
  do  
    tmpv=`grep -i ${i} pattern_file | xargs echo ${i},`; 
    echo ${tmpv} | sed '/^$/d'; 
done
于 2013-03-29T13:47:03.790 に答える