Blūma filtrs — kas tas ir, darbības princips un pielietojums
Blūma filtrs ir datu struktūra, kas efektīvi pārbauda, vai dots elements ir kopā vai nav. Tā izmanto vairākas hash funkcijas un vienkāršu bitu masīvu, lai ātri atbildētu uz jautājumu "vai elements varētu būt kopā?". Blūma filtrs ir varbūtiska (probabilistiska) datu struktūra: tas var dot viltus pozitīvu rezultātu, bet tam nav viltus negatīvu rezultātu — ja filtrs saka, ka elementa nav, tad to tiešām nav. Elementus var pievienot, bet ne izņemt (izņemšana bez papildu mehānismiem nav iespējama), un ar katru pievienoto elementu pieaug iespējamība iegūt viltus pozitīvu rezultātu.
Darbības princips
Blūma filtrs satur bitu masīvu (garumu m) un izmanto k neatkarīgas hash funkcijas. Lai pievienotu elementu, to izhashē ar k funkcijām; katrā rezultātā iegūtais indekss bitu masīvā tiek iestatīts uz 1. Lai pārbaudītu, vai elements ir kopā, to izhashē ar tām pašām k funkcijām un pārbauda attiecīgos bitus. Ja visiem k bitiem ir vērtība 1, filtrs atgriež "iespējams, ir kopā" (var būt viltus pozitīvs). Ja kāds no bitiem ir 0, filtrs atgriež "noteikti nav kopā".
Viltus pozitīvo rezultātu varbūtību ietekmē bitu masīva garums m, pievienoto elementu skaits n un hash funkciju skaits k. Aptuvenā formula viltus pozitīva varbūtībai p ir:
- p ≈ (1 − e^{−k n / m})^k
Optimalais k, kas minimizē p konkrētiem m un n, ir aptuveni k = (m / n) · ln 2. Tas parāda kompromisu starp atmiņas izmantošanu un kļūdu biežumu: vairāk bitu uz elementu samazina p, bet prasa vairāk atmiņas.
Vēsture un praktiska motivācija
Blūma filtru 1970. gadā ieviesa Burton H. Bloom (rakstā par telpas/laika kompromisiem ar pieļaujamu kļūdu). Bloom izmantoja piemērus, piemēram, vārdšķiršanas (hyphenation) problēmu, lai parādītu, ka ar mazu atmiņu iespējams izslēgt lielāko daļu laikietilpīgu meklēšanu vai diska piekļuves — pat ja reizēm rodas jāpārbauda papildu gadījumi (viltus pozitīvi), tas būtiski samazina kopējo laiku un resursus. Piemēram, ja hash laukums ir tikai apmēram 15% no ideāla bezkļūdu hash lauka lieluma, joprojām var novērst aptuveni 85% diska piekļuves reižu.
Pielietojumi
- Kešēšana un priekšfiltri (piem., pārbaudīt, vai URL jau apstrādāts tīmekļa rāvējamā)
- Datubāzes un sadrumstalotie sistēmu mezgli, lai ātri noteiktu, vai dati varētu būt lokāli
- Sūtījumu filtrēšana tīklos (piem., SPAM filtri, neapstrādātu elementu atlase)
- Bloom filtri izmantojami arī sadarbojošos sistēmās, lai samazinātu neefektīvas sinhronizācijas un datu apmaiņas apjomu
Ierobežojumi un paplašinājumi
Parastajam Blūma filtram ir būtiski ierobežojumi — nav iespējas droši izdzēst elementus un pastāv viltus pozitīvie. Lai risinātu šos trūkumus, attīstīti varianti:
- Counting Bloom filter — izmanto skaitītājus nevis vienu bitu, ļauj dzēst elementus (samazina atmiņas efektivitāti).
- Scalable Bloom filter — paplašināms filtrs, kas pievieno jaunas tablas, kad kopas lielums pieaug, saglabājot noteiktu kļūdu līmeni.
- Cuckoo filter — alternatīva, kas dažos gadījumos piedāvā labāku atmiņas izmantošanu un atbalstu dzēšanai, saglabājot zemu kļūdu līmeni.
- Kriptogrāfiskas drošības apsvērumi: ja hash funkcijas nav pietiekami labi izvēlētas, var rasties nevēlamas sadursmes; praksē izmanto labi izplatītas un ātras hash funkcijas vai kombinācijas no tām.
Praktisks skaitlisks piemērs
Ja m / n = 10 biti uz elementu, tad optimālais k ≈ 10 · ln 2 ≈ 7. Ar šo iestatījumu viltus pozitīvo varbūtību varam sagaidīt aptuveni p ≈ 0.7–1% (atkarībā no precīzā m un n vērtībām). Tāpēc tiek minēts, ka 1% viltus pozitīva iznākuma varbūtībai parasti nepieciešami mazāk nekā 10 biti uz elementu, neatkarīgi no kopas lieluma.
Kopsavilkums
Blūma filtrs ir vienkārša, ātra un ļoti atmiņas efektīva strukturāla tehnika, lai veiktu membership pārbaudes liela datu apjoma gadījumā, pieņemot kompromisu — pieļaujamu skaitu viltus pozitīvu rezultātu. To plaši lieto sistēmās, kur nepieciešama ātra filtrēšana un kur viltus pozitīvi ir pieņemami, savukārt viltus negatīvi nav atļauti. Kad vajadzīga dzēšana vai pilnīgas garantijas pret viltus pozitīviem, izvēlas paplašinātas versijas vai citas struktūras (piem., counting Bloom vai cuckoo filter).
Jautājumi un atbildes
J: Kas ir Bloom filtrs?
A: Blūma filtrs ir datu struktūra, kas ļauj datoriem noskaidrot, vai dotais elements ir sastopams kādā kopā. Lai to izdarītu, tiek izmantotas hash funkcijas, aprēķinot katra pievienotā elementa hash vērtību un salīdzinot to ar citiem elementiem kopā.
J: Kāda veida datu struktūra ir Blooma filtrs?
A: Blooma filtrs ir varbūtiska datu struktūra, kas nozīmē, ka pastāv iespēja iegūt viltus pozitīvus, bet ne viltus negatīvus rezultātus.
J: Kas ierosināja Blooma filtru?
A: Edvards Blūms ierosināja Blūma filtru 1970. gadā.
J: Kāds bija Edvarda piemērs viņa metodes izmantošanai?
A: Edvarda piemērs bija aptuveni 500 000 vārdu defisi; viņš atklāja, ka, izmantojot savu metodi, viņš var novērst lielāko daļu meklējumu un par 15 % samazināt piekļuvi diskam.
J: Cik bitu uz elementu ir nepieciešams, lai iegūtu 1% viltus pozitīvu rezultātu varbūtību?
A: 1% viltus pozitīvam rezultātam neatkarīgi no kopas lieluma vai elementu skaita ir nepieciešami mazāk nekā 10 biti uz elementu.
Vai ir iespējams no bloom filtra izņemt elementus pēc to pievienošanas?
A: Nē, elementus var tikai pievienot kopai, bet ne izņemt.
Vai, pievienojot vairāk elementu, palielinās vai samazinās viltus pozitīva rezultāta iegūšanas varbūtība?
A: Ja pievieno vairāk elementu, palielinās viltus pozitīva rezultāta iegūšanas varbūtība.
