大数据处理的一些算法学习

  1. 倒排索引 一般的索引都是通过在内容中提取关键词作为索引，索引文件记录每个文章中出现的关键词，查询的时候根据搜索内容去查询每个文档的关键词，来确定是否为所需文档，然后合并查询结果。（以文档为中心）

    倒排索引是通过关键词去存储相关的文档地址和频度(出现次数)，通过搜索词分词去查询关键字，然后得到关键词对应的文档地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。（以关键词为中心）

  2. bloomfilter

    两个不同url通过同一个hash可能得到相同的值(hash碰撞) 特性：bloomfilter不存在的肯定不存在，bloomfilter中存在的可能判断为不存在。不会漏，只会错 主要就是两个函数，求bitarray的大小的：m = ceil((n * ln(p)) / ln(1.0 / (pow(2.0, ln(2.0)))))；求hash函数的个数：k=(ln2)*(m/n)
    bloomfilter 可以看做是bitmap的扩展。
    bitmap一般采用bit位置表示值，而1或0表示是否存在该值

  3. 外排序

    1. 外排序其实就是内存不够用的时候，在外存储器（一般是硬盘）暂时存储排序数据的方式。
    2. 比如有一个文件很大，需要对其中的数据进行排序，而其容量大概是内存的10倍，这样

  4. trie树

    1. 将词语的每个字符作为节点构建树，算法十分简单
    2. 从root开始到叶子节点的路径，每一条都是一个词语
    3. 时间复杂度大概是O(N)，由于公共前缀会使用相同的路径，所以也节省了大量的空间，如果词语存在的公共前缀越多会越省空间（持久化的时候会比原文件小很多）。 但是由于每一个字符都会使用一个节点，对应一个变量空间，所以对于直接存储字符串，会浪费更多内存。支持字符集的N次方(N为词语长度)
    4. 我这里python版本的，使用dict嵌套完成，并不会存在以上的字符集N次方的问题，dict自动增长，默认支持所有的字符集，一般来讲会比原词语集占内存较少，只是保存dict结构需要浪费额外的内存。

  5. 双层桶划分

    1. 其实就是一种思想，就是当数据量过大，内存处理不过来时，将数据分割成内存可以处理的大小，然后分步处理，可以经过多次划分处理，直到内存可以合并最后的处理数据。
    2. 其实可以知外排序也是双层桶划分的一种体现。
Flag Counter