Database Reference
In-Depth Information
logs auftaucht. Wir können einen Bloomfilter nutzen, um herauszufinden,
ob ein Wort schon verwendet wird.
Ein Bloomfilter ist eine probabilistische Datenstruktur, mit der Sie prüfen
können, ob ein Element in einer Menge existiert. Wir haben ihn bereits in
4.3, Bloomfilter , auf Seite 121 betrachtet. Zwar kann er falsche Positive zu-
rückliefern, aber keine falschen Negative. Das ist nützlich, wenn Sie schnell
herausfinden wollen, ob ein Wert in einem System vorhanden ist oder nicht.
Bloomfilter bestimmen die „Nichtexistenz“ eines Wertes, indem Sie einen Wert
in eine dünnbesetzte Folge von Bits umwandeln und mit der Vereinigungs-
menge der Bits aller Werte vergleichen. Mit anderen Worten: Es wird ein neu-
er Wert über ein ODER mit der aktuellen Bloomfilter-Bitsequenz verknüpft.
Wenn Sie wissen wollen, ob ein Wert bereits im System vorliegt, führen Sie ein
UND über die Bloomfilter-Sequenz aus. Besitzt der Wert irgendwelche Wahr-
Bits, die an den entsprechenden Stellen des Bloomfilters nicht wahr sind,
dann gibt es den Wert nicht. Nachfolgend eine graphische Darstellung des
Konzepts.
ab
0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0
c
Wir wollen ein Programm schreiben, das eine Reihe von ISBN-Buchdaten
durchgeht, die Titel der Bücher extrahiert, vereinfacht und in einzelne Wörter
aufteilt. Jedes neue Wort läuft dann durch den Bloomfilter. Gibt der Bloom-
filter falsch zurück (d. h., das Wort kommt in unserem Bloomfilter noch nicht
vor), fügen wir es hinzu. Um das Ganze verfolgen zu können, geben wir jedes
neu hinzugefügte Wort aus.
$ gem install bloomfilter-rb
redis/isbn_bf.rb
# LIMIT = 1.0 / 0 # 1.0/0 ist bei Ruby unendlich
LIMIT= 10000
%w{rubygems time bloomfilter-rb}.each{|r| require r}
bloomfilter = BloomFilter::Redis.new(:size => 1000000)
$redis = Redis.new(:host => "127.0.0.1" , :port => 6379)
$redis.flushall
 
Search WWH ::




Custom Search