f



wildcard matching algorithm

Does anybody have an efficient, conventional rexx implementation of a
wildcard matching algorithm? Hopefully with positionals, i.e. "?" as
well as "*" or "%"
0
regli
9/8/2009 5:34:30 PM
comp.lang.rexx 2135 articles. 0 followers. Post Follow

13 Replies
2641 Views

Similar Articles

[PageSpeed] 57

I did this to start the discussion.  Likely to still have some bugs.

request = "?Y?abc??d%ef%mb"
request = translate(request)
str = 'XXXABCXXDEFGHIJKLMB'
str = translate(str)

TRUE = 1
FALSE = 0
exactMatch = ""
wildCard = FALSE
match = TRUE

len = length(request) + 1
posStr = 1

do i = 1 to len
   if i == len then
      maskChar = ""
   else
      maskChar = substr(request,i,1)
   select
     when maskChar == WILDCARDCHAR | maskChar == WILDPOSCHAR ,
          | maskChar == "" then do
        if wildCard then do
           wildCard = FALSE
           pos = pos(exactMatch,str,posStr)
           if pos = 0 then do
              match = FALSE
              leave
           end
           else do
              posStr = pos + length(exactMatch)
              exactMatch = ""
           end
        end
        else do
           if exactMatch <> "" & exactMatch == ,
                 substr(str,posStr,length(exactMatch)) then do
              posStr = posStr + length(exactMatch)
              exactMatch = ""
           end
        end
        if maskChar == WILDCARDCHAR then
           wildCard = TRUE
        else do
           if substr(str,posStr,1) == " " & maskChar <> "" then do
              match = FALSE
              leave
           end
           else
              posStr = posStr + 1
        end
     end
   otherwise
      exactMatch = exactMatch||maskChar
   end
end
if match then
   say '*** MATCHED - mask:"'request'" matched string:"'str'"'
else
   say "*** NO match ***"
exit
0
regli
9/9/2009 12:14:45 AM
regli <raeegli@gmail.com> wrote:

> Does anybody have an efficient, conventional rexx implementation of a
> wildcard matching algorithm? Hopefully with positionals, i.e. "?" as
> well as "*" or "%"

What OS/platform?

And what do you want search - lines in a file, or values in a stem array, or
what? 

-- 
Jeremy C B Nicoll - my opinions are my own.

Email sent to my from-address will be deleted. Instead, please reply
to newsreplynnn@wingsandbeaks.org.uk replacing "nnn" by "284".  
0
Jeremy
9/11/2009 2:46:32 AM
On Sep 10, 7:46=A0pm, Jeremy Nicoll - news posts
<jn.nntp.scrap...@wingsandbeaks.org.uk> wrote:
> regli <raee...@gmail.com> wrote:
> > Does anybody have an efficient, conventional rexx implementation of a
> > wildcard matching algorithm? Hopefully with positionals, i.e. "?" as
> > well as "*" or "%"
>
> What OS/platform?
>
> And what do you want search - lines in a file, or values in a stem array,=
 or
> what?
>
> --
> Jeremy C B Nicoll - my opinions are my own.
>
> Email sent to my from-address will be deleted. Instead, please reply
> to newsreply...@wingsandbeaks.org.uk replacing "nnn" by "284". =A0

It has to be platform independent, i.e. a pure Rexx implementation.  I
made some changes to the above and it works much better now.

However, it would be nice to see other implementations.

