4

I would like to search for edge-anchored text that has a block of preceding optional text, any amount of which can be included in the match. For instance, supposing I am trying to find ^xyz but would also accept ^wxyz, ^vwxyz, ^uvwxyz, ^tuvwxyz, ^stuvwxyz, ^rstuvwxyz, but no other possibilities (for my actual search, I couldn't simply use a regex character sequence like [r-w] because the actual block of preceding characters are not in alphabetical order as in this simplified example), I could use the command egrep '^r?s?t?u?v?w?xyz'. Is there another way to write this search such that I could simply apply the optional flag (?) to the entire sequence rather than to each element individually?

Edit:

Here is an example of more realistic data: The full text to be matched is AZHDEOIMOSJDJKEJLCN. However, letters are variably lost from the left end, so all the following should be matched:

^AZHDEOIMOSJDJKEJLCN
^ZHDEOIMOSJDJKEJLCN
^HDEOIMOSJDJKEJLCN
^DEOIMOSJDJKEJLCN
^EOIMOSJDJKEJLCN
^OIMOSJDJKEJLCN
^IMOSJDJKEJLCN
^MOSJDJKEJLCN
^OSJDJKEJLCN
^SJDJKEJLCN
^JDJKEJLCN
^DJKEJLCN
^JKEJLCN
^KEJLCN

Thus, the residual KEJLCN is essential and everything preceding it is optional. However, I cannot simply grep for KEJLCN because I only want instances that are anchored to the beginning of the line (^) and are optionally preceded by the other characters listed above. Also, note that the search string will be in a variable and the minimal residue (e.g., KEJLCN) will be extracted by a substring operation in a script (for example, in a perl environment, running egrep as a system command searching for the text $query, the essential text would be contained in substr($query,-6) and the optional preceding text would be contained in substr($query,0,length($query)-6). Therefore, the solution should be valid for regex in variable form rather than for string literals only.

  • 1
    Could you provide more realistic data, if they aren't actually letters? ^[r-w]*xyz matches your example. May characters/text blocks be repeated? – Michael Homer Jul 30 '14 at 22:33
  • Are the strings going in alphabetical order? For example, will you like to match ^ruvwxyz or ^uvrwxyz? – unxnut Jul 30 '14 at 22:41
  • I added a more detailed example. Please let me know if that clarifies the matter. Thanks. – user001 Jul 30 '14 at 22:48
  • I'm still not understanding why you can't simply use grep '^[A-Z]*KEJLCN' – steeldriver Jul 30 '14 at 23:11
  • @steeldriver: This is because the preceding sequence is definite. For instance, I would not want to count ZKEJLCN as a valid result. If the file consists only of capital letters, then grep '^[A-Z]*KEJLCN' is equivalent to grep KEJLCN. – user001 Jul 30 '14 at 23:20
2
grep '[[:lower:]]*xyz'

Would return you all lines on which that pattern is matched. But, of course, this does not match explicit sequences of characters.

Still, that appears to be a problem you have already solved:

grep -f - <<\STRINGS /dev/fd/3 3<<\DATA
^ZHDEOIMOSJDJKEJLCN
^HDEOIMOSJDJKEJLCN
^DEOIMOSJDJKEJLCN
^EOIMOSJDJKEJLCN
^OIMOSJDJKEJLCN
^IMOSJDJKEJLCN
^MOSJDJKEJLCN
^OSJDJKEJLCN
^SJDJKEJLCN
^JDJKEJLCN
^DJKEJLCN
^JKEJLCN
^KEJLCN
STRINGS

SJDJKEJLCN                                                                  
JDJKEJLCN
o;aidsfjoasjif
KKEJnotLCN
DATA

OUTPUT

SJDJKEJLCN                                                                 
JDJKEJLCN 

If you would like to programmatically generate the same lookup table...

grep -f - <<STRINGS /dev/fd/3 3<<\DATA
$(
    MATCH=ZHDEOIMOSJDJKEJLCN
    until [ ${#MATCH} -lt ${MINLEN=6} ]
    do  printf '^%s\n' "$MATCH"
        MATCH=${MATCH#?}
    done
)
STRINGS

SJDJKEJLCN                                                                  
JDJKEJLCN                                                                  
o;aidsfjoasjif                                                             
KKEJnotLCN                                                                 
DATA

OUTPUT

SJDJKEJLCN                                                                  
JDJKEJLCN
  • The problem is that it would also return, for example, ^axyz, which is undesired. – user001 Jul 30 '14 at 23:38
  • 1
    @user001 - Well, I could do it with sed, but I'd have to do a lookup table of the same kind - storing the stuff in holdspace. Plus, any regex is only going to wind up doing more of the same at the bottom-line - but it might do it on every line. It's better to do the hard part first - generating your search matches all at once - and then do the search. In that way, the search engine does not have to reparse the search match on every line. – mikeserv Jul 31 '14 at 0:07
  • 1
    You make an excellent point. I was operating under the impression that a regex equivalent to the family would be the most elegant solution, but failed to appreciate that constructing the family as a set of string literals would be computationally much less expensive, and moreover that the difference in computational overhead between the two approaches would scale with the size of the file to be examined. – user001 Jul 31 '14 at 0:12
  • 1
    @user001 - precisely. In my opinion, the words elegant and computation don't even belong in the same dictionary, let alone the same sentence. The computer is a very stupid machine. It cannot count higher than one. Everything it does it brute forced - always. Abstractions always only amount to more brute work in the end. The only thing it's got going for it is that it is really really fast at being stupid. – mikeserv Jul 31 '14 at 0:21
  • 1
    Yes, the attempt can be enjoyable as a thought exercise, though in the end, our goal as a programmer, as you have noted, must be efficiency. – user001 Jul 31 '14 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.