Bloom-Filter
Ett Bloom-filter är en datastruktur som gör det möjligt för datorer att se om ett visst element förekommer i en mängd. Bloom-filter använder hash-funktioner för att göra detta. För varje element som läggs till beräknas ett hashvärde. När ett nytt element läggs till jämförs dess hashvärde med värdet för de andra elementen i mängden. Ett Bloom-filter är en probabilistisk datastruktur. Det är möjligt att få ett falskt positivt resultat, men inte att få ett falskt negativt resultat. Med andra ord returnerar en fråga antingen "möjligen i mängden" eller "definitivt inte i mängden". Element kan läggas till i mängden, men inte tas bort. För varje tillagd element ökar sannolikheten för att få ett falskt positivt resultat.
Edward Bloom föreslog Bloom-filtret 1970. I artikeln antar Bloom att det finns en algoritm för att skilja ord i slutet av en rad med bindestreck. Enligt exemplet har de flesta ord enkla bindningsmönster. Men ungefär 10 % av orden kräver tidskrävande sökningar för att hämta rätt regel. Hans fall gällde bindestreckning av cirka 500 000 ord. Han såg att det skulle krävas mycket minne för att lagra bindningsmönstren med hjälp av den "normala" felfria hash-tekniken. Han upptäckte att han med sin teknik kunde eliminera de flesta sökningar. Till exempel eliminerar ett hashområde som bara är 15 % av den storlek som behövs för en idealisk felfri hash fortfarande 85 % av diskåtkomsterna.
Generellt sett krävs mindre än 10 bitar per element för att sannolikheten för falskt positiva resultat ska vara 1 %, oberoende av storleken eller antalet element i uppsättningen.
Frågor och svar
F: Vad är ett Bloom-filter?
S: Ett Bloom-filter är en datastruktur som gör det möjligt för datorer att se om ett visst element förekommer i en mängd. Det använder hashfunktioner för att göra detta genom att beräkna hashvärdet för varje element som läggs till och jämföra det med de andra elementen i mängden.
F: Vilken typ av datastruktur är ett Bloom-filter?
S: Ett Bloom-filter är en probabilistisk datastruktur, vilket innebär att det finns en möjlighet att få falska positiva men inte falska negativa resultat.
F: Vem föreslog Bloom-filtret?
Svar: Edward Bloom föreslog Bloom-filtret 1970.
F: Vad var Edwards exempel på hur han använde sin teknik?
S: Edwards exempel var att han tog fram ett exempel på att han skulle kunna ta bort de flesta sökningar och minska antalet diskåtkomster med 15 %.
F: Hur många bitar per element krävs för att sannolikheten för falskt positiva resultat ska vara 1 %?
S: Det krävs mindre än 10 bitar per element för att sannolikheten för falskt positiva resultat ska vara 1 %, oberoende av storleken eller antalet element i mängden.
F: Är det möjligt att ta bort element från ett Bloom-filter när de väl har lagts till?
Svar: Nej, element kan bara läggas till i mängden men inte tas bort.
F: Ökar eller minskar sannolikheten för att få ett falskt positivt resultat om man lägger till fler element?
S: Om fler element läggs till ökar sannolikheten för att få ett falskt positivt resultat.