Here is my latest code:



 WildCardMatch: PROCEDURE

   WILDCARDCHAR =3D "%"
   WILDPOSCHAR =3D "?"
   pattern =3D arg(1)
   pattern =3D translate(pattern)
   str =3D arg(2)
   str =3D translate(str)

   TRUE =3D 1
   FALSE =3D 0
   exactMatch =3D ""
   wildCard =3D FALSE
   match =3D TRUE

   len =3D length(pattern) + 1
   posStr =3D 1

   do i =3D 1 to len
      maskChar =3D substr(pattern,i,1)
      select
        when maskChar =3D=3D WILDCARDCHAR | maskChar =3D=3D WILDPOSCHAR ,
             | i =3D=3D len then do
           if wildCard then do
              if len =3D i then         /* end of loop with open wild
card */
                 leave
              wildCard =3D FALSE
              if exactMatch <> "" then do
                 pos =3D pos(exactMatch,str,posStr)
                 if pos =3D 0 then do
                    match =3D FALSE
                    leave
                 end
                 else do
                    posStr =3D pos + length(exactMatch)
                    exactMatch =3D ""
                 end
              end
           end
           else do
              if exactMatch <> "" then do
                 if exactMatch =3D=3D ,
                      substr(str,posStr,length(exactMatch)) then do
                    posStr =3D posStr + length(exactMatch)
                    exactMatch =3D ""
                 end
                 else do
                    match =3D FALSE
                    leave
                 end
              end
           end
           if maskChar =3D=3D WILDCARDCHAR then
              wildCard =3D TRUE
           else do
              if len =3D i then do
                 if substr(str,posStr) <> "" then do
                    match =3D FALSE
                    leave
                 end
                 else
                    leave
              end
              if substr(str,posStr,1) =3D=3D " " then do
                 match =3D FALSE
                 leave
              end
              else
                 posStr =3D posStr + 1
           end
        end
      otherwise
         exactMatch =3D exactMatch||maskChar
      end
   end
   return match
0
regli
9/11/2009 4:21:02 AM
On 8 Sep, 18:34, regli <raee...@gmail.com> wrote:
> Does anybody have an efficient, conventional rexx implementation of a
> wildcard matching algorithm? Hopefully with positionals, i.e. "?" as
> well as "*" or "%"

I used to have a really concise one, but this is the one I use now:
/* REXX
*/
/*-Start of PATMATCH function---------------------------Version-01.01-
*/
/*:PATMATCH function - Performs ISPF-type pattern matching on a pair
*/
/* of strings: 1st string is the pattern, 2nd is the data.
*/
/* Example: rc=PATMATCH('*EFG*','ABCDEFGH')
*/
/* Returns: 0:    Pattern does not match the data.
*/
/*          1:    Pattern does match the data.
*/
/*          text: Error occured, text gives the details.
*/
/* Copyright (C) 1996, 1998 Washington Systems. All rights reserved.
*/
/*--------------------------------------------------------------------
*/
PATMATCH: PROCEDURE EXPOSE
gbl.
TRACE
N
IF ARG() <> 2 THEN RETURN 'PATMATCH ERROR: 2 parms required,
caller',
                          'passed 'ARG()'
parms'
haystack = ARG(2)                  /* Data to be searched w/ pattern
*/
pattern = ARG(1)                   /* Search pattern
*/
wild = 0                           /* No '*' seen (yet)
*/
  DO WHILE pattern <> ''           /* Process pattern from L to R
*/

  a = POS('*',pattern)             /* Look for '*' in pattern
*/
  IF a > 0 THEN                    /* If found, extract any
*/
    DO                             /*  preceeding search string
*/
    PARSE VAR pattern needle '*' +0
newpattern
    IF needle = ''
THEN
      DO                           /* If no preceeding search string,
*/
      wild = 1                     /*  mark next search as 'wild
card'*/
      PARSE VAR newpattern 2 pattern /* remove '*' from pattern
*/
      ITERATE                      /*    and continue testing
*/
 
END
 
END

  p = POS('%',pattern)             /* Look for '%' in pattern
*/
  IF p > 0 & (a = 0 | p < a) THEN  /* If found before any '*',
extract*/
    DO                             /*  any preceeding search string
*/
    PARSE VAR pattern needle '%' +0
newpattern
    IF needle = ''
THEN
      DO                           /* If no preceeding search string,
*/
      needle = LEFT(haystack,1)    /* take next text as search string
*/
      PARSE VAR newpattern 2
newpattern
      wild = 0                     /* Mark next search 'not wild
card'*/
 
END
 
END

  IF p = 0 & a = 0                 /* No special chars, use remainder
*/
  THEN PARSE VAR pattern needle
