Филтърът на Блум
Филтърът на Блум е структура от данни, която позволява на компютрите да проверяват дали даден елемент се среща в дадено множество. За тази цел филтрите на Блум използват хеш функции. За всеки добавен елемент се изчислява хеш стойност. Когато се добави нов елемент, неговата хеш стойност се сравнява с тази на другите елементи в множеството. Филтърът на Блум е вероятностна структура от данни. Възможно е да се получи фалшиво положителен резултат, но не и фалшиво отрицателен. С други думи, дадена заявка връща или "вероятно в множеството", или "определено не е в множеството". Елементи могат да се добавят към множеството, но не и да се премахват. За всеки добавен елемент вероятността за получаване на фалшиво положителен резултат нараства.
Едуард Блум предлага филтъра на Блум през 1970 г. В статията Блум предполага, че съществува алгоритъм за разделяне на думите в края на реда. Според примера повечето думи имат прости модели на дефис. Но около 10% от думите изискват времеемки търсения, за да се извлече правилното правило. Неговият случай е свързан с дефисирането на около 500 000 думи. Той видял, че използването на "нормалните" техники за безгрешно хеширане, съхраняващи моделите за дефис, би изисквало много памет. Той установи, че използвайки своята техника, може да елиминира повечето търсения. Например област на хеширане, която е само 15 % от размера, необходим на идеалното безгрешно хеширане, все още елиминира 85 % от достъпа до диска.
По-общо казано, за 1 % вероятност за фалшиво положителен резултат са необходими по-малко от 10 бита на елемент, независимо от размера или броя на елементите в множеството.
Въпроси и отговори
В: Какво представлява филтърът на Блум?
О: Филтърът на Блум е структура от данни, която позволява на компютрите да проверяват дали даден елемент се среща в дадено множество. За целта се използват хеш функции, като се изчислява хеш стойността на всеки добавен елемент и се сравнява с другите елементи в множеството.
Въпрос: Какъв тип структура от данни е филтърът на Блум?
О: Филтърът на Блум е вероятностна структура от данни, което означава, че има възможност да се получат фалшиви положителни резултати, но не и фалшиви отрицателни.
В: Кой предложи филтъра на Блум?
О: Едуард Блум предлага филтъра на Блум през 1970 г.
В: Какъв е примерът на Едуард за използване на неговата техника?
О: Примерът на Едуард е свързан с дефисването на около 500 000 думи; той открива, че използвайки техниката си, може да премахне повечето търсения и да намали достъпа до диска с 15 %.
В: Колко бита на елемент са необходими за 1% вероятност за фалшиво положителен резултат?
О: За 1 % вероятност за фалшиво положителен резултат са необходими по-малко от 10 бита на елемент, независимо от размера или броя на елементите в множеството.
В: Възможно ли е да се премахнат елементи от цветен филтър, след като са добавени?
О: Не, елементи могат само да се добавят към множеството, но не и да се премахват.
Въпрос: Добавянето на повече елементи увеличава или намалява вероятността за получаване на фалшиво положителен резултат?
О: Добавянето на повече елементи увеличава вероятността за получаване на фалшив положителен резултат.
