July_algorithm 9.海量数据.pdf

海量数据处理七月算法邹博2015年11月14日10月算法在线班2/71倒排索引 倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件称为倒排索引文件，简称倒排文件(inverted file)。10月算法在线班3/71倒排列表 倒排列表记录了某个单词位于哪些文档中。一般在文档集合里会有很多文档包含某个单词，每个文档会记录文档编号(DocID)，单词在这个文档中出现的次数(TF)及单词在文档中哪些位置出现过等信息，这样与一个文档相关的信息被称做倒排索引项(Posting)，包含这个单词的一系列倒排索引项形成了列表结构，这就是某个单词对应的倒排列表。10月算法在线班4/71倒排列表10月算法在线班5/71倒排索引10月算法在线班6/71更新策略完全重建策略：当新增文档到达一定数量，将新增文档和原先的老文档整合，然后利用静态索引创建方法对所有文档重建索引，新索引建立完成后老索引会被遗弃。此法代价高，但是主流商业搜索引擎一般是采用此方式来维护索引的更新。再合并策略：当新增文档进入系统，解析文档，之后更新内存中维护的临时索引，文档中出现的每个单词，在其倒排表列表末尾追加倒排表列表项；一旦临时索引将指定内存消耗光，即进行一次索引合并，这里需要倒排文件里的倒排列表存放顺序已经按照索引单词字典顺序由低到高排序，这样直接顺序扫描合并即可。其缺点是：因为要生成新的倒排索引文件，所以对老索引中的很多单词，尽管其在倒排列表并未发生任何变化，也需要将其从老索引中取出来并写入新索引中，这样对磁盘消耗是没必要的。原地更新策略：试图改进再合并策略，在原地合并倒排表，这需要提前分配一定的空间给未来插入，如果提前分配的空间不够了需要迁移。实际显示，其索引更新的效率比再合并策略要低。混合策略：出发点是能够结合不同索引更新策略的长处，将不同索引更新策略混合，以形成更高效的方法。10月算法在线班7/71simHash算法 问题的起源：设计比较两篇文章相似度的算法。simHash算法分为5个步骤：分词 Hash 加权 合并 降维10月算法在线班8/71simHash的具体算法分词对待考察文档进行分词，把得到的分词称为特征，然后为每一个特征设置N等级别的权重。如给定一段语句：“CSDN博客结构之法算法之道的作者July”，分词后为：“CSDN 博客 结构 之 法 算法 之 道 的 作者 July”，然后为每个特征向量赋予权值：CSDN(4)博客(5)结构(3)之(1)法(2)算法(3)之(1)道(2)的(1)作者(5)July(5)，权重代表了这个特征在整条语句中的重要程度。hash通过hash函数计算各个特征的hash值，hash值为二进制数组成的n位签名。Hash(CSDN)=100101，Hash(博客)=101011。加权W=Hash*weight。W(CSDN)=100101*4=4-4-44-44，W(博客)=101011*5=5-55-555。合并将上述各个特征的加权结果累加，变成一个序列串。如：“4+5,-4+-5,-4+5,4+-5,-4+5,4+5”，得到“9,-9,1,-1,1”。降维对于n位签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们便可以根据不同语句simhash的海明距离来判断它们的相似度。例如把上面计算出来的“9,-9,1,-1,1,9”降维，得到“101011”，从而形成它们的simhash签名。10月算法在线班9/71分词的权值计算词频-逆文档频率TF-IDF(term frequencyinverse document frequency)是一种用于资讯检索与资讯探勘的常用加权技术。TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降：Weight=TF*IDF。如果某个分词在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。事实上，该技术在自然语言处理用途广泛，可以配合其它方法一起使用，如余弦距离(反比于相似度)、LDA主题模型等，用于聚类、标签传递算法等后续分析中。10月算法在线班10/7110月算法在线班11/71simHash的应用 每篇文档得到simHash签名值后，接着计算两个签名的海明距离即可。根据经验值，对64位的SimHash值，海明距离在3以内的可认为相似度比较高。海明距离的求法：两个二进制数异或值中1的个数 即：两个二进制数位数不同的个数。10月算法在线班12/71对simHash的分块处理 如何将其扩展到海量数据呢？譬如如何在海量的样本库中查询与其海明距离在3以内的记录呢？一种方案是查找待查询文本的64位simhashcode的所有3位以内变化的组合 大约43744个。10月算法在线班13/71倒排索引的应用：对simHash的分块处理 把64位的二进制simHash签名均分成4块，每块16位。根据抽屉原理，如果两个签名的海明距离在3以内，它们必有一块完全相同。然后把分成的4块中的每一个块分别作为前16位来进行查找，建立倒排索引。10月算法在线班14/71附：抽屉原理的应用 定义：二维坐标系oXY中，坐标(x,y)都是整数的点叫做“格点”。试证明：任取平面上5个格点，它们的连接线段的中点至少有1个是格点。10月算法在线班15/7110月算法在线班16/71对simHash进一步的思考 完全丢掉了位置信息和语义信息 考虑使用WordNet影响Hash值？考虑使用主题模型、标签传递等非确定性机器学习方法分析语义。10月算法在线班17/71倒排索引在实践中的另外一个应用 跳跃链表、跳跃表、跳表；GIS中的POI(Point of Interest)查询 部分匹配：七月算法在线学院，简称七月算法 跳跃匹配：中国科学院、中科院10月算法在线班18/71POI信息点搜索总框架10月算法在线班19/71建立查找树10月算法在线班20/71建立查找树10月算法在线班21/71处理Hash冲突10月算法在线班22/71Hash查找10月算法在线班23/71该复合结构可用性分析 假定POI总数为100万，每个POI平均字数为10个，那么，问题总规模为1000万；假定常用汉字为1万个，那么，Hash之后，1万个汉字对应的槽slot平均含有1000个POI信息；log1000=9.9658：即，将1000万次搜索，降到10次搜索。注：以上只是定性考虑，非准确分析10月算法在线班24/71Bloom Filter 布隆过滤器(Bloom Filter)是由Burton Howard Bloom于1970年提出的，它是一种空间高效(space efficient)的概率型数据结构，用于判断一个元素是否在集合中。在垃圾邮件过滤的黑白名单、爬虫(Crawler)的网址判重等问题中经常被用到。哈希表也能用于判断元素是否在集合中，但是Bloom Filter只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。Bloom Filter可以插入元素，但不可以删除已有元素。集合中的元素越多，误报率(false positive rate)越大，但是不会漏报(false negative)。10月算法在线班25/71Bloom Filter 如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比对来判定是否在集合内：链表、树等数据结构都是这种思路。但是随着集合中元素数目的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn)。可以利用Bitmap：只要检查相应点是不是1就知道可以集合中有没有某个数。这就是Bloom Filter的基本思想。10月算法在线班26/71Bloom Filter算法描述一个空的Bloom Filter是一个有m位的位向量B，每一个bit位都初始化为0。同时，定义k个不同的Hash函数，每个Hash函数都将元素映射到m个不同位置中的一个。记：n为元素数，m为位向量B的长度(位：槽slot)，k为Hash函数的个数。增加元素x计算k个Hash(x)的值(h1,h2hk)，将位向量B的相应槽Bh1,h2hk都设置为1；查询元素x即判断x是否在集合中，计算k个Hash(x)的值(h1,h2hk)。若Bh1,h2hk全为1，则x在集合中；若其中任一位不为1，则x不在集合中；删除元素x不允许删除！因为删除会把相应的k个槽置为0，而其中很有可能有其他元素对应的位。10月算法在线班27/71Bloom Filter 插入查找数据 插入x,y,z 判断w是否在该数据集中10月算法在线班28/71BloomFilter的特点 不存在漏报：某个元素在某个集合中，肯定能报出来；可能存在误报：某个元素不在某个集合中，可能也被认为存在：false positive；确定某个元素是否在某个集合中的代价和总的元素数目无关 查询时间复杂度：O(1)10月算法在线班29/71Bloom Filter参数的确定 单个元素某次没有被置位为1的概率为：k个Hash函数中没有一个对其置位的概率为：如果插入n个元素，仍未将其置位的概率为：因此，此位被置位的概率为：m11km11knm11knm11110月算法在线班30/71Bloom Filter参数的确定 查询中，若某个待查元素对应的k位都被置位，则算法会判定该元素在集合中。因此，该元素被误判的概率(上限)为：考虑到：从而：kknmkq111mknmknmmknmknemmm111111 kmknekP110月算法在线班31/71Bloom Filter参数的确定 P(k)为幂指函数，取对数后求导：kkkkkkebkmknbbbkbkPkPbkkPbekPmn1ln1ln11lnln11k的导数取关于令 nmnmkebbbbbbbbbbkbmknkkkkkkkkkk693.02ln21211ln1ln101ln1ln nmnmkkkP6185.0222112ln10月算法在线班32/71参数m、k的确定 m的计算公式：由 得 此外，k的计算公式：至此，任意先验给定可接受的错误率，即可确定参数空间m和Hash函数个数k。nmnmkkkP6185.0222112lnnPmnmPPnm212ln2lnln2ln2lnln22lnln2ln1Pnmk10月算法在线班33/71Bloom Filter参数的讨论 1.442695041 若接收误差率为10-6时，需要位的数目为29*n。2lnln2ln2lnln121PnmknPm10月算法在线班34/71Bloom Filter的特点 优点：相比于其它的数据结构，Bloom Filter在空间和时间方面都有巨大的优势。Bloom Filter存储空间是线性的，插入/查询时间都是常数。另外，Hash函数相互之间没有关系，方便由硬件并行实现。Bloom Filter不存储元素本身，在某些对保密要求非常严格的场合有优势。很容易想到把位向量变成整数数组，每插入一个元素相应的计数器加1，这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在BloomFilter里面。这一点单凭这个过滤器是无法保证的。另外计数器下溢出也会造成问题(槽的值已经是0了，仍然执行删除操作)。10月算法在线班35/71BloomFilter用例Google著名的分布式数据库Bigtable使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数；Squid网页代理缓存服务器在cachedigests中使用了BloomFilter；Venti文档存储系统采用BloomFilter来检测先前存储的数据；SPIN模型检测器使用BloomFilter在大规模验证问题时跟踪可达状态空间；Google Chrome浏览器使用BloomFilter加速安全浏览服务；在很多Key-Value系统中也使用BloomFilter来加快查询过程，如Hbase，Accumulo，Leveldb。一般而言，Value保存在磁盘中，访问磁盘需要花费大量时间，然而使用BloomFilter可以快速判断某个Key是否存在，因此可以避免很多不必要的磁盘IO操作；另外，引入布隆过滤器会带来一定的内存消耗。10月算法在线班36/71Bloom Filter+Storage结构10月算法在线班37/71排序的目的 排序本身：得到有序的序列 方便查找 长度为N的有序数组，查找某元素的时间复杂度是多少？长度为N的有序链表，查找某元素的时间复杂度是多少？单链表、双向链表 如何解决该问题？10月算法在线班38/71跳跃链表(Skip List)Treaps/RB-Tree/BTree 跳跃链表是一种随机化数据结构，基于并联的链表，其效率与RBTree相当。具有简单、高效、动态(Simple、Effective、Dynamic)的特点。跳跃链表对有序的链表附加辅助结构，在链表中的查找可以快速的跳过部分结点(因此得名)。查找、增加、删除的期望时间都是O(logN)with high probability(W.H.P.1-1/(n)10月算法在线班39/71跳跃链表(Skip List)跳跃列表在并行计算中非常有用，数据插入可以在跳表的不同部分并行进行，而不用全局的数据结构重新平衡。跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速跑道”，这里在层i中的元素按某个固定的概率p出现在层i+1中。平均起来，每个元素都在1/(1-p)个列表中出现。思考：为什么是1/(1-p)？10月算法在线班40/71跳跃表示例注：各个文献中对于“层”、“间隔”的定义略有差别10月算法在线班41/71双层跳表时间计算 粗略估算查找时间：T=L1+L2/L1(L1是稀疏层，L2是稠密层)在L2上均匀取值，构成L1；则L2/L1是L1上相邻两个元素在L2上的平均长度L1：在稀疏层的最差查找次数L1/L2：在稀疏层没有找到元素，跳转到稠密层需要找的次数 若基本链表的长度为n，即|L2|=n，|L1|为多少，T最小呢？T(x)=x+n/x，对x求导，得到x=sqrt(n)min(T(x)=2sqrt(n)10月算法在线班42/71 粗略估算查找时间：T=L1+L2/L1+L3/L2(L1是稀疏层，L2是稠密层，L3是基本层)在L3上均匀取值，构成L2；在L2上均匀取值，构成L1；则L2/L1是L1上相邻两个元素在L2上的平均长度，L3/L2是L2上相邻两个元素在L3上的平均长度 若基本链表的长度为n，即|L3|=n，|L1|、|L2|为多少，T最小呢？T(x,y)=x+y/x+n/y，对x,y求偏导，得到x=min(T(x,y)=时间复杂度分析3n33n10月算法在线班43/71 建立k层的辅助链表，可以得到最小时间 问题：在n已知的前提下，k取多大最好呢？显然，当k=logN时，T(n)=logN*n(-logN)问：n(-logN)等于几？一个很容易在实践中使用的结论是：当基本链表的数目为N时，共建立k=logN个辅助链表，每个上层链表的长度取下层链表的一半，则能够达到logN的时间复杂度！理想跳表：ideal skip list跳表最优时间分析knknT)(10月算法在线班44/71插入元素 随着底层链表的插入，某一段上的数据将不满足理想跳表的要求，需要做些调整。将底层链表这一段上元素的中位数在拷贝到上层链表中；重新计算上层链表，使得上层链表仍然是底层链表的1/2；如果上述操作过程中，上层链表不满足要求，继续上上层链表的操作。新的数据应该在上层甚至上上层链表中吗？因为要找一半的数据放在上层链表(为什么是一半？)，因此：抛硬币！10月算法在线班45/71插入元素后的跳表维护 考察待需要提升的某段结点。若抛硬币得到的随机数p0.5，则提升到上层，继续抛硬币，直到p0.5；或者到了顶层仍然p0.5，建立一个新的顶层10月算法在线班46/71删除元素 在某层链表上找到了该元素，则删除；如果该层链表不是底层链表，跳转到下一层，继续本操作。10月算法在线班47/71 若多次查找，并且相邻查找的元素有相关性(相差不大)，可使用记忆化查找进一步加快查找速度。对关于k的函数求导，可计算得到k=lnN处函数取最小值，最小值是elnN。对于N=10000，k取lnN和logN，两个最小值分布是：25.0363和26.5754。强调：编程方便，尤其方便将增删改查操作扩展成并行算法。跳表用单链表可以实现吗？用双向链表呢？进一步说明的问题knknT)(10月算法在线班48/71进行106次随机操作后的统计结果10月算法在线班49/71Code：Structure10月算法在线班50/71Code：Find10月算法在线班51/71Code：Insert10月算法在线班52/71Insert part110月算法在线班53/71Insert part210月算法在线班54/71Code：Delete10月算法在线班55/71Delete part10月算法在线班56/71Code：Test10月算法在线班57/71Test10月算法在线班58/71MD5 MD5(Message Digest Algorithm)，消息摘要算法，为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。文件号RFC 1321(R.Rivest,MIT Laboratory for Computer Science and RSA Data Security Inc.April 1992)10月算法在线班59/71MD5的框架理解 对于长度为512bit的信息，可以通过处理，得到长度为128bit的摘要。初始化摘要：0 x0123456789ABCDEFFEDCBA9876543210 A=0 x01234567B=0 x89ABCDEF C=0 xFEDCBA98D=0 x76543210 现在的工作，是要用长度为512位的信息，变换初始摘要。10月算法在线班60/71MD5的总体理解 定义变量a,b,c,d,分别记录A,B,C,D;将512bit的信息按照32bit一组，分成16组；分别记为Mj(0j15)；取某正数s、tk，定义函数：FF(a,b,c,d,Mj,s,tk)=(a+F(b,c,d)+Mj+tk)s 利用Mj分别进行信息提取，将结果保存到a 其中，F(X,Y,Z)=(X&Y)|(X&Z)10月算法在线班61/71MD5的总体理解 经过以上16次变换，a,b,c,d带有了Mj的信息 事实上经过四轮这样的变换(4轮*16次=64次)经过64次变换后，将a,b,c,d累加给A,B,C,D 此时，完成了512bit信息的提取；进行下一个512bit信息的相同操作10月算法在线班62/71MD5框架10月算法在线班63/71MD5细致算法 在算法中，首先需要对信息进行填充，使其长度对512求余的结果等于448。填充的方法如下，在信息的后面填充一个1和若干个0，直到满足上面的条件。然后，在这个结果后面附加一个以64位二进制表示的原始信息长度Length。经过这两步的处理，数据总长度为N*512+448+64=(N+1)*512，即长度恰好是512的整数倍。10月算法在线班64/71MD5的细致算法 定义四个非线性函数：F(X,Y,Z)=(X&Y)|(X)&Z)H(X,Y,Z)=XYZG(X,Y,Z)=(X&Z)|(Y&(Z)I(X,Y,Z)=Y(X|(Z)Mj表示数据的第j个子分组(0j15，循环表示)，常数tk是232*abs(sin(k)的整数部分，1k64，单位是弧度。FF(a,b,c,d,Mj,s,tk)=(a+F(b,c,d)+Mj+tk)s GG(a,b,c,d,Mj,s,tk)=(b+G(b,c,d)+Mj+tk)s HH(a,b,c,d,Mj,s,tk)=(b+H(b,c,d)+Mj+tk)s II(a,b,c,d,Mj,s,tk)=(b+I(b,c,d)+Mj+tk)s10月算法在线班65/7164次操作10月算法在线班66/71海量数据系统设计小结 相信理论，重视实践 O(NlogN)优于O(N2)O(N2.81)VS O(N3)内存命中、并行开销 融会贯通，适度改造 POI结构/R树变体10月算法在线班67/71思考10月算法在线班68/71讨论10月算法在线班69/71讨论10月算法在线班70/71我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班71/71感谢大家恳请大家批评指正！