newpattern

  pattern = newpattern             /* Update pattern for next pass
*/
  pos = POS(needle,haystack)       /* Look for this pattern
*/
  IF pos = 0 THEN RETURN 0         /* Not found, outta here
*/
  IF pos > 1 THEN                  /* Found, but not at start-of-text
*/
    IF wild <> 1                   /* Wild card char in effect?
*/
    THEN RETURN 0                  /* No wild card, outta here
*/
  wild = 0                         /* Reset wild card character
*/
  len = LENGTH(haystack)-LENGTH(needle)-pos
+1
  haystack = RIGHT(haystack,len)   /* Remove data that we just
scanned*/
  IF haystack = ''
THEN
    DO                             /* No more data to scan...
*/
    IF pattern = ''                /* Out of pattern as well?
*/
    THEN RETURN 1                  /* Yes, that's a match.
*/
    IF pattern = '*'               /* Did pattern end with wild card?
*/
    THEN RETURN 1                  /* Yes, that's a match too.
*/
    RETURN 0                       /* Else, sorry, not a match.
*/
 
END
  END                              /* Ran out of pattern to scan
*/
IF wild = 1                        /* Did pattern end with wild card?
*/
THEN RETURN 1                      /* Yes, that's a match.
*/
ELSE RETURN 0                      /* Else, sorry, not a match.
*/
/*-End of PATMATCH function-------------------------------------------
*/
0
Captain
9/14/2009 2:46:57 PM
Thanks a lot for your post!  I ran a test with both options and it
appears that parse makes it somewhat slower though only by a slight
margin.

19:07:19
elapsed:11.872000 - matched:300000
19:07:31
elapsed:8.199000 - matched:300000
19:07:39

I ran with 6 pattern matches for each each cycle and executed that
cycle 100,000 times which resulted in 300,000 matches. The first
execution is using your code and the second uses mine.

Again, thanks a lot!
0
regli
9/16/2009 2:19:40 AM
A perfect example of 'platform independent' not being the 
same as 'platform efficient'!
Run the same test on a mainframe, in particular VM/CMS, and 
measure cpu cycles and Parse will probably win by a 
significant amount. That's because the original VM Rexx was 
implemented with the mainframe instruction set and Parse 
was optimized for efficiency, according to Mike.

Les               (Change Arabic to Roman to email me)



regli wrote:
> Thanks a lot for your post!  I ran a test with both options and it
> appears that parse makes it somewhat slower though only by a slight
> margin.
> 
> 19:07:19
> elapsed:11.872000 - matched:300000
> 19:07:31
> elapsed:8.199000 - matched:300000
> 19:07:39
> 
> I ran with 6 pattern matches for each each cycle and executed that
> cycle 100,000 times which resulted in 300,000 matches. The first
> execution is using your code and the second uses mine.
> 
> Again, thanks a lot!
0
LesK
9/16/2009 10:31:24 PM
On Sep 16, 3:31=A0pm, LesK <5mr...@tampabay.rr.com> wrote:
> A perfect example of 'platform independent' not being the
> same as 'platform efficient'!
> Run the same test on a mainframe, in particular VM/CMS, and
> measure cpu cycles and Parse will probably win by a
> significant amount. That's because the original VM Rexx was
> implemented with the mainframe instruction set and Parse
> was optimized for efficiency, according to Mike.
>
> Les =A0 =A0 =A0 =A0 =A0 =A0 =A0 (Change Arabic to Roman to email me)
>
> regli wrote:
> > Thanks a lot for your post! =A0I ran a test with both options and it
> > appears that parse makes it somewhat slower though only by a slight
> > margin.
>
> > 19:07:19
> > elapsed:11.872000 - matched:300000
> > 19:07:31
> > elapsed:8.199000 - matched:300000
> > 19:07:39
>
> > I ran with 6 pattern matches for each each cycle and executed that
> > cycle 100,000 times which resulted in 300,000 matches. The first
> > execution is using your code and the second uses mine.
>
> > Again, thanks a lot!
>
>

You are right but I'd still like to see somebody running it on VM.
I'll ask for that favor in another forum and report back.
0
regli
9/17/2009 3:59:20 AM
As promised here are the results from z/OS 1.9:

Solution 1:
TOTAL TCB CPU TIME= .89 TOTAL ELAPSED TIME= 2.0

