下载文档原格式
Bloom Filter算法1. 引言Bloom Filter是一种概率数据结构，用于判断一个元素是否属于一个集合。
它通过使用位数组和多个哈希函数来实现高效的查询操作。
Bloom Filter具有快速查询、低内存占用和可调控的误判率等特点，在实际应用中被广泛使用。
本文将介绍Bloom Filter算法的原理、应用场景以及实现细节，并对其优缺点进行分析。
2. 原理Bloom Filter的核心思想是利用位数组和多个哈希函数来表示一个集合，并通过检查位数组中的特定位置来判断元素是否存在于集合中。
具体步骤如下：1.初始化：创建一个长度为m的位数组，所有位都初始化为0。
2.插入元素：将要插入的元素经过k个独立的哈希函数计算得到k个哈希值，然后将位数组中对应位置设置为1。
3.查询元素：将要查询的元素经过k个独立的哈希函数计算得到k个哈希值，然后检查位数组中对应位置是否都为1。
如果有任何一个位置不为1，则可以确定该元素不存在于集合中；否则，该元素可能存在于集合中（存在一定的误判率）。
Bloom Filter通过增加哈希函数的数量和位数组的长度，可以有效地降低误判率。
但是，随着哈希函数数量和位数组长度的增加，Bloom Filter的存储空间和查询时间也会增加。
3. 应用场景Bloom Filter在以下场景中得到广泛应用：3.1 垃圾邮件过滤Bloom Filter可以用于过滤垃圾邮件。
将已知的垃圾邮件地址构建成一个Bloom Filter，然后对每封新收到的邮件进行查询。
如果查询结果为存在，则可以判断该邮件是垃圾邮件；否则，该邮件可能是正常邮件（存在一定的误判率）。
3.2 缓存优化Bloom Filter可以用于缓存优化。
将已经访问过的数据项构建成一个Bloom Filter，然后对每个新访问请求进行查询。
如果查询结果为不存在，则可以避免不必要的缓存读取操作；否则，继续进行后续缓存读取操作。
3.3 URL去重Bloom Filter可以用于URL去重。
Bloom Filter研究进展严华云;关佶红【摘要】近年来,由于Bloom filter具有可压缩性和高效查询性,其在分布式数据库、网络缓存、对等网和信息检索等领域引起了越来越多的研究者关注.随着Bloom filter不同应用需求的出现,多种Bloom filter变体被提了出来,诸如:支持删除元素的CBF;可以统计频次型的SBF、DCF、dlCBF;大小可以动态伸长的DBF、SBF;压缩型BF等.本文对Bloom filter及其各种变体进行了介绍,并对其特点进行了分析比较,总结了它们各自的优势和不足,并进一步指出了Bloom filter未来的一些研究方向.【期刊名称】《电信科学》【年(卷),期】2010(026)002【总页数】6页(P31-36)【关键词】计算机网络;分布式计算;Bloom filter【作者】严华云;关佶红【作者单位】湖州师范学院信息与工程学院,湖州,313000;同济大学电子与信息工程学院,上海,201804;同济大学电子与信息工程学院,上海,201804【正文语种】中文1 引言在计算机应用领域，信息的表示和查询是核心问题，这两个问题常常是相关的。
其中，表示意味着根据一定的规则组织信息，查询则意味着判断一个给定属性值的元素是否属于某一集合。
Bloom filter[1]是一种节省空间、高效率的数据表示和查询结构。
它利用位数组很简洁地表示一个集合，并能以很高的概率判断一个元素是否属于这个集合。
因此，这种数据结构适合应用在能容忍低错误率的场合。
Burton H.Bloom于1970年提出Bloom filter用以解决某（些）元素是否为集合中元素的判断问题。
它突破了传统哈希函数的映射和存储元素的方式，通过一定的错误率换取了空间的节省和查询的高效。
在20世纪70年代，其应用价值并没有体现出来。
80年代，随着PC应用的推广，Bloom filter的应用开始推广，如高效地解决拼写检查问题[2]，解决多处理器计算机中数据库的连接问题[3]。
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.21, No.5, May 2010, pp.1098−1114 doi: 10.3724/SP.J.1001.2010.03495 Tel/Fax: +86-10-62562563© by Institute of Software, the Chinese Academy of Sciences. All rights reserved.4种计数型Bloom Filter的性能分析与比较∗张进+, 邬江兴, 刘勤让(国家数字交换系统工程技术研究中心,河南郑州 450002)Performance Evaluation and Comparison of Four Counting Bloom Filter SchemesZHANG Jin+, WU Jiang-Xing, LIU Qin-Rang(National Digital Switching System Engineering & Technology Research Center, Zhengzhou 450002, China)+ Corresponding author: E-mail: boost_zj@Zhang J, Wu JX, Liu QR. Performance evaluation and comparison of four counting bloom filter schemes.Journal of Software, 2010,21(5):1098−1114. /1000-9825/3495.htmAbstract: The Counting Bloom Filter (CBF) is a space-efficient data structure that extends a Bloom filter so as toallow approximate multiplicity queries on a dynamic multi-set. An in-depth study of three existing CBF schemes ispresented, that is, the Naïve Counting Bloom Filter (NCBF), the Space-Code Bloom Filter (SCBF) and the d-leftCounting Bloom Filter (dlCBF). Then, a CBF scheme called Binary Shrinking d-left Counting Bloom Filter(BSdlCBF) is proposed. A performance metrics named load adaptability for CBF schemes is also defined. Theperformance of the four CBF schemes is evaluated by using metrics of counting error, space complexity and loadadaptability under both uniform and Zipfian multiplicity distributions. The experimental results show that theproposed BSdlCBF outperforms the other three in terms of accuracy, space-efficiency and load adaptability. Thecost of such an advantage of BSdlCBF is a reasonable rise in computational and space complexity.Key words: counting bloom filter; performance evaluation; performance comparison; load adaptability摘要: 对3种已有的计数型Bloom filter——Naïve Counting Bloom Filter(NCBF),Space-Code Bloom Filter(SCBF)和d-left Counting Bloom Filter(dlCBF)——的查询错误概率进行了分析,得出了NCBF的计数器防溢出条件以及SCBF和dlCBF的参数最优设置准则.提出了一种衡量计数型Bloom filter性能的指标:负载适应性.针对dlCBF负载适应性差的问题,对dlCBF进行了改进,提出了一种计数型Bloom filter:Binary Shrinking d-left Counting BloomFilter(BSdlCBF).通过仿真实验,以计数误差、空间复杂度以及负载适应性为性能指标,对上述4种CBF进行了比较.实验结果表明,BSdlCBF具有最低的空间复杂度、最小的计数误差以及最佳的负载适应性. BSdlCBF赢得上述性能优势的代价在于其计算复杂度比其他3种计数型Bloom filter略高.关键词: 计数型Bloom filter;性能评估;性能比较;负载适应性中图法分类号: TP393文献标识码: ABloom filter是一种支持集合的近似表示以及近似从属查询(approximate membership query)的数据结构[1].∗Supported by the National Basic Research Program of China under Grant Nos.2007CB307100, 2007CB307102 (国家重点基础研究发展计划(973))Received 2008-06-18; Accepted 2008-10-27张进等:4种计数型Bloom Filter的性能分析与比较1099设集合S是集合U的一个子集,对于U中的任一元素e,Bloom filter可以一定的虚报概率判断e是否属于S. Bloom Filter突出优点是空间效率高:无论元素e自身的大小如何,每元素只需10比特,即可实现虚报概率约为1%的近似从属查询.计数型Bloom filter(counting bloom filter,简称CBF)[2−6]将Bloom filter的从属查询扩展为更一般的频率查询(multiplicity query,或者称为计数查询),允许S为动态多集,这极大地拓展了Bloom filter的应用领域.CBF在网络、数据库等众多领域得到了广泛的应用[3,4,6−9].文献[2]提出了Naïve Counting Bloom Filter(NCBF),文献[7]采用NCBF进行骨干网链路的长流流量测量;文献[4]提出了Space-Code Bloom Filter(SCBF)用于高速骨干网的逐流流量测量;文献[6]提出了d-left Counting Bloom Filter(dlCBF),文献[9]采用dlCBF构建大规模并发状态机.上述3种CBF结构简单,易于硬件实现,特别适合于高速数据的实时分析处理.除了上述3种CBF之外,还有文献[3,5]提出的两种CBF结构.但是,文献[3,5]中提出的CBF比上述3种CBF复杂,难以硬件实现,因此其应用范围也比上述3种CBF狭窄[6],故本文不将这两种CBF作为讨论的对象.由于各种不同的CBF在计算复杂度、空间复杂度以及计数误差等不同的性能指标之间有着不同的权衡,因此在实际使用中应当根据应用需求和资源约束,选择最合适的一种CBF.为了给CBF的设计选择提供准确而详尽的参考依据,对各种CBF进行系统、定量的分析比较显得尤为必要.然而,已有的研究工作中,比较的对象以及比较所采用的性能指标都不完备(已有的相关工作详见第6节).针对此问题,本文采用多种性能评价尺度,从不同角度对NCBF,SCBF,dlCBF以及本文提出的BSdlCBF进行了横向比较.具体而言,本文的主要贡献如下:(1) 对已有的3种CBF,即NCBF,SCBF以及dlCBF进行深入分析,给出了NCBF的防溢出条件以及SCBF 和dlCBF的参数最优设置准则,为上述CBF在实际使用时的参数最优设计提供了理论依据.(2) 提出了一种新的衡量CBF性能的指标:负载适应性.本文分析比较的4种计数型Bloom filter由于结构简单,因而常用于高速数据处理场合,如高速骨干网流量分析[4,7,9].高速数据处理应用中,算法一般采用硬件实现.在硬件实现中,计算与存储资源往往根据系统的最大负载预先设定.然而在实际应用中,系统负载通常是不稳定的,并且在大部分时间中,负载都远小于最大值.例如现有研究表明,在骨干网络链路中,最大并发数据流的数量会达到1M[3,6].然而,对实际采集的高速骨干网流量数据的分析表明,绝大部分情况下,链路上的并发流的数量都远小于最大值[10].本文将计数型Bloom filter在低负载时,充分利用已分配资源,降低计数误差的能力称为计数型Bloom filter的负载适应性.对于硬件实现而言,算法的负载适应性是一项重要的性能指标.(3) 提出了一种新的计数型Bloom filter:BSdlCBF.我们发现,已有的3种CBF(即NCBF,SCBF和dlCBF)中,虽然从计数误差、空间复杂度的角度而言dlCBF的性能最佳,但是,dlCBF的负载适应性却明显比NCBF要差.针对dlCBF负载适应性差的问题,本文对dlCBF进行了改进,提出了一种计数型Bloom filter:BSdlCBF. BSdlCBF 采用折半收缩机制,根据负载轻重程度动态地调整元素指纹的长度.在相同的空间复杂度下,满负载时,BSdlCBF 和dlCBF的性能一致;轻负载时,分析和实验的结果表明,BSdlCBF的计数误差明显小于dlCBF.分析结果表明, BSdlCBF的计算复杂度和空间复杂度略高于dlCBF.(4) 通过仿真实验的手段,采用计数误差、空间复杂度以及负载适应性为性能指标(这些指标的定义将在第1节给出),分别从3个不同的角度,对上述4种CBF的性能进行了系统的比较.首先,本文比较了相同空间复杂度下,NCBF,SCBF和dlCBF的计数误差;其次,本文比较了在计数误差相近的前提下,NCBF,SCBF和dlCBF的空间复杂度.上述两项比较工作均在满负载的条件下进行,由于在满负载时,BSdlCBF和dlCBF的性能一致,故上述两项性能比较无须包含BSdlCBF;最后,本文比较了4种CBF的负载适应性.仿真实验结果表明:1) 在满负载且空间复杂度相同时,SCBF的计数误差最大,NCBF次之,dlCBF的计数误差比NCBF和SCBF小若干个数量级;2) 在满负载且计数误差相近时,SCBF的空间复杂度最高,NCBF次之,dlCBF的空间复杂度最低;3) BSdlCBF具有最好的负载适应性,NCBF次之,dlCBF的负载适应性比NCBF差,SCBF的负载适应性最差.综上,在本文讨论的4种CBF中,BSdlCBF性能最佳.BSdlCBF赢得性能优势的代价是其计算复杂度比其他3种CBF略高.本文第1节定义衡量CBF性能的指标.第2节对已有的3种CBF的计数误差进行深入分析,给出NCBF的防溢出条件以及SCBF和dlCBF的参数最优设置准则.第3节提出一种计数型Bloom filter:BSdlCBF,并分析其1100 Journal of Software 软件学报 V ol.21, No.5, May 2010错误概率、计算复杂度和空间复杂度.第4节阐述并比较4种CBF 性能时所采用的方法.第5节给出实验结果与分析.第6节介绍相关的工作.第7节为全文总结.1 性能指标对于计数查询而言,不仅仅需要关注错误概率,还需关注在错误发生时相对误差的大小.错误概率和相对误差的定义如下:设U 为全体元素构成的集合,S (|S |=N )为多集(multi-set),且S ⊆U .对于任意e ∈U ,设f e (f e ∈[0,F ])为e 在S 中出现的频率(或次数),f e =0意味着e ∉S .ˆef为f e 的查询估计值. 定义1(错误概率). ∀e ∈U ,i ∈[0,F ],定义频率为i 的元素的错误概率为元素频率的估计值不等于真实值的概率.错误概率记作ˆ()ieEP P fi =≠.称ˆeef f >为阳性错误,ˆeef f <为阴性错误. 需要指出的是,本文所讨论的4种CBF 中,只有SCBF 的错误概率与元素频率是相关的,其他3种CBF 的错误概率与元素频率无关.为了不失一般性,本文将错误概率定义为与元素频率相关的形式.当错误概率与元素频率无关时,EP i 也可记作EP .定义2(相对误差). ∀e ∈S ,i ∈[1,F ],定义频率为i 的元素的相对误差为S 中所有频率为i ,并且发生查询错误(即ˆe e f f ≠)的元素的相对误差的期望.相对误差记作ˆ||e i f i RE E i ⎛⎞−=⎜⎟⎜⎟⎝⎠,ˆee f f i ≠=. CBF 的计数精度用计数误差来衡量.计数误差的定义如下:定义3(计数误差). ∀e ∈S ,i ∈[1,F ],定义CE i =EP i ⋅RE i 为频率为i 的元素的计数误差.本文采用不同负载率下的归一化错误概率和归一化计数误差来衡量4种CBF 的负载适应性.归一化错误概率和归一化计数误差的定义如下:定义4(归一化错误概率). 定义负载率为ρ(0<ρ≤1)时的错误概率和满负载时的错误概率之比为归一化错误概率.归一化错误概率记作NEP i (ρ)=EP i (ρ)/EP i (1).定义5(归一化计数误差). ∀i ∈[1,F ],定义负载率为ρ(0<ρ≤1)时的计数误差和满负载时的计数误差之比为归一化计数误差.归一化计数误差记作NCE i (ρ)=CE i (ρ)/CE i (1).图1为应用Bloom filter 进行数据处理的一般系统结构模型,新到达的数据可能触发更新操作或查询操作.更新操作指的是对于新到达的元素e ,更新其在计数型Bloom filter 中的频率计数值;查询操作指的是读取元素e在计数型Bloom filter 中的频率计数值,并据此给出其频率的估计值ˆef.需要指出的是,某些计数型Bloom filter (如SCBF)的更新操作不需要对存储单元进行读操作,而仅仅进行写操作.但为了不失一般性,如图1所示的更新操作包括读存储单元操作和写存储单元操作.在处理海量高速数据的应用场合(如高速骨干网流量分析),处理单元通常由ASIC,FPGA 或者专用CPU 等高性能处理器件实现;存储单元通常由高速SRAM 实现.此时,系统的性能瓶颈在于存储单元的带宽和容量,这两项性能指标分别用计算复杂度和空间复杂度来衡量[4].计算复杂度定义为每次更新或者查询操作中处理单元访问存储单元的次数;空间复杂度定义为存储单元的空间大小[4].Fig.1 A general system model of data processing using Bloom filters图1 应用Bloom filter 进行数据处理的一般系统结构模型2 3种已有CBF 的计数误差分析在具体分析每种CBF 的计数误差之前,首先说明一下本文的符号使用约定.为了便于区分,对于每种CBF,张进 等:4种计数型Bloom Filter 的性能分析与比较1101本文采用其缩写的首字母作为其特定参数的下标,例如NCBF 的参数记作k n ,m n ,w n ,SCBF 的参数记作g s ,b s 等等(上述参数的具体含义在下文分析中会详细说明). 2.1 NCBF 的计数误差分析NCBF 由k n 个独立的哈希函数h 1(⋅),h 2(⋅),…,()n k h ⋅和一个计数器向量C 构成.设C 中共包含了m n 个计数器,每个计数器的宽度为w n 比特.当更新元素e 的计数时,将计数器C [h 1(e )],C [h 2(e )],…,[()]n k C h e 分别增加1.当查询e 的频率f e 时,取C [h 1(e )],C [h 2(e )],…,[()]n k C h e 中最小的作为f e 的估计值,即ˆarg min([()]),[1,].e i nif C h e i k =∈ NCBF 的错误概率即为Bloom filter 的虚报概率[3],即11112nn n k k N k n n EP m ⎛⎞⎛⎞⎛⎞⎜⎟=−−≈⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠⎝⎠(1)其中,|N |=S ,k n =ln(2)⋅m n /N .文献[3,7]提出,采用最小增加(minimum increase,简称MI)策略可以有效地降低NCBF 的计数误差.当更新元 素e 的计数时,最小增加策略仅仅将计数器C [h 1(e )],C [h 2(e )],…,[()]n k C h e 中最小的计数器增加1,其他计数器的值设置为arg min([()])1i iC h e +与其原先的值中较大的那个.在采用MI 策略时,NCBF 的错误概率将难以分析.第5节通过仿真实验得出了采用MI 策略时NCBF 的计数误差.由于且仅由于NCBF 计数器的计数范围限制,会导致NCBF 产生阴性错误(ˆe ef f <).定理1给出了与阳性错 误相比,NCBF 的阴性错误可以忽略不计的条件.定理1的证明见附录A.定理1. 当CBF 计数器的计数上限为2F 时,即当w n =⎡log 2(2F +1)⎤ (2)时,NCBF 发生阴性错误的概率与发生阳性错误的概率之比小于0.07.n kNCBF 的主要参数见表1.在实验中,我们根据公式(2)设置w n 的取值,m n 在一定的范围内变化.实验细节见第4节和第5节.结论1给出了NCBF 的计算复杂度和空间复杂度.Table 1 Dominant parameters of NCBF表1 NCBF 的关键参数Parameter Descriptionm n Length of counter vector w n Counter width, set according to Formula (2)结论1. NCBF 更新操作的计算复杂度为2k n .NCBF 查询操作的计算复杂度为k n .NCBF 的空间复杂度为m n ⋅w n .2.2 SCBF 的计数误差分析Kumar 等人提出了Space-Code Bloom Filter(SCBF)用于高速骨干网的流量测量[4].如果将NCBF 采用的k n个哈希函数看作一个哈希函数组H ,则SCBF 由g s 个哈希函数组11122112212{(),(),...,()},{(),(),...,k H h h h H h h =⋅⋅⋅=⋅⋅212()},...,{(),(),...,()}s s s s g g g k g k h H h h h ⋅=⋅⋅⋅和一个比特向量B 构成,B 的长度为b s 比特.当更新元素e 的计数时,从g s 个哈希函数组中随机地选择一组(不妨设为H i )对e 作哈希运算,然后将比特向量B 的对应位1(()),i B h e2(()),...,(())i i k B h e B h e 置为1.对于元素e 而言,每次更新时都可能选择不同的哈希函数组.当估计e 的出现频率f e 时,则遍历查询所有的哈希函数组.对于哈希函数组i ,若12(()),(()),...,(())i i i k B h e B h e B h e 均为1,则称该哈希函数组与元素e 匹配.设遍历查询g s 个哈希函数组后,发现与元素e 匹配的哈希函数组的数量为θ.然后,利用某种估计算法根据θ估算出f e ,即ˆ()efestimator θ=.文献[4]提出了最大似然估计和最小均方误差估计这两种估计器.SCBF 每组哈希函数的数量为1102 Journal of Software 软件学报 V ol.21, No.5, May 2010ln(2)()ss b k N E f =⋅⋅ (3)其中,E (f )为元素频率的期望值.SCBF 由于采用了估计过程,其查询错误概率不再与元素的出现频率无关,因而难以分析.同时,估计器还会引起阴性错误.对参数g s 的最优设置问题需要进行深入的讨论.文献[4]指出,若g s 选取得过小,则估计器会存在较大的估计误差;若g s 选取得过大,则会由于Bloom filter 阳性错误的影响,使得观测值θ中噪声成分增加,从而引起较大的观测误差.但是,文献[4]并未给出g s 的最优设置准则.本文通过实验给出了g s 的最优设置准则,方法如下:令k s 分别取1到10,在某一k s 取值下,设置g s 分别为1F ~10F ,然后分别计算各个g s 取值下SCBF 的平均计数误差.在某一k s 取值下,导致平均计数误差最小的g s 取值为当前k s 取值下g s 的最佳值.表2给出了不同的k s 值下g s 的最佳值的计算结果.Table 2 Optimal g s under various k s 表2 不同的k s 值下g s 的最优取值k s1 2 3 4 5 6 7 8 9 10MLE 1F 1F 1F 1F 1F 2F 2F 3F 4F 8F EstimatorMVE 1F 1F 1F 1F 1F 2F 2F 3F 5F 7F表3列出了SCBF 的重要参数.结论2给出了SCBF 的计算复杂度和空间复杂度.Table 3 Dominant parameters of SCBF表3 SCBF 的关键参数Parameter Descriptions g s Number of hash groups结论2. SCBF 更新操作的计算复杂度为k s .SCBF 查询操作的计算复杂度为k s ⋅g s .SCBF 的空间复杂度为b s . 2.3 dlCBF 的计数误差分析Bonomi 等人提出了一种采用d-left 哈希函数结合元素指纹来构建计数型Bloom filter 的方法(d-left counting bloom filter,简称dlCBF)[6],如图2所示.d-left 哈希函数[11]将存储区等分为d 个块,每块又分为若干个相同容量的桶(d 个块的空间大小可以不相等.本文为了论述方便,假设d 个块的空间相同).不妨将各个块看作桶向量(bucket vector),从左向右依次记作BV 1,BV 2,…,BV d .例如,图2中的d-left 哈希函数的存储区划分为4个块,每块5个桶,每桶深度为4.当插入元素e 时,由d 个独立的哈希函数计算元素e 在各个块中的桶地址,分别记作h 1(e ),h 2(e ),…,h d (e ).然后将e 插入到BV 1(h 1(e )),BV 2(h 2(e )),…,BV d (h d (e ))中负载最轻的那个桶中.如果存在多个负载最轻的桶,则选择最左边那个.例如,图2是将元素e 插入到桶BV 1(4)中.遵循上述选择策略,可使得各个桶的负载较为平均,从而各个桶在平均负载的基础上再增加一个较小的额外桶空间,即可保证桶的溢出概率极低,从而有效地提高空间利用率[11].当额外桶空间一定时,d-left 哈希函数的并行选择机会越多(即d 值越大),桶溢出概率越低(对桶溢出概率的分析参见附录B).设元素指纹的长度为f d l 比特,计数器位宽为2(log (1))m md d l l F =+⎡⎤⎢⎥比特,由于d-left 哈希函数是一种近乎完美的哈希函数,因此,BV 的空间略大于||()f m d d S l l ⋅+比特.设每桶的平均深度为m d b ,额外深度为ed b .由文献[12]可知,取d =4及1e db =即可保证极低的桶溢出概率.在本文中,为了便于分析,d 和ed b 的取值均遵循此设置∗∗.由文献 [6]可知,dlCBF 的错误概率为∗∗下文的分析均基于这一参数设置.虽然在此设置下得出的结论不具有通用性,但是我们的分析方法仍然具有普适性和一般性.张进 等:4种计数型Bloom Filter 的性能分析与比较 11031112m d f db dd l EP ⋅⎛⎞=−−⎜⎟⎜⎟⎝⎠(4)当f d l 较大,如8f d l ≥时,上式近似化简为[6]422ffd d m m d dd l l b db EP ⋅≈=(5)dlCBF 的每个元素所需空间l d 为()21()log (1)m e m f m f d d d d d d d m md db b b l l l l F b b ++=⋅+=⋅++⎡⎤⎢⎥ (6)Fig.2 Structure illustration of dlCBF图2 dlCBF 的结构示意图通过分析dlCBF 的每个元素所需空间l d 和dlCBF 错误概率EP d 的关系我们发现,存在着最优的f d l 和md b 的取值,使得在l d 一定的前提下,错误概率EP d 最小.定理2给出了f d l 和mdb 的最优取值. 定理2. 当每元素空间l d 一定时,f d l 和md b 如下取值可使得dlCBF 的错误概率EP d 最小:f d l ⎤=⎥⎥ (7) 且m dd d b l l ⎡⎤⎛=+⎢⎥⎜⎜⎜⎜⎝⎝⎢⎥(8) 定理2的证明见附录C.表4列出了dlCBF 的重要参数.f d l 和md b 的取值根据公式(7)和公式(8)设置.结论3给出了dlCBF 的计算复杂度和空间复杂度.Table 4 Dominant parameters of dlCBF表4 dlCBF 的关键参数Parameter Descriptione db Extra bucket depth, set e d b =1 l dPer-Element space结论3. dlCBF 更新操作的计算复杂度为()1m e d d d b b ⋅++.dlCBF 查询操作的计算复杂度为()m ed d d b b ⋅+.dlCBF 的空间复杂度为l d ⋅N ,其中,N 为集合S 中元素的个数,l d 由公式(6)给出.BV 251104 Journal of Software 软件学报 V ol.21, No.5, May 20103 改进的dlCBF :BSdlCBF3.1 BSdlCBF 的结构描述BSdlCBF 根据桶负载大小,采用折半收缩的机制,动态地调整元素指纹的长度.图3给出了当dlCBF 的桶空间为8,桶负载分别为1,2,4,8时,BSdlCBF 和dlCBF 桶空间利用情况对比(阴影方格表示元素指纹,斜线方格标识频率计数器).由图3可以看出,当轻负载时,BSdlCBF 能够充分地利用桶空间,扩充元素指纹.因此在轻负载条件下,采用折半收缩机制可以有效的降低错误概率.Fig.3 Comparison of bucket space occupation of BSdlCBF and dlCBF under various load rate图3 不同负载率下,BSdlCBF 和dlCBF 的桶空间利用情况对比令f d l l =,称l 为单位指纹长度;令m ed d b b b =+.不妨设b 为2的自然数次幂(即b =2x ,x ∈N).对于每个元素e ,BSdlCBF 生成b 个l 比特的元素指纹F 1(e ),F 2(e ),…,F b (e ).设当向桶中插入元素e 时,桶中已有i −1个元素,则将F 1(e ),F 2(e ),…,F L (i )(e )写入桶中从A (i )开始的L (i )个单元即可,L (i )和A (i )分别由公式(9)和公式(10)确定.2log ()2i bL i ⎡⎤⎢⎥= (9)2log 1()1(2(2)1)()i A i i L i −⎡⎤⎢⎥=+⋅−−⋅ (10)L (i )的单位为单位指纹长度,A (i )为指纹单元地址.由公式(2)可知,当i >b /2时L (i )=1,此时,BSdlCBF 退化为元素指纹长度为1单位指纹长度的dlCBF.当b 不等于2的自然数次幂时,我们作如下处理:设2j <b <2j +1,当向桶中插入第i 个元素时,其元素地址A (i )和指纹长度L (i )分别为2log 2,2()1,2j i j ji L i i b −⎡⎤⎢⎥⎧≤⎪=⎨<≤⎪⎩ (11)2log 1()1(2(2)1)(),2(),2i j jA i i L i i A i i i b −⎡⎤⎢⎥⎧=+×−−⋅≤⎪=⎨<≤⎪⎩(12) BSdlCBF 的缺陷在于,由于使用了折半收缩机制,使其无法支持删除操作.另外,BSdlCBF 的计算复杂度和空间复杂度比dlCBF 略高.关于BSdlCBF 复杂度的分析详见下文. 3.2 BSdlCBF 的错误概率分析设共向BSdlCBF 中插入了x 个元素,则称1||di i xr BV ==∑为平均桶负载.定理3给出了在任意平均桶负载条件下,BSdlCBF 的错误概率.定理3. 设单位指纹长度为l ,桶深为b ,则当平均桶负载为r 且没有发生桶溢出时,BSdlCBF 的错误概率 EP Bd 为13241 5 3 6274811212341234567 8Bucket load =1Bucket load =4Bucket load =8Bucket load =2张进 等:4种计数型Bloom Filter 的性能分析与比较 1105()111(,0)(,)12di b Bd L i l i EP P r P r i ⋅=⎛⎞⎛⎞=−+−⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠∑ (13)其中,P (r ,i )为d-left 哈希函数的平均桶负载为r 时,对于任意一个桶,其中有i 个元素的概率(P (r ,i )的计算方法见附录B),L (i )由公式(11)确定.证明:BSdlCBF 的错误概率为对于任意一个元素指纹fp ,在任意d 个桶中,至少存在1个与之相同的指纹的概率.设EP ′为对于任意一个桶,其中的元素指纹都与fp 不一致的概率,则有:EP Bd =1−(EP ′)d (14)设i EP ′为当桶中有i (1≤i ≤b )个元素,并且这i 个元素指纹都与fp 不一致的概率,则由全概率公式,有:12(,0)(,1)(,2)...(,)r EP P r P r EP P r EP P r b EP ′′′′=+⋅+⋅++⋅ (15)考虑到112ii EP ⋅⎛⎞′=−⎜⎟⎝⎠(16)于是,将公式(16)带入公式(15),有:2(1)(2)()111(,0)(,1)1(,2)1...(,)1222bL lL l L b l EP P r P r P r P r b ⋅⋅⋅⎛⎞⎛⎞⎛⎞′=+−+−++−⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠⎝⎠(17) 将公式(17)带入公式(14),定理3得证.□定理3成立的条件是桶溢出概率为0.在实际应用中,为了保证桶溢出概率较低,一般设置桶深大于期望的平均桶负载.例如,当d =4,b −r =1时,桶溢出概率为10−10数量级;当d =4,b −r =2时,桶溢出概率为10−140数量级,可以忽略不计.可见,在实际使用中,定理3已经能足够精确地描述BSdlCBF 的错误概率.表5为3,1,m ed d b b ==d =4,l 分别取4和8时,BSdlCBF 的错误概率的理论值和实验值的比较.实验中,元素数量N =106,平均桶负载以0.5为步长,从3减小到0.5.由表5可以看出,定理3给出的BSdlCBF 错误概率的理论值和实验结果较为接近.Table 5 Comparison of theoretical and experimental error probability of BSdlCBF表5 BSdlCBF 错误概率的理论值与实验值比较r =3 r =2.5 r =2 r =1.5 R =1 r =0.5 Experimental value 0.485 4 0.321 5 0.107 6 0.015 9 0.003 9 6.0000e −5 l =4 Theoretical value 0.505 7 0.329 1 0.108 6 0.017 1 0.003 9 6.1264e −5 Experimental value 0.039 7 0.022 8 0.006 2 1.4200e −4 1.2000e −5 2.2700e −7 l =8Theoretical value0.042 10.024 10.006 01.3941e −4 1.1165e −52.6870e −73.3 BSdlCBF 的复杂度分析与dlCBF 相比,BSdlCBF 在计算复杂度和空间复杂度上均有所提高.定理4和定理5分别给出了BSdlCBF 和dlCBF 的空间复杂度与时间复杂度之比.定理4. BSdlCBF 和dlCBF 的空间复杂度之比为2log (1)1()f md d b b l l +⎡⎤⎢⎥++,其中,f d l 和mdl 分别为dlCBF 的元素指纹长 度和元素频率计数器位宽,b 为dlCBF 的桶深.证明:由于BSdlCBF 的每个桶需要设置一个负载计数器,以记录当前桶中的元素数量,因此,BSdlCBF 比 dlCBF 多需要21log (1)||di i b BV =+⎡⎤⎢⎥∑比特的存储空间.考虑到dlCBF 所需的存储空间为1()||dfm ddi i b l l BV =+∑比特,于 是,BSdlCBF 和dlCBF 的空间复杂度之比为211log (1)||1()||di i dfm ddi i b BV b l l BV ==+⎡⎤⎢⎥++∑∑=2log (1)1()f md d b b l l +⎡⎤⎢⎥++.1106 Journal of Software 软件学报 V ol.21, No.5, May 2010定理4得证. □定理5. BSdlCBF 和dlCBF 的查询操作的计算复杂度之比为1,BSdlCBF 和dlCBF 的更新操作的计算复杂度之比小于1+1/d .证明:设平均桶负载为r ,则BSdlCBF 每次查询操作均需要访问b ⋅d 个桶单元,而每次更新操作需要访问b ⋅d +log 2(L (⎡r ⎤))个桶单元.考虑到dlCBF 查询操作的计算复杂度为b ⋅d ,更新操作的计算复杂度为b ⋅d +1,于是, BSdlCBF 和dlCBF 的查询操作的计算复杂度之比为1,BSdlCBF 和dlCBF 的更新操作的计算复杂度之比为2log (())111111.111b d L r b d b b b b d b d b d b d d d×+⎡⎤×+−−⎢⎥≤=+<+=+×+×+×+×−定理5得证.□由定理5和定理6可以看出,与dlCBF 相比,BSdlCBF 的计算复杂度和空间复杂度略有提高.此外,有两个原因使得BSdlCBF 的处理单元的处理代价也略有提高:首先,BSdlCBF 的哈希运算所产生的元素指纹长度为dlCBF 的b 倍,其中b 为dlCBF 的桶深;其次,在进行元素指纹匹配时,dlCBF 为定长指纹匹配,而BSdlCBF 为变长指纹匹配.然而,由于哈希运算可以并行进行,并且实际应用场合中往往有实现代价较低的、几乎理想的哈希函数可供选择[13],因而提高的哈希运算代价并非不可接受.假设对于某一元素e ,在dlCBF 中的元素指纹为f ,在BSdlCBF 中的元素指纹为F [1:b ](F [i ](1≤i ≤b )的长度和f 的长度一致).对于e 所可能插入的d 个桶中的任意一个,设其中的元素指纹为B [1:b ].在dlCBF 中查找元素e 时,只需将f 分别与B [i ](1≤i ≤b )进行比较即可.在BSdlCBF 中查找元素e 时,设当前桶负载为r (1≤r ≤b ),则只需将F [map (r ,i )]与B [i ]进行比较即可,其中,map (r ,i )为总大小为b ⋅b 的映射表,例如map (1,i )=i ,map (b ,i )=1,等等.map (r ,i )可预先计算好,存放在片内的高速寄存器中.可见,变长指纹匹配的代价同样也可以接受.综上所述,与dlCBF 相比,BSdlCBF 的计算复杂度和空间复杂度并没有明显的提高.4 比较方法本文从3个不同的角度分别对上述4种CBF 的性能进行了比较:首先,本文比较了在相同的空间复杂度下4种CBF 的计数误差;其次,本文比较了在相近的计数误差的条件下4种CBF 的空间复杂度;最后,本文对4种CBF 的负载适应性进行了比较.前两项比较工作在满负载时进行.由于在满负载时,BSdlCBF 的性能与dlCBF 一致,因此前两项比较工作仅需要包括NCBF,SCBF 和dlCBF 这3种CBF 即可.为了比较NCBF,SCBF 和dlCBF 的计数误差,首先需要设置3种CBF 的空间复杂度相等.假设η=m n /N ,则对于NCBF 而言,每元素所需空间为η⋅w n 比特.于是,我们令l d =η⋅w n 且b s =m n ⋅w n ,则可以保证dlCBF 和SCBF 的空间复杂度与NCBF 相同.实验中我们保持N 不变,在一定范围内改变m n ,分别比较不同的η取值下3种CBF 的计数误差.为了比较NCBF,SCBF 和dlCBF 的空间复杂度,首先需要设置3种CBF 的计数误差相等.由于无法保证3种CBF 的计数误差严格相等,因此我们控制3种CBF 的平均计数误差之差的绝对值小于某一接近于0的常数ε,使之计数误差相近.对于某一固定的η,为使dlCBF 和NCBF 的计数误差相近,l d 首先取一个较小的值,然后每次增加1,直到两者计数误差之差的绝对值小于ε.同样地,对于某一η,为使SCBF 和NCBF 的计数误差相 近,首先设置b s 为0s n n b w m =⋅,然后每次增加∆b s ,其中,()ln(2)s N E f b ⋅∆=(18)直到两者计数误差之差的绝对值小于ε.选择每次增加∆b s 的原因是,b s 每增加∆b s ,k s 恰好增加1.这样便于计算阳性错误概率以及根据表2确定g s 的取值.在比较4种CBF 的负载适应性时,首先采用进行CBF 空间复杂度比较时的参数设置,通过适当的参数设置,使得4种CBF 的满负载计数误差相近;然后,再逐步降低负载率,比较不同负载率下,4种CBF 的归一化错误概率和归一化计数误差.。
cbf算法原理
CBF算法（Counting Bloom Filter）是一种基于布隆过滤器（Bloom Filter）的数据结构。
它通过组合布隆过滤器和计数
器实现了对数据出现次数的统计。
布隆过滤器是一种空间效率高、查询时间快的概率型数据结构，用于判断一个元素是否属于一个集合。
它使用一个位数组和多个哈希函数，当一个元素经过哈希函数映射后对应的位都被标记为1时，该元素可能在集合中。
但是由于哈希函数冲突的存在，可能会导致某个元素误判为在集合中。
CBF算法在布隆过滤器的基础上引入了计数器。
除了位数组外，每个哈希函数对应的位置会保存一个计数器，用于记录元素在集合中出现的次数。
当需要添加一个元素时，会将对应位置的计数器加1；当需要查询一个元素是否存在时，会检查对
应位置的计数器是否大于0。
CBF算法的原理如下：
1. 初始化时，创建一个位数组和多个哈希函数，以及对应的计数器数组，将其置为0。
2. 添加一个元素时，将元素经过多个哈希函数映射到位数组的对应位置，并将对应位置的计数器加1。
3. 查询一个元素是否存在时，将元素经过多个哈希函数映射到位数组的对应位置，检查对应位置的计数器是否大于0。
4. 删除一个元素时，将元素经过多个哈希函数映射到位数组的对应位置，并将对应位置的计数器减1。
由于CBF算法引入了计数器，可以实现对元素出现次数的统计，但是相应地增加了空间开销。
另外，由于哈希函数冲突的存在，可能会导致计数器值的不准确，一些元素的计数器值可能偏大或偏小。
因此，CBF算法适用于对数据出现次数的粗略统计，而不适用于精确计数场景。
BloomFilter算法Bloom Filter算法详解什么是布隆过滤器布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。
它实际上是⼀个很长的⼆进制向量和⼀系列随机映射函数 (下⾯详细说)，实际上你也可以把它简单理解为⼀个不怎么精确的set结构，当你使⽤它的contains⽅法判断某个对象是否存在时，它可能会误判。
但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对⾜够精确，只会有⼩⼩的误判概率。
当布隆过滤器说某个值存在时，这个值可能不存在；但是当它说不存在时，那么这个值⼀定不存在。
打个⽐⽅，当它说不认识你时，那就是真的不认识，但是当它说认识你时，可能是因为你长得像他认识的另⼀个朋友（脸长得有些相似），所以误判认识你。
布隆过滤器的使⽤场景在程序的世界中，布隆过滤器是程序员的⼀把利器，利⽤它可以快速地解决项⽬中⼀些⽐较棘⼿的问题。
如⽹页URL的去重、垃圾邮件识别、⼤集合中重复元素的判断和缓存穿透等问题。
布隆过滤器的典型应⽤有：⼤数据判断是否存在如果你的服务器内存⾜够⼤的话，那么使⽤HashMap可能是⼀个不错的解决⽅案，理论上时间复杂度可以达到O(1)级别，但是当数据量起来之后还是只能考虑布隆过滤器。
解决缓存穿透我们通常会把⼀些经常访问的数据放在Redis中当作缓存，例如产品详情。
通常⼀个请求过来之后，我们会先查询缓存，⽽不⽤直接读取数据库，这是提升性能最简单，也是最普遍的做法，但是如果⼀直请求⼀个不存在的缓存，那就会有⼤量的请求被直接打到数据库上，造成缓存穿透，布隆过滤器也可以⽤来解决此类问题。
爬⾍|邮箱等系统的过滤对爬⾍⽹址进⾏过滤，已经存在布隆中的⽹址，不再爬取。
对于垃圾邮件进⾏过滤，对每⼀个发送邮件的地址进⾏判断是否在布隆的⿊名单内，如果在就判断为垃圾邮件。
业务场景判断判断⽤户是否阅读过某视频或⽂章，⽐如抖⾳或头条，当然会导致⼀定的误判，但不会让⽤户看到重复的内容。
一种大象流两级识别方法严军荣;叶景畅;潘鹏【摘要】The high accuracy and low overhead of elephant flows identification have a great meaning on solving the controller's single point of failure problem in SDN traffic management.Aiming at the problem of high overhead of the existing elephant flows identification method,a two-level method for elephant flows identification was proposed which included a suspicious elephant detection algorithm based on TCP write-queue in the first stage and areal elephant detection algorithm based on flow duration in the second stage During the first stage,the suspicious elephant flows were identified in the end systems to reduce the amount of flows monitored by the SDN controller at the second stage Analysis and simulation prove that,under the premise of ensuring the accuracy of elephant flow identification,the two-level method for elephant flows identification reduces about 85％ overhead of identification compared with sampling identification method.%基于大象流的识别准确度高且开销低,对于解决SDN流量管理过程中控制器单点故障问题具有重要意义.针对现有大象流识别方法识别开销大的问题,提出一种大象流两级识别方法.该方法在第一阶段提出基于TCP发送队列的可疑大象流识别算法,在第二阶段提出基于流持续时间的真实大象流识别算法;第一阶段是在端系统中识别可疑大象流,用于降低第二阶段真实大象流识别过程中SDN控制器所需监测的网络流数量.实验分析表明,在保证大象流识别的高准确度前提下,大象流两级识别方法较基于采样的大象流识别方法可以降低约85％的控制器识别开销.【期刊名称】《电信科学》【年(卷),期】2017(033)003【总页数】8页(P36-43)【关键词】大象流识别;TCP发送队列;软件定义网络【作者】严军荣;叶景畅;潘鹏【作者单位】杭州电子科技大学通信工程学院,浙江杭州310018;杭州电子科技大学通信工程学院,浙江杭州310018;杭州电子科技大学通信工程学院,浙江杭州310018【正文语种】中文【中图分类】TP393软件定义网络（software defined networking，SDN）是一种新型网络架构[1,2]，其通过剥离网络设备的控制平面与数据转发平面并将控制平面抽象为集中式控制器，为网络提供了逻辑统一的转发控制平台，基于SDN特有的全网视图可快速实现流量调度策略的制定以及交换机流表的配置。
摘要Bloom Filter是Bloom在1970年提出的一种在可接收错误率范围之内利用Hash函数对时间和空间进行平衡折中的数据管理方法，主要涉及计算时间复杂度，占用空间大小和错误率三个因素，这种集合中特定元素存在与否判断的查询技术在现代网络中得到了很大的应用。
Counting Bloom Filter 使用计数器来替代Bloom Filter 中的比特位，从而对集合中的元素的频度进行测量，在具体的实现方法上有多层次、多Hash函数组和动态管理的计数器等许多具体形式。
论文结合入侵检测方面内容提出了用Count Bloom Filter实现对一些常见网络攻击进行异常检测的模型系统。
该系统基于Dos攻击原理，通过对数据包的特征提取，用Count Bloom Filter对特征值进行计数，然后由统计结果判断是否发生异常。
系统涉及到网络存储、Bloom Filter应用、网络攻击以及入侵检测等诸多方面的内容，且各方面紧密结合。
论文将对所有相关方面做个简单介绍以方便读者了解课题背景及课题任务。
最后论文将给出一个可以用于实践的模型关键词: HASH ；CBF；特征提取；TCP数据包ABSTRACTBloom Filter was raised by Bloom in 1970 to propos a reception in the error rate within the scope of benefits Hash functions of time and space for a balanced compromise methods of data management, mainly involving complex computing time, the space size occupiedand and the error rate . The technology has been largely used in judging whether a specific element is in a set. Counting Bloom Filter uses counters to substitute the Bloom Filter bit spaces.Then it can be used to measure the frequency of the element in the set.There are many ways to implement such as multiple levels、multiple hash and Dynamic management of the Counters.For a computer getting into the network, every time it is receiving and sending data. Now the most common network attack is DoS such as sending a great numberm of data packets in a short period to occupancy the resource of main computer,and make it can not proces normal data. In this paper, the starting point for this. Papers achieve a network traffic monitoring system. When a data packet flow reaches a certain threshold value we can say that someone is attacking me.Paper uses the counter of CBF to count the TCP date packets. Taking into account only for Anomaly Detection ,this system can only count with port number of TCP data packet. Papers relating to network storage, Bloom Filter application, Network attacks and intrusion detection and many other aspects.At last,paper will give a model that can be used in reality.Keywords：HASH；CBF；Feature Extraction；TCP data packets目录第一章背景介绍 (1)1.1Bloom Filter简介 (1)1.1.1 Bloom filter概念 (1)1.1.2集合表示和元素查询 (1)1.1.3 错误率估计 (2)1.1.4 位数组大小 (2)1.1.5 从哈希存储到Bloom Filter (3)1.2 Count Bloom Filter 简介 (4)1.2.1 Count Bloom Filter 概念及原理 (4)1.2.2 Count Bloom Filter的一般应用及变种 (5)第二章课题关键技术研究 (9)2.1 网络攻击简介 (9)2.1.1 服务拒绝攻击 (9)2.1.2利用型攻击 (10)2.1.3信息收集型攻击 (11)2.1.4假消息攻击 (12)2.2 TCP介绍 (12)2.3 SYN ACK 统计 (12)2.4 特征值，抓包 (13)2.5 散列算法介绍 (14)2.5.1 概念 (14)2.5.2 常见散列算法 (14)2.5.3 SHA/SHA-1算法 (14)第三章系统概要设计 (16)3.1 系统原型及目的 (16)3.2 流程图 (16)第四章程序设计及模拟系统实现 (19)4.1程序设计 (19)4.2 模拟系统实现 (20)第五章小结 (23)结束语 (24)致谢 (25)参考文献 (26)第一章背景介绍1.1Bloom Filter简介1.1.1 Bloom filter概念Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。
基于抽样和两级CBF的长流识别算法翟金凤;孙立博;鲁凯;林学勇;秦文虎【摘要】为满足高速网络流量测量需求,结合网络流显著的重尾分布特征,提出一种基于抽样和两级CBF的长流识别算法,先对观测时间内链路上通过的报文进行系统抽样,继而利用两级CBF对被抽样报文分别进行长流过滤和流长计数处理,最后再利用第二级CBF继续对所有未被抽样的报文进行查询,统计出长流所含的总报文数.实验验证该算法能在有效节约空间和时间资源的基础上,既实现对长流的准确识别,又实现对原始流长度的高精度测量,识别出的长流信息与真实信息完全相同.同时,该算法还具有可扩展性,一定误差范围内可以选用相对简单的哈希算法,或者使用硬件实现,进一步提高算法的处理效率.【期刊名称】《中国测试》【年(卷),期】2018(044)007【总页数】5页(P105-109)【关键词】网络流量测量;长流识别;抽样;计数型布隆过滤器;阈值【作者】翟金凤;孙立博;鲁凯;林学勇;秦文虎【作者单位】东南大学仪器科学与工程学院,江苏南京 210096;东南大学仪器科学与工程学院,江苏南京 210096;南京市计量监督检测院,江苏南京 210049;南京市计量监督检测院,江苏南京 210049;东南大学仪器科学与工程学院,江苏南京 210096【正文语种】中文【中图分类】TP393.060 引言随着网络带宽的增加和互联网应用的变化，网络技术和行为的频繁更新导致网络规模迅速扩大，网络环境日益复杂多变，引发出各种各样的安全问题[1]。
网络流量测量是掌握网络特征和解决各种问题的重要手段，成为各国科研机构和学术人员关注的焦点。
然而，新一代互联网的异构性和复杂性仍在不断加强[2]，与之矛盾的却是系统处理分析和存储资源的缺乏，使得对网络流量进行全数据采集的精确测量已不再可行[3-4]。
诸多研究表明，网络流具有显著的重尾分布特征，数量较少的长流占据了网络流量的大部分[5]。
因此掌握长流信息就可以对链路上经过的所有网络流有个整体的认识，便于对网络流量进行管理和监测分析，对网络流量计费、安全检测、流量调控等工程应用起着重大作用，并且对长流进行识别可以有效缩减处理和存储的数据量，提高系统处理效率和资源利用率。
