Jump to content

Boolean pattern matching, with a wildcard


crelf

Recommended Posts

OK - it's Friday afternoon and we have our office Christmas party tonight, so my brain's checked out for the day :)

Here's the issue: I get a 1D array of Booleans from an instrument, and I need to write an event to disk whenever that array matches some predefined patterns. Sounds pretty straight forward, right? Here's the twist: the predefined patterns can have a wildcard in them (the pattern is a 1D array of values that could a mixture of TRUE, FALSE or DON'T_CARE.

Here's some examples (note: the "." represents "DON'T_CARE"):

Match:

   pattern = 1 0 1 0 . 0 1 0instrument = 1 0 1 0 1 0 1 0

Match:

   pattern = 1 0 1 0 . 0 1 0instrument = 1 0 1 0 0 0 1 0

Not A Match

   pattern = 1 0 1 0 . 0 1 0instrument = 1 1 1 0 1 0 1 0

So I've implemented this quickly by converting the pattern to string of 0s, 1s and .s (TRUE to "1", FALSE to "0", and DON'T_CARE to ".") then I used the pattern match primative to see if there's a match - and it works great! The issue is that it's too slow for my application (I have up to 1000 possible patterns to match).

I thought about converting everything to Booleans, but the what do I do with the DON'T_CARE? I thought about converting everything to an I8, but I'm not sure how to pattern match that.

Anyone got any ideas? I've attached an example pattern file.

Link to comment

QUOTE (crelf @ Dec 12 2008, 02:28 PM)

The standard way to do that is with bitmasks.

QUOTE (crelf @ Dec 12 2008, 02:28 PM)

Match:

   pattern = 1 0 1 0 . 0 1 0instrument = 1 0 1 0 1 0 1 0

So in this case, your criterion consists of a mask: 1111 0111 (in other words 1 = care, 0 = don't care).

and a pattern: 1010 0010 in this case, make sure the don't care bits are also zero.

and your code looks like: (instrument AND mask) =? pattern

though it might be safer to do this (only helps if you trust the mask more than the pattern):

(instrument AND mask) =? (pattern AND mask)

Of course labview will handle integers or boolean arrays with equal aplomb.

you can use the mask with other boolean operations to test for just the zeros, or just the ones, or toggle selected digits.

Link to comment

Don't you guys think that converting the string to boolean array is the real bottleneck here???

All implementations of arrays/matrices and case structures will be fast enough, but I would bet that "Convert String to Byte Array" is faster than looping a string with "array subset" to extract the booleans. So if one must stream the instrument status bytes as fast as possible, then it's the string conversion that would concern me. :2cents:

Link to comment

QUOTE (normandinf @ Dec 13 2008, 11:42 AM)

Don't you guys think that converting the string to boolean array is the real bottleneck here???

All implementations of arrays/matrices and case structures will be fast enough, but I would bet that "Convert String to Byte Array" is faster than looping a string with "array subset" to extract the booleans. So if one must stream the instrument status bytes as fast as possible, then it's the string conversion that would concern me. :2cents:

I didn't see where anyone suggested looping a string with array subset. I'm not sure why a string would be used at all. crelf stored the patterns in a spreadsheet, but it seemed like he was doing that for lack of a better idea. Presumably the patterns would be loaded from a file just once, so speed wouldn't matter, but chris didn't really provide enough details.

The most efficient way is to store the pattern and the mask is to pack the booleans into integers. The pattern was 128 bits, so you could use four U32s for each pattern (and 4 more for the mask), but you're probably right that integers or booleans are fast enough, .

Link to comment

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Unfortunately, your content contains terms that we do not allow. Please edit your content to remove the highlighted words below.
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

By using this site, you agree to our Terms of Use.