18 января 2011 в 15:26

Фильтр Блума

И снова здравствуйте! Сегодня я поведаю о фильтре Блума — структуре данных гениальной в своей простоте. По сути, этот фильтр реализует вероятностное множество всего с двумя операциями: добавление элемента к множеству и проверка принадлежности элемента множеству. Множество вероятностное потому, что последняя операция на вопрос «принадлежит ли этот элемент множеству?» даёт ответ не в форме «да/нет», а в форме «возможно/нет».


Как фильтр это делает?


Как я уже говорил, идея до гениальности проста. Заводится массив битов фиксированного размера m и набор из k различных хеш-функций, выдающих значения от 0 до m - 1. При необходимости добавить элемент к множеству, для элемента считается значение каждой хеш-функции и в массиве устанавливаются биты с соответствующими индексами.

Для проверки принадлежности, как вы уже догадались, достаточно посчитать значения хеш-функций для потенциального члена и убедиться, что все соответствующие биты установлены в единицу — это и будет ответом «возможно». Если же хотя бы один бит не равен единице, значит множество этого элемента не содержит — ответ «нет», элемент отфильтрован.

Реализация


Код на JavaScript, просто потому что на Хабре он понятен многим. Прежде всего, нам нужно как-то представить битовый массив:

function Bits()
{
    var bits = [];
   
    function test(index)
    {
        return (bits[Math.floor(index / 32)] >>> (index % 32)) & 1;
    }
    
    function set(index)
    {
        bits[Math.floor(index / 32)] |= 1 << (index % 32);
    }
    
    return {test: test, set: set};
}

Так же, нам понадобится параметризированное семейство хеш-функций, чтобы было проще создавать k различных. Реализация простая, но работает на удивление хорошо:

function Hash()
{
    var seed = Math.floor(Math.random() * 32) + 32;
    
    return function (string)
    {
        var result = 1;
        for (var i = 0; i < string.length; ++i)
            result = (seed * result + string.charCodeAt(i)) & 0xFFFFFFFF;
        
        return result;
    };
}

Ну и собственно, сам фильтр Блума:

function Bloom(size, functions)
{
    var bits = Bits();
    
    function add(string)
    {
        for (var i = 0; i < functions.length; ++i)
            bits.set(functions[i](string) % size);
    }
    
    function test(string)
    {
        for (var i = 0; i < functions.length; ++i)
            if (!bits.test(functions[i](string) % size)) return false;
        return true;
    }
        
    return {add: add, test: test};
}

Пример использования:

var fruits = Bloom(64, [Hash(), Hash()]);
fruits.add('apple');
fruits.add('orange');

alert(fruits.test('cabbage') ? 'Возможно фрукт.' : 'Не фрукт, инфа 100%.');

После игр с параметрами, становится понятно, что для них должны быть какие-то оптимальные значения.

Оптимальные значения параметров


Конечно, теоритические оптимальные значения я сам не выводил, просто сходил на Википедию, но и без неё, включив логику, можно прикинуть и уловить некоторые закономерности. Например, нет смысла использовать большой битовый массив, если вы собираетесь хранить там два значения, обратное тоже верно, иначе массив будет перенаселён, что приведёт к росту ошибочных ответов «возможно». Оптимальный размер массива в битах:
Формула оптимального размера массива
, где n — предполагаемое количество элементов хранящихся в фильтре-множестве, p — желаемая вероятность ложного срабатывания.

Количество хеш-функций должно быть не большим, но и не маленьким. Оптимальное количество:

Формула оптимального количества функций
Применим полученные знания:

function OptimalBloom(max_members, error_probability)
{
    var size = -(max_members * Math.log(error_probability)) / (Math.LN2 * Math.LN2);
    var count = (size / max_members) * Math.LN2;

    size = Math.round(size);
    count = Math.round(count);
 
    var functions = [];
    for (var i = 0; i < count; ++i) functions[i] = Hash();
    
    return Bloom(size, functions);
}


Где использовать?


Например, Гуголь использует фильтры Блума в своей BigTable для уменьшения обращений к диску. Оно и не удивительно, ведь по сути, BigTable — это большая очень разреженная многомерная таблица, поэтому большая часть ключей указывает в пустоту. К тому же, данные распиливаются на относительно небольшие блоки-файлы, каждый из которых опрашивается при запросах, хотя может не содержать требуемых данных.

В данном случае, выгодно потратить немного оперативной памяти и сильно уменьшить использование диска. Скажем, чтобы уменьшить нагрузку в 10 раз, необходимо хранить примерно 5 бит информации на каждый ключ. Чтобы уменьшить в 100 раз, нужно порядка 10 бит на ключ. Выводы делайте сами.

Разные мысли


Судя по тестам, оптимальные значения параметров для практики несколько завышены, можно смело понижать порог ложного срабатывания на порядок-два. Только обязательно протестируйте, если будете использовать — возможно, в моих тестах подобралась какая-то уникальная комбинация данных и хеш-функций или я банально где-то ошибся.

