bash - 是否有 grep 的逆：在长模式中找到短线？

Question

在 grep 从查找文件的长行中的模式文件中找到一个短模式的地方，我需要一个工具来提取可以在较长模式中找到的查找文件的短行。

换句话说，给定莎士比亚的作品，每行一句话，说一本法语词典，我想找出在莎士比亚的哪一行中找到了哪些法语单词，从而可以检测到莎士比亚的一行可能包含更多的事实。一个法语单词，并且一个法语单词可能出现在不止一行的莎士比亚。

例如：

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 逐行遍历整个查找文件：

    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 大小的循环和模式文件兼容。

score 6 · Accepted Answer

您可以使用-f开关在 grep 中使用“模式文件”：

egrep -i -f lookup_file pattern_file >> result_file

这会更快，因为grep编译lookup_file成一个同时检查所有匹配项的状态机，而不是分别针对每一行检查每个模式。

如果您的 lookup_file 包含文本而不是正则表达式，您可以使用 fgrep ，它会更快。

要获得理想的输出，您可以使用 -n 和 -o 开关，并获得与每一行匹配的模式列表。

score 3 · Accepted Answer

由于您指出任何语言都可以接受，因此我将发布一种完全不同的方法：使用 shell 脚本，您将永远无法击败内存工具或数据库的性能。如果您有大量数据，则应该使用专门用于此类操作的数据库，并且可以更好地扩展。

所以这是一个使用 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第二个片段：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”），
导入实用程序，
输出格式，
查询优化。

score 3 · Accepted Answer

您的解决方案实际上可能很慢，因为它创建了 50.000 个进程，所有进程都读取 500 行模式文件。

另一个“纯 bash 和 unix utils”解决方案可能是让它grep做它最擅长的事情，并将输出与你的 pattern_file 匹配。

所以使用grep来查找匹配的行和实际匹配的部分。

我在这里使用单词匹配，可以通过删除 grep 行中的开关来关闭它，-w并获得示例中描述的初始行为。

输出尚未重定向到result_file.csv.. 这很容易在以后添加 8)

#!/bin/bash
# open pattern_file
exec 3<> pattern_file

# declare and initialize integer variables
declare -i linenr
declare -i pnr=0

# loop for reading from the grep process
#
# grep process creates following output:
#   <linenumber>:<match>
# where linenumber is the number of the matching line in pattern_file
# and   match is the actual matching word (grep -w) as found in lookup_file
# grep output is piped through sed to actually get
#   <linenumber> <match>
while read linenr match ; do

   # skip line from pattern_file till we read the line
   # that contained the match
   while [[ ${linenr} > ${pnr} ]] ; do
       read -u 3 pline
       pnr+=1
   done

   # echo match and line from pattern_file
   echo "$match, $pline"
done < <( grep -i -w -o -n -f lookup_file pattern_file | sed -e 's,:, ,' )

# close pattern_file
exec 3>&-

结果是

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

对于给出的例子。注意：匹配现在是保留大小写的完全匹配。所以这不会导致Sun, ...但会导致sun, ....

结果是一个脚本，它使用 grep 读取 pattern_files 一次，在最好的情况下读取 pattern_file 和 lookup_file 一次 - 取决于实际实现。它只会启动两个额外的进程：grep和sed. （如果需要，sed可以用外循环中的一些 bash 替换来替换）

我没有尝试使用 50.000 行 lookup_file 和 500 行 pattern_file。但我认为它可能和 grep 一样快。

只要grep可以将lookup_file保存在内存中，它可能是合理的快。（谁知道）

无论它是否解决了您的问题，我都会对它与您的初始脚本相比的性能感兴趣，因为我确实缺少很好的测试文件。

如果grep -f lookup_file使用太多内存（正如您之前在评论中提到的），它可能是一种解决方案，可以将其拆分为实际适合内存的部分并多次运行脚本或使用不止一台机器，在这些机器上运行所有部分并且只是收集并连接结果。只要 lookup_files 不包含欺骗，您就可以连接结果而不检查欺骗。如果排序很重要，您可以对所有单个结果进行排序，然后使用sort -m.

只要您只拆分一次lookup_file 并重新运行脚本，拆分lookup_file 不会显着影响运行时间，因为您的pattern_file 可能足够小，它的500 行无论如何都可以保留在内存缓存中！？如果您使用多于一台机器，lookup_file 可能也是如此 - 它的部分可能只保留在每台机器的内存中。

编辑：

正如我在评论中指出的那样，这不适用于开箱即用的重叠文件，因为grep -f似乎只返回最长的匹配并且不会重新匹配，所以如果lookup_file包含

Sun
Shining
is
S

结果将是

sun, The sun is shining
is, The sun is shining
shining, The sun is shining

并不是

sun, The sun is shining
is, The sun is shining
shining, The sun is shining
s, The sun is shining
s, The sun is shining
s, The sun is shining

因此，所有匹配项s（匹配三次）都丢失了。

