4

Given a small group of words (for concreteness, say 3), but more generally n, I want to search a file for occurrences of two of those words being close to each other. By close, let's say that the two words are at most k characters apart, where k is some constant.

Rationale: I'm looking for specific emails in my INBOX (/var/spool/mail/username), with specific keywords. I'm not sure how the key words occur. However, one word is relatively common. Two words close together is less common.

A specific motivating example:

"aluminium", "luggage", "storage".

In this case, I'm searching for emails about a luggage box.

A solution in terms of n and k would be best.

Some indication of how to apply this to multiple files would be helpful.

And I don't care what language the solution is in.

4
  • 1
    Wouldn't it be simpler to search for messages that contain all three words instead of just looking for them near each other? Why don't you show us an example of the format so we can figure out how to define a message and the look for all three words within one. – terdon Dec 17 '17 at 16:22
  • @terdon I'm only looking for a two word match out of a larger group of words. And the INBOX is one file. I suppose one could check for message separators, but that might be more work. – Faheem Mitha Dec 17 '17 at 16:36
  • Not really more work, almost certainly simpler, and more likely to find what you want. – terdon Dec 17 '17 at 16:45
  • grepmail is a perl script to search mailboxes. -E takes sophisticated patterns. Or you could use it to "subclass" the mails word by word. – meuh Dec 17 '17 at 20:39
1

You might consider:

1) glark, which has an option:
   ( expr1 --and=NUM expr2 )
   Match both of the two expressions, within NUM lines of each other.

2) bool, with expressions like:
   bool -O0 -C0 -D5 -b "two near three"

3) peg, which accepts options like:
   peg "/x/ and near(sub { /y/ or /Y/ }, 5)"

The code for glark is at https://github.com/jpace/glark and might be in some repositories.

Some details for bool and peg:

bool    print context matching a boolean expression (man)
Path    : ~/executable/bool
Version : 0.2.1
Type    : ELF 64-bit LSB executable, x86-64, version 1 (SYS ...)
Help    : probably available with -h,--help
Home    : https://www.gnu.org/software/bool/ (doc)

peg     Perl version of grep, q.v. (what)
Path    : ~/bin/peg
Version : 3.10
Length  : 4749 lines
Type    : Perl script, ASCII text executable
Shebang : #!/usr/bin/env perl
Repo    : Debian 8.9 (jessie) 
Home    : http://piumarta.com/software/peg/ (pm)
Home    : http://www.cpan.org/authors/id/A/AD/ADAVIES/peg-3.10 (doc)

Best wishes ... cheers, drl

1
  • 1
    glark looks like a great tool, thanks for making my search for such a tool that can search across a short number of context lines quick. You might be able to install glark with gem install glark (Ruby has to be installed); try that before downloading the source. – eewanco Sep 6 '19 at 14:11
0

Start with a stemming tool like https://linux.die.net/man/1/hunspell then use regex https://linux.die.net/man/1/grep then use wc sort and unique to sort by how close the words are.

pseudo-bash;

WORDS=$1
HAYSTACK=/var/mail

STEMS=$(hunspell --stem $WORDS)
REGEX=$(echo $STEMS | perl -pe 's/ /.*/g')
while read MATCH ; do
    FILE=$(echo $MATCH | cut -d : 1)
    COUNT=$(echo $MATCH | cut -d : 2 | perl -pe 's/.*('"$REGEXX"').*/$1/g' | wc -c)
    echo $COUNT\t$FILE
done < <(grep -rP "$REGEX" $HAYSTACK) | \
sort -nr

If you want it faster you can use https://linux.die.net/man/1/locate with regex to limit space between words

a.{1,50}b
1
  • Can you give an example of how this might work? – roaima Dec 17 '17 at 17:19
0

I like the idea of grepmail (and at our shop we coded a utility called rapgrep, require all patterns, for the general case).

A more specific answer in terms of character distance is demonstrated with this snippet, looking for words: country, men, time:

# Utility functions: print-as-echo, print-line-with-visual-space.
pe() { for _i;do printf "%s" "$_i";done; printf "\n"; }
pl() { pe;pe "-----" ;pe "$*"; }
pl " Input data file $FILE:"
head $FILE

pl " Results, egrep:"
egrep 'time|men|country' $FILE

pl " Results, egrep, with byte offset:"
egrep -b 'time|men|country' $FILE

pl " Results, egrep, with byte offset, matches only:"
egrep -o -b 'time|men|country' $FILE |
tee t1

pl " Looking for minimum distance between all pairs:"

awk -F":" '
  { a[$2] = $1  # Compare every item to the new item
    for ( b in a ) {
      for ( c in a ) {
      # print " Working on b = ",b," c = ",c
        if ( b != c ) {
        v0 = a[c]-a[b]
        v1 = v0 < 0 ? -v0 : v0  # convert to > 0
        v2 = (b < c) ? b " " c : c " " b  # trivial sort of names
        print v1, v2
      }
    }
    }
  }

' t1 |
datamash -t" " -s --group 2,3 min 1 

producing:

-----
 Input data file data1:
Now is the time
for all good men
to come to the aid
of their country.

-----
 Results, egrep:
Now is the time
for all good men
of their country.

-----
 Results, egrep, with byte offset:
0:Now is the time
16:for all good men
52:of their country.

-----
 Results, egrep, with byte offset, matches only:
11:time
29:men
61:country

-----
 Looking for minimum distance between all pairs:
country men 32
country time 50
men time 18

and with a slightly more complicated file with multiple occurrences of some words:

-----
 Input data file data2:
Now is the time men
for all good men
to come to the aid
of their men country.

-----
 Results, egrep:
Now is the time men
for all good men
of their men country.

-----
 Results, egrep, with byte offset:
0:Now is the time men
20:for all good men
56:of their men country.

-----
 Results, egrep, with byte offset, matches only:
11:time
16:men
33:men
65:men
69:country

-----
 Looking for minimum distance between all pairs:
country men 4
country time 58
men time 5

This makes use of the byte count option in GNU grep, the awk program calculates all distances among the word pairs, finally datamash sorts, groups, and chooses the minimum distances.

This could be fairly easily parameterized to allow words on a command line, as well as the allowable distance. See file t1 for the form on the input data to datamash from the awk program.

Run on a system like:

OS, ker|rel, machine: Linux, 3.16.0-4-amd64, x86_64
Distribution        : Debian 8.9 (jessie) 
bash GNU bash 4.3.30
grep (GNU grep) 2.20
awk GNU Awk 4.1.1, API: 1.1 (GNU MPFR 3.1.2-p3, GNU MP 6.0.0)
datamash (GNU datamash) 1.2

Best wishes ... cheers, drl

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.