Bloom filter

Пример Фильтра Блума

by asartem

JavaScript

function Bits()
{
    var bits = [];   
    function test(index)
    {
        var bit_position = Math.floor(index / 32);
        var value_from_bitarray = bits[bit_position];
        var position_shif = value_from_bitarray >>> (index % 32)
        var result = position_shif & 1;
        return result;
    }
    
    function set(index)
    {
        var bit_position = Math.floor(index / 32);
        var value_from_bitarray = bits[bit_position];
        var bit_OR_result = value_from_bitarray |= 1;
        var result = bit_OR_result << (index % 32);        
        return result;
        
        //bits[Math.floor(index / 32)] |= 1 << (index % 32);
    }    
    return {test: test, set: set};
}
// самописная хеш-функция
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)
        {
            var hash_result = functions[i](string); // результат хеш-функции
            var bit_position = hash_result % size; // номер позиции бита в векторе размера size
            bits.set(bit_position);
        }
    }
    
    function lookup(string)
    {
        for (var i = 0; i < functions.length; ++i)
        {
            var hash_result = functions[i](string); // результат хеш-функции
            var bit_position = hash_result % size; // номер позиции бита в векторе размера size
            var test_result = bits.test(bit_position) // проверка бита в позиции
            if (!test_result) 
                return false;
        }
        return true;
    }
        
    return {add: add, test: lookup};
}



var fruits = Bloom(64, [Hash(),...