Блумов филтар

Из Википедије, слободне енциклопедије
(преусмерено са Блумов филтер)

Блумов филтар је просторно-ефикасна пробабилистичка структура података која служи за тестирање да ли је елемент члан скупа. Осмислио га је Бартон Хауард Блум 1970. године[1]. Лажни позитивни резултати су могући, али лажни негативни нису; то значи да упит враћа или „јесте у скупу (што може да буде погрешно)“ или „дефинитивно није у скупу“. Елементи могу да се додају у скуп, али не могу да се из њега избацују (мада ово може да се реши помоћу бројачког филтра). Што се више елемената додаје у скуп, већа је вероватноћа лажних позитивних резултата.

Опис алгоритма[уреди]

Пример Блумовог филтра, представља скуп {x, y, z}. Обојене стрелице показују показују позиције у битовском низу у које је сваки елемент мапиран. Елемент w није у скупу {x, y, z}, јер једна од његових хеш вредности у низу садржи 0. На овој слици је m=18 и k=3.

Празан Блумов филтар је битовски низ од m битова који су сви постављени на 0. Такође је потребно и да буде дефинисано k различитих хеш функција, од којих свака пресликава неки скуп елемената у једну од m позиција са униформном случајном дистрибуцијом.

Како би се додао елемент у филтар, потребно је за њега израчунати сваку од k хеш вредности. Сваку од добијених k позиција у низу треба поставити на 1.

Како би се филтар претражио за неки елемент (тестирање да ли је елемент у скупу), поново се за њега рачуна свака од k хеш вредности како би се добило k позиција у низу. Ако је било који бит на некој од ових позиција једнак 0, елемент сигурно није у скупу – јер да јесте, онда би сви битови били постављени на 1 приликом уметања. Ако су све вредности једнаке 1, онда је или елемент у скупу, или су сви битови већ постављени на 1 током уметања других елемената скупа, што доводи до лажног позитивног резултата. У једноставном Блумовом филтру не постоји начин да се разликују ова два случаја, али напредније технике могу да се користе за решавање овог проблема.

Захтев за дефинисањем k различитих независних хеш функција може да буде незгодан за велико k. Код „добре“ хеш функције са дугачким излазом, требало би да има јако мало или нимало корелација између различитих битовских поља таквог хеша, тако да оваква хеш функција може да се користи за генерисање више „различитих“ хеш функција тако што се њен излаз исецка у више битовских низова. Други приступ је да се проследи k различитих почетних вредности (на пример 0, 1, ..., k − 1) хеш функцији која узима два параметра, или да се ове вредности додају (допишу) елементу који се убацује у скуп. За веће m и(ли) k, услов независности између хеш функција може да се релаксира са занемарљивим порастом вероватноће лажних позитивних резултата (Dillinger & Manolios (2004a), Kirsch & Mitzenmacher (2006)). Специфично, показана је (Dillinger & Manolios (2004b)) ефективност добијања k индекса коришћењем унапређеног двоструког хеширања или троструког хеширања, што су варијанте двоструког хеширања које су ефективно једноставни генератори случајних бројева иницијализовани са две или три хеш вредности.

Уклањање елемената из једноставног Блумовог филтра је немогуће јер лажни негативни резултати нису дозвољени. Елемент се пресликава у k бита, и иако би постављање било ког од ових k бита на нулу било довољно да се елемент уклони, то би уједно уклонило и сваки други елемент који је пресликан у тај бит. Како не постоји начин да се утврди да ли је било који други елемент пресликан у неки од битова елемента који се уклања, постављање било ког од тих битова на 0 би увело могућност лажних негативних резултата.

Једнократно брисање елемента из Блумовог филтра може да се симулира додавањем другог Блумовог филтра који би садржавао елементе који су обрисани. Међутим, лажни позитивни резултати у другом филтру би могли да произведу лажне негативне разултате, што није допуштено. У овом приступу не би било могуће поновно додавање претходно обрисаних елемената, јер би они морали да буду уклоњени из другог филтра.

Међутим, чест је случај да су сви елементи скупа доступни и могуће их је побројати, али је то скупо (на пример, јер захтева доста читања са диска). У овом случају, ако стопа лажних позитивних резултата постане сувише висока, филтар може да буде регенерисан; то би требало да се дешава релативно ретко.

Вероватноћа лажног позитивног резултата[уреди]

Вероватноћа лажног позитивонг резултата p као функција броја елемената n у филтру и величине филтра, m. Подразумеван је оптималан број хеш функција, k= (m/n) \ln 2.

Нека важи претпоставка да хеш функција бира сваки елемент низа са једнаком вероватноћом. Ако је m број битова у низу, вероватноћа да одређени бит није постављен на јединицу од стране одређене хеш функције током уметања елемента износи

1-\frac{1}{m}.

Вероватноћа да тај бит није постављен на јединицу од стране било које хеш функције приликом уметања једног елемента је

\left(1-\frac{1}{m}\right)^k.

Ако је уметнуто n елемената, вероватноћа да је одређени бит још увек једнак нули је

\left(1-\frac{1}{m}\right)^{kn};

Из тога следи да је вероватноћа да је постављен на јединицу једнака

1-\left(1-\frac{1}{m}\right)^{kn}.

Нека се тестира припадност скупу неког елемента који није у скупу. Сваки од k битова које дају хеш функције је 1 са вероватноћом датом горе. Вероватноћа да су сви они једнаки 1, што би довело до тога да алгоритам погрешно врати да је елемент у скупу, се често наводи као

\left(1-\left[1-\frac{1}{m}\right]^{kn}\right)^k \approx \left(1-e^{-kn/m} \right)^k.

Ово није строго тачно јер подразумева независност вероватноћа постављања сваког бита. Међутим ако се претпостави да је то блиска апроксимација, важи да вероватноћа лажних позитивних резултата опада како m (број битова у низу) расте, и повећава се како n (број уметнутих елемената) расте. За дато m и n, вредност за k (број хеш функција) које минимизују вероватноћу лажног позитивног резултата је

\frac{m}{n}\ln 2 \approx 0.7\frac{m}{n},

што даје вероватноћу лажног позитивног резултата од

2^{-k} \approx {0.6185}^{m/n}.

Потребан број битова, m за дато n (број уметнутих елемената) и тражену вероватноћу лажног позитивног резултата, p (уз претпоставку да се користи оптимална вредност за k) може да се израчуна заменом оптималне вредности за k у горњој једначини:

p = \left(1-e^{-(m/n\ln 2) n/m} \right)^{(m/n\ln 2)}

што може да се поједностави:

\ln p = -\frac{m}{n} \left(\ln 2\right)^2.

а то даје:

m=-\frac{n\ln p}{(\ln 2)^2}.

Ово значи да дужина Блумовог филтра мора да расте линеарно са бројем уметнутих елемената како би се одржала фиксна вероватноћа лажних позитивних резултата. Иако је горња формула асимптотска (то јест, важи за m, n → ∞), сасвим је прихватљива и за коначне вредности m и n; вероватноћа лажног позитивног резултата за коначни Блумов филтар од m битова, n елемената и k хеш функција је највише

\left(1-e^{-k(n+0.5)/(m-1)} \right)^k.


Референце[уреди]

  1. ^ Donald Knuth. The Art of Computer Programming, Errata for Volume 3 (2nd ed.)“. 

Литература[уреди]

Спољашње везе[уреди]

Викиостава
Викимедијина остава има још мултимедијалних датотека везаних за: Блумов филтар

Имплементације[уреди]