String pattern matching and position

I am not an expert with linux, but following various posts on this forum, I have been trying to write a script to match pattern of charters occurring together in a file.
My file has approximately 200 million characters (upper and lower case), with about 50 characters per line. I have merged all the lines together to make it one line using

tr -d '\n' < input.txt > oneLineInput.txt

I now have all charcters in my file in the same line without spaces.

I am trying to count the number of times the specific characters occur together. For example, in the file below

IamTryingtobuildascriptfortrestingthetyposinmysentence

I am trying to look for the pattern 'tr' that occurs in the sentence. The script I have now is

grep -o -i oneLineInput.txt -e tr | sort | uniq -c

The above script works perfectly fine for a small file, but when I try to run it on my actual file with more than 200 million characters, it takes ages to finish the task (I lost patience and did not check the total time taken).

Is there a way I can optimize the code?

Next, I have been trying to get the position of the match. For example, in the above example file, 'tr' is starts on 4th and 27th position. I just want the number as output.

Is it possible?

Thank you

By definition, grep , sort , and uniq work on text files; and the input your feeding to grep is not a line. (A line ends with a newline character and, including the newline character, contains no more than LINE_MAX bytes. On most systems, LINE_MAX is the minimum allowed by the standards, 2048.)

The standards also require operands to follow options on the command line. So, what you are doing is not portable and will not work at all on many systems.

On Linux systems, where the command you showed might work, it will take a lot longer than processing a normal text file because you require the entire (200Mb) file to be read into the address space of grep at once.

If the command line you showed works on your system, you may be able to get offsets in the file offsets (0-based rather than 1-based) of each match (rather than the number of occurrences of TR , Tr , tR , and tr ) by using the command line:

grep -bio tr oneLineInput.txt

In the original files with about 50 characters per line, could patterns be spread over two consecutive lines?

@ Scrutinizer: The patterns in the original file are indeed spread over two consecutive lines. That is the reason I merged the two.
I did manage to get an answer for the problem from Jotne and Tom Fenech at stackoverflow.

To count the number of occurrences:

awk -F"[Tt][Rr]" '{print NF-1}' oneLineInput.txt

To get the position:

awk -F"[Tt][Rr]" 'BEGIN {print "hit\tposition"} {for (i=1;i<NF;i++) {p+=length($i);print ++a"\t"p+1+(a-1)*2}}' oneLineInput.txt

Another approach:

{ 
    while (match($0, /[Tt][Rr]/)) {
        ++n
        m += RSTART
        $0 = substr($0, RSTART + RLENGTH)
        printf "match %d: position %d\n", n, m + n - 1
    }
}

awk -f matches.awk file

Thank you trying to help me.

@ Don Cragun: perfect explanation for why the script I tried did not work.

Amazed by the capabilities of what scripting can do.

The awk utility is also only defined to work when the input files it reads are text files. So, although some versions of awk can handle long, and/or incomplete lines or both, many cannot. If you would like something that should work on any UNIX or Linux system, you could try something like this:

awk '
function p(spot) {
	printf("%10d %10d\n", ++cnt, spot)
}
te && /^[Rr]/ {
	p(te)
}
{	while(match($0, /[Tt][Rr]/)) {
		p(off + RSTART)
		$0 = substr($0, 1, RSTART - 1) " " substr($0, RSTART + 1)
	}
}
{	off += length($0)
	if($0 ~ /[Tt]$/) {
		te = off
	} else	te = 0
}' input.txt

Note that this works on your input file before stripping out the <newline> characters, so instead of having to allocate 200Mb of memory to read in your one-line file, it just needs to read one ~50 character line at a time.

With the following randomly generated list of upper- and lower-case letters (except for the 1st 8 and last 8 characters in the file):

