PHP データ構造: 効率的なコレクション取得を実現するためのブルーム フィルターの賢明な使用

ブルーム フィルターは、要素がセットに属しているかどうかを判断するために使用されるスペース効率の高いデータ構造です。ハッシュ関数とビット配列を使用して、要素が存在するかどうかを効率的に検索します (誤検知も発生する可能性があります)。 URL 重複検出など、多数の要素を迅速に取得する必要があるシナリオに適しています。

PHP データ構造: ブルーム フィルターを賢く使用して、効率的なコレクションの取得を実現します

はじめに

ブルーム フィルターは、要素がギャザリングに属するかどうかを決定するために使用される、スペース効率の高いデータ構造です。ハッシュ関数とビット配列を使用して、要素が存在するかどうかを効率的に検索します。

原理

ブルームフィルターはビット配列を初期化し、各位置は最初は0です。次に、複数のハッシュ関数を使用して要素がハッシュされ、ビット配列にハッシュ値のインデックスが付けられ、その位置の値が 1 に設定されます。

要素がセットに属している場合、そのハッシュ値はビット配列内で 1 である位置を少なくとも 1 つ見つけます。ただし、セットに属さない要素の 1 の位置を見つけることも可能であり、これは偽陽性と呼ばれます。

実装

class BloomFilter {

    // 过滤器大小 (位数)
    private $size;

    // 哈希函数个数
    private $numHashes;

    // 哈希函数
    private $hashFunctions;

    // 过滤器位数组
    private $filter;

    // 初始化布隆过滤器
    public function __construct($size, $numHashes) {
        $this->size = $size;
        $this->numHashes = $numHashes;
        $this->initHashFunctions();
        $this->filter = array_fill(0, $this->size, 0);
    }

    // 初始化哈希函数
    private function initHashFunctions() {
        $this->hashFunctions = [];
        for ($i = 0; $i < $this->numHashes; $i++) {
            $this->hashFunctions[] = function ($key) use ($i) {
                return abs(crc32($key . $i));
            };
        }
    }

    // 向过滤器中添加元素
    public function add($element) {
        foreach ($this->hashFunctions as $hashFunction) {
            $index = $hashFunction($element) % $this->size;
            $this->filter[$index] = 1;
        }
    }

    // 检查元素是否存在过滤器中
    public function isExists($element) {
        foreach ($this->hashFunctions as $hashFunction) {
            $index = $hashFunction($element) % $this->size;
            if ($this->filter[$index] == 0) {
                return false;
            }
        }
        // 找到了元素的所有哈希值对应的位，但可能是假阳性
        return true;
    }
}

実際のケース: URLの重複を検出

目標: ブルームフィルターを使用して、多数のURLがクロールされたかどうかを迅速に検出します。

実装:

1. ブルームフィルターを初期化し、ハッシュ関数のサイズと数を設定します。
2. クロールされた URL ごとに add() メソッドを呼び出して、フィルタに追加します。 add() 方法将其添加到过滤器中。
3. 当遇到新的 URL 时，使用 isExists()
新しい URL を見つけた場合は、isExists() メソッドを使用して、それがフィルター内にすでに存在するかどうかをすばやく確認します。存在する場合、その URL はスキップされ、存在しない場合は、新しい URL がフィルタに追加されます。

利点:

• スペース効率: ブルームフィルターのサイズは、検出する必要がある要素の数とは関係がありません。
• 高速な取得: ハッシュ関数を使用すると、取得操作でコレクション全体を走査する必要がなくなります。
• 許容可能なエラー率: ブルーム フィルターでは一部の誤検知が許容されますが、必要に応じてハッシュ関数のサイズと数を調整してエラー率を最適化できます。

🎜

以上がPHP データ構造: 効率的なコレクション取得を実現するためのブルーム フィルターの賢明な使用の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。