Shell Programming and Scripting

Hi,

I am stuck with a problem, will be thankful for your guidance and help.

I have two files. Each line is a group of words with first word as group Id. eg. 'gp1' in File1 and 'grp1' in File2.

Code:

 
<File1> 
gp1 : xyz xys3 syt2 ssx itt kty
gp2 : syt2 kgk iti op2 
gp3 : ppy yt5 itt sky utw yry

Code:

 
<File2>
grp1 : yt5 utw
grp2 : iti op2 kty
grp3 : kty xys3 syt2 
grp4 : utw ppy
grp5 : xyz iti yt5
grp6 : ssx xyz

I want to find out which (complete) group of words of file2 occur in group of words in File1. So, each line of file2 is searched against each line of file1.

The output file should give which groups of file2 were found in which groups of file1.

Code:

 
<OutFile>
gp1 : grp3 grp6
gp2 : None
gp3 : grp1 grp4

Think of the files as database tables. You want to do a join, where you match key columns of table a to table b, creating a new view, virtual table c. However, your files have multiple keys in each line, variable numbers of keys, too. To be relational, you want to unstack the lines and compare column 2 to column 2. The file 2 query is only satisfied with N (2 or 3) matches. So, the count for each grep can be a third relation/table.

Often, the solution so such joins for smaller files is to load one file into content-addressable/associative arrays or vectors in perl, awk, ksh or bash, and then examine the other file field by field against the arrays.

For large data sets, some sort of sort-merge finds all matches, and another sort-merge allows the matches to be checked to see if there are enough matches to make a hit. This is a vary old EDP pragma, but very robust and efficient for large sets.

Thanks DGPickett for your suggestions. I tried something with perl, comparing 2 arrays in some way but it didn't work.

Please help with other suggestions.

What did you try? In what way did it "not work"?

One approach is to compare each item of file2 with every line of file1...and grep won't work unless each line of file2 was matched in file1 exactly and this isnt the case. Take line "grp1 : yt5 utw" of file2...these items are found in "gp3 : ppy yt5 itt sky utw yry" of file1 but they are not side by side so grep will fail. That is why it is better to pick each item in file2 and see if it is contained in a line of file1. If all the items match then that line of file2 is contained in file1.

File 1 should be put in arrays, and file 2 examined with it, or vice versa. How you strucutre the arrays depends on whether the words are unique in the file you store. This is because when you address an array with a value, it returns only one string. If there is uniqueness, that helps. One way to deal with not unique is to add a dimension to hold values 1 to N, and add a parallel vector to hold N.

File 2 not only has (unique on line) words but also the word count, which is needed as a minimum word count to achieve match, and which might go in a parallel array. However, you need to structure the array so the address is the question and the returned value is the answer, not vice versa, so it may not be unique that way.

The sort merge is to build three 2-column files: file 1 key to each one file 1 word, file 2 key to each file 2 word, and file 2 key to word count. Sort file 1 and 2 by word and merge the sorted output to build a three column file: file 2 key, file 1 key, word, sort that by file 2 key and merge with third file, seeing if the number of matched words is right. In some respects, this is simpler than the array solution, where you need to deal with unique and which field is the key to which array. This is robust against all file sizes, duplicates. If there are duplicates, sort can remove them, or the merge, knowing some files are not unique, can deal with that. You want to avoid the cartesian join problem, where the N records in one file for a key field match M records on the other file, for NxM output records. If this is the case, sort into flat files and use 'join' to do the walking.

Crude and lewd is many passes: For each line of file 2, for each line of file 1 for each word in file 1 line for each word of file 2 line if match set indicator and break, etc. File 2 gets read file 1 lines times.

Not sure how this solution is going to pan out because sorting file1 and file2 still wont lineup the records for a match...unless you provide the script to show how it works as i am unable to visualize it.

Here's my solution which stores file1 and file2 in arrays and matches items of file2 array against items of file1 array...incrementing a counter so no of matches equals no of items in each record of file2.

Code:

awk '{
   FS = " : "
   if (FILENAME == "file1") x[$1] = $2
   if (FILENAME == "file2") y[$1] = $2
} END {
   for (i in x) {
      for (j in y) {
         n = split(y[j], a, " ")
         for (p = 1; p <= n; p++)
            s += gsub(a[p], a[p], x[i])
         if (n == s) u[i] = u[i] ? u[i]" "j : i FS j
         s = 0
      }
      if (!u[i]) u[i] = i" : None"
   }
   for (i in u) print u[i]
}' file1 file2