海量数据处理问题

分治法

• 总体思想是先根据Hash函数将一个内存难以一次性读取的大文件分散到若干小文件中（其中相同的数据会被hash到同一个小文件中），然后对每一个小文件的数据进行处理，再进行合并处理（例如外排序：对小文件进行快排，然后对于有序的子序列，只需要很少的内存就可以进行归并排序）
• 在处理海量数据中的最小k个数之类的问题可以使用堆排序（时间复杂度为O(N*lgk)）

多层划分

• 举例：求取海量数据的中位数。对于int32整数来说，可以按照32个位的前n位进行区域划分，可以划分2^n个区域，这些区域间是有序的。这样就可以确定中位数再哪个区域的第几大 数

bitmap

• 实质为bit数组，每一位只能为0或1
• int32只需要512M的内存就可以存储全部的整数
• 可以用2bit来表示多种状态，例如00表示无，01表示出现1次，10表示出现多次

字典树（Trie Tree）

• 只能用于字符串
• 在遍历时构建
• 相比于Hash表优点在于空间开销小

bloom filter

• 一般用bit数组存储，用于在海量数据下判断某元素时候存在于集合之中
• 使用k个Hash函数，将每一个数据都映射在bit数组中的k个位上（使用多个hash函数是为了减缓冲突问题，但是仍不可避免冲突所以有误差）
• 缺点是不能删除元素，除非把bit数组换成int数组，每一位表示一个计数器

倒排索引

• 用于文本检索，对所有文档建立倒排索引，可以查询指定单词出现在哪些文档中

simhash

• 用于比较文本之间的相似度
• 思想是将高维的特征向量降维成低维的特征向量，通过两个向量的海明距离来判断相似度
• 五个步骤：
  • 分词：将文本进行分词并对每个词赋予一个权重，代表该词在整个文本中的重要程度
  • hash：通过hash函数将原词映射为n位bit签名，将字符串转换为了向量
  • 加权：给词向量加权，对于每一位，1则直接乘权重，0则乘负的权重
  • 合并：将文本中的所有的词向量加权结果进行累加，变成一个向量
  • 降维：根据合并结果，大于0则置为1，小于0则置为0。这样就得到了一个n-bit的文本simhash签名
• 根据经验，文本之间海明距离小于3则认为相似度较高