Parsing the longest match substring Post: 302992875

Sponsored Content

Top Forums Shell Programming and Scripting Parsing the longest match substring Post 302992875 by Don Cragun on Thursday 2nd of March 2017 09:42:42 PM

03-02-2017

Registered User

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:

Don Cragun

View Public Profile for Don Cragun

Find all posts by Don Cragun

10 More Discussions You Might Find Interesting

1. 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...

2. 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...

3. 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

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

5. 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

6. 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...

7. 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/...

8. 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...

9. 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...

10. 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...

LEARN ABOUT NETBSD

quiz

QUIZ(6) 							 BSD Games Manual							   QUIZ(6)

NAME

     quiz -- random knowledge tests

SYNOPSIS

     quiz [-t] [-i file] [question answer]

DESCRIPTION

     The quiz utility tests your knowledge of random facts.  It has a database of subjects from which you can choose.  With no arguments, quiz
     displays the list of available subjects.

     The options are as follows:

     -t      Use tutorial mode, in which questions are repeated later if you didn't get them right the first time, and new questions are presented
	     less frequently to help you learn the older ones.

     -i      Specify an alternative index file.

     Subjects are divided into categories.  You can pick any two categories from the same subject.  quiz will ask questions from the first cate-
     gory and it expects answers from the second category.  For example, the command ``quiz victim killer'' asks questions which are the names of
     victims, and expects you to answer with the cause of their untimely demise, whereas the command ``quiz killer victim'' works the other way
     around.

     If you get the answer wrong, quiz lets you try again.  To see the right answer, enter a blank line.

   Index and Data File Syntax
     The index and data files have a similar syntax.  Lines in them consist of several categories separated by colons.	The categories are regular
     expressions formed using the following meta-characters:

	   pat|pat  alternative patterns
	   {pat}    optional pattern
	   [pat]    delimiters, as in pat[pat|pat]pat

     In an index file, each line represents a subject.	The first category in each subject is the pathname of the data file for the subject.  The
     remaining categories are regular expressions for the titles of each category in the subject.

     In data files, each line represents a question/answer set.  Each category is the information for the question/answer for that category.

     The backslash character (``'') is used to quote syntactically significant characters, or at the end of a line to signify that a continuation
     line follows.

     If either a question or its answer is empty, quiz will refrain from asking it.

FILES

     /usr/share/games/quiz.db  The default index and data files.

BUGS

     quiz is pretty cynical about certain subjects.

BSD
								   May 31, 1993 							       BSD

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Finding longest common substring among filenames

Discussion started by: cmcnorgan

2. Shell Programming and Scripting

Parsing file to match strings

Discussion started by: yawalias

3. Shell Programming and Scripting

Awk Array doesnt match for substring

Discussion started by: pinnacle

4. Shell Programming and Scripting

shell script: longest match from right?

Discussion started by: honglus