BloomFilter-Beschreibungs- und Implementierungsbeispiel (JAVA)

1. BloomFilter Beschreibung und Beispiel

1-1. Erforderlicher Anwendungsfall

Es ist ein bisschen schwierig, also gebe ich Ihnen ein Beispiel. Es ist weder ein richtiger Anwendungsfall noch eine Realität.

1. Erstellen Sie eine App, mit der Sie Geld senden können, indem Sie die Kontonummer des anderen Teilnehmers auf Ihrem Smartphone eingeben
2. Es kann kein Geld an eine nicht vorhandene Kontonummer gesendet werden

In diesem Fall

1. Fragen Sie die Serverdatenbank nach der Kontonummer des anderen Teilnehmers ab
2. Wenn es nicht existiert, wird ein Fehler zurückgegeben und wenn es existiert, wird die Anzahlung dort verarbeitet.

Wird sein.

Hier wie folgt Wenn die App eine Liste hat, ob die Kontonummer vorhanden ist oder nicht Sie müssen sich nicht die Mühe machen, die Datenbank über das Netzwerk nach der Existenz der Kontonummer zu fragen.

** Wenn die Kontonummer jedoch sehr groß ist, ist es für die Smartphone-App schwierig, so viele Informationen zu speichern. ** ** ** ** In einem solchen Fall können Sie bei Verwendung von BloomFilter sehr kompakte Informationen erhalten, die "fast" Aufschluss darüber geben, ob Ihre Kontonummer vorhanden ist oder nicht. ** ** **

1-2. Mechanismus

Detaillierte Erklärung ist [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).

1. Bereiten Sie einen Datensatz mit einer bestimmten Länge vor, der Bitinformationen von 0 und 1 enthalten kann.
2. Wenden Sie eine Hash-Funktion auf die Kontonummer an und konvertieren Sie den resultierenden Hash in eine Bitfolge der Datensatzlänge 01.
3. Setzen Sie ein Bit an der entsprechenden Stelle im Datensatz

Zu diesem Zeitpunkt gibt es mehrere Positionen, an denen 1 steht.

Wenn dies für alle Kontonummern wiederholt wird, erhöht sich die Anzahl der Positionen, an denen 1 steht.

Wenn Sie diesen Datensatz haben, wenn Sie die Kontonummer in der obigen App eingeben ** Genau der gleiche Hash ⇒ 01-Bit-String-Konvertierung durchführen und den Teil, in dem 1 steht, mit dem Datensatz abgleichen ** ** Wenn alle Einsen gesetzt sind, bedeutet dies, dass die Wahrscheinlichkeit, dass die Kontonummer existiert, extrem hoch ist. ** ** **

--Ober: Datensätze mit Informationen zu allen Kontonummern --Niedriger: Hash ⇒ 01 Konvertierungsergebnis der Kontonummer "111-111-111"

⇒ Da an allen Zielpositionen 1 gesetzt ist, ist es sehr wahrscheinlich, dass der Datensatz vorhanden ist.

** "Extrem teuer" ist nicht absolut. ** ** ** Weil die Position, an der 1 steht, mit anderen Kontonummern in Konflikt steht Es besteht die Möglichkeit, dass 1 an dieser Position durch die Bitfolge anderer Kontonummerninformationen gesetzt wird.

• Erste Zeile: Aufzeichnung mit den folgenden Kontonummerninformationen
• Zweite Zeile: Bitinformationen der vorhandenen Kontonummer "111-111-111"
• Dritte Zeile: Bitinformationen der vorhandenen Kontonummer "222-222-222"

Geben Sie hier die nicht vorhandene Kontonummer "999-999-999" ein. Wenn das Ergebnis der Hash ⇒ 01-Bit-Konvertierung wie folgt lautet, wird festgestellt, dass die Daten versehentlich vorhanden sind.

• Erste Zeile: Aufzeichnung mit den folgenden Kontonummerninformationen (wie zuvor)
• Zweite Zeile: Konvertierungsergebnis der nicht vorhandenen Kontonummer "999-999-999"

