Shell Programming and Scripting

I am trying to solve the issue of identifying names from the initials which are prefixed to it and are all conjoined.
The prefixing can be of three major types.
A single Letter prefixed: jsmith
Two letters prefixed:jksmith
Three letters prefixed:jkdsmith

The algorithm which I had in mind was something like this:
BASIC PREMISE:
The data has both correct names and also garbage where intial letters which are not part of the name are appended to the name.
The appending is of the 3 types mentioned above
BASIC INPUTS
For each type, there is a NGram look-up:
uni-,di-, tri-
There is a basic dictionary which contains all the possible valid combos
HOW TO SET ABOUT IT.
The program takes the word from the input file as input and checks against the dictionary.
If the word is found , it goes on to the next
If word not found, then it checks against the digram list, strips off the digram and validates whether the residue exists in the dictionary
If residue maps to dictionary, show the input as PREF.+ word
If word not found, flag it as a possible error.
Bucketing would be the ideal solution, starting off with the largest set of trigrams and then going down to the unigram.

To solve the issue I wrote a PERL program with help from a colleague which is appended below:

Code:

#!/usr/bin/perl
# -d <dictionary> -p <prefixes [=digrams]>
use Getopt::Std;
getopts('d:p:');
open DICT, $opt_d;
@dict = <DICT>;
open PREF, $opt_p;
@pref = <PREF>;
while (<>) {
    /^(..)(.*)$/;
    ($p, $r) = ($1, $2);
    if (grep /$p/, @pref and grep /$r/, @dict) { print "$p + $r\n" }
}

DICT is the dictionary and PREF is the N-Gram file
However my main issue is that any given time, the program can handle only one issue say a digram or a trigram (by adding one more.)
What I need is a program which could start off with the trigrams, take on the digrams and finally identify the Unigrams, in other words bucketing the data and sieving through it.

A small database is given below:
DICTIONARY:

Code:

smith
green
brown
black

NGrams

Code:

Unigram:j,k,d
Digrams:jd,jl,jk
Trigrams:jdm,jlk,jkv

Testdatabase:

Code:

jsmith
kbrown
jdblack
jlgreen
jdmsmith
jlkbrown
jkvblack

Expected result:

Code:

j+smith
k+brown
jd+black
jl+green
jdm+smith
jlk+brown
jkv+black

This would be possible only if the dictionary is checked each time and the residue is flagged as such (as I have shown in the algo)
The script works perfectly for a single type but I don't know how to bucket the data using multiple N-Grams at one shot. Does PERL support such an action of chaining and filtering. This is too complex and beyond my scripting abilities.

Any solutions would be highly appreciated. Many thanks in anticipation

Don't know about using perl, but this is pretty easy in awk:

Code:

awk -F',' 'FNR==1{F++}
F==1{D[$0]++}
F==2{for(i=1;i<=NF;i++) G[$i]++}
F==3{for(i=3;i>0;i--)
   if(substr($0,1,i) in G && substr($0,i+1) in D) {
      print substr($0,1,i) "+" substr($0,i+1);
      next;
   }
   print "!!" $0;
}' DICTIONARY NGrams Testdatabase

Many thanks. It works just fine. Quick and rapid. Took hardly one second to run through a dictionary of around 200,000 lakh words and an NGram list of around 200

---------- Post updated at 11:26 PM ---------- Previous update was at 11:09 PM ----------

Hello,
On testing the script. Found one small "bug" Let us suppose that the dictionary contains both smith and jsmith and that j is also listed as an NGram. When jsmith is given to the testdatabase, it should pass, instead it is shown as j+smith. I suppose this because the largest string is not checked. I don't know whether this hypothesis is correct.
Otherwise the script runs like a charm.
Many thanks

Yep didn't consider that case, this update checks for it:

Code:

awk -F',' 'FNR==1{F++}
F==1{D[$0]++}
F==2{for(i=1;i<=NF;i++) G[$i]++}
F==3{if($0 in D) print $0; else {
   for(i=3;i>0;i--)
   if(substr($0,1,i) in G && substr($0,i+1) in D) {
      print substr($0,1,i) "+" substr($0,i+1);
      next;
   }
   print "!!" $0;
   }
}' DICTIONARY NGrams Testdatabase

Works great and gives the right output. Many thanks for a fabulous script.