c++ - 匹配位串

我需要实现一个字符串搜索算法，该算法可在位文本中查找位模式(匹配可能不是字节/字对齐的)。首先，我实现了Boyer-Moore算法，但是比较单个位对于我的目的来说太慢了。因此，我改为尝试实现一个基于阻塞的版本，该版本将比较this paper中描述的整个字节/字，但是它变得复杂且难以管理(部分原因是由于我不完全了解自己在做什么)。

有人能很好地实现这种算法吗？

我的特定用例是模式长度N >= 32，文本窗口2N以及打包到int中的位。在这种情况下，N也是char大小N % 8 == 0的倍数。我进行过一次预处理，并且在更改文本方面使用了很多次，例如Boyer-Moore。我需要第一场比赛。性能是关键。

编辑:成功实现Blocked Boyer-Moore算法后，我没有发现任何改进(我的点点滴答速度更快!)这可能是我自己的错误，因为我一直在绞尽脑汁并对其进行优化，没有多行评论就毫无意义的观点，但它仍然较慢。 Here是。

最佳答案

概述
我是SO社区的新手，但我希望能有所返回。
有趣的问题。我整理了一个只执行基于字节的比较(借助于预先计算的位模式和位掩码)的实现，而不是对比较执行昂贵的位操作。结果，它应该相当快。它没有实现针对Boyer-Moore algorithm讨论的任何Shift规则(性能优化)，因此可以进一步改进。
尽管此实现确实取决于模式位％CHAR_BIT == 0的数量-在8位计算机上，满足您的标准N％8 == 0，该实现将找到非字节对齐的位模式。 (它目前也需要8位字符(CHAR_BIT == 8)，但是在极少数情况下，您的系统未使用8位字符，可以通过将所有数组/vector 从uint8_t更改为char并进行调整来轻松适应它们所包含的值以反射(reflect)正确的位数。)
鉴于搜索不进行任何位纠结(除了和预先计算的字节掩码之外)，它应该是相当不错的。
算法总结
简而言之，指定了要搜索的模式，实现将其移动一位并记录已移动的模式。它还为移位模式计算掩码，因为对于非字节对齐的位模式，比较的开始和结尾的某些位将需要忽略以确保正常行为。
搜索每个移位位置中的所有模式位，直到找到匹配项或到达数据缓冲区的末尾。

//
//  BitStringMatch.cpp
//

#include "stdafx.h"
#include <iostream>
#include <cstdint>
#include <vector>
#include <memory>
#include <cassert>

int _tmain(int argc, _TCHAR* argv[])
{
    //Enter text and pattern data as appropriate for your application.  This implementation assumes pattern bits % CHAR_BIT == 0
    uint8_t text[] = { 0xcc, 0xcc, 0xcc, 0x5f, 0xe0, 0x1f, 0xe0, 0x0c }; //1010 1010, 1010 1010, 1010 1010, 010*1 1111, 1110 0000, 0001 1111, 1110 0000, 000*0 1010
    uint8_t pattern[] = { 0xff, 0x00, 0xff, 0x00 }; //Set pattern to 1111 1111, 0000 0000, 1111 1111, 0000 0000

    assert( CHAR_BIT == 8 ); //Sanity check
    assert ( sizeof( text ) >= sizeof( pattern ) ); //Sanity check

    std::vector< std::vector< uint8_t > > shiftedPatterns( CHAR_BIT, std::vector< uint8_t >( sizeof( pattern ) + 1, 0 ) );  //+1 to accomodate bit shifting of CHAR_BIT bits.
    std::vector< std::pair< uint8_t, uint8_t > > compareMasks( CHAR_BIT, std::pair< uint8_t, uint8_t >( 0xff, 0x00 ) );

    //Initialize pattern shifting through all bit positions
    for( size_t i = 0; i < sizeof( pattern ); ++i ) //Start by initializing the unshifted pattern
    {
        shiftedPatterns[ 0 ][ i ] = pattern[ i ];
    }

    for( size_t i = 1; i < CHAR_BIT; ++i )  //Initialize the other patterns, shifting the previous vector pattern to the right by 1 bit position
    {
        compareMasks[ i ].first >>= i;  //Set the bits to consider in the first...
        compareMasks[ i ].second = 0xff << ( CHAR_BIT - i ); //and last bytes of the pattern

        bool underflow = false;
        for( size_t j = 0; j < sizeof( pattern ) + 1; ++j )
        {
            bool thisUnderflow = shiftedPatterns[ i - 1 ][ j ] & 0x01 ? true : false;
            shiftedPatterns[ i ][ j ] = shiftedPatterns[ i - 1][ j ] >> 1;

            if( underflow ) //Previous byte shifted out a 1; shift in a 1
            {
                shiftedPatterns[ i ][ j ] |= 0x80;  //Set MSb to 1
            }

            underflow = thisUnderflow;
        }
    }

    //Search text for pattern
    size_t maxTextPos = sizeof( text ) - sizeof( pattern );
    size_t byte = 0;
    bool match = false;
    for( size_t byte = 0; byte <= maxTextPos && !match; ++byte )
    {
        for( size_t bit = 0; bit < CHAR_BIT && ( byte < maxTextPos || ( byte == maxTextPos && bit < 1 ) ); ++bit )
        {
            //Compare first byte of pattern
            if( ( shiftedPatterns[ bit ][ 0 ] & compareMasks[ bit ].first ) != ( text[ byte ] & compareMasks[ bit ].first ) )
            {
                continue;
            }

            size_t foo = sizeof( pattern );
            //Compare all middle bytes of pattern
            bool matchInProgress = true;
            for( size_t pos = 1; pos < sizeof( pattern ) && matchInProgress; ++pos )
            {
                matchInProgress = shiftedPatterns[ bit ][ pos ] == text[ byte + pos ];
            }
            if( !matchInProgress )
            {
                continue;
            }

            if( bit != 0 )  //If compare failed or we're comparing the unshifted pattern, there's no need to compare final pattern buffer byte
            {
                if( ( shiftedPatterns[ bit ][ sizeof( pattern ) ] & compareMasks[ bit ].second ) != ( text[ byte + sizeof( pattern ) ] & compareMasks[ bit ].second ) )
                {
                    continue;
                };
            }

            //We found a match!
            match = true;   //Abandon search
            std::cout << "Match found!  Pattern begins at byte index " << byte << ", bit position " << CHAR_BIT - bit - 1 << ".\n";
            break;
        }
    }
    //If no match
    if( !match )
    {
        std::cout << "No match found.\n";
    }

    std::cout << "\nPress a key to exit...";
    std::getchar();

    return 0;
}

我希望这是有帮助的。