2

ビットごとの演算子を使用して int 値のリストをマスクし、そのマスクを使用して int 値がマスク内の値の 1 つであるかどうかを知る方法があるかどうか疑問に思っていました。

つまり、値が 129 と 17 の場合、int 値がマスクに対応するかどうか (int 値が 129 または 17 の場合) を示すマスクを計算するにはどうすればよいでしょうか。

私の問題は、次の疑似コードでよりよく理解できると思います。

* *編集: int 配列を 1 つの値 (マスク) だけでパック、マスク、または「圧縮」してから、マスクする値のリスト (配列) にある値のみを受け入れます。

出来ますか？前もって感謝します。

valuesToMask = [17, 129, ...]
mask = getmask(valuesToMask)
lstValues = [0,1, 10, ..., 17, 18, 19, ..., 129, ...]
foreach(int value, in lstValues) {
    if(check(mask,value)) 
       printf("\nValue %d is in the mask", value);
    else 
       printf("\nValue %d is not in the mask", value);
}

前もって感謝します。私は本当にあなたの助けとあなたの時間に感謝します.

（私の英語でごめんなさい）

4

3 に答える 3

2

これは特定の値のセットに対して実行できますが、必ずしも一般的ではありません。たとえば、値が4、5、6、または7のいずれであるかを判別する場合は、次のように実行できます。

if ((value & ~3) == 4) ...

これにより、最下位2ビットを除くすべてのビット1でマスクが作成されます。&オペレーターは、最下位2ビットを事実上0に設定します。次に、比較により、ビットのパターンが探している値と一致するかどうかが確認されます。バイナリ表現では、これは次のようになります（value8ビット値であると想定）。

value        masked
00000011     00000000 = 0
00000100     00000100 = 4
00000101     00000100 = 4
00000110     00000100 = 4
00000111     00000100 = 4
00001000     00001000 = 8

たとえば、「4、5、または7」だけをチェックしたい場合、この手法は機能しません。

于 2012-05-03T23:49:32.250 に答える
2

Bloom Filtersで問題を部分的に解決できます。これが機能する方法は、アイテムのセットのメンバーシップをテストするために、ハッシュ関数を定義して各アイテムをビットキーにマップすることです。element を挿入するには、フィルタのビットを...の位置に 1 に設定します。 element を検索する場合、 ...のいずれかでゼロのビットを検出すると、 がセットに含まれていないことが保証されます。ただし、N、M、および K の値によっては、誤検知が発生する可能性がわずかにあります (つまり、ハッシュ関数からゼロを検出せず、以前にフィルターに格納されていなかった)。NKMah1(a)hk(a)bh1(b)hk(b)bb

擬似コード:

const int M = 256;
typedef std::bitset<M> Mask;

int listValues[N] = { v1, ... , vN };
typedef unsigned char (*)(int) HashFunction; // maps int to 0...255
HashFunction hash[K] = { h1, ..., hK };

Mask make_mask(int x)
{
    Mask m(0):
    for (int i = 0; i < K; ++i) { 
        m[(hash[i])(x)] = 1; // update mask with item's hash
    }
    return(m);
}    

// initialize
Mask BloomFilter(0);
for (int i = 0; i < N; ++i) {        
    BloomFilter |= make_mask(listValues[i]);
}

// probe
bool is_not_in_filter(const Mask& F, int x)
{
    // if a zero-bit in F matches a 1-bit in make_mask(x), then x is not in F
    return ~F & make_mask(x) != 0; 
}

// call
int x = ...;
bool in_set = is_not_in_filter(BloomFilter, x);

事実上、これは各項目を M ビットのキーに展開し、フィルタはすべての項目のビットごとの OR を集約したものです。set-membership のテストは、NEGATED フィルターとテスト対象の M ビット拡張アイテムとの間の単純な (確率論的ではありますが) ビット単位の AND になります。

更新: 上記のコードは、それがどのように機能するかを説明するための擬似コードです。実際のライブラリを取得するには、実験的なBoost.BloomfiltersまたはBloomなどを参照してください。

于 2012-05-04T12:55:42.100 に答える
-1

129番なのか17番なのかをどうやって確認したらいいのかとおっしゃっていると思います。

int[] lstValues = [0,1, 10, 17, 18, 19, 129];
foreach(int value in lstValues) {
    if(lstValues == 129 || lstValues == 17) 
        printf("\nValue is in the mask");
    else 
        printf("\nValue is not in the mask");
}
于 2012-05-03T23:50:32.263 に答える