PHP 데이터 구조: Bloom 필터를 영리하게 사용하여 효율적인 컬렉션 검색 달성

블룸 필터는 요소가 집합에 속하는지 여부를 결정하는 데 사용되는 공간 효율적인 데이터 구조입니다. 해시 함수와 비트 배열을 사용하여 요소가 존재하는지(오탐 가능성이 있음) 효율적으로 찾습니다. URL 중복 감지와 같이 많은 수의 요소를 신속하게 검색해야 하는 시나리오에 적합합니다.

PHP 데이터 구조: Bloom 필터를 영리하게 사용하여 효율적인 컬렉션 검색을 달성하세요

Introduction

Bloom 필터는 요소가 수집에 속하는지 여부를 결정하는 데 사용되는 매우 공간 효율적인 데이터 구조입니다. 해시 함수와 비트 배열을 사용하여 요소의 존재 여부를 효율적으로 찾습니다.

원리

블룸 필터는 비트 배열을 초기화하며 각 위치는 초기에 0입니다. 그런 다음 요소는 여러 해시 함수를 사용하여 해시되고 비트 배열은 해시 값으로 인덱싱되며 해당 위치의 값은 1로 설정됩니다.

요소가 집합에 속하는 경우 해당 해시 값은 비트 배열에서 1인 위치를 하나 이상 찾습니다. 그러나 집합에 속하지 않는 요소에 대해 위치 1을 찾는 것도 가능하며, 이를 거짓양성(false positive)이라고 합니다.

구현

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을 건너뛰고, 그렇지 않은 경우 새 URL이 필터에 추가됩니다.

장점:

• 공간 효율성: 블룸 필터 크기는 감지해야 하는 요소 수와 아무 관련이 없습니다.
• 빠른 검색: 해시 함수를 사용하면 검색 작업 시 전체 컬렉션을 탐색할 필요가 없습니다.
• 허용되는 오류율: 블룸 필터는 일부 거짓 긍정을 허용하지만 오류율을 최적화하기 위해 필요에 따라 해시 함수의 크기와 수를 조정할 수 있습니다.

🎜

위 내용은 PHP 데이터 구조: Bloom 필터를 영리하게 사용하여 효율적인 컬렉션 검색 달성의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!