Salut, habrozhiteli! Les algorithmes sont le cœur et l'âme de l'informatique. Vous ne pouvez pas vous en passer, ils sont partout - du routage réseau et des calculs génomiques à la cryptographie et à l'apprentissage automatique. L '«algorithme parfait» fera de vous un véritable pro qui définira les tâches et les résoudra magistralement à la fois dans la vie et lors d'un entretien lors de l'embauche d'une entreprise informatique.
Dans le deuxième livre, Tim Rafgarden, le gourou des algorithmes, parle de la recherche de graphes et de son application, de l'algorithme de recherche de chemin le plus court, et de l'utilisation et de la mise en œuvre de certaines structures de données: tas, arbres de recherche, tables de hachage et filtre Bloom.
Cet article présente un extrait de Bloom Filters: The Basics.
De quoi parle ce livre
La deuxième partie du livre «Algorithme parfait» est un cours d'introduction sur les bases de l'alphabétisation sur les trois sujets suivants.
Recherche graphique et applications . Les graphiques modélisent un certain nombre de types de réseaux différents, notamment la route, la communication, les réseaux sociaux et les réseaux de dépendances entre les tâches. Les graphiques peuvent être complexes, mais il existe des primitives incroyablement rapides pour parler de la structure des graphiques. Nous commencerons par des algorithmes de recherche de graphes linéaires, depuis des applications allant de l'analyse de réseau à la construction d'une séquence d'opérations.
Les chemins les plus courts . Dans le problème de chemin le plus court, l'objectif est de calculer le meilleur itinéraire dans le réseau du point A au point B. Cette tâche a des applications évidentes, telles que le calcul des itinéraires de trafic, et se produit également sous forme déguisée dans de nombreuses autres tâches universelles. Nous généraliserons l'un de nos algorithmes de recherche de graphes et arriverons au célèbre algorithme de recherche de chemin le plus court de Dijkstra.
Structures de données . Ce livre fera de vous un utilisateur très instruit de plusieurs structures de données différentes conçues pour prendre en charge un ensemble évolutif d'objets avec leurs clés associées. L'objectif principal est de développer une intuition sur la structure de données qui convient à votre application. Des sections supplémentaires fournissent des instructions pour implémenter ces structures de données à partir de zéro.
Tout d'abord, nous discutons des tas qui peuvent rapidement identifier l'objet stocké avec la plus petite clé, et sont également utiles pour le tri, la mise en œuvre d'une file d'attente prioritaire et la mise en œuvre de l'algorithme presque linéaire-temporel de Dijkstra. Les arborescences de recherche maintiennent l'ordre complet des clés sur les objets stockés et prennent en charge une gamme d'opérations encore plus large. Les tables de hachage sont optimisées pour les opérations de recherche ultrarapides et sont répandues dans les programmes modernes. Nous examinons également le filtre Bloom, un proche parent de la table de hachage, qui utilise moins d'espace en raison d'erreurs aléatoires.
Vous pouvez vous familiariser avec le contenu du livre plus en détail dans les sections «Conclusions», qui complètent chaque chapitre et identifient les points les plus importants. Les sections du livre, marquées d'un astérisque, sont les plus avancées en termes de niveau d'information présenté. Si le livre est conçu pour une familiarisation superficielle avec le sujet, le lecteur peut les ignorer sans perdre l'intégrité de l'écrit.
Sujets traités en trois autres parties . La première partie du livre «Algorithme parfait. Fundamentals »couvre la notation asymptotique (la notation O-large et ses proches parents), les algorithmes« diviser pour mieux régner »et le théorème de la relation de récurrence principale - la méthode principale, le tri rapide randomisé et son analyse, ainsi que les algorithmes de sélection linéaire-temporelle. La troisième partie traite des algorithmes gourmands (planification, travées minimales, clustering, codes Huffman) et de la programmation dynamique (problème de sac à dos, alignement de séquence, chemins les plus courts, arbres de recherche optimaux). La quatrième partie est consacrée à l'exhaustivité de NP, à ce qu'elle signifie pour un concepteur d'algorithmes et aux stratégies de résolution de problèmes de calcul insolubles, y compris l'analyse heuristique et la recherche locale.
12.5. Filtres Bloom: les bases
Les filtres Bloom sont des parents proches des tables de hachage. Ils sont très compacts, mais font régulièrement des erreurs. Cette section décrit comment les filtres Bloom sont bons et comment ils sont mis en œuvre, tandis que la section 12.6 présente une courbe de compromis entre la quantité d'espace utilisé par le filtre et son taux d'erreur.
12.5.1. Opérations prises en charge
La raison de l'existence de filtres Bloom est essentiellement la même que celle d'une table de hachage: opérations d'insertion et de visualisation ultra-rapides, grâce auxquelles vous pouvez vous rappeler rapidement ce que vous avez vu et ce qui ne l'a pas été. Pourquoi devrions-nous être gênés par une structure de données différente avec le même ensemble d'opérations? Parce que les filtres Bloom sont préférables aux tables de hachage dans les applications où l'espace vaut son pesant d'or, et une erreur aléatoire n'est pas un obstacle à la transaction.
Comme les tables de hachage avec adressage ouvert, les filtres Bloom sont beaucoup plus faciles à implémenter et à imaginer lorsqu'ils ne prennent en charge que les opérations d'insertion et de visualisation (et sans l'opération de suppression). Nous allons nous concentrer sur ce cas.
FILTRES BLOOM: OPÉRATIONS SUPPORTÉES
Vue: avec la touche k, retournez «oui» si k a été précédemment inséré dans le filtre Bloom, et «non» sinon.
Coller: ajoutez une nouvelle clé k au filtre Bloom.
Les filtres Bloom sont très efficaces sur le plan spatial; généralement, ils peuvent nécessiter seulement 8 bits par insert. C'est assez incroyable, car 8 bits est complètement insuffisant pour se souvenir même d'une clé 32 bits ou d'un pointeur sur un objet! Pour cette raison, l'opération Afficher dans le filtre Bloom renvoie uniquement la réponse «oui» / «non», tandis que dans la table de hachage, cette opération renvoie un pointeur sur l'objet souhaité (s'il est trouvé). C'est pourquoi l'opération d'insertion accepte désormais uniquement la clé et non le (pointeur vers) l'objet.
Contrairement à toutes les autres structures de données que nous avons étudiées, les filtres Bloom peuvent être erronés. Il existe deux types d'erreurs: les faux négatifs lorsque l'opération View renvoie «false» même si la clé demandée a déjà été insérée plus tôt, et les fausses déclarations (ou positives) lorsque l'opération View renvoie «true», bien que la clé demandée n'ait pas encore été insérée dans le passé. . Dans la section 12.5.3, nous verrons que les filtres Bloom de base ne souffrent jamais de faux négatifs, mais ils peuvent avoir des «éléments fantômes» sous la forme de fausses déclarations. La section 12.6 montre que la fréquence des fausses déclarations peut être contrôlée en ajustant de manière appropriée l'utilisation de l'espace. Une implémentation typique d'un filtre Bloom peut avoir un taux d'erreur d'environ 1% ou 0,1%.
Les temps d'exécution des opérations d'insertion et de visualisation sont aussi rapides que dans la table de hachage. Et mieux encore, ces opérations sont garanties d'être effectuées en temps constant, quelle que soit la mise en œuvre du filtre Bloom et de l'ensemble de données1. Cependant, l'implémentation et l'ensemble de données affectent le taux d'erreur du filtre.
Pour résumer les avantages et les inconvénients des filtres Bloom sur les tables de hachage:
FILTRE BLOOM CONTRE LES TABLES DE HACHAGE
1. Avantages: plus efficace spatialement.
2. Avantages: opérations permanentes garanties pour chaque ensemble de données.
3. Inconvénients: impossible de stocker des pointeurs sur des objets.
4. Inconvénients: suppressions plus complexes par rapport à une table de hachage avec un embrayage.
5. Inconvénients: probabilité non nulle d'une fausse déclaration.
La liste des indicateurs pour les filtres Bloom de base est la suivante.
Tableau 12.4. Filtres Bloom de base: opérations prises en charge et leur temps d'exécution. Le signe de la dague (†) indique que l'opération de visualisation a une probabilité contrôlable mais non nulle de fausses déclarations
Les filtres Bloom doivent être utilisés à la place des tables de hachage dans les applications où leurs avantages sont importants et leurs inconvénients ne sont pas un obstacle à la transaction.
QUAND UTILISER LE FILTRE BLOOM
Si une application nécessite une recherche rapide avec un ensemble d'objets en évolution dynamique, l'espace vaut son pesant d'or et un petit nombre acceptable de fausses allégations, alors le filtre Bloom est généralement la structure de données préférée.
12.5.2. Les applications
Ensuite, il y a trois utilisations avec des analyses répétées, où économiser de l'espace peut être important, et les fausses déclarations ne sont pas un obstacle à la transaction.
Correcteurs orthographiques. Dans les années 1970, les filtres Bloom étaient utilisés pour implémenter des correcteurs orthographiques - correcteurs orthographiques. Au stade du prétraitement, chaque mot du dictionnaire est inséré dans le filtre Bloom. L'orthographe d'un document se résume à une opération. Regardez un mot dans un document, en marquant tous les mots pour lesquels cette opération renvoie «non».
Dans cette annexe, une fausse déclaration correspond à un mot invalide que le correcteur orthographique accepte par inadvertance. De telles erreurs ne rendaient pas les vérificateurs orthographiques idéaux. Cependant, au début des années 1970, l'espace valait son pesant d'or, donc l'utilisation de filtres Bloom à cette époque était une stratégie gagnant-gagnant.
Mots de passe interdits . Une ancienne application qui reste valable à ce jour suit les mots de passe interdits - des mots de passe trop courants ou trop faciles à deviner. Initialement, tous les mots de passe interdits sont insérés dans le filtre Bloom; des mots de passe interdits supplémentaires peuvent être insérés ultérieurement, si nécessaire. Lorsqu'un utilisateur essaie de définir ou de réinitialiser son mot de passe, le système recherche le mot de passe proposé dans le filtre Bloom. Si la recherche renvoie «oui», l'utilisateur est invité à réessayer avec un mot de passe différent. Ici, une fausse déclaration est traduite en un mot de passe fort, que le système rejette.
Pourvu que le taux d'erreur ne soit pas trop élevé, disons pas plus de 1% ou 0,1%, cela n'a pas beaucoup d'importance. De temps en temps, certains utilisateurs auront besoin d'une nouvelle tentative pour trouver un mot de passe acceptable pour le système.
Routeurs Internet . Un certain nombre d'applications étonnantes de filtres Bloom se déroulent au plus profond d'Internet, où les paquets de données transitent par des routeurs avec une vitesse de streaming. Il existe de nombreuses raisons pour lesquelles un routeur peut vouloir rappeler rapidement ce qu'il a vu dans le passé. Par exemple, un routeur peut vouloir trouver l'adresse IP source d'un paquet dans la liste des adresses IP bloquées, suivre le contenu du cache afin d'éviter les vues de cache parasites ou conserver des statistiques qui aident à identifier une attaque de réseau par déni de service. Le taux d'arrivée des paquets nécessite des vues ultrarapides et la mémoire limitée du routeur fait de l'espace un pesant d'or. Ces applications sont directement gérées par le filtre Bloom.
12.5.3. Implémentation
En regardant à l'intérieur du filtre Bloom, vous pouvez voir une mise en œuvre élégante. La structure de données prend en charge une chaîne de n bits ou, également, un tableau A de longueur n dans lequel chaque élément est 0 ou 1. (Tous les éléments sont initialisés à zéro.) Cette structure utilise également m fonctions de hachage h1, h2, ..., hm , tandis que chacun mappe l'univers U de toutes les clés possibles à l'ensemble {0, 1, 2, ..., n - 1} de positions dans le tableau. Le paramètre m est proportionnel au nombre de bits utilisés par le filtre Bloom pour l'insertion et, en règle générale, est une petite constante (par exemple, 5).
Chaque fois qu'une clé est insérée dans un filtre Bloom, chacune des m fonctions de hachage définit un indicateur, définissant le bit correspondant du tableau A sur 1.
FILTRE BLOOM: INSÉRER (SUR TOUCHE)
for i = 1 to m do A[hi(k)] := 1
Par exemple, si m = 3 et h1 (k) = 23, h2 (k) = 17 et h3 (k) = 5, l'insertion de k entraîne la mise à égalité des 5e, 17e et 23e bits du tableau. 1 (Fig.12.5).
Dans l'opération Afficher, le filtre Bloom recherche l'empreinte digitale qui aurait pu rester sur l'insert k.
FILTRE BLOOM: VUE (TOUCHE CLÉ)
for i = 1 to m do if A [hi (k)] = 0 then return «» return «»
Nous pouvons maintenant voir pourquoi les filtres Bloom ne peuvent pas souffrir de faux négatifs. Lorsque la clé k est insérée, les m bits correspondants sont mis à 1. Pendant la durée de vie du filtre Bloom, les bits peuvent changer leur valeur de 0 à 1, mais pas l'inverse. Ainsi, ces m bits restent 1 pour toujours. Chaque opération View k suivante est garantie de renvoyer la bonne réponse oui.
Nous pouvons également voir comment de fausses déclarations surviennent. Supposons que m = 3 et les quatre clés k1, k2, k3, k4 aient les valeurs de hachage suivantes:
Supposons que nous insérions k1, k2, k3 et k4 dans un filtre Bloom (figure 12.6). Ces trois insertions conduisent à un total de neuf bits mis à 1, dont trois bits dans l'empreinte digitale de la clé k1 (5, 17 et 23). À ce stade, le filtre Bloom ne peut plus distinguer si la clé k1 a été insérée ou non. Même si k1 n'a pas été inséré dans le filtre, la recherche retournera «oui», ce qui est une fausse déclaration.
Intuitivement, nous pouvons supposer qu'avec une augmentation de la taille n du filtre Bloom, le nombre de superpositions entre les empreintes digitales de différentes clés devrait diminuer, ce qui, à son tour, conduit à un plus petit nombre de fausses déclarations. Mais l'objectif principal du filtre Bloom est de gagner de l'espace. Existe-t-il un terrain d'entente où n et la fréquence des fausses déclarations sont simultanément petits? La réponse n'est pas évidente et nécessite une analyse mathématique entreprise dans la section suivante.
»Plus d'informations sur le livre sont disponibles sur
le site Web de l'éditeur»
Contenu»
ExtraitPour Khabrozhiteley 20% de réduction sur le coupon -
AlgorithmesLors du paiement de la version papier du livre, un livre électronique est envoyé par e-mail.