09:39:20
elapsed:125.018178 - matched:30000
09:41:25

Solution 2:
TOTAL TCB CPU TIME=   1.16 TOTAL ELAPSED TIME=   1.8

09:42:05
elapsed:110.321300 - matched:30000
09:43:55

It shows that the parse solution gained a tremendous amount and won
the contest on the mainframe as I believe that in that scenario CPU
time is more telling that elapse time.
0
regli
9/18/2009 5:09:51 PM
On 16 Sep, 23:31, LesK <5mr...@tampabay.rr.com> wrote:
> A perfect example of 'platform independent' not being the
> same as 'platform efficient'!
> Run the same test on a mainframe, in particular VM/CMS, and
> measure cpu cycles and Parse will probably win by a
> significant amount. That's because the original VM Rexx was
> implemented with the mainframe instruction set and Parse
> was optimized for efficiency, according to Mike.
>
> Les =A0 =A0 =A0 =A0 =A0 =A0 =A0 (Change Arabic to Roman to email me)

Ahh but if it was on VM I would be using the PIPATTERN extension for
CMS/TSO PIPELINES to match the string.
0
Captain
9/18/2009 8:58:07 PM
Captain Paralytic wrote:
> Ahh but if it was on VM I would be using the PIPATTERN extension for
> CMS/TSO PIPELINES to match the string.

What?  Not one of the xxGREP stages?

�R
0
Glenn
9/18/2009 10:16:24 PM
But then you couldn't compare apples to apples! The 
original requirement was for platform independence.

Les               (Change Arabic to Roman to email me)



Captain Paralytic wrote:
> On 16 Sep, 23:31, LesK <5mr...@tampabay.rr.com> wrote:
>> A perfect example of 'platform independent' not being the
>> same as 'platform efficient'!
>> Run the same test on a mainframe, in particular VM/CMS, and
>> measure cpu cycles and Parse will probably win by a
>> significant amount. That's because the original VM Rexx was
>> implemented with the mainframe instruction set and Parse
>> was optimized for efficiency, according to Mike.
>>
>> Les               (Change Arabic to Roman to email me)
> 
> Ahh but if it was on VM I would be using the PIPATTERN extension for
> CMS/TSO PIPELINES to match the string.
0
LesK
9/19/2009 6:02:43 AM
It would be interesting to see the two Pipe solutions and 
measurements :-)

Les               (Change Arabic to Roman to email me)



Glenn Knickerbocker wrote:
> Captain Paralytic wrote:
>> Ahh but if it was on VM I would be using the PIPATTERN extension for
>> CMS/TSO PIPELINES to match the string.
> 
> What?  Not one of the xxGREP stages?
> 
> �R
0
LesK
9/19/2009 6:05:49 AM
On 18 Sep, 23:16, Glenn Knickerbocker <N...@bestweb.net> wrote:
> Captain Paralytic wrote:
> > Ahh but if it was on VM I would be using the PIPATTERN extension for
> > CMS/TSO PIPELINES to match the string.
>
> What? =A0Not one of the xxGREP stages?
>
> =ACR

I don't have access to the latest VM PIPLEINEs anymore :-(

Nearest to grep that was available when I had the access was PIPATTERN.
0
Captain
9/19/2009 12:33:21 PM
Reply:

Similar Artilces:

A small wildcard matching algorithm
\ A small wildcard matching algorithm. \ Converted from Jack Handy "wildcmp" C source. \ see https://secure.codeproject.com/string/wildcmp.asp \ WILDCARD-MATCH ( text ntext wild nwild -- flag ) ( s" bl?h.*" s" blah.jpg" WILD-COMPARE if ." we have a match!" else ." no match" then ; ) \ NB: ANDIF, ORIF see Neil Bawd http://home.earthlink.net/~neilbawd/ char * constant '*' char ? constant '?' : up2 ( a b -- A B ) upper swap upper ; : ucharC ( a n i -- c ) tuck > if chars + c@ else 2drop 0 then ; ...