事实上，这是这个解决方案的另一个问题：如果一个字符串被找到两次，它将被匹配两次，并且将返回相同的行，这可以通过uniq.

可能的解决方法：拆分lookup_file搜索字符串的按字符串长度。这将减少运行 grep 所需的最大内存，但也会稍微减慢整个过程。但是：然后您可以并行搜索（如果在同一台服务器上执行此操作，可能需要检查greps选项）。--mmap

score 2 · Accepted Answer

您需要交换“模式”和“查找”文件的含义，并使用 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

score 2 · Accepted Answer

编辑：对不起，前面的例子不起作用。

这似乎是 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); 
}

请注意，我在这里切换了模式和查找的含义。图案就是图案。如果您想打印图案而不是线条，那很好，但我不会更改它们的名称。

score 2 · Accepted Answer

使用哈希表或集合（取决于您的语言）以全小写形式存储字典。对于每一行，将行拆分为基于非字母字符的单词数组。根据这些单词构建一个微型哈希表，转换为小写，以消除重复。遍历该微型哈希表中的每个单词，验证它是否存在于您的字典哈希表中。如果存在，则打印该单词和整行。

这是 Perl 中的一个实现。

#! /usr/bin/perl

my $dictFile=$ARGV[0];
my $srchFile=$ARGV[1];
(-f $dictFile and -f $srchFile) or die "Usage: $0 dictFile srchFile";

# Load dictionary into hash table
my %dict=();
open($df, "<$dictFile") or die "Cannot open $dictFile";
while (<$df>) {
  chomp;
  $dict{lc($_)}=1;
}

# Search file for your dictionary words
open($sf, "<$srchFile") or die "Cannot open $srchFile";
my $lineNo=0;
while ($line=<$sf>) {
  $lineNo++;
  chomp($line);
  my %words=();
  my @sentence=split(/[^a-zA-ZÀ-ÿ0-9]+/, $line);
  foreach $word (@sentence) {
    $words{lc($word)}=1;
  }
  while ( my ($key) = each(%words) ) {
    if ($dict{$key}) {
      print "$lineNo, $key, $line\n";
    }
  }
}

模式.txt

The sun is shining!
It is a beautiful day!

查找.txt

Rain
Sun
Cloud
Beautiful
Shining

$ ./deepfind lookup.txt pattern.txt

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

编辑：根据您的评论，这是在“句子”中定义“单词”集的另一种方法。这准备了与字典中找到的任何序列的长度相匹配的所有可行序列。

#! /usr/bin/perl
my $dictFile=$ARGV[0];
my $srchFile=$ARGV[1];
(-f $dictFile and -f $srchFile) or die "Usage: $0 dictFile srchFile";
# Load sequence dictionary into hash table
my %dict=();
my %sizes=();
open($df, "<$dictFile") or die "Cannot open $dictFile";
while (<$df>) {
  chomp;
  $dict{lc($_)}=1;
  $sizes{length($_)}=1;
}

# Search file for known sequences
open($sf, "<$srchFile") or die "Cannot open $srchFile";
my $lineNo=0;
while ($line=<$sf>) {
  $lineNo++;
  chomp($line);
  # Populate a hash table with every unique sequence that could be matched
  my %sequences=();
  while ( my ($size) = each(%sizes) ) {
    for (my $i=0; $i <= length($line)-$size; $i++) {
      $sequences{substr($line,$i,$size)}=1;
    }
  }
  # Compare each sequence with the dictionary of sequences.
  while ( my ($sequence) = each(%sequences) ) {
    if ($dict{$sequence}) {
      print "$lineNo, $sequence, $line\n";
    }
  }
}

score 0 · Accepted Answer

使用后缀数组或后缀数组怎么样？您可以在此处找到一个具有坚持使用类似 grep 选项的优势的实现，尽管我从未使用过它，也无法证明它的效率和易用性。

后缀树/数组需要预处理将在 O(n) 到 O(n log n) 时间内搜索的文件（n 是查找文件的长度），并且后缀树/数组本身将比原始文件（常数因子），但有磁盘绑定算法，它们经常用于搜索整个人类基因组（几 GB）。然后在文件中搜索字符串只需要 O(m) 时间，其中 m 是字符串的长度，这比 grep (O(n log m)?) 快得多。由于您似乎会多次搜索同一个文件，因此对后缀树/数组所需的预处理步骤的投资可能是值得的。

score 0 · Accepted Answer

结合上面提到的一些想法，我提出了一个两遍系统，使用grep和合并结果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 脚本。它将查找读入缓冲区，并通过模式。

脚本.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!

score -1 · Accepted Answer

这可能不会更快，但您可以尝试：

for i in `cat lookup_file`; 
  do  
    tmpv=`grep -i ${i} pattern_file | xargs echo ${i},`; 
    echo ${tmpv} | sed '/^$/d'; 
done

bash - 是否有 grep 的逆：在长模式中找到短线？

9 回答 9

Related

Reference