Очевидно, что удалять элементы из фильтра невозможно, но это просто решается — достаточно заменить битовый массив на массив счётчиков — инкрементировать при добавлении, декрементировать при удалении. Расход памяти, естественно, возрастает.

Так же очевидно, что невозможно динамически изменять параметры фильтра. Проблема элегантно решается введением иерархии фильтров, каждый последующий более точен, при необходимости иерархия растёт вглубь.

Пожалуй, на этом всё. Пока.
+82
5667
154
stab 48,3

Комментарии (34)

0
Lass_ua, #
Хоть и не люблю такого стиля изложения, но статья понравилась, спасибо.
+2
stab, #
Пожалуйста. Над стилем буду работать. Что с ним не так? :)
+2
o_O_Tync, #
Зря, со стилем всё отлично: грамотно и последовательно. Остальное придёт с опытом :)
+12
Lass_ua, #
>>Здравствуй, мой маленький любитель алгоритмов.
>>До свидания, мой маленький.
Воспринимается неоднозначно. Но это мое субъективное имхо.
+1
stab, #
Подумалось, что без этого как-то суховато, тем более статья до академического уровня явно не дотягивает. Ничего плохого не имел в виду, чесслово.
+8
gvsmirnov, #
Ну совсем несерьёзно, люди с повышенным ЧСВ могут обидеться, чесслово!
0
lesha_penguin, #
Если ориентироваться на людей с повышенным ЧСВ, то придется вообще ничего не писать и не говорить, а заперется в глубоком бункере и молчать в тряпочку, потому что те, у кого ЧСВ выше среднего обижаются вообще на пустом месте:)

А статья интересная, хотелось бы развития темы в плане насколько фильтр блума может ускорить производительность на некоторых типовых задачах. Например, сравнить производительность проверки данных с «длинным ключем» на массивах данных хотя бы сотни тысяч записей без Фильтра Блума и с ним.
Т.е. интересует с практической стороны, что может получить в плане прироста производительности если перед «тяжелой проверкой» (поиск длинного ключа) поставить «легкую проверку» (Фильтр Блума).
+1
kirilloid, #
И взяли стиль изложения ксакепа ;-)
+6
stab, #
Исправил от греха подальше :)
+5
HomoLuden, #
Начало и концец — обращение к «маленьким», а вот изложение непростое…
Заводится массив бит фиксированного размера m и набор из k различных хеш-функций, выдающих значения от 0 до m — 1. При необходимости добавить элемент к множеству, для элемента считается значение каждой хеш-функции и в массиве устанавливаются соответствующие биты.

Идея-то может и проста, но вот такое описание я только с восьмого прочтения переваривать начал.
Хэш-функция выдает значение и что? Устанавливается бит с индексом, равным полученному значению? Или в массив записываются биты полученного числа.
Формулы пронумеровать бы… Последнее выражение для «k»… База логарифма какая?
0
HomoLuden, #
И вот еще…
достаточно посчитать значения хеш-функций для потенциального члена и убедиться, что все соответствующие биты установлены в единицу — это и будет ответом «возможно». Если же хотя бы один бит не равен единице, значит множество этого элемента не содержит — ответ «нет», элемент отфильтрован

«Соответствующие биты» — соответствующие чему? Можно пример небольшой? Хэш-функций много меньше числа бит в массиве. Все биты не будут установлены по получаемым индексам. А если не все, то какие? Шаблон использовать для массива?
0
stab, #
Про индексы поправил. Основание натуральное.
0
leventov, #
log означает базу 2, но автор намудрил там. Надо было писать ln 2
+2
Aivean, #
log — это общая функция. lg — основание 10, lb — основание 2.
–4
leventov, #
Впервые вижу «lb». log n — повсеместное сокращение log2n
–1
HomoLuden, #
Я lb не встречал, но выглядит вполне логично.
0
safron, #
еще ln — по основанию e
0
EXSlim, #
0 False, 1 True, 2 Maybe?
if maybe a in seq:
   pass
+6
dom1n1k, #
Странное ощущение от статьи: вроде каждое предложение по отдельности понятно, а общая картина смысла не складывается.
Есть какой-то алгоритм, есть структуры, есть код, есть формулы оптимальных параметров и даже вроде примерно понятно, зачем это может быть нужно.
Но понимания сути, как же это внутри работает, статья не даёт — а ведь это главное.
Например, про пузырьковую сортировку мне достаточно знать и понимать общий принцип сравнения/обмена соседних элементов, в результате которого за каждый проход наверх «всплывает» одно значение. Имея в голове ясную пошаговую картинку алготитма, код нетрудно «изобрести» самостоятельно.
0
HomoLuden, #
Именно так… Примеров наверное не хватает.
+5
afiskon, #
Хм, я конечно понимаю, что вы старались и все такое, но если честно, статья не очень понравилось.

