filter_filters - CSDN
filter 订阅
Filter 技术是servlet 2.3 新增加的功能。servlet2.3是sun公司于2000年10月发布的,它的开发者包括许多个人和公司团体,充分体现了sun公司所倡导的代码开放性原则。在众多参与者的共同努力下,servlet2.3比以往功能都强大了许多,而且性能也有了大幅提高。 展开全文
Filter 技术是servlet 2.3 新增加的功能。servlet2.3是sun公司于2000年10月发布的,它的开发者包括许多个人和公司团体,充分体现了sun公司所倡导的代码开放性原则。在众多参与者的共同努力下,servlet2.3比以往功能都强大了许多,而且性能也有了大幅提高。
信息
外文名
Filter
发    布
2000年10月
体    现
代码开放性原则
作    用
改变request和修改response
出    自
sun公司
中文名
过滤器
所    属
servlet 2.3
Filter特点功能
它新增加的功能包括:1. 应用程序生命周期事件控制;2. 新的国际化;3. 澄清了类的装载规则;4. 新的错误及安全属性;5. 不赞成使用HttpUtils 类;6. 各种有用的方法;7. 阐明并扩展了几个servlet DTD;8. filter功能.
收起全文
  • java过滤器Filter

    2019-07-31 19:08:31
    Servlet中的过滤器Filter是实现了javax.servlet.Filter接口的服务器端程序,主要的用途是过滤字符编码、做一些业务逻辑判断如是否有权限访问页面等。其工作原理是,只要你在web.xml文件配置好要拦截的客户端请求,它...

    一、简介

    Servlet中的过滤器Filter是实现了javax.servlet.Filter接口的服务器端程序,主要的用途是过滤字符编码、做一些业务逻辑判断如是否有权限访问页面等。其工作原理是,只要你在web.xml文件配置好要拦截的客户端请求,它都会帮你拦截到请求,此时你就可以对请求或响应 (Request、Response)统一设置编码,简化操作;同时还可进行逻辑判断,如用户是否已经登陆、有没有权限访问该页面等等工作。它是随你的 web应用启动而启动的,只初始化一次,以后就可以拦截相关请求,只有当你的web应用停止或重新部署的时候才销毁,以下通过代码示例来了解它 的使用。

    二、实例

    package test.filter; 
    import ...; 
    /**
     * 介绍过滤器的使用,以设置编码为例
     */
    public class MyFilter implements Filter { 
      private FilterConfig config = null; 
      private boolean isFilter = false;
      
      public void destroy() { 
       System.out.println("MyFilter准备销毁..."); 
      } 
      
      public void doFilter(ServletRequest arg0, ServletResponse arg1, FilterChain chain) throws IOException, ServletException { 
       // 强制类型转换 
       HttpServletRequest request = (HttpServletRequest)arg0; 
       HttpServletResponse response = (HttpServletResponse)arg1; 
       // 获取web.xm设置的编码集,设置到Request、Response 中   
       request.setCharacterEncoding(config.getInitParameter("charset"));   
       response.setContentType(config.getInitParameter("contentType"));   
       response.setCharacterEncoding(config.getInitParameter("charset"));   
       // 将请求转发到目的地继续执行
       chain.doFilter(request, response);
      } 
      
      public void init(FilterConfig arg0) throws ServletException { 
       this.config = arg0; 
       if(isFilter){
          System.out.println("MyFilter初始化..."); 
       }
      } 
      
      private void setIsFilter(boolean isFilter){
    	this.isFilter = isFilter;
      }
    }

    然后在web. xml中配置该过滤器:

     <filter>
     	<filter-name>MyFilter</filter-name>
     	<filter-class>test.filter.MyFilter</filter-class>
     	<init-param>
     		<param-name>isFilter</param-name>
     		<param-value>true</param-value>
     	</init-param>
     </filter>
     <filter-mapping>
     	<filter-name>MyFilter</filter-name>
     	<url-pattern>/*</url-pattern>
     	<dispatcher>REQUEST</dispatcher> <!-- 没有配置dispatcher就是默认request方式的 -->
     	<dispatcher>FORWARD</dispatcher>
     	<dispatcher>ERROR</dispatcher>
     	<dispatcher>INCLUDE</dispatcher>
     </filt

    三、详细介绍

    在doFilter方法中通常都做些什么呢,下面列举一下:

    1、通过控制对chain.doFilter的方法的调用,来决定是否需要访问目标资源。

    比如,可以在用户权限验证等等。判断用户是否有访问某些资源的权限,有权限放行,没权限不执行chain.doFilter方法。
    2、在调用chain.doFilter方法之前,做些处理来达到某些目的。
    比如,解决中文乱码的问题等等。可以在doFilter方法前,执行设置请求编码与响应的编码。甚至可以对request接口进行封装装饰来处理get请求方式的中文乱码问题(重写相应的request.getParameter方法)。
    3、在调用chain.doFilter方法之后,做些处理来达到某些目的。
    比如对整个web网站进行压缩。在调用chain.doFilter方法之前用类A对response对象进行封装装饰,重写getOutputStream和重写getWriter方法。在类A内部中,将输出内容缓存进ByteArrayOutputStream流中,然后在chain.doFilter方法执行后,获取类A中ByteArrayOutputStream流缓存数据,用GZIPOutputStream流进行压缩下。

    Filter不仅可以通过url-pattern来指定拦截哪些url匹配的资源。而且还可以通过servlet-name来指定拦截哪个指定的servlet(专门为某个servlet服务了,servlet-name对应Servlet的相关配置)。

    filter-mapping标签中dispatcher指定过滤器所拦截的资源被Servlet 容器调用的方式,可以是REQUEST,INCLUDE,FORWARD和ERROR之一,默认REQUEST。用户可以设置多个<dispatcher> 子元素用来指定 Filter 对资源的多种调用方式进行拦截。

    REQUEST:

    当用户直接访问页面时,Web容器将会调用过滤器。如果目标资源是通过RequestDispatcher的include()或forward()方法访问或ERROR情况时,那么该过滤器就不会被调用。

    INCLUDE:

    如果目标资源是通过RequestDispatcher的include()方法访问时,那么该过滤器将被调用。除此之外,该过滤器不会被调用。

    FORWARD:

    如果目标资源是通过RequestDispatcher的forward()方法访问时,那么该过滤器将被调用,除此之外,该过滤器不会被调用。

    ERROR:

    如若在A.jsp页面page指令中指定了error属性=examError.jsp,那么A.jsp中若出现了异常,会跳转到examError.jsp中处理。而在跳转到examError.jsp时,若过滤器配置了ERROR的dispather那么则会拦截,否则不会拦截。

    四、高级配置(允许代理注入spring bean)

    web.xml中配置过滤器DelegatingFilterProxy:

     

    <filter>
        <filter-name>permission</filter-name>
        <filter-class>org.springframework.web.filter.DelegatingFilterProxy</filter-class>
        <init-param>
            <param-name>targetFilterLifecycle</param-name>
            <param-value>true</param-value>
        </init-param>
    </filter>
     <filter-mapping>
        <filter-name>permission</filter-name>
        <url-pattern>*.htm</url-pattern>
    </filter-mapping>

    在spring bean配置中加入:

    <bean id="permission" class="你的bean"></bean>

    bean的id必须和filter-name一样。如果想不一样,可以这样配置:

    <filter>
        <filter-name>permission</filter-name>
        <filter-class>org.springframework.web.filter.DelegatingFilterProxy</filter-class>
         <init-param>
            <param-name>targetFilterLifecycle</param-name>
            <param-value>true</param-value>
        </init-param>
        <init-param>
            <param-name>targetBeanName</param-name>
            <param-value>test</param-value>
        </init-param>
    </filter>
    <filter-mapping>
        <filter-name>permission</filter-name>
        <url-pattern>*.htm</url-pattern>
    </filter-mapping>

    在spring bean配置中加入:

    <bean id="test" class="你的bean"></bean>

    以上你的spring bean必须实现Filter接口。

    那这样子做是为了什么呢?

    答:这样做就可以将DelegatingFilterProxy所代理的filter作为spring的bean,受到spring的管理,也就是通过Spring容器来管理filter的生命周期,还有就是如果filter中需要一些Spring容器的实例,可以通过spring直接注入,另外读取一些配置文件这些便利的操作都可以通过Spring来配置实现。

    其中如果设置"targetFilterLifecycle"为True,则Filter.init()和Filter.destroy()有效;若为false,则这两个方法失效。

    如果大家有用到shiro(一个强大且易用的Java安全框架,执行身份验证、授权、密码学和会话管理等)的话,通常就会用到这个DelegatingFilterProxy了!

     

    展开全文
  • Bloom Filter概念和原理

    2007-02-05 21:22:00
    Bloom Filter概念和原理焦萌 2007年1月27日 Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断...

    Bloom Filter概念和原理

    焦萌 2007127

     

    Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

    集合表示和元素查询

    下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时,Bloom Filter是一个包含m位的位数组,每一位都置为0

    为了表达S={x1, x2,…,xn}这样一个n个元素的集合,Bloom Filter使用k个相互独立的哈希函数(Hash Function),它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x,第i个哈希函数映射的位置hi(x)就会被置为11ik)。注意,如果一个位置多次被置为1,那么只有第一次会起作用,后面几次将没有任何效果。在下图中,k=3,且有两个哈希函数选中同一个位置(从左边数第五位)。   

     

    在判断y是否属于这个集合时,我们对y应用k次哈希函数,如果所有hi(y)的位置都是11ik),那么我们就认为y是集合中的元素,否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合,或者刚好是一个false positive

    错误率估计

    前面我们已经提到了,Bloom Filter在判断一个元素是否属于它表示的集合时会有一定的错误率(false positive rate),下面我们就来估计错误率的大小。在估计之前为了简化模型,我们假设kn<m且各个哈希函数是完全随机的。当集合S={x1, x2,…,xn}的所有元素都被k个哈希函数映射到m位的位数组中时,这个位数组中某一位还是0的概率是:

    其中1/m表示任意一个哈希函数选中这一位的概率(前提是哈希函数是完全随机的),(1-1/m)表示哈希一次没有选中这一位的概率。要把S完全映射到位数组中,需要做kn次哈希。某一位还是0意味着kn次哈希都没有选中它,因此这个概率就是(1-1/m)的kn次方。令p = e-kn/m是为了简化运算,这里用到了计算e时常用的近似:

     

    ρ为位数组中0的比例,则ρ的数学期望E(ρ)= p’。在ρ已知的情况下,要求的错误率(false positive rate)为:

    (1-ρ)位数组中1的比例,(1-ρ)k就表示k次哈希都刚好选中1的区域,即false positive rate。上式中第二步近似在前面已经提到了,现在来看第一步近似。p’只是ρ的数学期望,在实际中ρ的值有可能偏离它的数学期望值。M. Mitzenmacher已经证明[2] ,位数组中0的比例非常集中地分布在它的数学期望值的附近。因此,第一步的近似得以成立。分别将pp’代入上式中,得:

       

       

    相比p’f’,使用pf通常在分析中更为方便。

    最优的哈希函数个数

    既然Bloom Filter要靠多个哈希函数将集合映射到位数组中,那么应该选择几个哈希函数才能使元素查询时的错误率降到最低呢?这里有两个互斥的理由:如果哈希函数的个数多,那么在对一个不属于集合的元素进行查询时得到0的概率就大;但另一方面,如果哈希函数的个数少,那么位数组中的0就多。为了得到最优的哈希函数个数,我们需要根据上一小节中的错误率公式进行计算。

     

    先用pf进行计算。注意到f = exp(k ln(1 − e−kn/m)),我们令g = k ln(1 − e−kn/m),只要让g取到最小,f自然也取到最小。由于p = e-kn/m,我们可以将g写成

    根据对称性法则可以很容易看出当p = 1/2,也就是k = ln2· (m/n)时,g取得最小值。在这种情况下,最小错误率f等于(1/2)k (0.6185)m/n。另外,注意到p是位数组中某一位仍是0的概率,所以p = 1/2对应着位数组中0和1各一半。换句话说,要想保持错误率低,最好让位数组有一半还空着。

     

    需要强调的一点是,p = 1/2时错误率最小这个结果并不依赖于近似值pf。同样对于f’ = exp(k ln(1 − (1 − 1/m)kn))g’ = k ln(1 − (1 − 1/m)kn)p’ = (1 − 1/m)kn,我们可以将g’写成

    同样根据对称性法则可以得到当p’ = 1/2时,g’取得最小值。

    位数组的大小

    下面我们来看看,在不超过一定错误率的情况下,Bloom Filter至少需要多少位才能表示全集中任意n个元素的集合。假设全集中共有u个元素,允许的最大错误率为є,下面我们来求位数组的位数m

     

    假设X为全集中任取n个元素的集合,F(X)是表示X的位数组。那么对于集合X中任意一个元素x,在s = F(X)中查询x都能得到肯定的结果,即s能够接受x。显然,由于Bloom Filter引入了错误,s能够接受的不仅仅是X中的元素,它还能够є (u - n)false positive。因此,对于一个确定的位数组来说,它能够接受总共n + є (u - n)个元素。在n + є (u - n)个元素中,s真正表示的只有其中n个,所以一个确定的位数组可以表示

    个集合。m位的位数组共有2m个不同的组合,进而可以推出,m位的位数组可以表示

       

    个集合。全集中n个元素的集合总共有

       

    个,因此要让m位的位数组能够表示所有n个元素的集合,必须有

       

    即:

       

    上式中的近似前提是nєu相比很小,这也是实际情况中常常发生的。根据上式,我们得出结论:在错误率不大于є的情况下,m至少要等于n log2(1/є)才能表示任意n个元素的集合。

     

    上一小节中我们曾算出当k = ln2· (m/n)时错误率f最小,这时f = (1/2)k = (1/2)mln2 / n。现在令fє,可以推出

    这个结果比前面我们算得的下界n log2(1/є)大了log2 e 1.44倍。这说明在哈希函数的个数取到最优时,要让错误率不超过єm至少需要取到最小值的1.44倍。

    总结

    在计算机科学中,我们常常会碰到时间换空间或者空间换时间的情况,即为了达到某一个方面的最优而牺牲另一个方面。Bloom Filter在时间空间这两个因素之外又引入了另一个因素:错误率。在使用Bloom Filter判断一个元素是否属于某个集合时,会有一定的错误率。也就是说,有可能把不属于这个集合的元素误认为属于这个集合(False Positive),但不会把属于这个集合的元素误认为不属于这个集合(False Negative)。在增加了错误率这个因素之后,Bloom Filter通过允许少量的错误来节省大量的存储空间。

     

    自从Burton Bloom70年代提出Bloom Filter之后,Bloom Filter就被广泛用于拼写检查和数据库系统中。近一二十年,伴随着网络的普及和发展,Bloom Filter在网络领域获得了新生,各种Bloom Filter变种和新的应用不断出现。可以预见,随着网络应用的不断深入,新的变种和应用将会继续出现,Bloom Filter必将获得更大的发展。

    参考资料

    [1] A. Broder and M. Mitzenmacher. Network applications of bloom filters: A survey. Internet Mathematics, 1(4):485–509, 2005.

    [2] M. Mitzenmacher. Compressed Bloom Filters. IEEE/ACM Transactions on Networking 10:5 (2002), 604—612.

    [3] www.cs.jhu.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf

    [4] http://166.111.248.20/seminar/2006_11_23/hash_2_yaxuan.ppt

    展开全文
  • 海量数据处理之Bloom Filter详解 前言 本博客内曾已经整理过十道海量数据处理面试题与十个方法大总结。接下来,本博客内会重点分析那些海量数据处理的方法,并重写十道海量数据处理的面试题。如果有任何问题,欢迎...

    海量数据处理之Bloom Filter详解

     

    前言

        本博客内曾已经整理过十道海量数据处理面试题与十个方法大总结。接下来,本博客内会重点分析那些海量数据处理的方法,并重写十道海量数据处理的面试题。如果有任何问题,欢迎不吝指正。谢谢。

    一、什么是Bloom Filter

        Bloom Filter是一种空间效率很高的随机数据结构,它的原理是,当一个元素被加入集合时,通过K个Hash函数将这个元素映射成一个位阵列(Bit array)中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检索元素一定不在;如果都是1,则被检索元素很可能在。这就是布隆过滤器的基本思想。

        但Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

        有人可能想知道它的中文叫法,倒是有被译作称布隆过滤器。该不该译,译的是否恰当,由诸君品之。下文之中,如果有诸多公式不慎理解,也无碍,只作稍稍了解即可。

    1.1、集合表示和元素查询

        下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时,Bloom Filter是一个包含m位的位数组,每一位都置为0

        为了表达S={x1, x2,…,xn}这样一个n个元素的集合,Bloom Filter使用k个相互独立的哈希函数(Hash Function),它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x,第i个哈希函数映射的位置hi(x)就会被置为11ik)。注意,如果一个位置多次被置为1,那么只有第一次会起作用,后面几次将没有任何效果。在下图中,k=3,且有两个哈希函数选中同一个位置(从左边数第五位,即第二个“1“处)。   

     

        在判断y是否属于这个集合时,我们对y应用k次哈希函数,如果所有hi(y)的位置都是11ik),那么我们就认为y是集合中的元素,否则就认为y不是集合中的元素。下图中y1就不是集合中的元素(因为y1有一处指向了“0”位)。y2或者属于这个集合,或者刚好是一个false positive

    1.2、错误率估计

        前面我们已经提到了,Bloom Filter在判断一个元素是否属于它表示的集合时会有一定的错误率(false positive rate),下面我们就来估计错误率的大小。在估计之前为了简化模型,我们假设kn<m且各个哈希函数是完全随机的。当集合S={x1, x2,…,xn}的所有元素都被k个哈希函数映射到m位的位数组中时,这个位数组中某一位还是0的概率是:

        其中1/m表示任意一个哈希函数选中这一位的概率(前提是哈希函数是完全随机的),(1-1/m)表示哈希一次没有选中这一位的概率。要把S完全映射到位数组中,需要做kn次哈希。某一位还是0意味着kn次哈希都没有选中它,因此这个概率就是(1-1/m)的kn次方。令p = e-kn/m是为了简化运算,这里用到了计算e时常用的近似:

     

    令ρ为位数组中0的比例,则ρ的数学期望E(ρ)= p’。在ρ已知的情况下,要求的错误率(false positive rate)为:

    (1-ρ)为位数组中1的比例,(1-ρ)k就表示k次哈希都刚好选中1的区域,即false positive rate。上式中第二步近似在前面已经提到了,现在来看第一步近似。p’只是ρ的数学期望,在实际中ρ的值有可能偏离它的数学期望值。M. Mitzenmacher已经证明[2] ,位数组中0的比例非常集中地分布在它的数学期望值的附近。因此,第一步的近似得以成立。分别将pp’代入上式中,得:

       

    相比p’f’,使用pf通常在分析中更为方便。

    1.3、最优的哈希函数个数

        既然Bloom Filter要靠多个哈希函数将集合映射到位数组中,那么应该选择几个哈希函数才能使元素查询时的错误率降到最低呢?这里有两个互斥的理由:如果哈希函数的个数多,那么在对一个不属于集合的元素进行查询时得到0的概率就大;但另一方面,如果哈希函数的个数少,那么位数组中的0就多。为了得到最优的哈希函数个数,我们需要根据上一小节中的错误率公式进行计算。

        先用pf进行计算。注意到f = exp(k ln(1 − e−kn/m)),我们令g = k ln(1 − e−kn/m),只要让g取到最小,f自然也取到最小。由于p = e-kn/m,我们可以将g写成

        根据对称性法则可以很容易看出当p = 1/2,也就是k = ln2· (m/n)时,g取得最小值。在这种情况下,最小错误率f等于(1/2)k (0.6185)m/n。另外,注意到p是位数组中某一位仍是0的概率,所以p = 1/2对应着位数组中0和1各一半。换句话说,要想保持错误率低,最好让位数组有一半还空着。

        需要强调的一点是,p = 1/2时错误率最小这个结果并不依赖于近似值pf。同样对于f’ = exp(k ln(1 − (1 − 1/m)kn))g’ = k ln(1 − (1 − 1/m)kn)p’ = (1 − 1/m)kn,我们可以将g’写成

    同样根据对称性法则可以得到当p’ = 1/2时,g’取得最小值。

    1.4、位数组的大小

        下面我们来看看,在不超过一定错误率的情况下,Bloom Filter至少需要多少位才能表示全集中任意n个元素的集合。假设全集中共有u个元素,允许的最大错误率为є,下面我们来求位数组的位数m

        假设X为全集中任取n个元素的集合,F(X)是表示X的位数组。那么对于集合X中任意一个元素x,在s = F(X)中查询x都能得到肯定的结果,即s能够接受x。显然,由于Bloom Filter引入了错误,s能够接受的不仅仅是X中的元素,它还能够є (u - n)false positive。因此,对于一个确定的位数组来说,它能够接受总共n + є (u - n)个元素。在n + є (u - n)个元素中,s真正表示的只有其中n个,所以一个确定的位数组可以表示

    个集合。m位的位数组共有2m个不同的组合,进而可以推出,m位的位数组可以表示

       

    个集合。全集中n个元素的集合总共有

       

    个,因此要让m位的位数组能够表示所有n个元素的集合,必须有

       

    即:

       

    上式中的近似前提是nєu相比很小,这也是实际情况中常常发生的。根据上式,我们得出结论:在错误率不大于є的情况下,m至少要等于n log2(1/є)才能表示任意n个元素的集合。

     

    上一小节中我们曾算出当k = ln2· (m/n)时错误率f最小,这时f = (1/2)k= (1/2)mln2 / n。现在令fє,可以推出

    这个结果比前面我们算得的下界n log2(1/є)大了log2e 1.44倍。这说明在哈希函数的个数取到最优时,要让错误率不超过єm至少需要取到最小值的1.44倍。

    1.5、概括

        在计算机科学中,我们常常会碰到时间换空间或者空间换时间的情况,即为了达到某一个方面的最优而牺牲另一个方面。Bloom Filter在时间空间这两个因素之外又引入了另一个因素:错误率。在使用Bloom Filter判断一个元素是否属于某个集合时,会有一定的错误率。也就是说,有可能把不属于这个集合的元素误认为属于这个集合(False Positive),但不会把属于这个集合的元素误认为不属于这个集合(False Negative)。在增加了错误率这个因素之后,Bloom Filter通过允许少量的错误来节省大量的存储空间。

        自从Burton Bloom70年代提出Bloom Filter之后,Bloom Filter就被广泛用于拼写检查和数据库系统中。近一二十年,伴随着网络的普及和发展,Bloom Filter在网络领域获得了新生,各种Bloom Filter变种和新的应用不断出现。可以预见,随着网络应用的不断深入,新的变种和应用将会继续出现,Bloom Filter必将获得更大的发展。

    二、适用范围

        可以用来实现数据字典,进行数据的判重,或者集合求交集 

    三、基本原理及要点

        对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这 个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。 

        还有一个比较重要的问题,如 何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应 该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。 

    举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。 

        注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。 
     

    四、扩展

        Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。 
     

    五、问题实例

        给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢? 

    根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。 


    参考文献及推荐阅读

    1. http://blog.csdn.net/jiaomeng/article/details/1495500
    2. http://blog.redfox66.com/post/2010/09/24/mass-data-topic-1-start.aspx
    3. 维基百科上关于布隆过滤器的介绍:http://zh.wikipedia.org/zh-cn/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8
    4. 海量数据处理利器之Bloom Filter:http://www.dbafree.net/?p=36
    展开全文
  • MATLAB新手学习记录——filter函数使用filter概念与基本语法以最简单的 y = filter(b,a,X) 为例**可实现差分方程** 上学期刚学过《信号与系统》,因此这个寒假打算在确定考研(有一丢丢可能保研)目标院校之余,学习...


    上学期刚学过《信号与系统》,因此这个寒假打算在确定考研(有一丢丢可能保研)目标院校之余,学习如何使用MATLAB对《信号与系统》中的一些内容进行分析和实现。
    特此使用博客帮助记录与温习

    filter概念与基本语法

    filter函数是一维的数字滤波器,主要的应用语法如下所示

    y = filter(b,a,X)

    [y,zf] = filter(b,a,X)

    [y,zf] = filter(b,a,X,zi)

    y = filter(b,a,X,zi,dim)

    […] = filter(b,a,X,[],dim)

    以最简单的 y = filter(b,a,X) 为例

    y = filter(b,a,X) 滤除向量X中的数据,其中b是分子系数向量,a是分母系数向量。如果a(1)不等于1的话,则就利用a(1)标准化滤波器系数,可以利用多项式除法使分母变为1;如果 a(1) 等于0,滤波器返回错误值。

    可实现差分方程

    Y = FILTER(B,A,X) ,输入X为滤波前序列,Y为滤波结果序列,B/A 提供滤波器系数,B为分子, A为分母
    整个滤波过程是通过下面差分方程实现的:
    a(1)*y(n) = b(1)*x(n) + b(2)*x(n-1) + … + b(nb+1)*x(n-nb)-a(2)*y(n-1) - a(3)*y(n-2) + … + a(nb+1)*y(n-nb)

    图片来源于百度
    图片源于百度

    例:
    filter([1,2],1,[1,2,3,4,5])
    实现 y[k]=x[k]+2*x[k-1]
    括号中向量b为x[k]、x[k-1]、…的系数,向量a为y[k]、y[k-1]、…的系数。

    x为需要滤波的向量,y为滤波后的向量(显然,x和y的长度是一样的,看后面例子就知道了)。

    举个例子来说明filter的原理,如下:

    a = [1 2];
    b = [2 3];
    x = [1 2 3 4 5 6];
    y = filter(b, a, x)
    y =
    2 3 6 5 12 3
    下面给出具体的计算过程如下:
    a(1)y(1) = b(1)x(1); %可以求出y(1)
    a(1)y(2) = b(1)x(2)+b(2)x(1) –a(2)y(1); %可以由y(1)求出y(2)
    a(1)y(3) = b(1)x(3)+b(2)x(2)-a(2)y(2); %可以由y(2)求出y(3)
    a(1)y(4) = b(1)x(4)+b(2)x(3)-a(2)y(3); %可以由y(3)求出y(4)
    a(1)y(5) = b(1)x(5)+b(2)x(4)-a(2)y(4); %可以由y(4)求出y(5)
    a(1)y(6) = b(1)x(6)+b(2)x(5)-a(2)y(5); %可以由y(5)求出y(6)

    计算结束,得到y(n)(n=1、2、…、6)

    目前就暂且记到这里

    展开全文
  • 1. Bloom-Filter算法简介  Bloom-Filter,即布隆过滤器,1970年由Bloom中提出。它可以用于检索一个元素是否在一个集合中。  Bloom Filter(BF)是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一...
  • 之前的Java集合中removeIf的使用一文写了使用removeIf来实现按条件对集合进行过滤。这篇文章使用同样是JDK1.8新加入的Stream中filter方法来实现同样的效果。
  • 过滤器(Filter) 过滤器实际上就是对web资源进行拦截,做一些处理后再交给servlet。 通常都是用来拦截request进行处理的,也可以对返回的response进行拦截处理 大概流程图如下 应用场景 自动登录 统一设置...
  • 而对于不支持CSS3的浏览器如何进行透明处理,保持浏览器效果的一致,这个估计谁都会写,但是涉及到filter的具体语法含义和各版本写法的不同区别,很多人都搞不准确,我曾经问过许多群里的大牛,说的都不是很准确,...
  • java中Filter与Servlet非常相似,也是一些web应用程序组件,可以绑定到一个web应用程序中。但是与其他web应用程序组件不同的是,过滤器是"链"在容器的处理过程中的。这就意味着它们会在servlet处理器之前访问一个...
  • MATLAB filter函数解析

    2017-06-26 21:27:24
    现在正在学习MATLAB信号处理方面的应用,程序中遇到filter函数,从网上查阅资料,我能找到的资料感觉写的也是模棱两可,不易使人明白,所以就花了一下午的时间好好研究了下,终于知道这个函数的使用方法了,下面以...
  • <br />OpenFileDialog对话框的Filter属性说明:  首先说明一个示例,分析一下Filter属性的构成:“Excel文件|*.xls”,前面的“Excel文件”成为标签,是一个可读的字符串,可以自定定义,“|*.xls”是...
  • vue filter的几种用法

    2017-04-18 11:48:29
    (1)全局方法 Vue.filter() 注册一个自定义过滤器,必须放在Vue实例化前面 (2) 过滤器函数始终以表达式的值作为第一个参数。带引号的参数视为字符串,而不带引号的参数按表达式计算 (3)可以设置两个过滤器参数,前提...
  • Kalman Filter 通俗讲解

    2018-06-03 16:44:05
    Kalman Filter,很多人刚听到这个名词时,总是会下意识认为这就是个滤波器。我这里想要重点声明的是,Kalman Filter不是滤波,它是一种信息融合的过程。 那么Kalman Filter到底是什么?它在那些方面有着应用,它的...
  • js filter()方法的使用

    2018-10-22 11:17:29
    和map()不同的是,filter()把传入的函数依次作用于每个元素,然后根据返回值是true还是false决定保留还是丢弃该元素。 例如,在一个Array中,删掉偶数,只保留奇数,可以这么写 var arr = [1, 2, 4, 5...
  • 一、引言 本来想记录一下关于用户登陆和登陆之后的权限管理、...关于Interceptor解决权限和菜单管理的问题,在放在下一篇写吧,就酱紫。...1、过滤器(Filter) ...首先说一下Filter的使用地方,我们在配置web.x...
  • 在使用Filter对一些自己指定的URL进行过滤拦截时,经常会出现如下错误:1、 明明在@WebFilter(urlPatterns={"/app/online"})中过滤的是/app/online 路径,但是运行之后发现,这个WebFilter过滤器对所有的...
  • 图像处理中常常会听到盒子滤波(Box Filter)这个概念。A boxfilter is also called a mean filter。也就是说,Box Filter对当前像素及其相邻的的像素点都一视同仁,统一进行平均处理,这样就可以滤去图像中的噪声。...
  • bilateral filter双边滤波器的通俗理解  图像去噪的方法很多,如中值滤波,高斯滤波,维纳滤波等等。但这些降噪方法容易模糊图片的边缘细节,对于高频细节的保护效果并不明显。相比较而言,bilateral filter双边...
  • 1、query和filter的本质区别? 以下几张图能更好的概括: query关注点:此文档与此查询子句的匹配程度如何? filter关注点:此文档和查询子句匹配吗? 2、Query检索细化关注点 1)是否包含? 确定文档是否...
1 2 3 4 5 ... 20
收藏数 1,021,991
精华内容 408,796
关键字:

filter