Re^2: [OT] The interesting problem of comparing bit-strings.

[BrowserUk]

I bet you could use the same basic idea of building a state machine of the next address to check

Um. Boyer Moore is an optimisation of the basic string search isn't it?

Right now I'm stuck just trying to implement the basic search taking into account the bit-level offsets. Optimisations can come later if required.

[salva]

No Boyer-Moore, but you can convert your bitstring search into a regular expression (in the CS sense, not the Perl one), and then compile it into an efficient state-machine.

For instance, in order to look for bitstring 010101, you have to look for character strings matching any of...

s1: 010101xx
s2: x010101x
s3: xx010101
s4: xxx01010 1xxxxxxx
s5: xxxx0101 01xxxxxx
s6: xxxxx010 101xxxxx
s7: xxxxxx01 0101xxxx
s8: xxxxxxx0 10101xxx

You can write the regular expression matching s1 as a character set $s1 = qr/[\x54\x55\x56\x57]/, and similarly for s2-s8, and then combine all of them as qr/$s1|$s2|...|$s8/.

Then you would need some module able to convert that regular expression into a state machine, and use it for matching the vector... I am sure there is already some RegExp backend on CPAN that does that.

The downside is that the resulting state-machines may be huge.

[BrowserUk]

As you are the third respondent that has suggested bit-masks of one form or another, either:

1. My question/description is unclear.
2. Or I'm missing something fundamental.

Both distinct possibilities.

As I see it, my problem isn't how to isolate the bits of the strings that I need to compare -- __shiftleft128() does that easily and efficiently.

The problem is one of how to construct/combine the nested loops in order to perform the iteration of the bits and quads in the proper way.

Looking up a basic (ie. not the gcc version which incredibly complicated) strstr() function I found this:

char *strstr( char *haystack, char *needle ) {
    char *hp;
    char *np;

    if( !*needle ) return haystack;              // null needle; retur
+n haystack (strange POSIX specification requirement!)

    while( *haystack ) {                         // until we reach the
+ end of the haystack
        hp = haystack;                           // copy of the haysta
+ck pointer      
        np = needle;                             // copy of the needle
+ pointer
        do {
            if( !*np ) return haystack;          // end of needle; mat
+ch completed; return current value of haystack pointer
        } while( *hp++ == *np++ );               // increment both poi
+nter (copies) while the chars match
        ++haystack;                              // Got here means a m
+ismatch; base pointer to next character.
    }
    return 0;                                    // Got here means we 
+hit the terminating null of the haystack; no match; return null.
}

If my bitstrings where always 64-bit aligned, I could just substitute U64 for char everywhere, and that would be that; but of course it isn't.

Essentially, there are five operations I need to encapsulate:

1. Incrementing haystack by 1-bit.
2. Incrementing haystack by 64-bits (1 quad + offset).
3. Incrementing needle by 64-bits (1 quad + offset).
4. Detecting EOS of the haystack.
5. Detecting EOS of the needle.

For 2 & 3 I thought to write a function:

U64 nextQuad( U64 **p, U8 o ) {                  // p: pointer to poin
+ter to the 'current' quad; o: value of the unused bits at the beginni
+ng.
    U64 hi = *( ++*p )                           // increment the poin
+ter at *p, and set hi to the value it points at.
      , lo = *( *p+1 );                          // and lo to the valu
+e + 1 it points at
    return __shiftleft128( lo, hi, o );          // return the value f
+rom the higher location with o bits from lo shifted in from the right
+.
}

I think that would work, but for efficiency, you'd want to keep hi and lo in registers between calls, and you can't take the address of regiters, so I'd be relying on the compiler to recognise the importance of doing so.

For one, things get more complicated. Now I need a pointer to the offset as well:

U64 nextBit( U64 **p, U8 *o ) {                  // p: pointer to poin
+ter to current quad; o: pointer to current offset
    U64 hi, lo;
    if( ++( *o ) == 64 ) {                       // increment the offs
+et and detect transitions across quad boundaries.
        *o = 0;                                  // reset the offset.
        ++*p;                                    // increment the quad
+ pointer.
    }
    hi = **p;                                     // Get the 'current'
+ (unshifted) quad value
    lo = *( *p + 1 );                             // And the next
    return __shiftleft128( lo, hi, *o );          // return the value 
+from the higher location with *o bits from lo shifted in from the rig
+ht.
}

For 4 & 5, I need to calculate whether I've reached the end from the current values of the quad pointer & associated offset.

Putting it all together and getting it to compile is defeating me at the moment.

[Krambambuli]

Might be that I'm totally wrong, but I think that as long as you're trying to consider

1. Incrementing haystack by 1-bit.

an important primary op, there's something wrong.

I'd basically try to first find out how the needle would need to be shifted in order to match the char_aligned haystack, and leave the haystack as it is - always.

My somewhat naive approach would be to start with building the set of 256 possible 'needle heads' (going for char operations all over). A 'needle head' could be say 8 chars long (or some other convenient value).

Then, look for the occurences of the needle_heads within haystack. For each needle_head, you know the offset (needed shift) associated with it. (Yes, that means 256 searches instead of 1, but it still might be better than shift-ing things around for every next bit-position.)

If needlehead is found, go on with a full, char-wise compare, with haystack's chars untouched and every next needle-char obtained via a proper shift from the next two chars of the needle.

End of string is bit-masked as needed to comply with the known offset.

Maybe you've tried something like that already?

Krambambuli
---

[marinersk]

My turn to wonder if I'm missing something fundamental or failing to communicate my solution.

I guess I'm just going to have to find time to code up a working example.

Either I'll prove my concept or figure out which kind of left field I'm standing in.  :-)

[Anonymous Monk]

DFA space requirement and construction are both O(m*s) where m is needle length and s the alphabet size. Search is O(n) (linear to text size). In practice, one would handle say 8 bits (a byte) at a time. Even then, the space requirement hardly matters with small patterns..

[salva]

The think is that O(m*s) can actually be huge!

For a 256 alphabet and supposing that a pointer per entry is enough, it results in 1KB per needly byte. Three orders of magnitude bigger than the needle size.

Admittedly, that is a worst case scenario as in most cases, the transition tables collapse into just a few exits per state and can be represented in more efficient ways. But I don't know if the OP case fits into that "most cases".