Bloomo filtras — apibrėžimas, veikimo principas ir panaudojimas

Sužinokite, kas yra Bloomo filtras, kaip veikia hash funkcijos, klaidingo teigiamo esmė ir praktinis panaudojimas bei atminties taupymo privalumai.

Bloomo filtras — tai duomenų struktūra, suteikianti greitą ir atminties efektyvų būdą patikrinti, ar tam tikras elementas yra aibėje. Bloomo filtrai naudoja hash funkcijas ir bitų masyvą vietoj pilno elementų saugojimo, todėl jie ypač tinka situacijoms, kur svarbu taupyti atmintį ir greitai atsakyti į užklausas.

Veikimo principas

Bloomo filtras sudarytas iš didelio bitų masyvo (dydis m) ir k skirtingų hash funkcijų. Operacijos veikia taip:

• Pridėjimas: elementui pritaikomos k hash funkcijų, kiekviena grąžina indeksą bitų masyve; kiekvienas atitinkamas bitas nustatomas į 1. (Jei bitas jau buvo 1, jis lieka 1.)
• Tikrinimas: norint patikrinti, ar elementas yra aibėje, apskaičiuojamos tos pačios k hash reikšmės ir tikrinami atitinkami bitai. Jei nors vienas bitas yra 0 — elementas tikrai nėra aibėje. Jei visi k bitai yra 1 — elementas gali būti aibėje, tačiau tai gali būti klaidingas teigiamas rezultatas.

Taigi atsakymas į užklausą būna arba „tikrai nėra aibėje“, arba „gali būti aibėje“. Į aibę elementus galima įtraukti, bet jų negalima saugiai pašalinti be specialių modifikacijų; su kiekvienu nauju pridėjimu auga tikimybė gauti klaidingą teigiamą rezultatą.

Tikimybinė savybė ir formulės

Bloomo filtras yra tikimybinė duomenų struktūra: ji leidžia klaidingus teigiamus rezultatus, bet — be papildomų mechanizmų — neleidžia klaidingų neigiamų rezultatų. Apytiksliai klaidingo teigiamo rezultato tikimybę p galima apskaičiuoti pagal formulę:

p ≈ (1 − e^(−k·n/m))^k,

kur n — įterptų elementų skaičius, m — bitų masyvo ilgis, o k — hash funkcijų skaičius. Optimalus k, mažinantis klaidingų teigiamų rezultatų tikimybę, yra maždaug k ≈ (m/n)·ln 2.

Dažnai skaičiuojant bitų skaičių vienam elementui naudojama išraiška:

m/n ≈ −(ln p) / (ln 2)^2.

Praktinis pavyzdys: siekiant maždaug 1 % (bitų) klaidingų teigiamų rezultatų, reikia mažiau nei 10 bitų vienam elementui, nepriklausomai nuo bendro elementų skaičiaus.

Trumpa istorija

1970 m. Edwardas Bloomas pasiūlė Bloomo filtrą. Jo straipsnyje Bloomas nagrinėjo problemą, susijusią su žodžių brūkšneliais (hyphenation) ir pabrėžė, kad saugant taisykles dideliam žodžių rinkiniui reikėtų daug atminties. Jis siūlė atminties ir skaičiavimo kompromisą, kuris leido taupyti vietą ir sumažinti sunkesnių paieškų skaičių. Pavyzdžiui, hešo sritis gali užimti tik apie 15 % vietos, reikalingos idealiam be klaidų hešui, tuo pačiu atmesdama didelę dalį diskinių užklausų.

Panaudojimo sritys

Bloomo filtrai plačiai naudojami daugybėje sričių dėl greičio ir mažo atminties poreikio:

• Tarpinių kaupiklių (cache) ir duomenų bazių užklausų prevencijai — greitai nustatyti, ar duomenų elemento tikrai nėra, taip išvengiant brangių disko užklausų.
• Tinklo sistemose ir filtravime (pvz., tinklo paketų atpažinimas, SPAM filtrai).
• Paieškos sistemose ir interneto robotuose — patikrinti, ar URL jau buvo nuskaitytas.
• Sklaidos sistemas, paskirstytas duomenų saugyklas, blokų grandines ir kt., kur reikia greitai atmesti neesminius užklausimus.
• Antivirusinėse arba kenkėjiškų programų aptikimo sistemose, kur reikia greitai patikrinti, ar failas ar jo savybė anksčiau sutiko.

Apribojimai ir variantai

Pagrindiniai trūkumai:

• Negalima saugiai pašalinti elementų (įprastame Bloomo filtre). Jeigu reikia pašalinimo — naudojami skaitiniai (counting) Bloom filtrai, kuriuose vietoje bitų saugomi skaitikliai.
• Klaidingų teigiamų rezultatų tikimybei didėjant su kiekvienu pridėjimu.
• Bloomo filtras neleidžia atkurti sąrašo (negali išvesti, kurių elementų jis turi), tinka tik nariumo patikrinimui.
• Svarbi yra hash funkcijų kokybė ir nepriklausomumas — prastos hash funkcijos gali padidinti klaidų dažnį.

Populiarūs modifikacijų variantai, leidžiantys spręsti kai kurias problemas:

• Counting Bloom filter — leidžia pašalinti elementus, bet reikalauja daugiau atminties (skaitikliai vietoje bitų).
• Scalable Bloom filter — automatiškai plečiamas, kai didėja elementų skaičius, palaikant fiksuotą klaidingų teigiamų tikimybę.
• Cuckoo filter — alternatyva, leidžianti ir pašalinti elementus, dažnai efektyvesnė mažiems klaidų lygiams.
• Partitioned Bloom filter, Compressed Bloom filter ir kiti pritaikyti variantai tam tikriems poreikiams.

Praktiniai patarimai

• Renkantis parametrus, apskaičiuokite m ir k pagal numatomą n ir pageidaujamą p. Optimalus k dažnai apskaičiuojamas kaip (m/n)·ln2.
• Naudokite kelias, gerai parinktas hash funkcijas arba vieną universalų hash su šeimininkavimo (salting) metodu, kad išvengtumėte koreliacijos tarp funkcijų.
• Jei reikia pašalinimo — apsvarstykite counting Bloom ar cuckoo filtrą.
• Bloomo filtrus verta naudoti kaip pirmą filtravimo sluoksnį: greitas „ne“ identifikavimas gali žymiai sumažinti vėliau atliekamų lėtų operacijų skaičių.

Apibendrinant: Bloomo filtras yra efektyvus ir paprastas įrankis, suteikiantis greitą būdą atmesti daug netinkamų užklausų taupant atmintį, tačiau jis reikalauja kompromiso — leidžia klaidingus teigiamus rezultatus ir nebūtinai tinka, jei reikia tiksliai valdyti elementų pašalinimą ar sugrąžinti saugomų elementų sąrašą.

Klausimai ir atsakymai

Klausimas: Kas yra Bloomo filtras?

K: Kokio tipo duomenų struktūra yra Bloomo filtras?

K: Kas pasiūlė Bloomo filtrą?

K: Koks buvo Edwardo pavyzdys, kaip naudoti jo metodą?

K: Kiek bitų vienam elementui reikia, kad klaidingai teigiamų rezultatų tikimybė būtų 1 %?

K: Ar galima pašalinti elementus iš žiedinio filtro, kai jie jau yra pridėti?

K: Ar pridėjus daugiau elementų padidėja ar sumažėja tikimybė gauti klaidingai teigiamą rezultatą?

Paieška pagal raidę