Structure de données PHP : utilisation intelligente des filtres Bloom pour obtenir une récupération efficace des collections

Le filtre Bloom est une structure de données peu encombrante utilisée pour déterminer si un élément appartient à un ensemble. Il utilise une fonction de hachage et un tableau de bits pour déterminer efficacement si l'élément est présent, éventuellement avec des faux positifs. Il convient aux scénarios dans lesquels un grand nombre d'éléments doivent être récupérés rapidement, comme la détection des doublons d'URL.

Structure de données PHP : utilisez intelligemment les filtres Bloom pour obtenir une récupération efficace des collections

Introduction

Un filtre Bloom est une structure de données très économe en espace utilisée pour déterminer si un élément appartient à une collecte. Il utilise une fonction de hachage et un tableau de bits pour déterminer efficacement si l'élément est présent.

Principe

Le filtre Bloom initialise un tableau de bits, et chaque position est initialement 0. Ensuite, les éléments sont hachés à l'aide de plusieurs fonctions de hachage, le tableau de bits est indexé avec la valeur de hachage et la valeur à cette position est définie sur 1.

Si un élément appartient à l'ensemble, sa valeur de hachage trouvera au moins une position dans le tableau de bits qui est 1. Cependant, il est également possible de trouver une position de 1 pour un élément n'appartenant pas à l'ensemble, appelé faux positif.

Mise en œuvre

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;
    }
}

Cas pratique : Détecter les doublons d'URL

Objectif : Utilisez le filtre Bloom pour détecter rapidement si un grand nombre d'URL ont été explorées.

Mise en œuvre :

1. Initialisez le filtre Bloom, définissez la taille et le nombre de fonctions de hachage.
2. Appelez la méthode add() pour chaque URL explorée pour l'ajouter au filtre. add() 方法将其添加到过滤器中。
3. 当遇到新的 URL 时，使用 isExists()
Lorsque vous rencontrez une nouvelle URL, utilisez la méthode isExists() pour vérifier rapidement si elle existe déjà dans le filtre. Si elle existe, l'URL est ignorée ; sinon, la nouvelle URL est ajoutée au filtre.

Avantages :

• Efficace en termes d'espace : la taille du filtre Bloom n'a rien à voir avec le nombre d'éléments qui doivent être détectés.
• Récupération rapide : en utilisant des fonctions de hachage, les opérations de récupération ne nécessitent pas de parcourir toute la collection.
• Taux d'erreur acceptable : les filtres Bloom autorisent certains faux positifs, mais la taille et le nombre de fonctions de hachage peuvent être ajustés selon les besoins pour optimiser le taux d'erreur.

🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!