Is there an inverse of grep: finding short lines in long patterns?

Question

Where grep finds a short pattern from a pattern file in long lines of a look-up file, I need a tool that would allow me to extract short lines of a lookup file that can be found within a longer pattern.

In other words, given the works of Shakespeare with one sentence per line and say a French dictionary, I want to find which French words are found in which line of Shakespeare, allowing for the detection of the fact that a line of Shakespeare may contain more than one French word and that a French word may appear in more than one line of Shakespeare.

For example:

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

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

What I would like is

function file pattern

To give both the line that is found in the longer pattern and the longer pattern itself separated by a coma, with multiple matches being detected.

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

Currently, I loop over the whole lookup file line by line with grep:

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

This is incredibly slow! My lookup_file contains over 50 000 lines while my pattern_file contains 500. Where as using grep to find an even shorter pattern in my lookup_file takes seconds, a single pass using my loop approach takes day/weeks.

Solutions in any language would be appreciated.

Somewhat related to
Very slow loop using grep or fgrep on large datasets
Is Perl faster than bash?

The solution needs to be compatible with GB size loopup and pattern files.

Answer 1

You can use the -f switch to use a "pattern file" in grep:

egrep -i -f lookup_file pattern_file >> result_file

This will be faster because grep compiles lookup_file into a single state machine that checks all matches at the same time, rather than checking each pattern against each line separately.

If your lookup_file consists of text and not regular expressions, you can use fgrep and it will be even faster.

To get your ideal output you can use the -n and -o switches and you get a list of patterns that match each line.

Answer 2

Since you indicated any language is acceptable I will post a completely different approach: with shell scripting you will never beat the performance of in-memory tools or databases. If you have a lot of data you should use databases which are meant for these kind of operations and it scales much better.

So here is a simple example using sqlite (www.sqlite.org).

You need to import your patterns and data into tables, like this for example (you can script this if you want):

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;

Then run a select query to get your desired output:

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;

If you save the first snippet as data.sql and the second one as query.sql you use this on the command line:

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

This gives you:

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

which is what you want I believe. To make it more fancy use your favourite more advanced tool with a database library. I would choose python for this.

Suggestions for further improvement:

• use regex instead of like to filter whole words (i.e. pattern "sun" matches "sun" but not "sunny"),

• import utility,

• output formatting,

• query optimization.

Answer 3

Your solution may actually be slow because it creates 50.000 processes all reading the 500 lines pattern_file.

Another "pure bash & unix utils" solution could be to let grep do what it can do best and just match the output against your pattern_file.

So use grep to find matching lines and the parts that actually do match.

I use word matching here, which can be turned off by removing the -w switch in the grep line and to get initial behavior as described in your example.

The output is not yet redirected to result_file.csv.. which is easy to add later 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>&-

result is

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

for the example given. Attention: the match is now the exact match where the case is preserved. So this does not results in Sun, ... but in sun, ....

The result is a script which reads pattern_files once using a grep which in the best case reads pattern_file and lookup_file once - depending on the actual implementation. It only starts two additional processes: grep and sed. (if needed, sed can be replaced by some bash substitution within the outer loop)

I did not try it with 50.000 line lookup_file and 500 lines pattern_file though. But I think it may be as fast as grep can be.

As long as grep can keep the lookup_file in memory it may be reasonable fast. (Who knows)

No matter if it solves your problem I would be interested how it performs compared to your initial script since I do lack nice test files.

If grep -f lookup_file uses too much memory (as you mentioned in a comment before) it may be a solution to split it in portions that actually do fit into memory and run the script more then once or use more then one machine, run all parts on those machines and just collect and concatenate the results. As long as the lookup_files do not contain dupes, you can just concatenate the results without checking for dupes. If sorting matters, You can sort all single results and then merge them quiet fast using sort -m.

Splitting up the lookup_file should not affect runtimes dramatically as long as you split the lookup_file only once and rerun the script, since your pattern_file may be small enough with its 500 lines to stay in memory cache anyway!? The same may be true for the lookup_file if you use more then one machine - its parts may just stay in memory on every machine.

EDIT:

As pointed out in my comment this will not work for overlapping files out of the box since grep -f seems to return only the longest match and will not rematch so if lookup_file contains

Sun
Shining
is
S

the result will be

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

and not

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

So all the matching s (it matches three times) are missing.

In fact this is another issue with this solution: If a string is found twice it will be matched twice and identical lines will be returned, which can be removed by uniq.

Possible workaround: Split the lookup_file by string length of search strings. Which will decrease maxmimum memory needed for a run of grep but also slow down the whole thing a little bit. But: You can then search in parallel (and may want to check greps --mmap option if doing that on the same server).

Answer 4

You need to swap the meanings of the "pattern" and "lookup" files, and use grep's -o switch.

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

$ cat lookup 
Rain
Sun
Cloud
Beautiful

$ grep -iof lookup patterns 
sun
beautiful

Answer 5

EDIT: Sorry, previous example did not work.

This seems like a perfect match for perl. Start with

#!/usr/bin/perl

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

my @l = <LOOKUP>;

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

Note that I've switched the meaning of pattern and lookup here. A pattern is a pattern. If you want to print patterns instead of lines, that's fine, but I wouldn't change their names.

Answer 6

Use a hash table or set (depending on your language) to store the dictionary in all lower-case. For each line, split the line into an array of words based on non-alpha characters. Build a miniature hash table based on those words, converted to lower case, to eliminate duplicates. Iterate through each word in that miniature hash table, verifying whether it exists in your dictionary hash table. If it exists, print the word and the entire line.

Here's an implementation of this in 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";
    }
  }
}

pattern.txt

The sun is shining!
It is a beautiful day!

lookup.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!

EDIT: Based on your comments, here's an alternate approach to defining the set of "words" in the "sentence". This prepares all viable sequences matching the length of any sequence found in the dictionary.

#! /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";
    }
  }
}

Answer 7

How about using something like a suffix array or a suffix array? You can find an implementation that has the advantage of sticking to grep-like options here, though I've never used it and can't attest to its efficiency and ease-of-use.

Suffix trees/arrays need to preprocess the file that will be search in O(n) to O(n log n) time (n being the length of the lookup file), and the suffix tree/array itself will be several times larger than the original file (constant factor), but there are disk-bound algorithms, and they get used for searching entire human genomes quite often (which are a few GBs). Searching for a string in the file then only takes O(m) time, where m is the length of the string, which is much faster than, say, grep (O(n log m)?). Since it seems you'll be searching the same file very many times, the investment in the preprocessing step that suffix trees/arrays require might be worth it.

Answer 8

Combining some of the ideas mentioned above, I've come up with a two-pass system using grep and merging the results using join as follows:

patterns

The sun is shining!
It is a beautiful day!

lookup

Rain
Sun
Cloud
Beautiful
Is

script

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/:/,/'

generates the following results

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

If you want an output of lookup match and pattern comma-delimited, here's a small python 2.x script that would work. It reads the lookups into a buffer, and does one pass through the patterns.

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),

running python script.py lookup patterns yields:

Sun,The sun is shining!
Is,The sun is shining!
Beautiful,It is a beautiful day!
Is,It is a beautiful day!

Answer 9

This may not be faster, but you could try :

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