C# を使用してブルーム フィルター アルゴリズムを作成する方法

C# を使用してブルーム フィルター アルゴリズムを作成する方法

ブルーム フィルターは、要素が次の要素に属するかどうかの判断に使用できる、非常にスペース効率の高いデータ構造です。セット。その基本的な考え方は、複数の独立したハッシュ関数を通じて要素をビット配列にマッピングし、対応するビット配列のビットを 1 としてマークすることです。要素が集合に属するかどうかを判断するには、対応するビット配列のビットがすべて 1 であるかどうかを判断するだけで済みます。いずれかのビットが 0 であれば、その要素は集合に含まれていないと判断できます。ブルーム フィルターは、高速なクエリと小さなスペース占有という特徴を備えており、多くのシナリオで広く使用されています。

この記事では、C# を使用してブルーム フィルター アルゴリズムを作成する方法を紹介し、具体的なコード例を示します。

まず、ブルーム フィルター クラスを定義し、必要な変数とメソッドを宣言する必要があります。以下は、単純なブルーム フィルター クラスの定義です。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Security.Cryptography;

public class BloomFilter
{
    private BitArray _bits;
    private int _hashFunctionsCount;

    public BloomFilter(int capacity, double falsePositiveRate)
    {
        int bitsCount = GetBitsCount(capacity, falsePositiveRate);
        _bits = new BitArray(bitsCount);
        _hashFunctionsCount = GetHashFunctionsCount(bitsCount, capacity);
    }

    public void Add(string item)
    {
        foreach (int hash in GetHashes(item))
        {
            _bits.Set(Math.Abs(hash % _bits.Length), true);
        }
    }

    public bool Contains(string item)
    {
        foreach (int hash in GetHashes(item))
        {
            if (!_bits[Math.Abs(hash % _bits.Length)])
            {
                return false;
            }
        }
        return true;
    }

    private IEnumerable<int> GetHashes(string item)
    {
        using (SHA256 sha256 = SHA256.Create())
        {
            byte[] hashBytes = sha256.ComputeHash(System.Text.Encoding.UTF8.GetBytes(item));
            for (int i = 0; i < _hashFunctionsCount; i++)
            {
                yield return BitConverter.ToInt32(hashBytes, i * 4);
            }
        }
    }

    private int GetBitsCount(int capacity, double falsePositiveRate)
    {
        return (int)Math.Ceiling(capacity * Math.Log(falsePositiveRate) / Math.Log(1 / Math.Pow(2, Math.Log(2))));
    }

    private int GetHashFunctionsCount(int bitsCount, int capacity)
    {
        return (int)Math.Round((double)(bitsCount / capacity) * Math.Log(2));
    }
}

上記のコードは、コンストラクター、Add メソッド、および を含む BloomFilter クラスを定義します。 メソッドが含まれています。コンストラクターは、容量と誤検知率の 2 つのパラメーターを受け取り、これらの 2 つのパラメーターに基づいて、必要なビット配列のサイズとハッシュ関数の数が計算されます。 Add メソッドは、ブルーム フィルターに要素を追加し、複数のハッシュ関数を通じて要素をビット配列にマップし、対応するビット配列のビットを 1 としてマークするために使用されます。 Contains メソッドは、ブルーム フィルターに要素が存在するかどうかを判断し、複数のハッシュ関数を通じて要素をビット配列にマップし、対応するビット配列のビットがすべて 1 であるかどうかを判断するために使用されます。

次に、ブルーム フィルター クラスをテストに使用できます。以下は簡単な例です。

using System;

public class Program
{
    public static void Main(string[] args)
    {
        BloomFilter bloomFilter = new BloomFilter(100000, 0.01);

        bloomFilter.Add("apple");
        bloomFilter.Add("banana");
        bloomFilter.Add("orange");

        Console.WriteLine(bloomFilter.Contains("apple")); // 输出：True
        Console.WriteLine(bloomFilter.Contains("banana")); // 输出：True
        Console.WriteLine(bloomFilter.Contains("orange")); // 输出：True
        Console.WriteLine(bloomFilter.Contains("watermelon")); // 输出：False
    }
}

上記のコード例は、ブルーム フィルター オブジェクトを作成し、それに 3 つの要素 (「リンゴ」、「バナナ」、「オレンジ」) を追加します。次に、Contains メソッドを使用して、ブルーム フィルターに要素が存在するかどうかを確認します。

なお、ブルームフィルタには一定の誤判定率があるため、ブルームフィルタに含まれるか否かを判定する際に誤判定が発生する可能性があります。したがって、ブルーム フィルターは、URL が訪問されたかどうかを判断するなど、特定の誤判定率が許容されるシナリオに主に適しています。

要約すると、この記事では、C# を使用してブルーム フィルター アルゴリズムを作成する方法を紹介し、関連するコード例を示します。効率的なデータ構造として、ブルーム フィルターはいくつかの特定のシナリオで重要なアプリケーション価値を持っています。この記事がブルーム フィルター アルゴリズムの理解と適用に役立つことを願っています。

以上がC# を使用してブルーム フィルター アルゴリズムを作成する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。