Database Reference
In-Depth Information
count, start = 0, Time.now
File.open(ARGV[0]).each
do
|line|
count += 1
next if
count == 1
_
,
_
,
_
, title = line.split(
"
\t
"
)
next if
title ==
"
\n
"
words = title.gsub(/[^\w\s]+/,
''
).downcase
# Wörter verarbeiten
words = words.split(
''
)
words.each
do
|word|
# Dem Bloomfilter bekannte Wörter überspringen
next if
bloomfilter.include?(word)
# Neue Wörter ausgeben
puts word
# und in Bloomfilter einfügen
bloomfilter.insert(word)
end
# Setzen Sie ein LIMIT, wenn nicht alle Daten eingefügt werden sollen
break if
count >= LIMIT
end
puts
"Contains Jabbyredis?
#{bloomfilter.include?(
'jabbyredis'
)}
"
puts
"
#{count}
lines in
#{Time.now - start}
seconds"
Ruby-Wunderkind Ilya Grigorik hat diesen Redis-gestützten Bloomfilter ent-
wickelt, doch das Konzept ist auf jede Sprache übertragbar.
Der Client verwendet die gleiche ISBN-Datei, benötigt aber nur die Buchtitel.
$ ruby isbn
_
bf.rb isbn.tsv
Zu Beginn der Ausgabe sollte Sie viele gängige englische Wörter wie
and
und
the
sehen. Gegen Ende der Daten werden die Wörter immer esoterischer, wie
unindustria
.
Der Vorteil dieses Ansatzes besteht darin, doppelte Wörter erkennen zu kön-
nen. Der Nachteil ist, dass einige falsche Positive durch den Rost fallen -
der Bloomfilter könnte ein Wort kennzeichnen, das er noch nicht gesehen
hat. Aus diesem Grund würde in einem realen Anwendungsfall eine zweite
Prüfung vorgenommen werden, etwa eine langsamere Query über eine ent-
sprechende Datenbank. Das sollte aber nur für einen kleinen Prozentsatz
notwendig sein, wenn der Filter groß genug ist (was man berechnen kann).
4
SETBIT und GETBIT
Wie bereits erwähnt, arbeiten Bloomfilter mit der Umkehr bestimmter Bits in
einem dünnbesetzten Binärfeld. Die von uns verwendete Redis Bloomfilter-
Implementierung nutzt zwei relativ neue Redis-Befehle, die genau das ma-
chen:
SETBIT
und
GETBIT
.