Wenn an der Position, an der 1 steht, sogar eine 0 vorhanden ist, kann zu 100% definitiv festgestellt werden, dass keine Daten vorhanden sind. Selbst wenn sich an der Position, an der alle Einsen stehen, eine 1 befindet, kann nicht zu 100% bestätigt werden, dass Daten vorhanden sind. ** Wir sagen, dass es keine falschen Negative gibt, aber es gibt falsche Positive. ** ** **

Wenn Sie eine ausreichend lange Aufzeichnung machen, werden Fehlalarme reduziert. Wenn Sie eine zu lange Aufzeichnung aufnehmen, wird die Kapazität verringert.

** Für 1 Million Kontonummern (beliebig viele Ziffern) ** ** False Positives konvergieren zu ungefähr 1%, wenn es eine Region von ungefähr 1,2 MB gibt. ** ** ** ** Wenn eine Region von ungefähr 1,8 MB vorbereitet werden kann, konvergieren falsch positive Ergebnisse auf ungefähr 0,1%. ** ** **

Mit einer App wie der oben genannten müssen Sie also nur wenige Aufzeichnungen führen Der Netzwerkzugriff und der Datenbankzugriff können erheblich unterdrückt werden.

• In diesem Fall jedes Mal, wenn ein neues Konto hinzugefügt wird *

• Es gibt einen Punkt, an dem der aktualisierte Datensatz heruntergeladen werden kann. * *

• Wenn Daten in mehreren Speichern oder Segmenten gespeichert werden *

• Es kann auch verwendet werden, um effizient nach Datenspeicherorten zu suchen, aber es ist schwierig, dies zu vermitteln *

• Ich konnte mir nicht sofort andere gute Anwendungsfälle vorstellen, die leicht zu erklären waren. Bitte verzeihen Sie mir. * *

2. BloomFilter-Implementierungsbeispiel

Ich werde die Implementierung in Java so wie sie ist veröffentlichen.

MyBloomFilter.java

import java.io.Serializable;
import java.nio.charset.Charset;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

/**
 *Hat nur die grundlegendsten Funktionen von BloomFilter
 * @author owl
 * @param <E>
 */
public class MyBasicBloomFilter<E> implements Serializable {

    private final BitSet bitFilter;                                             //Filterkörper
    private final int bitFilterSize;                                            //Filtergröße
    private int numberOfAddedElements;                                          //Aktuelle Anzahl der Elemente
    private final int countOfHashNumCreatePerOneElement;                        //Anzahl der wahren Bits pro Element (Hashing ⇒ Anzahl der numerischen Konvertierungen)

    static final Charset DEFAULT_CHARSET = Charset.forName("UTF-8");            

    /**
     *Falsch positives Niveau
     * High:Hohe Fehlalarme, aber kompakte Filtergröße und gute Leistung
     *Mitte: Balance zwischen falsch positiven Ergebnissen, Filtergröße und Leistung
     * Low:Halten Sie Fehlalarme so gering wie möglich, auch wenn die Filtergröße erhöht oder die Verarbeitungszeit lang ist.
     */
    public static enum FalsePositiveProbability{ High, Middle, Low }
    