TrTRtrtRmzGArXRqWdKOmxzDWLKZVnPRRrAVNcpAflTxvLkLbs
NbZdBuopHQnEqVJiLWYHVZUfHLqUTmRPesoqVbVdgXXglCCEQC
ZRfvLdXyfgpufseFnIIboRbtDXtlttNQudyeOGyLvLGzSOPyMo
VpxGVwNJKXpYUlhZuNgIcgYuscJRzmExrJZWeeRgnHXwxkxbKh
mndPLikztEWtlovWaOddGCSEijRtrkgWWzvQADIQhsfVEAwmXQ
eIImjmJnvLTQLubbchEwLclnjVmUKuIRxmUOSmarnWYyEBKQpX
gEpdrIXIXiUsiMjQQWWIYWYCfSBwMsPQwvLHyGRwKldfvOxzar
xgwKodWiJxgAhVhlCfalWRpijwiHRlYntBOxweZrvwPPLTYpmN
REPdLIcZnBLWORUkpLCBtlTzjOmQBDVuFEAYfzLTIbyZaNVUMt
rfDzbKDxzXoCqnpWntyTrkyIrSrZTopjapZFouHDGxmlZmxswW
AcvPaJKxLSXZLCLfRZVuxusjYcKzlpZajBMvweadarCAIGjPdM
yiFAqrMDySoxpPREnFPHDQaFJDVUDsYXmbZGkhbvImOkCKfAsg
kauwlSzzrbqrBrXCLJsHXlHAdoRBjXjQbUoFJslyENNKnjIADT
RMEZvOSLWqHeeEoIUddxBxdHuuEMqTpYVTIoGUNVPxKPcSadji
ecsIoISmpwIPIqCXYdwqsvbtTKuoQflREDkZPLxtlyfOVeuKxj
LkwARhocaWFEMjZlPHtuCiYmxfqtYSGwlRSLZHzYGDZoHzvJbm
GsXLsRcuvLEQcXPRakbdeHGLrrnZgwyMFHmXNMmNNbEnfkXumM
pUSpOhpTakWOpQNohhjcuObfSfteNBMyJivKQKhPJQtrtRTrTR

it produces the output:

         1          1
         2          3
         3          5
         4          7
         5        228
         6        450
         7        470
         8        650
         9        893
        10        895
        11        897
        12        899

giving you the number of matches found and their positions in the file (not counting <newline> characters).

Indeed it is best to keep the file original. Awk can be easily adjusted to work with the original file. For example an adjustment of Jotne's suggestion:

awk -F"[Tt][Rr]" '{gsub(/\n/,x); for (i=1;i<NF;i++) {p+=length($i); print ++a, p+1+(a-1)*2}}' RS=� file

Will maybe work with gawk and maybe mawk , since they have very good line limitations.

Also a perl solution like:

perl -0077 -ne 's/\n//g; print (++$c," ",(pos() +1 -2)."\n") while /tr/gi' file

But while it perhaps may be even less likely than awk to run into line length limitations, just like the awk approach it will read the entire file in memory, which with 200M records is at least a 200 MB footprint...

I came up with a similar approach to Don's, but it uses index() rather than match() and it works for variable length patterns:

awk -v pattern="tr" '
BEGIN {
  pat_width=length(pattern)
}

{
  curline=tolower($0)
  chunk=rest curline
  while (pos=index(chunk,pattern)) {
    relpos+=pos
    print ++count, basepos + relpos
    chunk=substr(chunk, pos+pat_width)
    relpos+=pat_width - 1
  } 
  relpos=1-pat_width
  rest=substr(curline, length(curline) - pat_width + 2)
  basepos+=length(curline)
}

' file

Also, with all the approaches so far, they will look for the next match AFTER last match.

This next approach will also find additional pattern that were already part of a previous match:

awk -v pattern="trt" '
BEGIN {
  pat_width=length(pattern)
}

{
  curline=tolower($0)
  chunk=rest curline
  while (pos=index(chunk,pattern)) {
    relpos+=pos
    print ++count, basepos + relpos
    chunk=substr(chunk, pos+1)
  } 
  rest=substr(curline, length(curline) - pat_width + 2)
  basepos+=length(curline)
  relpos=-pat_width+1
}

' file

If we take the last part of Don's example: trtRTrTR , when trying to match "try" it will find 3 matches, while the others find only two.

Output:

1 1
2 3
3 5
4 893
5 895
6 897 

Whereas the previous (using the pattern "trt" ) will find:

1 1
2 5
3 893
4 897