Wikiszótár

Bloom-szűrő

Magyar

Kiejtés

  • IPA: [ ˈbloomsyːrøː]

Főnév

Bloom-szűrő

  1. (matematika, algoritmusok)

Bloom-szűrő

A Bloom-szűrő egy valószínűségi adatszerkezet, amely gyorsan és hatékonyan képes megmondani, hogy egy elem valószínűleg jelen van, vagy biztosan nincs jelen egy adathalmazban. A Bloom-szűrő általánosan használt olyan alkalmazásokban, ahol nagy mennyiségű adatot kezelnek, és a gyors keresés fontosabb, mint a 100%-os pontosság.


Működési elve

  1. Hash-függvények:
    • A Bloom-szűrő több hash-függvényt használ az elemek leképezésére egy bit-tömbben.
  2. Beszúrás:
    • Egy elem beszúrásakor minden hash-függvény kiszámítja az elemhez tartozó indexet, és ezeket a biteket 1-re állítja.
  3. Lekérdezés:
    • Egy elem keresésekor a hash-függvények ellenőrzik a megfelelő biteket. Ha bármelyik bit 0, az elem biztosan nincs jelen. Ha minden bit 1, az elem valószínűleg jelen van.
  4. Hamis pozitív eredmények:
    • A Bloom-szűrők nem garantálják a találatot, mivel hamis pozitív eredményeket adhatnak. Azonban garantáltan nincsenek hamis negatívok.


Használati esetek

  1. Adatok gyors keresése:
    • Webes alkalmazások cache-kezelése.
  2. Spam-szűrők:
    • Spam szavak gyors felismerése.
  3. DNS cache:
    • Kérések gyors ellenőrzése, hogy már léteznek-e.
  4. Adatok deduplikációja:
    • Ellenőrzés, hogy egy elem már létezik-e egy adatbázisban.


Python implementáció

Alapvető Bloom-szűrő

import hashlib

class BloomFilter:
    def __init__(self, size, hash_count):
        """
        Bloom-szűrő inicializálása.
        :param size: A bit-tömb mérete.
        :param hash_count: Hash-függvények száma.
        """
        self.size = size
        self.hash_count = hash_count
        self.bit_array = [0] * size

    def _hashes(self, item):
        """
        Hash-függvények generálása.
        :param item: Az elem, amelyet hash-elünk.
        :return: Az elemhez tartozó hash indexek.
        """
        result = []
        for i in range(self.hash_count):
            # Hash indexek generálása különböző algoritmusokkal
            hash_result = int(hashlib.md5((str(item) + str(i)).encode()).hexdigest(), 16)
            result.append(hash_result % self.size)
        return result

    def add(self, item):
        """
        Elem hozzáadása a Bloom-szűrőhöz.
        :param item: Az elem, amelyet hozzáadunk.
        """
        for index in self._hashes(item):
            self.bit_array[index] = 1

    def check(self, item):
        """
        Ellenőrzés, hogy egy elem jelen van-e.
        :param item: Az elem, amelyet keresünk.
        :return: True, ha valószínűleg jelen van; False, ha biztosan nincs jelen.
        """
        for index in self._hashes(item):
            if self.bit_array[index] == 0:
                return False
        return True

# Példa használat
bloom = BloomFilter(size=100, hash_count=3)

# Elemek hozzáadása
bloom.add("apple")
bloom.add("banana")
bloom.add("cherry")

# Ellenőrzés
print(bloom.check("apple"))  # True (valószínűleg jelen van)
print(bloom.check("banana"))  # True (valószínűleg jelen van)
print(bloom.check("grape"))  # False (biztosan nincs jelen)

Paraméterek finomhangolása

  • Bit-tömb mérete ((m)):
    • Minél nagyobb a bit-tömb, annál kisebb az ütközések valószínűsége.
  • Hash-függvények száma ((k)):
    • A túl sok hash-függvény növeli az időbonyolultságot, míg a túl kevés növeli a hamis pozitív valószínűséget.
  • Hamis pozitív valószínűség ((p)):
    • A (p = (1 - e{-kn/m})k) képlet szerint határozható meg, ahol (n) az elemek száma.


Kiterjesztett használati példák

Dinamizált Bloom-szűrő

  • Ha az adathalmaz növekedése várható, a Bloom-szűrőt úgy bővíthetjük, hogy újabb bit-tömböket és hash-függvényeket adunk hozzá.

Counting Bloom Filter

  • Egy “számláló Bloom-szűrő” nemcsak azt tudja ellenőrizni, hogy egy elem jelen van-e, hanem azt is, hogy hányszor szerepel. Ebben az esetben a bit-tömb helyett számlálókat használunk.


Előnyök

  1. Gyors és memóriahatékony:
    • A hagyományos adatszerkezetekhez képest kevesebb memóriát igényel.
  2. Hamis negatív eredmények hiánya:
    • Mindig garantáltan észleli, ha egy elem biztosan nincs jelen.

Hátrányok

  1. Hamis pozitív eredmények:
    • Nem garantálja, hogy egy elem tényleg jelen van.
  2. Törlés nehézsége:
    • Elemet nem lehet könnyen törölni a szűrőből (csak speciális változatokkal, pl. counting Bloom-szűrő).


Felhasználási területek

  • Web cache: Gyors keresés, hogy egy oldal már meglátogatott-e.
  • Adatbázisok: Gyors szűrés, hogy egy adat már létezik-e az adatbázisban.
  • Spam-szűrés: Emailek gyors ellenőrzése spam-listák alapján.

A Bloom-szűrő remek választás, ha memóriahatékony, gyors keresési megoldásra van szükség, különösen akkor, ha a hamis pozitív eredmények kezelhetők a probléma jellegénél fogva.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Bloom-szűrő&oldid=3480392”