match match match
hi everyone, iam feeling shy to ask such a small question to the great scholars,but i must in order to complete my project.Could you please suggest me any reference for finding information about 1.how to design a matched filter to detect a PAM signal. 2.Is it possible to replace an equalizer with matched filter? **I will be more thankful to you if u could give the answers as quickly as possible.** vimmi wrote: > hi everyone, > iam feeling shy to ask such a small question to the great scholars,but i > must in order to complete my project.Could you please suggest me any > referen...

Wildcard matching
I'm trying to find and replace any non-alphanumeric character (or lack thereof), followed by a specified word, followed by any other non- alphanumeric character (or lack thereof). Here's where I am so far, using "jason" as the specified word: $comment =~ s/(\W)jason(\W)/$1*****$2/i; Specifically, I want to catch things like " Jason" (notice the opening whitespace), "<br>Jason!", "***Jason***", and "<br>Jason\n". I'm not so concerned about underscores, which I understand aren't included in \W. Any sug...

how to not match a match?
hi, I want to print out lines that do not match "field-power" in them. I have gotten the expression which matches the line, but can't seem to do the inverse. see: awk '/(field\-power)/ { print $0 }' On Thu, 16 Mar 2006 09:51:01 -0800, yusuf wrote: > hi, I want to print out lines that do not match "field-power" in them. > I have gotten the expression which matches the line, but can't seem to > do the inverse. see: > > awk '/(field\-power)/ { print $0 }' grep -v "field-power" filename Mr_Bill Thnaks, that worked. Just f...

Wildcard match?
If I have a file.txt in a directory, I can echo "hello" as follows: if [ -a file.txt ]; then echo "hello"; fi But how can I use a wildcard in this situation, such as *.txt and echo if there is one or more matches? For example: if [ -a *.txt ]; then echo "hello"; fi Wtih the above, although if there's no match there's no error or echo, which is correct, but if there is one match the error "[: file.txt: binary operator expected" occurs, or if there are more matches the error "[: too many arguments" occurs. How ca...

Matching Algorithm
Hi guys, Any idea how to write an algorithm for an online dating agency matching service where each user has a number of features such as eyes = brown, height = 170cms and a number of preferences ie height >170cms eyes = brown or blue but not green? Thanx Bruno writes: > Any idea how to write an algorithm for an online dating agency matching > service where each user has a number of features such as eyes = brown, > height = 170cms and a number of preferences ie height >170cms eyes = brown > or blue but not green? Sounds like a neat problem to attempt to solve. I assum...

Unexpected wildcard matching
--14dae934117bf2018304d41ced0b Content-Type: text/plain; charset=ISO-8859-1 Hello, I want to have a dummy (internal) root NS to resolve specific name hello.test.com to 4.5.6.7, everything else to 1.2.3.4. Using a wildcard does not work as expected (by me), though. 1st attempt: # cat db.root $TTL 86400 @ IN SOA ns1.root.internal. dnsadmin.root.internal. 1 21600 3600 604800 600 IN NS ns1.root.internal. * IN A 1.2.3.4 hello.test.com. IN A 4.5.6.7 # dig +shor...

Matching algorithm #2
Let's say I have a DB with thousands of records for people. Each person as a unique id (integer), and a set of (key, value) pairs, such as "firstname=Bob", "lastname=Smith", "birth=19691123", "SSN=44556677", etc. Each key in this list has associated with it an integer weigth; the larger the integer, the higher the likelihood that key can uniquely identify that person. Therefore, SSN would have a larger weight than firstname. Now, say I am given a set of (key,value) actual pairs, and I have to fetch the ordered set of all persons that match this set,...

image matching algorithms
Hi all, There are a number of free tools for image matching but it's not very easy to decipher the actual algorithm from the code that includes db management, GUI, etc, etc. I have my own image database and GUI so all I need is the actual algorithm preferably in pseudo code and not in the form of a research paper (from which I also found a lot but since I'm not that much interested in the actual science of image recognition this seems like an over kill). My understanding of image matching is that it works by first calculating N real numbers for an image and defining a metric for pair...

