Boolean pattern matching, with a wildcard

[crelf]

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.

[jdunham]

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

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.

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.

[Francois Normandin]

Using Byte Array Conversion will get you there quite fast...

[Aristos Queue]

Here:

Download File:post-5877-1229132728.vi

Very fast and saved in LV8.6.

[Darren]

My first thought was to solve it like jdunham suggested...it would be interesting to compare the performance of the techniques...I wonder if there's a way to get rid of the memory allocation on the second indexing tunnel?

-D

[Francois Normandin]

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:

[jdunham]

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

[Francois Normandin]

QUOTE (jdunham @ Dec 13 2008, 08:08 PM)

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

Instruments usually send a string, which you need to process. That's what I gathered from Chris' post:

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

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

This is the reason I think any fast implementation of the masking as you proposed should start with a string and not with a boolean array.

[crelf]

Obviously my brain was fried on Friday afternoon: I hadn't even thought of U8 pattern matching. I've updated my code and now the pattern matching is no longer the bottleneck. Now I know why I keep hanging out here :thumbup: Thanks everyone!