Bloomo filtras
Bloomo filtras - tai duomenų struktūra, leidžianti kompiuteriams patikrinti, ar tam tikras elementas yra aibėje. Bloomo filtrai tam naudoja hash funkcijas. Kiekvienam pridėtam elementui apskaičiuojama hash reikšmė. Pridėjus naują elementą, jo hash vertė palyginama su kitų rinkinio elementų verte. Bloomo filtras yra tikimybinė duomenų struktūra. Galima gauti klaidingą teigiamą rezultatą, bet negalima gauti klaidingo neigiamo rezultato. Kitaip tariant, užklausa grąžina arba "galbūt yra aibėje", arba "tikrai nėra aibėje". Elementus į aibę galima įtraukti, bet ne pašalinti. Su kiekvienu pridėtu elementu tikimybė gauti klaidingą teigiamą rezultatą didėja.
1970 m. Edwardas Bloomas pasiūlė Bloomo filtrą. Straipsnyje Bloomas daro prielaidą, kad egzistuoja algoritmas, leidžiantis brūkšneliu atskirti žodžius eilutės pabaigoje. Remiantis pavyzdžiu, dauguma žodžių turi paprastus brūkšnelių darybos modelius. Tačiau maždaug 10 % žodžių reikia atlikti daug laiko reikalaujančias paieškas, kad būtų gauta teisinga taisyklė. Jo atveju reikėjo brūkšneliu sutrumpinti apie 500 000 žodžių. Jis pamatė, kad naudojant "įprastus" be klaidų naudojamus šifravimo metodus, saugant brūkšniavimo modelius, reikėtų daug atminties. Jis nustatė, kad naudodamas savo metodą, jis gali pašalinti daugumą paieškų. Pavyzdžiui, hešo sritis sudaro tik 15 % dydžio, kurio reikia idealiam be klaidų atliekamam hešui, vis tiek panaikina 85 % kreipimųsi į diską.
Apskritai 1 % klaidingo teigiamo rezultato tikimybei pasiekti reikia mažiau nei 10 bitų vienam elementui, nepriklausomai nuo aibės dydžio ar elementų skaičiaus.
Klausimai ir atsakymai
Klausimas: Kas yra Bloomo filtras?
A: Bloomo filtras yra duomenų struktūra, leidžianti kompiuteriams patikrinti, ar tam tikras elementas pasitaiko aibėje. Tam naudojamos hash funkcijos, apskaičiuojant kiekvieno pridėto elemento hash vertę ir lyginant ją su kitais rinkinio elementais.
K: Kokio tipo duomenų struktūra yra Bloomo filtras?
A: Bloomo filtras yra tikimybinė duomenų struktūra, t. y. yra galimybė gauti klaidingai teigiamus, bet ne klaidingai neigiamus rezultatus.
K: Kas pasiūlė Bloomo filtrą?
A. Edvardas Bloomas pasiūlė Bloomo filtrą 1970 m.
K: Koks buvo Edwardo pavyzdys, kaip naudoti jo metodą?
A: Edwardo pavyzdys buvo apie 500 000 žodžių kirčiavimas; jis nustatė, kad naudodamasis savo metodu jis gali pašalinti daugumą paieškų ir 15 % sumažinti kreipimųsi į diską.
K: Kiek bitų vienam elementui reikia, kad klaidingai teigiamų rezultatų tikimybė būtų 1 %?
A: 1 % klaidingai teigiamų rezultatų tikimybei pasiekti reikia mažiau nei 10 bitų vienam elementui, nepriklausomai nuo aibės dydžio ar elementų skaičiaus.
K: Ar galima pašalinti elementus iš žiedinio filtro, kai jie jau yra pridėti?
Atsakymas: Ne, elementus galima tik įtraukti į rinkinį, bet ne pašalinti.
K: Ar pridėjus daugiau elementų padidėja ar sumažėja tikimybė gauti klaidingai teigiamą rezultatą?
A: Pridėjus daugiau elementų, padidėja tikimybė gauti klaidingai teigiamą rezultatą.
