系统设计学习（四）海量数据

十一，百亿数据中找中位数

1. 桶/计数排序思想

   根据数据的特征，比如数据落在某个固定范围内，可以使用桶排序或计数排序的思想。通过统计每个桶内元素的数量，我们可以确定中位数所在的桶，然后在该桶内使用更精确的方法计算中位数。

2. 外部排序

   如果数据无法一次性装入内存，则可以使用外部排序。这个过程包括将数据分割成多个块，每个块单独排序并存储在外部存储器（如硬盘）上，再将这些有序的块合并来找出整体的中位数。

   1. 分割数据
   将原始数据集分割成多个小块，称为“runs”或“chunks”。每个小块的大小应当适合放入内存中进行排序。
   
   2. 排序小块
   读取每个小块至内存，使用内部排序算法（如快速排序、堆排序等）对其进行排序。
   
   3. 存储排序后的小块
   将排序后的小块写回到外部存储（硬盘等）上。这样，硬盘上就有了多个有序的数据块。
   
   4. 归并排序
   使用N路归并排序算法，将所有有序的小块合并成一个完整有序的数据集。这个步骤通常涉及以下操作：
   
   创建一个优先队列（最小堆），初始化时将每个有序块的第一个元素加入。
   不断从优先队列（堆）中取出最小元素，并将该元素所在块的下一个元素加入队列。
   将取出的最小元素写入到最终的输出文件中。
   重复以上过程直到所有块中的元素都被处理。
   5. 输出最终结果
   最终，所有数据块中的元素都按顺序写入到最终输出文件中，完成总体的排序任务。
   
   外部排序的效率很大程度上取决于磁盘IO的速度以及归并阶段处理有序块的效率。在现代操作系统中，通常会使用缓冲区来减少磁盘IO次数，提高外部排序的速度。
   

3. MapReduce估算中位数

   • 将数字按范围（数位大小）分到不同的桶中

   • 每个分位桶排序计算得到一个局部中位数

   • 以中间两个桶的局部中位数为基础来估算全局中位数

十二，海量数据，求TopK问题

海量日志数据，提取出某日访问百度次数最多的那个IP，如果想一次性把所有IP数据装进内存处理，则内存容量明显不够，故针对数据太大，内存受限的情况，可以把大文件转化成（取模映射）小文件，从而大而化小，逐个处理。换言之，先映射，而后统计，最后排序。

具体分为以下3个步骤

• 1.分而治之/hash映射
  • 首先把这一天访问百度日志的所有IP提取出来，然后逐个写入到一个大文件中，接着采用映射的方法，比如%1000，把整个大文件映射为1000个小文件。
• 2.hash_map统计
  • 当大文件转化成了小文件，那么我们便可以采用hash_map(ip, value)来分别对1000个小文件中的IP进行频率统计，再找出每个小文件中出现频率最大的IP。
• 3.堆/快速排序
  • 统计出1000个频率最大的IP后，依据各自频率的大小进行排序(可采取堆排序)，找出那个频率最大的IP，即为所求。

注：Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中去的情况，即这里采用的是%1000算法，那么同一个IP在hash后，只可能落在同一个文件中，不可能被分散的。

同样的，有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词

解法：

• 1.分而治之/hash映射
  • 顺序读取文件，对于每个词x，取hash(x)%5000，然后把该值存到5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。当然，如果其中有的小文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。
• 2.hash_map统计
  • 对每个小文件，采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
• 3.堆/归并排序
  • 取出出现频率最大的100个词（可以用含100个结点的最小堆）后，再把100个词及相应的频率存入文件，这样又得到了5000个文件。最后就是把这5000个文件进行归并（类似于归并排序）的过程了。

参考：https://www.cnblogs.com/xingyunblog/articles/9078808.html

十三、如何设计一个比较两篇文章相似度的算法？

局部敏感哈希（Locality-Sensitive Hashing，LSH）是一种用于快速相似性搜索的算法技术。该技术主要用于高维空间中的数据，其目标是为相似的对象生成相同或相近的哈希值，而对于不相似的对象则生成不同的哈希值。通过这种方式，LSH能够在大规模数据集中高效地执行近邻搜索任务。

特点：
局部敏感性：如果两个数据点相似，那么它们被哈希到相同桶中的概率会很高。
可调性：LSH家族通常有参数可以调整，以控制相似度与哈希碰撞概率之间的平衡。

simhash作为locality sensitive hash（局部敏感哈希）的一种：

• 其主要思想是降维，将高维的特征向量映射成低维的特征向量，通过两个向量的Hamming Distance来确定文章是否重复或者高度近似。

  其中，Hamming Distance，又称汉明距离，在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。如此，通过比较多个文档的simHash值的海明距离，可以获取它们的相似度。

simhash算法分为5个步骤：分词、hash、加权、合并、降维，具体过程如下所述：

• 分词
  • 给定一段语句，进行分词，得到有效的特征向量，然后为每一个特征向量设置1-5等5个级别的权重（如果是给定一个文本，那么特征向量可以是文本中的词，其权重可以是这个词出现的次数）。例如给定一段语句：“CSDN博客结构之法算法之道的作者July”，分词后为：“CSDN 博客 结构 之 法 算法 之 道 的 作者 July”，然后为每个特征向量赋予权值：CSDN(4) 博客(5) 结构(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括号里的数字代表这个单词在整条语句中的重要程度，数字越大代表越重要。
• hash
  • 通过hash函数计算各个特征向量的hash值，hash值为二进制数01组成的n-bit签名。比如“CSDN”的hash值Hash(CSDN)为100101，“博客”的hash值Hash(博客)为“101011”。就这样，字符串就变成了一系列数字。
• 加权
  • 在hash值的基础上，给所有特征向量进行加权，即W = Hash * weight，且遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘。例如给“CSDN”的hash值“100101”加权得到：W(CSDN) = 100101_4 = 4 -4 -4 4 -4 4，给“博客”的hash值“101011”加权得到：W(博客)=101011_5 = 5 -5 5 -5 5 5，其余特征向量类似此般操作。
• 合并
  • 将上述各个特征向量的加权结果累加，变成只有一个序列串。拿前两个特征向量举例，例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”进行累加，得到“4+5 -4±5 -4+5 4±5 -4+5 4+5”，得到“9 -9 1 -1 1”。
• 降维
  • 对于n-bit签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们便可以根据不同语句simhash的海明距离来判断它们的相似度。例如把上面计算出来的“9 -9 1 -1 1 9”降维（某位大于0记为1，小于0记为0），得到的01串为：“1 0 1 0 1 1”，从而形成它们的simhash签名。