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.
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 )).
A Flajolet-Martin-algoritmus a következő lépéseken alapul:
( h(a) = 12 1100 2 ).
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))
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 = * 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 = max(max_zeros, 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 =
unique_estimate = flajolet_martin(stream)
print(f"Becsült egyedi elemek száma: {unique_estimate}")
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.
Az algoritmus nem igényel a teljes adathalmaz tárolását.
Az algoritmus idő- és tárbonyolultsága ( O(n) ).
Valós idejű adatfeldolgozásra alkalmas.
Nem garantálja a pontos eredményt, csak becslést ad.
A hash függvény minősége befolyásolja a pontosságot.
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.