C'est un peu difficile, alors je vais vous donner un exemple. Ce n'est ni un cas d'utilisation approprié ni une réalité.
Dans ce cas
Sera.
Ici, comme suit Si l'application a une liste indiquant si le numéro de compte existe ou non Il n'est pas nécessaire de se soucier de demander à la base de données l'existence du numéro de compte via le réseau.
| numéro de compte |
|---|
| 111-111-111 |
| 222-222-222 |
| 333-333-333 |
| ......... |
** Cependant, si le numéro de compte est énorme, il est difficile pour l'application pour smartphone de conserver autant d'informations. ** ** ** Dans un tel cas, si vous utilisez BloomFilter, vous pouvez avoir des informations très compactes qui vous indiquent "presque" si votre numéro de compte existe ou non. ** **
L'explication détaillée est [Wiki](https://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AB%E3%83%BC%E3%83%A0%E3%83%95% E3% 82% A3% E3% 83% AB% E3% 82% BF).
A ce moment, il y a une pluralité de positions où 1 se trouve.
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
|---|
Si cela est répété pour tous les numéros de compte, le nombre de positions où 1 se trouve augmentera.
Si vous avez cet enregistrement lorsque vous entrez le numéro de compte dans l'application ci-dessus ** Exactement le même hachage ⇒ Effectuer une conversion de chaîne de 01 bits et faire correspondre la partie où 1 se trouve avec l'enregistrement ** ** Si tous les 1 sont définis, cela signifie que la probabilité que le numéro de compte existe est extrêmement élevée. ** **
--En haut: enregistrements avec des informations sur tous les numéros de compte
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
⇒ Puisque 1 est défini dans toutes les positions cibles, il est très probable que l'enregistrement existe.
** «Extrêmement cher» n'est pas absolu. ** ** Parce que la position où 1 est en conflit avec d'autres numéros de compte Il est possible que 1 soit mis à cette position par la chaîne de bits d'autres informations de numéro de compte.
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
Entrez ici le numéro de compte inexistant "999-999-999" Si le résultat de la conversion de hachage ⇒ 01 bit est le suivant, il est déterminé que les données existent par erreur.
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
S'il y a même un 0 dans la position où 1 se trouve, il peut être déterminé à 100% qu'il n'y a pas de données. Même s'il y a un 1 dans la position où tous les 1 se trouvent, il ne peut pas être confirmé à 100% qu'il y a des données. ** Nous disons qu'il n'y a pas de faux négatifs, mais il y a de faux positifs. ** **
Prendre un enregistrement suffisamment long réduira les faux positifs, Si vous prenez un enregistrement trop long, la capacité sera réduite.
** Cependant, pour 1 million de numéros de compte (n'importe quel nombre de chiffres) ** ** Les faux positifs convergent vers environ 1% s'il existe une région d'environ 1,2 Mo. ** ** ** Si une région d'environ 1,8 Mo peut être préparée, les faux positifs convergeront vers environ 0,1%. ** **
Ainsi, avec une application comme celle ci-dessus, il vous suffit de conserver quelques enregistrements L'accès au réseau et l'accès à la base de données peuvent être considérablement supprimés.
Dans ce cas, chaque fois qu'un nouveau compte est ajouté *
Il y a un point pour télécharger l'enregistrement mis à jour. *
Lorsque les données sont stockées dans plusieurs stockages ou segments *
Il peut également être utilisé pour rechercher efficacement des emplacements de stockage de données, mais il est difficile de le transmettre *
Je ne pouvais pas penser immédiatement à d'autres bons cas d'utilisation qui pourraient être facilement expliqués, alors pardonnez-moi. *
Je publierai l'implémentation en Java telle quelle.
MyBloomFilter.java
import java.io.Serializable;
import java.nio.charset.Charset;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
/**
*N'a que les fonctionnalités les plus basiques de BloomFilter
* @author owl
* @param <E>
*/
public class MyBasicBloomFilter<E> implements Serializable {
private final BitSet bitFilter; //Corps de filtre
private final int bitFilterSize; //Taille du filtre
private int numberOfAddedElements; //Nombre actuel d'éléments
private final int countOfHashNumCreatePerOneElement; //Nombre de vrais bits par élément (hachage ⇒ Nombre de conversions numériques)
static final Charset DEFAULT_CHARSET = Charset.forName("UTF-8");
/**
*Faux niveau positif
* High:Faux positifs élevés, mais taille de filtre compacte et bonnes performances
*Milieu: équilibre les faux positifs, la taille du filtre et les performances
* Low:Gardez les faux positifs aussi bas que possible même si la taille du filtre est augmentée ou si le temps de traitement est long.
*/
public static enum FalsePositiveProbability{ High, Middle, Low }
/**
*Exécuter le résumé du message
*/
static final MessageDigest digestFunction;
static final String hashName = "MD5";
static {
MessageDigest tmp;
try { tmp = java.security.MessageDigest.getInstance(hashName); } catch (NoSuchAlgorithmException e) { tmp = null; }
digestFunction = tmp;
}
/**
*constructeur
* @param c Nombre de bits utilisés par élément
* @param n (nombre maximum attendu d'éléments)
* @Nombre de bits vrais par élément param k (hachage ⇒ nombre de conversions de nombres)
*/
public MyBasicBloomFilter(double c, int n, int k) {
this.countOfHashNumCreatePerOneElement = k;
//Nombre d'éléments*Déterminez la taille de bits du filtre par le nombre de bits utilisés par élément
this.bitFilterSize = (int)Math.ceil(c * n);
numberOfAddedElements = 0;
this.bitFilter = new BitSet(bitFilterSize);
}
/**
*
* @param expectedItemCount
* @param fpp
*/
public MyBasicBloomFilter(int expectedItemCount, FalsePositiveProbability fpp) {
switch(fpp){
case High : {
this.bitFilterSize = (int)Math.ceil(expectedItemCount * 4.8);
break;
}
case Low : {
this.bitFilterSize = (int)Math.ceil(expectedItemCount * (9.6 + 4.8));
break;
}
default : {
this.bitFilterSize = (int)Math.ceil(expectedItemCount * 9.6);
}
}
this.countOfHashNumCreatePerOneElement
= (int) Math.round((this.bitFilterSize / (double)expectedItemCount) * Math.log(2.0));
numberOfAddedElements = 0;
this.bitFilter = new BitSet(bitFilterSize);
}
public MyBasicBloomFilter(int expectedItemCount) {
this(expectedItemCount, FalsePositiveProbability.Middle);
}
/**
*Hashing
* @données param Données d'entrée
* @param hashCount Count
* @return Valeur numérique obtenue par hachage (position debout du bit)
*/
public static int[] createHashes(byte[] data, int hashCount) {
int[] result = new int[hashCount];
int k = 0;
byte seed = 0;
while (k < hashCount) {
//Hashing
byte[] digest;
synchronized (digestFunction) {
digestFunction.update(++seed);
digest = digestFunction.digest(data);
}
//Int à 4 octets délimiteur et pack dans le tableau
for (int i = 0; i < digest.length/4 && k < hashCount; i++) {
int h = 0;
for (int j = (i*4); j < (i*4)+4; j++) {
h <<= 8;
h |= ((int) digest[j]) & 0xFF;
}
result[k] = h;
k++;
}
}
return result;
}
/**
*Ajouter un élément
* @param element
*/
public void add(E element) {
add(element.toString().getBytes(DEFAULT_CHARSET));
}
/**
*Ajouter un élément
* @param bytes
*/
public void add(byte[] bytes) {
int[] hashes = createHashes(bytes, countOfHashNumCreatePerOneElement);
for (int hash : hashes) bitFilter.set(Math.abs(hash % bitFilterSize), true);
numberOfAddedElements ++;
}
/**
*Jugement
* @élément élément param
* @return
*/
public boolean contains(E element) {
return contains(element.toString().getBytes(DEFAULT_CHARSET));
}
/**
*Jugement
* @Tableau d'octets de l'élément param bytes
* @return
*/
public boolean contains(byte[] bytes) {
int[] hashes = createHashes(bytes, countOfHashNumCreatePerOneElement);
for (int hash : hashes) {
if (!bitFilter.get(Math.abs(hash % bitFilterSize))) {
return false;
}
}
return true;
}
/**
*Obtenir le filtre
* @filtre de retour
*/
public BitSet getBitSet() {
return bitFilter;
}
/**
*Obtenez le nombre d'articles ajoutés
* @nombre d'articles de retour
*/
public int getAddItemCount(){
return this.numberOfAddedElements;
}
public double getFalsePositiveProbability() {
// (1 - e^(-k * n / m)) ^ k
return
Math.pow((1 - Math.exp(-countOfHashNumCreatePerOneElement * (double) this.numberOfAddedElements
/ (double) bitFilterSize)), countOfHashNumCreatePerOneElement);
}
}
Échantillon d'appel
import java.util.ArrayList;
import java.util.List;
import org.apache.commons.lang.RandomStringUtils;
/**
*Essayez BloomFilter
* @author owl
*/
public class ExecBloomFilterSample {
public static void main(String argv[]){
MyBasicBloomFilter<String> bf = new MyBasicBloomFilter<>(1000000, MyBasicBloomFilter.FalsePositiveProbability.Low);
List<String> addList = new ArrayList<>(); //Données à ajouter à BloomFilter
List<String> notAddList = new ArrayList<>(); //Données non ajoutées à BloomFilter
//Ajout de 10000 données à BloomFilter
//En même temps, générez 10000 données de vérification qui ne sont pas ajoutées à BloomFilter
for(int i=0;i<2000000;i++){
if(i % 2 == 0) {
String s = RandomStringUtils.randomAlphabetic(24);
bf.add(s);
addList.add(s);
} else {
notAddList.add(RandomStringUtils.randomAlphabetic(24));
}
}
//Sortie de l'état de BloomFilter
for(int i=0; i < bf.getBitSet().size(); i++ ){
System.out.print(bf.getBitSet().get(i) ? "1" : "0");
if(i>1000) break;
}
//Taille des données de sortie BloomFilter et probabilité de faux positifs calculée
System.out.println();
System.out.println("Taille des données--> " + bf.getBitSet().size() + " | K-Nombre d'octets d'octets" + (double)((double)(bf.getBitSet().size())/8/1024));
System.out.println("Probabilité faussement positive--> " + String.format("%.5f", bf.getFalsePositiveProbability()));
//Vérifiez si toutes les données ajoutées à BloomFilter sont positives
//(S'il n'y a pas de problème, rien ne s'affiche)
System.out.println();
System.out.println("■■■■■ Commencez à vérifier si toutes les données supplémentaires sont positives ■■■■■");
addList
.stream()
.sequential()
.filter(e -> !bf.contains(e))
.forEach(e-> System.out.println("Jugement manquant:" + e));
//Nombre de sorties pour lesquelles les données non ajoutées à BloomFilter étaient faussement positives
System.out.println("■■■■■ Commencez à vérifier si des données non supplémentaires sont jugées faussement positives ■■■■■");
System.out.println("Dans 1000000 données..." +
notAddList
.stream()
.sequential()
.filter(e -> bf.contains(e))
.count() + "Un faux positif a été détecté.");
}
}
Résultat d'exécution
000011100100001110011011100010101001100110111000100011001(réduction)
Taille des données--> 14400000 | K-Nombre d'octets 1757.8125
Probabilité faussement positive--> 0.00099
■■■■■ Commencez à vérifier si toutes les données supplémentaires sont positives ■■■■■
■■■■■ Commencez à vérifier si des données non supplémentaires sont jugées faussement positives ■■■■■
Dans 1000000 données...994 faux positifs ont été détectés.
Recommended Posts