Wikiszótár

Flajolet-Martin-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈflɒjolɛtmɒrtinɒlɡoritmuʃ]

Főnév

Flajolet-Martin-algoritmus

  1. (matematika)

Flajolet-Martin-algoritmus

A Flajolet-Martin-algoritmus egy valószínűségi algoritmus, amelyet nagy adathalmazokban található egyedi elemek számának becslésére használnak. A probléma gyakori a streaming adatok és a Big Data feldolgozásában, ahol a teljes adathalmaz tárolása és pontos feldolgozása nem lehetséges.


Probléma

Legyen adott egy adathalmaz ( S ), amely tartalmaz ismétlődő elemeket. A cél annak meghatározása, hogy hány különböző elem (( n )) található az adathalmazban.

Példa:
Adott az ( S = {a, b, a, c, b, d, e, e} ) adathalmaz.
Az egyedi elemek száma ( n = 5 ) (( a, b, c, d, e )).


Módszer

A Flajolet-Martin-algoritmus a következő lépéseken alapul:

  1. Hashing:
    • Az adathalmaz elemeit egy hash függvénnyel dolgozzuk fel.
    • A hash függvény véletlenszerű és egyenletes eloszlású értékeket generál.
  2. Bináris reprezentáció vizsgálata:
    • Minden elem hash értékét binárisan ábrázoljuk.
    • Figyeljük meg a hash értékben található jobb oldali nullák sorozatának hosszát.
  3. Becslés:
    • A legnagyobb jobb oldali nullák száma (R) alapján becslést adunk az egyedi elemek számára: [ n ^R ]
    • Minél több az egyedi elem, annál hosszabb jobb oldali nullák sorozatát találhatjuk véletlenszerűen a hash értékekben.
  4. Pontosítás:
    • Az algoritmus egyszerre több hash függvényt használ, hogy az eredmény stabilabb és pontosabb legyen.


Lépések részletesen

  1. Hash függvény alkalmazása: Minden elemhez számítsunk egy hash értéket (( h(x) )), amely binárisan ábrázolható.
  2. Jobb oldali nullák meghatározása:
    • Például:

( h(a) = 12 1100 2 ).

  1. Legnagyobb nullaszám kiválasztása:
    • Az összes hash érték közül meghatározzuk a legnagyobb jobb oldali nullák számát (R).
  2. Becslés: [ n ^R ]
  3. Több hash függvény használata (opcionális):
    • Több hash függvényből származó értékek átlagolása pontosabb eredményt ad.


Python Implementáció

Az alábbi kód egy egyszerű implementációt mutat be a Flajolet-Martin-algoritmushoz. 

import hashlib

def hash_function(item):
    """
    Egy egyszerű hash függvény, amely SHA-1 hashből bináris számot generál.
    """
    hash_object = hashlib.sha1(item.encode())
    hex_dig = hash_object.hexdigest()
    binary_hash = bin(int(hex_dig, 16))[2:]
    return binary_hash

def trailing_zeros(binary_string):
    """
    Jobb oldali nullák számának meghatározása egy bináris számban.
    """
    return len(binary_string) - len(binary_string.rstrip('0'))

def flajolet_martin(stream, num_hashes=10):
    """
    Flajolet-Martin algoritmus implementációja.
    :param stream: Bemeneti adathalmaz (list).
    :param num_hashes: Hash függvények száma a pontosabb eredményhez.
    :return: Az egyedi elemek becsült száma.
    """
    max_zeros = [0] * num_hashes

    for item in stream:
        for i in range(num_hashes):
            # Minden hash függvényhez tartozó érték
            hash_value = hash_function(item + str(i))
            zeros = trailing_zeros(hash_value)
            max_zeros[i] = max(max_zeros[i], zeros)

    # Átlagolás a hash függvények alapján
    avg_zeros = sum(max_zeros) / num_hashes
    return 2 ** avg_zeros

# Példa használat
stream = ["a", "b", "a", "c", "b", "d", "e", "e"]
unique_estimate = flajolet_martin(stream)
print(f"Becsült egyedi elemek száma: {unique_estimate}")

Magyarázat

  1. Hash függvény:
    • SHA-1 hash függvényt használunk a bemenet bináris reprezentációjára.
    • A hash értékek egyenletesen eloszlanak, ami biztosítja a véletlenszerűség feltételét.
  2. Jobb oldali nullák száma:
    • A jobb oldali nullák száma a hash értékben a ritkaságra utal. Minél több az egyedi elem, annál hosszabb nullasorozatot találunk.
  3. Több hash függvény:
    • A több hash függvény használata javítja a pontosságot és csökkenti az eltéréseket.


Példa kimenet

Becsült egyedi elemek száma: 5.0

Valós adatok esetén a becslés nem mindig pontos, de az eltérés általában kicsi.


Előnyök

  1. Nagy adathalmazok kezelése:

Az algoritmus nem igényel a teljes adathalmaz tárolását.

  1. Hatékony:

Az algoritmus idő- és tárbonyolultsága ( O(n) ).

  1. Streaming adatokra optimalizált:

Valós idejű adatfeldolgozásra alkalmas.


Hátrányok

  1. Valószínűségi algoritmus:

Nem garantálja a pontos eredményt, csak becslést ad.

  1. Hash függvények érzékenysége:

A hash függvény minősége befolyásolja a pontosságot.


Alkalmazások

  1. Big Data feldolgozás:
    • Egyedi felhasználók számának becslése webes forgalomban.
  2. Adatstream kezelés:
    • Nagy volumenű logfájlok elemzése.
  3. Adattömörítés és optimalizáció:
    • Adatbázisokban vagy hálózatkezelésben egyedi elemek gyors becslése.


Összegzés

A Flajolet-Martin-algoritmus egy hatékony és memóriahatékony módszer nagy adathalmazok egyedi elemeinek becslésére. Bár valószínűségi algoritmus, a gyakorlatban rendkívül jól használható streaming adatok és Big Data esetén.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Flajolet-Martin-algoritmus&oldid=3480715”