    /**
     *Führen Sie Message Digest aus
     */
    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;
    }    

    /**
     *Konstrukteur
     * @param c Anzahl der pro Element verwendeten Bits
     * @param n (maximal erwartete Anzahl von Elementen)
     * @Anzahl der wahren Bits pro Parameter k-Element (Hashing ⇒ Anzahl der Zahlenumwandlungen)
     */
    public MyBasicBloomFilter(double c, int n, int k) {

        this.countOfHashNumCreatePerOneElement = k;
        
        //Elementanzahl*Bestimmen Sie die Filterbitgröße anhand der Anzahl der pro Element verwendeten Bits
        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
     * @Parameterdaten Eingabedaten
     * @param hashCount Count
     * @return Numerischer Wert, der durch Hashing erhalten wird (Bitstandposition)
     */
    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 bei 4Byte Trennzeichen und in Array packen
            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;
    }    
    
    /**
     *Element hinzufügen
     * @param element 
     */
    public void add(E element) {
       add(element.toString().getBytes(DEFAULT_CHARSET));
    }    
    
    /**
     *Element hinzufügen
     * @param bytes 
     */
    public void add(byte[] bytes) {
       int[] hashes = createHashes(bytes, countOfHashNumCreatePerOneElement);
       for (int hash : hashes) bitFilter.set(Math.abs(hash % bitFilterSize), true);
       numberOfAddedElements ++;
    }

    /**
     *Beurteilung
     * @param Element Element
     * @return 
     */
    public boolean contains(E element) {
        return contains(element.toString().getBytes(DEFAULT_CHARSET));
    }
    
    /**
     *Beurteilung
     * @Byte-Array des Param Bytes-Elements
     * @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;
    }    
    
    /**
     *Filter holen
     * @Rücklauffilter
     */
    public BitSet getBitSet() {
        return bitFilter;
    }

    /**
     *Holen Sie sich die Anzahl der hinzugefügten Elemente
     * @Anzahl der Rücksendungen
     */
    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);
    }    
    
}

Probe aufrufen

import java.util.ArrayList;
import java.util.List;
import org.apache.commons.lang.RandomStringUtils;

/**
 *Probieren Sie BloomFilter aus
 * @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<>();           //Daten, die BloomFilter hinzugefügt werden sollen
        List<String> notAddList = new ArrayList<>();        //Daten nicht zu BloomFilter hinzugefügt
        
        //BloomFilter wurden 10.000 Daten hinzugefügt
        //Generieren Sie gleichzeitig 10.000 Verifizierungsdaten, die nicht zu BloomFilter hinzugefügt werden
        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));
            }
        }

        //Geben Sie den Status von BloomFilter aus
        for(int i=0; i < bf.getBitSet().size(); i++ ){
            System.out.print(bf.getBitSet().get(i) ? "1" : "0");
            if(i>1000) break;
        }
        
        //Ausgabe der BloomFilter-Datengröße und berechnete falsch positive Wahrscheinlichkeit
        System.out.println();
        System.out.println("Datengröße--> " + bf.getBitSet().size() + " | K-Byte Anzahl der Bytes" + (double)((double)(bf.getBitSet().size())/8/1024));
        System.out.println("Falsch positive Wahrscheinlichkeit--> " + String.format("%.5f", bf.getFalsePositiveProbability()));

        //Überprüfen Sie, ob alle zu BloomFilter hinzugefügten Daten positiv sind
        //(Wenn es kein Problem gibt, wird nichts angezeigt)
        System.out.println();
        System.out.println("■■■■■ Überprüfen Sie, ob alle zusätzlichen Daten positiv sind. ■■■■■");
        addList
            .stream()
            .sequential()
            .filter(e -> !bf.contains(e))
            .forEach(e-> System.out.println("Fehlendes Urteil:" + e));
        
        //Die Anzahl der Ausgaben, für die keine Daten zu BloomFilter hinzugefügt wurden, war fälschlicherweise positiv
        System.out.println("■■■■■ Überprüfen Sie, ob nicht zusätzliche Daten als falsch positiv beurteilt werden. ■■■■■");
        System.out.println("In 1000000 Daten..." +
            notAddList
                .stream()
                .sequential()
                .filter(e -> bf.contains(e))
                .count() + "Ein falsches Positiv wurde festgestellt.");
        
    }
    
}

Ausführungsergebnis

000011100100001110011011100010101001100110111000100011001(Kürzung)
Datengröße--> 14400000 | K-Byteanzahl der Bytes 1757.8125
Falsch positive Wahrscheinlichkeit--> 0.00099

■■■■■ Überprüfen Sie, ob alle zusätzlichen Daten positiv sind. ■■■■■
■■■■■ Überprüfen Sie, ob nicht zusätzliche Daten als falsch positiv beurteilt werden. ■■■■■
In 1000000 Daten...994 falsch positive Ergebnisse wurden festgestellt.