Filename wildcard match
My XML looks like: <role type="Joker"> <Profile id="13">ABC_Organization</Profile> </role> My XSL looks like: <xsl:variable name="prefix">profile_joker_</xsl:variable> <xsl:variable name="vid"><xsl:value-of select="Profile/@id"/></xsl:variable> <xsl:variable name="vname"><xsl:value-of select="Profile"/></xsl:variable> <xsl:variable name="suffix">.xml</xsl:variable> <xsl:variable name="tmp1"><xsl:value-of sel...

no wildcards in string match?
The documentation says I should be able to use wildcards with string match. However: % info patchlevel 8.4.12 % set foo bar bar % string match $foo "bar" 1 % string match $foo "b?r" 0 % string match $foo "b*" 0 % string match $foo b* 0 So, what am I doing wrong here? -- Unabashedly littering the information superhighway with detritus like this for over 15 years now. Todd A. Jacobs wrote: > The documentation says I should be able to use wildcards with string > match. However: > > % info patchlevel > 8.4.12 > % set foo bar >...

Color matching algorithm
Does anyone have any idea how the Image Color Matching function in Photoshop works? (the one that matches the color of one image to the other) Thats is, the theory behind it all. Regards /Morten ...

Point Matching Algorithm
I have a set of 200,000 x,y,z points (set1) and a set of 1,000,000 points x,y,z,otherInfo (set2)... I for each point in set1, I need to find the closest point from set2 which contains additional information that I want to assingn to the points in set1. Can anyone point me to an efficient algorithm that will do this? The brute force approach of comparing the set1 point to every set2 points seems like an unnecesary and computer intensive process. Thanks for the help. Rock Rock wrote: > I have a set of 200,000 x,y,z points (set1) and a set of 1,000,000 > points x,y,z,otherInfo (set2)....

Wildcard for relationship match?
Hi, I'd like to use a relationship to filter records in a portal. The portal displays records which are related with a usual ID-matching arrangement. The related records also have a "type" field (as an example, values could be type "A", "B", or "C".) I've made a table occurrence with a relationship matching both the ID and the type (against a global field). Using a pull-down menu for the global, I can successfully filter the portal for different values of type. However, I'd also like an option to display the related records of ALL ...

Web resources about - wildcard matching algorithm - comp.lang.rexx

Algorithm - Wikipedia
Flow chart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named ...

Latest Facebook News Feed Algorithm Tweak: High Ratings and Likely Engagement
... take action on, and that people might want to see near the top of their News Feed. How will the newest change to Facebook’s News Feed algorithm ...

Why Google won’t start announcing algorithm updates
... ‘ mobile friendly ’ in search results as of the 21 st April. This prompted a lot of speculation that Google might start to announce its algorithm ...

Google's British AI startup beat Facebook in the race to build an algorithm that can take on the best ...
Something strange happened in the world of artificial intelligence (AI) on Wednesday. Facebook CEO Mark Zuckerberg posted on his Facebook profile ...

Google's latest data-squeezing algorithm is coming to Chrome
Google is no Silicon Valley startup, but it's just as intent on creating compression algorithms as the fictional "Pied Piper." The search giant ...

Career Trends: Why It's Imperative to Embrace the Algorithms in Our Future
Remember Hal, the computer run amok in Stanley Kubrick’s 2001: A Space Odyssey? Forget him. The human vs. machine battle is so 20th century. ...

Google puts AI expert in charge of its search algorithms
Financial Times Google puts AI expert in charge of its search algorithms Financial Times For Google, Mr Singhal's departure is as significant ...

Clickbait be gone: Facebook changes News Feed algorithm to show more than just Like-worthy posts
... on social media, The Onion has a whole parody site dedicated to them. But Facebook may kill clickbait with an update to its News Feed algorithm. ...

Warning! This Shane Smith Interview Has 52 F-Bombs: "If I Can Come Up With the New Algorithm, Then I ...
Shane Smith knows exactly what you think of his plan to conquer cable TV — and he doesn't care.

Tinder’s Secret ‘Desirability Algorithm’ Is Not Just About The Swipe
... in popularity, and according to CEO Sean Rad, on Tinder it’s about more than the swipe. CNET reports that Rad explains the desirability algorithm ...

Resources last updated: 2/4/2016 12:05:47 PM