Blūma filtrs
Blūma filtrs ir datu struktūra, kas ļauj datoriem pārbaudīt, vai dotais elements ir sastopams kopā. Blooma filtri šim nolūkam izmanto hash funkcijas. Katram pievienotajam elementam tiek aprēķināta hash vērtība. Kad tiek pievienots jauns elements, tā hash vērtība tiek salīdzināta ar citu kopas elementu vērtību. Blooma filtrs ir varbūtiska datu struktūra. Ir iespējams iegūt viltus pozitīvu rezultātu, bet nav iespējams iegūt viltus negatīvu rezultātu. Citiem vārdiem sakot, vaicājums atgriež vai nu "iespējams, ir kopā", vai "noteikti nav kopā". Elementus var pievienot kopai, bet ne izņemt. Ar katru pievienoto elementu pieaug varbūtība, ka tiks iegūts viltus pozitīvs rezultāts.
Edvards Blūms Blūma filtru ierosināja 1970. gadā. Šajā rakstā Blūms pieņem, ka pastāv algoritms, kas ļauj salikt vārdus rindas beigās. Saskaņā ar piemēru lielākajai daļai vārdu ir vienkārši defisēšanas modeļi. Taču aptuveni 10 % vārdu ir nepieciešama laikietilpīga meklēšana, lai iegūtu pareizo noteikumu. Viņa piemērs bija apmēram 500 000 vārdu defisi. Viņš redzēja, ka, izmantojot "parastās" bezkļūdu šifrēšanas metodes, kas glabā defisifikācijas modeļus, būtu nepieciešams daudz atmiņas. Viņš atklāja, ka, izmantojot savu paņēmienu, viņš var novērst lielāko daļu meklēšanu. Piemēram, ja hash laukums ir tikai 15 % no ideālam bezkļūdu hash laukumam nepieciešamā lieluma, joprojām tiek novērsti 85 % diska piekļuves reižu.
Vispārīgāk runājot, 1 % viltus pozitīva iznākuma varbūtībai ir nepieciešami mazāk nekā 10 biti uz elementu neatkarīgi no kopas lieluma vai elementu skaita.
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.
