精华内容
参与话题
问答
  • bloom

    2019-07-16 18:22:48
    BloomFilter 模块信息 util/bloom.cc 模块概要 布隆过滤器由一个很大的bit数组和很多的哈希函数组成,用于判断一个元素是否在集合中。 当要往集合中加入一个元素时,就通过这些哈希函数将这个元素映射到bit数组不同...

    BloomFilter

    模块信息

    util/bloom.cc

    模块概要

    布隆过滤器由一个很大的bit数组和很多的哈希函数组成,用于判断一个元素是否在集合中。

    当要往集合中加入一个元素时,就通过这些哈希函数将这个元素映射到bit数组不同的位上,并将该位设置为1。

    当要判断一个元素是否在集合中时,同样通过一系列哈希函数将元素映射到bit数组不同位上,如果出现某个位不为1,则说明该元素不在集合中。

    布隆过滤器是有可能产生错误的,为了减少错误,bit数组不能太小,不然很快各个位就变为1了。假设要加入n个元素,有k个哈希函数,bit数组大小位m,则满足以下公式时有最低误差率:
    k=(m/n)ln2 k=(m/n)*ln2

    主要接口

    方法 说明
    void CreateFilter(const Slice* keys, int n, std::string* dst) 加入n个key到dst中,用string来表示
    bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) 判断key是否在集合中

    源码分析

    void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
        // 总共的位数为n个key*每个key所占的位数
        size_t bits = n * bits_per_key_;
    
    	// 为了保证位数不能太少,不然很快就全1了
        if (bits < 64) bits = 64;
    	// 向上找到第一个8的倍数,因为一个字节是8位,为了方便查找
        size_t bytes = (bits + 7) / 8;
        bits = bytes * 8;
    	
    	// 获取原有string的大小,resize是调整大小,新增的bytes部分置0,最后一个字节放k
    	// 可以看出,一个string装了多个bit数组
        const size_t init_size = dst->size();
        dst->resize(init_size + bytes, 0);
        dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter
        
        // (*dst)[init_size]是刚刚新增加内容的首个元素,用一个指针array指向它,这样就可以通过
        // array来改变string即bit数组的内容了
        char* array = &(*dst)[init_size];
        for (int i = 0; i < n; i++) {
          // 获取元素的哈希值
          uint32_t h = BloomHash(keys[i]);
          const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
          for (size_t j = 0; j < k_; j++) {
            const uint32_t bitpos = h % bits;
            // bitpos/8代表在第几个字节中(char占一个字节),bitpos%8代表在这个字节中的第几位
            array[bitpos / 8] |= (1 << (bitpos % 8));
            // 每次改变这个哈希值,就像用了k个哈希函数一样
            h += delta;
          }
        }
    }
    
    bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override {
        const size_t len = bloom_filter.size();
        if (len < 2) return false;
    
        const char* array = bloom_filter.data();
        // len包括了最后一个k的,所以减1
        const size_t bits = (len - 1) * 8;
    
        // 获取哈希函数个数
        const size_t k = array[len - 1];
        if (k > 30) {
          // Reserved for potentially new encodings for short bloom filters.
          // Consider it a match.
          return true;
        }
    	// 映射的方法和插入一样
        uint32_t h = BloomHash(key);
        const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
        for (size_t j = 0; j < k; j++) {
          const uint32_t bitpos = h % bits;
          // 哈希映射到的那一位不为1
          if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;
          h += delta;
        }
        return true;
      }
    

    TO_DO

    • delta设置为循环右移17位有什么讲究?
    展开全文
  • Bloom

    千次阅读 2016-07-30 14:59:53
    Bloom 高斯模糊effect有各种各样的应用。比如,可以用于区分场景中背景objects(通过模糊处理使得objects呈现出一种失去焦点的现象)和前景objects(没有模糊处理)。另外还可以用于bloom(曝光) effect中,一种...

    Bloom

    高斯模糊effect有各种各样的应用。比如,可以用于区分场景中背景objects(通过模糊处理使得objects呈现出一种失去焦点的现象)和前景objects(没有模糊处理)。另外还可以用于bloom(曝光) effect中,一种bloom effect通过增强场景中明亮的区域来模拟真实世界中的照相机。图18.6显示了在一个场景中使用曝光(上图)和不使用曝光effect的输出结果。


    图18.6 A scene rendered with (top) and without (bottom) a bloom effect. (Skybox texture by Emil Persson. Earth texture from Reto Stöckli, NASA Earth Observatory.)
    使用如下的步骤可以创建一种bloom effect:
    1、把场景绘制到一个off-screen render target中。
    2、从场景图像中提取明亮的斑点保存到一个off-screen render target(创建一个glow map)中。
    3、对glow map进行模糊处理并保存到一个off-screen render target中。
    4、把经过模糊处理后的glow map与原始的scene texture进行合并,并把结果渲染到屏幕上。
    列表18.12列出了Bloom.fx effect的代码。其中包含了三个独立的techniques:一个用于从输入的texture中提取出明亮的区别,创建一个曝光贴图(glow map),另一个是把模糊处理后的glow map与原始的scene texture进行合并,第三个是渲染未经过修改的原始scene texture。在Bloom.fx effect中没有复制高斯模糊的代码,因为可以在应用程序中直接使用前面编写的高斯模糊component对提取出的glow map进行模糊处理。

    列表18.12 The Bloom.fx Effect

    /************* Resources *************/
    
    static const float3 GrayScaleIntensity = { 0.299f, 0.587f, 0.114f };
    
    Texture2D ColorTexture;
    Texture2D BloomTexture;
    
    cbuffer CBufferPerObject
    {
        float BloomThreshold = 0.3f;
        float BloomIntensity = 1.25f;
        float BloomSaturation = 1.0f;
        float SceneIntensity = 1.0f;
        float SceneSaturation = 1.0f;
    };
    
    SamplerState TrilinearSampler
    {
        Filter = MIN_MAG_MIP_LINEAR;
        AddressU = WRAP;
        AddressV = WRAP;
    };
    
    /************* Data Structures *************/
    
    struct VS_INPUT
    {
        float4 Position : POSITION;
        float2 TextureCoordinate : TEXCOORD;
    };
    
    struct VS_OUTPUT
    {
        float4 Position : SV_Position;
        float2 TextureCoordinate : TEXCOORD;  
    };
    
    /************* Utility Functions *************/
    
    float4 AdjustSaturation(float4 color, float saturation)
    {
        float intensity = dot(color.rgb, GrayScaleIntensity);
        
        return float4(lerp(intensity.rrr, color.rgb, saturation), color.a);
    }
    
    /************* Vertex Shader *************/
    
    VS_OUTPUT vertex_shader(VS_INPUT IN)
    {
        VS_OUTPUT OUT = (VS_OUTPUT)0;
        
        OUT.Position = IN.Position;
        OUT.TextureCoordinate = IN.TextureCoordinate;
        
        return OUT;
    }
    
    /************* Pixel Shaders *************/
    
    float4 bloom_extract_pixel_shader(VS_OUTPUT IN) : SV_Target
    {
        float4 color = ColorTexture.Sample(TrilinearSampler, IN.TextureCoordinate);
    
        return saturate((color - BloomThreshold) / (1 - BloomThreshold));
    }
    
    float4 bloom_composite_pixel_shader(VS_OUTPUT IN) : SV_Target
    {
        float4 sceneColor = ColorTexture.Sample(TrilinearSampler, IN.TextureCoordinate);
        float4 bloomColor = BloomTexture.Sample(TrilinearSampler, IN.TextureCoordinate);
        
        sceneColor = AdjustSaturation(sceneColor, SceneSaturation) * SceneIntensity;
        bloomColor = AdjustSaturation(bloomColor, BloomSaturation) * BloomIntensity;
        
        sceneColor *= (1 - saturate(bloomColor));	
    
        return sceneColor + bloomColor;
    }
    
    float4 no_bloom_pixel_shader(VS_OUTPUT IN) : SV_Target
    {
        return ColorTexture.Sample(TrilinearSampler, IN.TextureCoordinate);
    }
    
    /************* Techniques *************/
    
    technique11 bloom_extract
    {
        pass p0
        {
            SetVertexShader(CompileShader(vs_5_0, vertex_shader()));
            SetGeometryShader(NULL);
            SetPixelShader(CompileShader(ps_5_0, bloom_extract_pixel_shader()));
        }
    }
    
    technique11 bloom_composite
    {
        pass p0
        {
            SetVertexShader(CompileShader(vs_5_0, vertex_shader()));
            SetGeometryShader(NULL);
            SetPixelShader(CompileShader(ps_5_0, bloom_composite_pixel_shader()));
        }
    }
    
    technique11 no_bloom
    {
        pass p0
        {
            SetVertexShader(CompileShader(vs_5_0, vertex_shader()));
            SetGeometryShader(NULL);
            SetPixelShader(CompileShader(ps_5_0, no_bloom_pixel_shader()));
        }
    }
    
    

    在bloom_extract_pixel_shader中,将纹理采样的颜色值与一个从应用程序中传递过来的threshold变量值进行比较,如果颜色值小于threshod,输出的pixel就是黑色的。然后对threshold进行取反并用于调整颜色值。这并不是创建一个glow map的唯一方法:还可以使用纹理采样的强度值与曝光的threshod值进行比较。例如:

    float4 bloom_extract_pixel_shader(VS_OUTPUT IN) : SV_Target
    {
    	float4 color = ColorTexture.Sample(TrilinearSampler, IN.TextureCoordinate);
    	float intensity = dot(color.rgb, GrayScaleIntensity);
    	return (intensity > BloomThreshold ? color : float4(0, 0, 0, 1));
    }
    
    

    图18.7中显示了使用这两种pixel shaders从一个场景中提取的glow map结果。


    图18.7 Glow maps extracted from a scene using the original method (top) and an alternate method (bottom). (Skybox texture by Emil Persson. Earth texture from Reto Stöckli, NASA Earth Observatory.)
    通过使用高斯模糊组件对glow map进行模糊处理,使得该glow map显示出了一种“流血”的效果就像光被其实的pixels吸收了一样。然后把模糊处理后的glow map与原始的scene texture结合得到最终的结果,但是你也可以使用强度(intensity)和饱和度(saturation)值进一步调整最终的scene颜色值。本书的配套网站上提供了一个示例程序,支持在运行时动态调整强度和饱和度值。通过使用不同的值将会生成一些有趣的结果。

    Distortion Mapping

    本章要讨论的最后一种post-processing technique是失真贴图(distortion mapping)。Distortion mapping类似于第9章“Normal Mapping and Displacement Mapping”所讲的移位贴图(displacement mapping) effect。但不同的是,displacement mapping是通过改一个object的vertices,而distortion mapping是改变pixels。更具体地说,就是首先经过纹理采样(一个distortion map)得到水平和垂直方向的偏移量,然后把这些偏移量用作在scene texture查找纹理的UV坐标。

    A Full-Screen Distortion Shader

    列表18.13列出了一个full-screen post-processing distortion effect的pixel shader的代码。

    列表18.13 A Full-Screen Distortion Mapping Pixel Shader

    cbuffer CBufferPerObjectComposite
    {
    	float DisplacementScale = 1.0f;
    }
    
    Texture2D SceneTexture;
    Texture2D DistortionMap;
    
    SamplerState TrilinearSampler
    {
    	Filter = MIN_MAG_MIP_LINEAR;
    	AddressU = CLAMP;
    	AddressV = CLAMP;
    };
    
    float4 displacement_pixel_shader(VS_OUTPUT IN) : SV_Target
    {
    	float4 OUT = (float4)0;
    	float2 displacement = DistortionMap.Sample(TrilinearSampler, IN.TextureCoordinate).xy - 0.5;
    	OUT = SceneTexture.Sample(TrilinearSampler, IN.TextureCoordinate + (DisplacementScale * displacement));
    	return OUT;
    }
    
    

    在pixel shader中,通过采样两个通道值(x和y)得到displacement变量的水平和垂直方向值。这些通道值都是8-bit,由范围[0, 255]映射到浮点数范围[0.0, 1.0]。但是pixel的displacement值可以是正数也可以是负数,因此需要扩展这些范围。具体范围由所创建的displacement maps决定,但是在本书的这个例子中使用范围[-0.5, 0.5]。从一个美术设计师的角度看,通道值为127表示(almost几乎)不进行移位displacement。之所以说几乎(almost)不移位,是因为127 / 255 ≈ 0.49804,因此有一个0.5 - 0.49804 = 0.00196的误差值。通过在displaceent计算中加上该误差值,就可以抵销这个误差。例如:

    static const float ZeroCorrection = 0.5f / 255.0f;
    float2 displacement = DistortionMap.Sample(TrilinearSampler, IN.TextureCoordinate).xy - 0.5 + ZeroCorrection;
    
    

    渲染这种distortion mapping shader与color filtering shadrs一样,就是一个正常的post-processing。首先把场景渲染到一个off-screen render target中,然后使用distortion mapping shader把一个full-screen quad渲染到back buffer中。图18.8显示了displacement shader的渲染输出结果,其中使用了一种看起来像毛玻璃效果的distortion map。


    图18.8 Output of the full-screen distortion mapping shader using a distortion map resembling warped glass. (Skybox texture by Emil Persson. Earth texture from Reto Stöckli, NASA Earth Observatory.)

    使用毛玻璃效果的distortion map所产生的变化是如此细微,以至于无法简单地区分失真的干扰(即使是在一个放大的图像中)。因此,在displacement shader中使用一种包含“Direct3D !”文字的distortion map(如图18.9下图所示),可以得到如图18.9上图所示的输出结果。该distortion map呈现出一种淡黄色,因为在该map中每一个pixel只填充了red和green通道值。


    图18.9 Output of the full-screen distortion mapping shader (top) and associated distortion map (bottom). (Skybox texture by Emil Persson. Earth texture from Reto Stöckli, NASA Earth Observatory.)

    A Masking Distortion Shader

    使用full-screen distortion mapping shader可以产生一些有趣的效果,如果动态处理displacenment偏移值(通过使用一个持续变化的值(如时间值)来调整该偏移值),则会使渲染结果更有趣。但是,我们可能并不想让整个场景都失真。例如,通过使图像局部失真可以模拟一团火焰上(或者发热的路面上)的烟雾,并在该特定区域独立使用这种effect。

    实现这种效果的一种方法是创建一个运行时的distortion mask(失真蒙板),在一个full-screen distortion map上裁剪一块将要进行失真处理的区域。图18.10显示了一个使用毛玻璃的失真贴图以及一个sphere创建的distortion mask。


    图18.10 A distortion mask made with a sphere.
    要创建这种distortion mask,需要在一个off-screen render target中首先ClearRenderTarget为黑色,然后渲染objects。但是,我们可以从一个distortion map中获取偏移值,而不是从一个object的color texture中采样颜色值。因此,在最终创建的distortion mask中要么是黑色的区域要么是distortion偏移值。创建完mask之后,就可以在scene texture和distortion mask之间执行post-processing操作。首先,从distortion mask中采样偏移值,如果该值表示黑色,那么采scene texture就不需要移位纹理的UV坐标。否则,就使用从mask中采样的偏移值对纹理的UV坐标进行偏移。列表18.14列出了distortion mapping effect的完整代码。

    列表18.14 A Masking Distortion Mapping Effect

    /************* Resources *************/
    static const float ZeroCorrection = 0.5f / 255.0f;
    
    cbuffer CBufferPerObjectCutout
    {
        float4x4 WorldViewProjection : WORLDVIEWPROJECTION;	
    }
    
    cbuffer CBufferPerObjectComposite
    {
        float DisplacementScale = 1.0f;
    }
    
    Texture2D SceneTexture;
    Texture2D DistortionMap;
    
    SamplerState TrilinearSampler
    {
        Filter = MIN_MAG_MIP_LINEAR;
        AddressU = CLAMP;
        AddressV = CLAMP;
    };
    
    /************* Data Structures *************/
    
    struct VS_INPUT
    {
        float4 Position : POSITION;
        float2 TextureCoordinate : TEXCOORD;
    };
    
    struct VS_OUTPUT
    {
        float4 Position : SV_Position;
        float2 TextureCoordinate : TEXCOORD;
    };
    
    /************* Cutout *************/
    
    VS_OUTPUT distortion_cutout_vertex_shader(VS_INPUT IN)
    {
        VS_OUTPUT OUT = (VS_OUTPUT)0;
        
        OUT.Position = mul(IN.Position, WorldViewProjection);
        OUT.TextureCoordinate = IN.TextureCoordinate;
    
        return OUT;
    }
    
    float4 displacement_cutout_pixel_shader(VS_OUTPUT IN) : SV_Target
    {
        float2 displacement = DistortionMap.Sample(TrilinearSampler, IN.TextureCoordinate).xy;
    
        return float4(displacement.xy, 0, 1);
    }
    
    /************* Compositing *************/
    
    VS_OUTPUT distortion_composite_vertex_shader(VS_INPUT IN)
    {
        VS_OUTPUT OUT = (VS_OUTPUT)0;
        
        OUT.Position = IN.Position;
        OUT.TextureCoordinate = IN.TextureCoordinate;
        
        return OUT;
    }
    
    float4 distortion_composite_pixel_shader(VS_OUTPUT IN) : SV_Target
    {
        float4 OUT = (float4)0;
    
        float2 displacement = DistortionMap.Sample(TrilinearSampler, IN.TextureCoordinate).xy;
        if (displacement.x == 0 && displacement.y == 0)
        {
            OUT = SceneTexture.Sample(TrilinearSampler, IN.TextureCoordinate);
        }
        else
        {
            displacement -= 0.5f + ZeroCorrection;
            OUT = SceneTexture.Sample(TrilinearSampler, IN.TextureCoordinate + (DisplacementScale * displacement));
        }
    
        return OUT;
    }
    
    float4 no_distortion_pixel_shader(VS_OUTPUT IN) : SV_Target
    {
        return SceneTexture.Sample(TrilinearSampler, IN.TextureCoordinate);
    }
    
    /************* Techniques *************/
    
    technique11 displacement_cutout
    {
        pass p0
        {
            SetVertexShader(CompileShader(vs_5_0, distortion_cutout_vertex_shader()));
            SetGeometryShader(NULL);
            SetPixelShader(CompileShader(ps_5_0, displacement_cutout_pixel_shader()));
        }
    }
    
    technique11 distortion_composite
    {
        pass p0
        {
            SetVertexShader(CompileShader(vs_5_0, distortion_composite_vertex_shader()));
            SetGeometryShader(NULL);
            SetPixelShader(CompileShader(ps_5_0, distortion_composite_pixel_shader()));
        }
    }
    
    technique11 no_distortion
    {
        pass p0
        {
            SetVertexShader(CompileShader(vs_5_0, distortion_composite_vertex_shader()));
            SetGeometryShader(NULL);
            SetPixelShader(CompileShader(ps_5_0, no_distortion_pixel_shader()));
        }
    }
    
    

    在该shader中包含了三种techniques: distortion_cutout:调用vertex和pixel shader用于创建distortion mask。在vertex shader中,输入参数的vertex position应该位于object space,因此需要对position执行变换。在pixel shader中,使用vertices的纹理坐标从distortion map采样颜色值,然后把x和y通道值作为输出。
    distortion:定义了在scene texture和distortion map之间post-processing的执行步骤。在vertex shader中要求输入的vertex positions已经位于screen space,而且不执行变换(与所有的post-processing effects一样)。在pixel shader中根据采样得到的偏移值,判断在采样scene texture时是否要使用displacement偏移值。
    no_distortion:不执行失真操作,直接输出scene texture。

    渲染masking distortion shader需要使用两个render targets,一个用于渲染无失真的背景objects,另一个用于创建distortion mask。在本书的配套网站上提供一个完整示例程序。图18.11中显示了使用masking distortion shader的输出结果(上图),该shader中使用了一种人形躯干模型创建distortion mask(下图)。


    图18.11 Output of the distortion masking shader (top) and associated distortion mask (bottom). (Skybox texture by Emil Persson. 3D model by Nick Zuccarello, Florida Interactive Entertainment Academy.)

    总结

    本章介绍了post-processing主题相关的知识,post-processing是指在渲染完成后的场景中使用一些图形技术。编写了大量的post-processing effects用于表示color filtering,Gaussian blurring,bloom/glow以及distortion mapping。并在C++渲染引擎中使用full-screen render target和quad component集成了这些effects,最后通过演示程序练习了这些effects的使用。
    在下一章,我们将会学习projective texture mapping(投影纹理贴图)和shadow mapping(阴影贴图)。

    Exercises

    1. Experiment with all the effects and demo applications from this chapter. Vary the shader
    inputs, and observe the results.
    2. Create your own distortion maps for the post-processing distortion shader, and use them
    with the associated demo application.
    3. Animate the masking distortion shader to simulate heat haze above a fire. Hint: Use
    GameTime::TotalGameTime() as input into the shader.
    1、测试本章所有的effect和示例程序。在shader中使用不同的输入,并观察输了结果。
    2、创建你自己的distortion maps用于post-processing distortion shader,并在对应的示例程序中使用该shader。
    3、实现一个动态变化的masking distortion shader,用于模拟一团火焰上的烟雾效果。提示:使用函数GameTime::TotalGameTime()的返回值作为shader的输入。
    展开全文
  • 文章目录布隆过滤器 - Redis 布隆过滤器,Guava 布隆过滤器 BloomFilter1、布隆过滤器的起源,用途2、布隆过滤器的概念3、布隆过滤器的优缺点1、优点2、缺点4、应用场景5、布隆过滤器的工作原理6、布隆过滤器的设计 ...

    布隆过滤器 - Redis 布隆过滤器,Guava 布隆过滤器 BloomFilter


    1、布隆过滤器的起源,用途

    布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

    2、布隆过滤器的概念

    如果想要判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表(又叫哈希表,Hash table)的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点。这样一来,我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

    Hash面临的问题就是冲突。假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们在说谎,不过直觉上判断这种事情的概率是比较低的。

    3、布隆过滤器的优缺点

    1、优点

    相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

    布隆过滤器可以表示全集,其它任何数据结构都不能。

    2、缺点

    但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。常见的补救办法是建立一个小的白名单,存储那些可能被误判的元素。但是如果元素数量太少,则使用散列表足矣。

    另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位列阵变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

    在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

    4、应用场景

    • 网页URL 去重
    • 垃圾邮件识别
    • 黑名单
    • 查询加速【比如基于KV结构的数据】
    • 集合元素重复的判断
    • 缓存穿透

    5、布隆过滤器的工作原理

    布隆过滤器本身是一个很长的二进制向量,既然是二进制的向量,那么显而易见的,存放的不是0,就是1。

    新建一个16位的布隆过滤器,如图
    在这里插入图片描述

    有一个对象,我们通过

    • 方式一计算他的hash值,得到hash = 2
    • 方式二计算他的hash值,得到hash = 9
    • 方式三计算他的hash值,得到hash = 5

    通过三个方法计算得到三个数值,我们把这三个数值对应的布隆过滤器向量值改为1,表明该位置有值。

    第二个对象,加入得到值1 6 3,就把1 6 3 改为1

    对于布隆过滤器本身来说,并没有存储任何数据,只是计算该数据的位置,然后存储向量值

    那么,如果需要判断某个数据是否存在于布隆过滤器,就只需要判断计算出来的所有向量值是否都为1即可


    但是:

    当存储的数据向量不断增多,就可能会出现,2 9 5 向量值都为1,但是实际上没有这个数据的情况,这样就导致了,布隆过滤器只能判断某个数据一定不存在,但是不能保证某个数据一定存在。

    另外,因为一个向量位置可能被多个对象映射,所以,布隆过滤器无法删除数据

    6、布隆过滤器的设计

    布隆过滤器思路比较简单,但是对于布隆过滤器的随机映射函数设计,需要计算几次,向量长度设置为多少比较合适,这个才是需要认真讨论的。

    如果向量长度太短,会导致误判率直线上升。
    如果向量太长,会浪费大量内存。
    如果计算次数过多,会占用计算资源,且很容易很快就把过滤器填满。

    展开全文
  • Unreal Bloom

    2020-12-04 14:02:20
    Do you have any plan to include the unreal bloom effect inside postprocessing effects ? (already included bloom seems to not achieve the same effect). If not, do you have any hint or feedback on the ...
  • Reimplement bloom

    2020-12-01 20:10:46
    <div><p>The old bloom code dating back to 2007 is gone but nothing has yet been implemented as the replacement for it. Bloom and/or HDR is pretty much a must-have feature for any modern engine so this...
  • BLOOM_CARDINALITY(BLOOM_INTERSECTION(BLOOM_UNION_AGG(cohortsize.uniqueusers), BLOOM_UNION_AGG(retentionusers.uniqueusers))) AS retained, BLOOM_CARDINALITY(BLOOM_UNION_AGG(cohortsize.uniqueusers)) AS...
  • <div><p>Stumbled upon a weird bug due to the implementation of <code>lib/bloom.js</code>. The <code>add</code> function works but the <code>check</code> function does not (it always returns false). ...
  • Convert Bloom to es6 class

    2020-11-20 22:39:48
    <div><p>Converts Bloom to an es6 class, and moves it to a directory to have it as a separate module. <p>My thinking is to structure the VM as multiple modules which contain most of the code, and in ...
  • neo4j-bloom-1.3.1.zip

    2020-05-13 10:19:05
    【Neo4j Bloom是一个图形浏览应用程序,用于与图形数据进行可视化交互。Bloom为提供了从不同业务角度直观地调查和探索其图形数据的能力。它的说明性,无代码搜索到可视化设计使其成为促进同级,经理和执行人员之间...
  • Bloom Filter based on Redis

    2020-12-05 06:33:55
    concept of Redis to construct a Bloom Filter, For example (from another one): <pre><code> # encoding=utf-8 import redis from hashlib import md5 class SimpleHash(object): def __init__(self, ...
  • <ul><li>Added BloomFilter support in HashJoinTranslator. Optimizer can enable or disable the bloom filter by setting the flag in HashJoinPlan. Since we don't have cost model yet, it's default ...
  • <div><p>I would like to use outline upon mouse hovering a mesh and selective bloom when mesh gets actually selected. <p>In the following sample I am unable to do so, it seems than bloom is always ...
  • <p>How do I create a Bloom Effect on a scene drawn over a transparent canvas and background? <p>The closest I've gotten is with ALPHA blend mode which adds a blackish glow, similar in volume and ...
  • <div><p>Bloom filter in header section of so files is well described by: https://blogs.oracle.com/solaris/gnu-hash-elf-sections-v2 and lld/ELF/SyntheticSections.cpp <p>The point is that the static ...
  • <div><p>I got a Philips Hue Bloom and tried to add it to zigbee2mqtt. The device supports brightness and rgb but no kelvin levels. I have added the following to devices.js. <pre><code> { zigbeeModel...
  • <div><p>When clients like Go-ethereum and Parity create bloom filters, they trim leading zeroes off the topic before applying keccak to hash the value. As far as I can tell, this is inconsistent with ...
  • Bloom & Blur effects

    2020-12-02 02:18:43
    <p>Anybody knows the approach to achieve a blur or bloom effect with Rajawali? I think the solution is to use Post processing filters, but i don't know how to isolate the objects that i want to be...
  • RedisBloom-master.zip

    2020-05-11 19:18:53
    隆过滤器是Burton Howard Bloom在1970年提出来的,一种空间效率极高的概率型算法和数据结构,主要用来 判断一个元素是否在集合中存在。因为他是一个概率型的算法,所以会存在一定的误差,如果传入一个值去布隆过 ...
  • <p>Note that this appears to be a function of the cardinality of the bloom filter. The problem is manifest for </p><pre> bloom_agg("dataPoints.ids"->0->>'idValue', 0.05, ...
  • m trying to use ReBloom to create a bloom filter for checking user passwords against <a href="https://www.troyhunt.com/introducing-306-million-freely-downloadable-pwned-passwords/">the 300M+...
  • <p>As mentioned <a href="https://github.com/RedisLabsModules/rebloom/issues/9">in my other issue, I have a pretty large bloom filter (~320M items)</a>. My hope was to be able to build this bloom ...
  • <p>It includes the Bloom filter but I have added the option of enabling or disabling it to the options screen, it is <strong>off</strong> by default. <p>There were a number of things which I didn'...
  • sstable: prefix bloom filter

    2020-11-29 17:11:11
    <div><p>Add support for constructing the bloom filter on a prefix of the user key. Add a <code>Comparator.PrefixExtractor</code> function for extracting the prefix. <p>One question here is whether ...
  • will have no effect outside a bloom block. When used on tables, <= will place the tuples in, available in the <em>next</em> tick. <p>Disallowing <= loses us nothing that <+ doesn...
  • <p>The colour of the Hue Bloom isn't updated in the API. <h2>Steps to reproduce the behavior <p>Set the colour to <code>{"xy": [0, 0]}</code>. The bloom sets itself to its blue point, [0....

空空如也

1 2 3 4 5 ... 20
收藏数 5,375
精华内容 2,150
关键字:

bloom