Login or Register to Ask a Question and Join Our Community


Shell Programming and Scripting

Parsing the longest match substring

Login to Discuss or Reply to this Discussion in Our Community

 
Thread Tools Search this Thread
Top Forums Shell Programming and Scripting Parsing the longest match substring
# 1  
Old 03-01-2017
Parsing the longest match substring
Hello gurus,

I have a database of possible primary signal strings

Code:
pp22
pt22dx
pp22dx
jty2234

Also I have a list of scrambled signals which has a shorter string and a longer string separated by // (double slash ). Always the shorter string of a scrambled signal will have the primary signal as a substring and I need to parse out the longest possible primary signal from it.


So if my list of scrambled signals are

Code:
())[pt22dx]dfdfs//(dsgfspp22dx/pg22dx)-signal
(\\b-[pt22dx]dfdfs/(dsgfspp22dx//[(\pp22dx)-@@----B-@--
signal-ef##$@pp22//[[((dsgfspp22dx/pg22dx)-signal[(\pp22dx)-@@----B-@--

My desired output is

Code:
())[pt22dx]df/(dsgfspp22dx/pg22dx)-signal                                                                    pt22dx
(\\b-[pt22dx]dfdfs/(dsgfspp22dx//[(\pp22dx)-@@----B-@--                                            pp22dx
signal-ef##$@pp22//[[((dsgfspp22dx/pg22dx)-signal[(\pp22dx)-@@----B-@--                pp22

Note that the primary signal in second row is pp22dx and not pp22 since pp22dx is the longest possible match.


My working solution is as follows, this returns every match and not the longest. Also I believe there could be a more efficient way.

Code:
awk -F"//"  'NR==FNR{primary[$1];next} { short=length($1)>length($2)? $2:$1 } { for( ps in primary) { if(short~ps) { print $0,ps }}}' primary scrambled

())[pt22dx]dfdfs//(dsgfspp22dx/pg22dx)-signal pt22dx
(\\b-[pt22dx]dfdfs/(dsgfspp22dx//[(\pp22dx)-@@----B-@-- pp22dx
(\\b-[pt22dx]dfdfs/(dsgfspp22dx//[(\pp22dx)-@@----B-@-- pp22
signal-ef##$@pp22//[[((dsgfspp22dx/pg22dx)-signal[(\pp22dx)-@@----B-@-- pp22


Please assist.
Last edited by senhia83; 03-01-2017 at 09:25 PM..
# 2  
Old 03-02-2017
You state that the desired match for the input:
Code:
(\\b-[pt22dx]dfdfs/(dsgfspp22dx//[(\pp22dx)-@@----B-@--

is pp22dx instead of pp22 because pp22dx is longer. But why isn't pt22dx just as valid as pp22dx? (Both appear in the input file named primary, both are the same length, and pt22dx appears on that line of input before pp22dx.)

Assuming either input is allowed, you could try something like:
Code:
awk -F// -v OFS="\t\t" '
FNR == NR {
	if((l = length($0)) in pat) {
		pat[l] = pat[l] "|" $0
		next
	}
	pat[l] = $0
	for(i = 1; i <= nl && lengths[i] > l; i++)
		new[i] = lengths[i]
	new[i] = l
	for(; i <= nl; i++)
		new[i + 1] = lengths[i]
	nl++
	for(i = 1; i <= nl; i++)
		lengths[i] = new[i]
	next
}
{	for(i = 1; i <= nl; i++)
		if(match($1, pat[lengths[i]])) {
			print $0, substr($1, RSTART, RLENGTH)
			next
		}
	print $0, "No match"
}' primary scrambled

which with your sample inputs produces the output:
Code:
())[pt22dx]dfdfs//(dsgfspp22dx/pg22dx)-signal		pt22dx
(\\b-[pt22dx]dfdfs/(dsgfspp22dx//[(\pp22dx)-@@----B-@--		pt22dx
signal-ef##$@pp22//[[((dsgfspp22dx/pg22dx)-signal[(\pp22dx)-@@----B-@--		pp22

The above code just uses awk features defined by the standards. If someone wants to try this on a Solaris/SunOS system, change awk to /usr/pg4/bin/awk or nawk. Sorting the lengths array might be done more efficiently with built-in functions in some versions of awk.
This User Gave Thanks to Don Cragun For This Post:
senhia83
# 3  
Old 03-02-2017
Stealing from and simplifying Don Cragun's approach - try
Code:
awk -F// -v OFS="\t\t" '
FNR == NR       {l = length($0)
                 pat[l] = pat[l] DL[l] $0
                 DL[l]  = "|"
                 MX = l>MX?l:MX
                 next
                }

                {for (i=MX; i>0; i--)   {if (pat[i] && match($1, pat[i]))       {print $0, substr($1, RSTART, RLENGTH)
                                                                                 next
                                                                                }
                                        }
                 print $0, "No match"
                }
' primary scrambled

This User Gave Thanks to RudiC For This Post:
senhia83
# 4  
Old 03-02-2017
Hi Don and Rudi,

I am highlighting the part from my original request

Quote:
Also I have a list of scrambled signals which has a shorter string and a longer string separated by // (double slash ). Always the shorter string of a scrambled signal will have the primary signal as a substring and I need to parse out the longest possible primary signal from it.


for this string

Code:
(\\b-[pt22dx]dfdfs/(dsgfspp22dx//[(\pp22dx)-@@----B-@--

only the shorter of the two columns (compared by length separated by //) will have the primary signal, in this case [(\pp22dx)-@@----B-@-- , so the answer is pp22dx.
# 5  
Old 03-02-2017
Are you saying that what you really want is the longest string that matches an entire line in the file named primary that appears on both sides of the // on each line in the file named scrambled?

To determine whether the time my script spends keeping the lengths[] array in order is worth the effort, how many lines are typically in each of your two real input files?
# 6  
Old 03-02-2017
Quote:
Originally Posted by Don Cragun
Are you saying that what you really want is the longest string that matches an entire line in the file named primary that appears on both sides of the // on each line in the file named scrambled?

To determine whether the time my script spends keeping the lengths[] array in order is worth the effort, how many lines are typically in each of your two real input files?
Not the entire the line, only the shorter split (separated by //) will have the primary signal.

In my original code I use

{ short=length($1)>length($2)? $2:$1 } to determine which of the two fields is shorter in length and just search that for the primary signal if(short~ps).

There are 10k primary signals and 400k scrambled signals at this point. The scrambled signals will be more (~100k per year) as we collect more data.
# 7  
Old 03-02-2017
With your sample data, the following seems to do what you want fairly efficiently:
Code:
awk -F// -v OFS="\t\t" '
BEGIN {	M = 0
	m = 32000
}
FNR == NR {
	if((l = length($0)) in pat) {
		pat[l] = pat[l] "|" $0
		#printf("appending pattern: pat[%d]=\"%s\"\n", l, pat[l])
	} else {pat[l] = $0
		#printf("adding pattern: pat[%d]=\"%s\"\n", l, pat[l])
		if(l > M)
			M = l
		if(l < m)
			m = l
	}
	next
}
#FNR == 1 {
#	for(i = M; i >= m; i--)
#		if(i in pat)
#			printf("pat[%d]=\"%s\"\n", i, pat[i])
#}
{	short = length($1) < length($2) ? 1 : 2
	for(i = M; i >= m; i--)
		if(i in pat && match($short, pat[i])) {
			print $0, substr($short, RSTART, RLENGTH)
			next
		}
	print $0, "No match"
}' primary scrambled

but I don't have any good way to test how this might work if you have EREs with thousands of patterns to be matched as alternatives in a single ERE. With your sample inputs, it produces:
Code:
())[pt22dx]dfdfs//(dsgfspp22dx/pg22dx)-signal		pt22dx
(\\b-[pt22dx]dfdfs/(dsgfspp22dx//[(\pp22dx)-@@----B-@--		pp22dx
signal-ef##$@pp22//[[((dsgfspp22dx/pg22dx)-signal[(\pp22dx)-@@----B-@--		pp22

as its output (which I think meets your requirements).

PS: Depending on the distribution of the lengths of your patterns, you might want to try the code I used in post #2 in this thread to sort the lengths and avoid processing lengths that don't exist in your data. I assume you won't have any problem merging the code from these two suggestions to get what you need.
Last edited by Don Cragun; 03-02-2017 at 11:09 PM.. Reason: Add PS.
This User Gave Thanks to Don Cragun For This Post:
senhia83
Login or Register to Ask a Question

Previous Thread | Next Thread

10 More Discussions You Might Find Interesting

1. UNIX for Beginners Questions & Answers

Replace substring by longest string in common field (awk)

Hi, Let's say I have a pipe-separated input like so: name_10|A|BCCC|cat_1 name_11|B|DE|cat_2 name_10|A|BC|cat_3 name_11|B|DEEEEEE|cat_4 Using awk, for records with common field 2, I am trying to replace all the shortest substrings by the longest string in field 3. In order to get the... (5 Replies)
Discussion started by: beca123456
5 Replies

2. Shell Programming and Scripting

Match text to lines in a file, iterate backwards until text or text substring matches, print to file

hi all, trying this using shell/bash with sed/awk/grep I have two files, one containing one column, the other containing multiple columns (comma delimited). file1.txt abc12345 def12345 ghi54321 ... file2.txt abc1,text1,texta abc,text2,textb def123,text3,textc gh,text4,textd... (6 Replies)
Discussion started by: shogun1970
6 Replies

3. Shell Programming and Scripting

Match substring from a column of the second file

I want to merge the lines by matching substring of the first file with first column of the second file. file1: S00739A_ACAGTG_L001_R1.fq.gz S00739A_ACAGTG_L001_R2.fq.gz S00739B_GCCAAT_L001_R1.fq.gz S00739B_GCCAAT_L001_R2.fq.gz S00739D_GTGAAA_L001_R1.fq.gz S00739D_GTGAAA_L001_R2.fq.gz... (14 Replies)
Discussion started by: yifangt
14 Replies

4. UNIX for Dummies Questions & Answers

Deleting files based on Substring match

In folder there are files (eg ABS_18APR2012_XYZ.csv DSE_17APR2012_ABE.csv) . My requirement is to delete all the files except today's timestamp I tried doing this to list all the files not having today's date timestamp #!/bin/ksh DATE=`date +"%d%h%Y"` DIR=/data/rfs/... (9 Replies)
Discussion started by: manushi88
9 Replies

5. Shell Programming and Scripting

Longest word in a file

I am trying to write a command on just one line, i.e seperated by ';' and '|' etc, that finds the number of characters in the longest word of a file, preferably using the 'tr' and 'wc' commands. i no that wc shows the number of lines words and characters in a file but im not sure how to use it... (5 Replies)
Discussion started by: scotty85
5 Replies

6. Shell Programming and Scripting

Substring match

Hi, I want to find a file / directory with the name xxxxCELLxxx in the given path. The CELL is can be either in a UPPER or lower case. Thanks (4 Replies)
Discussion started by: youknowme
4 Replies

7. Shell Programming and Scripting

shell script: longest match from right?

Return the position of matched string from right, awk match can do from left only. e.g return pos 7 for search string "service" from "AA-service" or return the matched string "service", then caculate the string length. Thanks!. (3 Replies)
Discussion started by: honglus
3 Replies

8. Shell Programming and Scripting

Awk Array doesnt match for substring

Awk Array doesnt match for substring nawk -F"," 'FNR==NR{a=$2 OFS $3;next} a{print $1,$2,a}' OFS="," file1 file2 I want cluster3 in file1 to match with cluster3int in file2 output getting: Output required: Help is appreciated (8 Replies)
Discussion started by: pinnacle
8 Replies

9. Shell Programming and Scripting

Parsing file to match strings

I have a file with the following format 12g data/datasets/cct 8g data/dataset/cct 10 g data/two 5g data/something_different 10g something_different 5g data/two is there a way to loop through this... (1 Reply)
Discussion started by: yawalias
1 Replies

10. Shell Programming and Scripting

Finding longest common substring among filenames

I will be performing a task on several directories, each containing a large number of files (2500+) that follow a regular naming convention: YYYY_MM_DD_XX.foo_bar.A.B.some_different_stuff.EXT What I would like to do is automatically discover the part of the filenames that are common to all... (1 Reply)
Discussion started by: cmcnorgan
1 Replies
Login or Register to Ask a Question