概要
私は SO コミュニティには不慣れですが、何かお返しできることを楽しみにしています。
興味深い問題です。比較で高価なビット操作を実行するのではなく、(事前に計算されたビット パターンとビット マスクを使用して) バイト ベースの比較のみを行う実装をまとめました。その結果、かなり高速になるはずです。これは、 Boyer-Moore アルゴリズムについて説明したシフト ルール (パフォーマンスの最適化) を実装していないため、さらに改善される可能性があります。
この実装はパターン ビット % CHAR_BIT == 0 の数に依存しますが、8 ビット マシンでは N % 8 == 0 の基準を満たしますが、実装は非バイト アライン ビット パターンを検出します。(現在は 8 ビット文字 ( CHAR_BIT == 8 ) も必要ですが、万一システムが 8 ビット文字を使用していない場合は、すべての配列/ベクトルを uint8_t から char に変更し、調整することで簡単に適応できます。それらに含まれる値は、正しいビット数を反映しています。)
検索がビット操作を行わないことを考えると (事前に計算されたバイト マスクを AND 処理する以外に)、かなりのパフォーマンスが得られるはずです。
アルゴリズムの概要
簡単に言えば、検索するパターンを指定し、実装はそれを 1 ビット シフトして、シフトされたパターンを記録します。また、シフトされたパターンのマスクも計算します。バイト境界で整列されていないビット パターンの場合、適切な動作のために比較の最初と最後のビットを無視する必要があります。
検索は、一致が見つかるか、データ バッファの最後に到達するまで、各シフト位置のすべてのパターン ビットに対して実行されます。
//
// 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;
}
これがお役に立てば幸いです。