ここで大声で考えただけですが、これがアルゴリズム的に意味があるかどうか見てみましょう。
すべてのページについて、次の 3 つのフィールドを保存します。
ユーザーがページにアクセスすると、そのユーザーのハッシュが生成されます。そのハッシュがすでにブルーム フィルターにある場合は、ビュー カウンターを上げてください。
ブルーム フィルターにない場合は、両方のカウンターをバンプし、そのハッシュをフィルターに追加します。ただし、ハッシュによっては、ブルーム フィルター メンバーシップ チェックで誤検出が発生する可能性があります (ただし、誤検出は発生しません)。そのため、ハッシュ アルゴリズムの選択方法には注意してください。
3 つのフィールド。悪くない。:)
参照:ウィキペディアのブルーム フィルター
編集:私はこのコードをしばらくの間浮かんでいました-コアが最初にどこから来たのかわかりませんが、何年にもわたって微調整しました-LINQPadの準備ができました:
void Main()
{
var estimatedCount = 100000;
var falsePositiveProbability = 0.001;
var falsePositiveCount = 0;
var memberCount = 0;
var bloom = BloomFilter<char>.Create(
estimatedCount,
falsePositiveProbability,
c => c.GetHashCode(),
c => (int)c);
var allChars = Enumerable.Range(0, 0xffff).Select(i => (char)i).ToList();
foreach(var c in allChars)
{
var alreadyIn = bloom.Test(c);
if(alreadyIn)
{
falsePositiveCount++;
}
bloom.Add(c);
memberCount++;
}
Console.WriteLine("Predicted count: {0} Predicted false positive: {1:p} ", estimatedCount, falsePositiveProbability);
Console.WriteLine("Actual false positive count: {0} Actual member count: {1} ", falsePositiveCount, memberCount);
Console.WriteLine("False positive rate: {0:p}", ((double)falsePositiveCount / memberCount));
}
// Define other methods and classes here
public class BloomFilter<TValue>
{
private BitArray hashbits;
private int numKeys;
private Func<TValue,int> _hashFunc1;
private Func<TValue,int> _hashFunc2;
public static BloomFilter<TValue> Create(int estimateCount, double falsePositiveRate, Func<TValue,int> hash1, Func<TValue,int> hash2)
{
// formulae courtesy of http://hur.st/bloomfilter
var tableSize = Math.Ceiling((estimateCount * Math.Log(falsePositiveRate)) / Math.Log(1.0 / (Math.Pow(2.0, Math.Log(2.0)))));
var keyCount = Math.Round(Math.Log(2.0) * tableSize / estimateCount);
return new BloomFilter<TValue>((int)tableSize, (int)keyCount)
{
_hashFunc1 = hash1,
_hashFunc2 = hash2
};
}
private BloomFilter(int tableSize, int nKeys)
{
numKeys = nKeys;
hashbits = new BitArray(tableSize);
}
public bool Test(TValue val)
{
var hashKeys = GenerateHashes(val);
foreach (int hash in hashKeys)
{
if (!hashbits[hash])
return false;
}
return true;
}
public bool Add(TValue val)
{
bool rslt = true;
var hashKeys = GenerateHashes(val);
foreach (int hash in hashKeys)
{
if (!hashbits[hash])
{
rslt = false;
hashbits[hash] = true;
}
}
return rslt;
}
private int[] GenerateHashes(TValue val)
{
int hash1 = _hashFunc1(val);
int hash2 = _hashFunc2(val);
var hashKeys = new int[numKeys];
hashKeys[0] = Math.Abs(hash1 % hashbits.Count);
if (numKeys > 1)
{
for (int i = 1; i < numKeys; i++)
{
hashKeys[i] = Math.Abs((hash1 + (i * hash2)) %
hashbits.Count);
}
}
return hashKeys;
}
}