На Википедии достаточно одного взгляда на картинку, чтобы понять, о чем речь. У вас же тут килобайта 3 текста из которых я так и не понял, зачем нужно _несколько_ хэш-функций.
0
Aivean, #
Интересно. Хотелось бы, конечно, оценок эффективности, особенно по сравнению с одной хэш-функцией и с отдельным массивом для каждой хэш-функции. Как я понимаю, «фишка» этой реализации в том, что благодаря случайному распределению хэшей при оптимальных параметрах эффективность выше, чем если бы массив был отдельный для каждой хэш-функции.
+1
stab, #
Честно говоря, долго пытался придумать пример наглядно показывающий, почему при одном массиве и нескольких функциях эффективность выше, чем при одном массиве и одной функции. Ни одной интуитивно понятной аналогии мне так в голову и не пришло, поэтому решил об этом не писать.

Фишка в том, что при заданной вероятности ложного срабатывания, одной функии и конечном кол-ве элементов, которые предполагается запомнить фильтром, эффективность фильтра ниже, поскольку все те «избыточные» биты, которые были введены для удерживания кол-ва ошибок выше определённого потолка, «никак» не используются.

Если ввести вторую функцию, то эти «неиспользуемые» биты разделяются между ними, при этом кол-во необходимых бит на ключ растёт линейно, а точность экспоненциально.
0
HomoLuden, #
После прочтения первого абзаца я, кажется, начал понимать суть, но тут же предложение из пятидесяти слов выбило почву из-под ног.
0
stab, #
Плин, «ниже определённого потолка».
+4
LiaDesign, #
После прочтения статьи на википедии сложилось такое «наглядное» представление назначения такой структуры данных:
есть много серверов, которые содержат key-value пары. Для выборки значения по ключу Key мы отправляем запрос на каждый сервер. Без подобного фильтра каждый сервер выполняет полноценный поиск по своему индексу — и эта операция довольно дорогая и будет выполнена на каждом сервере!
Фильтр Блума позволяет с малыми затратами ресурсов выяснить, что этот ключ может быть на 2-х серверах из 10-и — и отправить полноценный запрос лишь на эти два сервера.
Т.о. вопрос «зачем» для меня решен, а «как» — при необходимости приложится.
0
HomoLuden, #
Уже лучше… Вот бы нечто подобное с описанием «как» (еще раз, чтоб дуболому «мне» уж точно удалось понять) в статью вставить.
НЛО прилетело и опубликовало эту надпись здесь
0
stab, #
Почитал, на сколько я понял, фильтр Блума там используется для быстрой проверки на отсутствие слова в словаре исключений. А сами словари в виде trie представлены.
НЛО прилетело и опубликовало эту надпись здесь
+1
Frip, #
Если я правильно понял, алгоритм эффективен только при определенных обстоятельствах.

Допустим, мы хотим, чтобы наша реализация фильтра Блума отвечала на вопрос принадлежности с пятидесятипроцентной точностью. Тогда оптимальная длина вектора:
m = n* (-ln(0.5)/ln(2)^2) ~ 1.44*n

Но если мы возьмем вектор длинны n (в полтора раза меньший!) то можем просто хранить в нем информацию обо всех элементах множества, то есть отвечать на вопрос о пренадлежности со стопроцентной вероятностью. Ну, конечно, если найдем способ отображения наших элементов в множество натуральных чисел: )

Получается, есть смысл применять алгоритм тогда, когда ни отоброжение, ни индексирование элементов невозможно (затруднительно). При этом, чтобы получить 90% вероятность правильного срабатывания алгоритма, нам нужно выделить массиво бит, чья длинна (m ~ 5*n) в пять раз привышает длинну исходного множества элементов (вот! только теперь я понял смысл фразы «чтобы уменьшить нагрузку в 10 раз, необходимо хранить примерно 5 бит информации на каждый ключ.»!: ))

Вы знаете, следовало бы добавить в статью несколько простых примеов, объяснить «на пальцах»: )
0
BlastBeat, #
Спасибо за пояснения, сразу ответил на несколько возникших у меня вопросов.
Вердикт — съедобно.
0
DankoUA, #
Если мы найдем отображение нашего множества во множество {1,...,n}, то это еще не означает, что мы сможем хранить информацию в n битах — на практике нужно же еще как-то хранить само отображение, а на это отображение может уйти ооочень много бит. В случае фильтра Блума накладные расходы будут на сохранение набора хеш-функций, тоже не мало, но наверное всё-таки поменьше, чем если в тупую сохранять всё множество таблицей.
0
iPavel, #
Спасибо автору за то, что сказали о существовании такой штуки а также спасибо всем комментирующим. Отправился в википедию, дошло.
А в этой статье мне стало непонятно на фразе «При необходимости добавить элемент к множеству, для элемента считается значение каждой хеш-функции и в массиве устанавливаются биты с соответствующими индексами.» ИМХО эту часть стоит перефразировать, действительно пример или картинку/схему.

Только зарегистрированные пользователи могут оставлять комментарии.
Войдите, пожалуйста.