海量数据处理 | 关于TopK的思考

   目  录   

海量数据处理–TopK引发的思考

1 三问海量数据处理

2 解决Top K

     2.1抛出问题：寻找热门查询

     2.2分析问题

         2.2.1划分

         2.2.2统计

          2.2.3数据结构

          2.2.4合并

          2.2.5结束

3 Trie树和倒排索引

    3.1倒排索引

    3.2字典树

    3.3应用实例

 海量数据处理–TopK引发的思考

01

三问海量数据处理

什么是海量数据处理，为什么出现这种需求？

如何进行海量数据处理，常用的方法和技术有什么？

如今分布式框架已经很成熟了，为什么还用学习海量数据处理的技术？

简单回答

什么是海量数据处理，为什么出现这种需求？

如今互联网产生的数据量已经达到PB级别，如何在数据量不断增大的情况下，依然保证快速的检索或者更新数据，是我们面临的问题。所谓海量数据处理，是指基于海量数据的存储、处理和操作等。因为数据量太大无法在短时间迅速解决，或者不能一次性读入内存中。

如何进行海量数据处理，常用的方法和技术有什么？

时间角度，我们需要设计巧妙的算法配合合适的数据结构来解决；例如常用到的数据结构：哈希、位图、堆、数据库（B树），红黑树、倒排索引、Trie树等。空间角度：我们只需要分而治之即可，两大步操作：分治、合并。MapReduce就是基于这个原理。

如今分布式框架已经很成熟了，为什么还用学习海量数据处理的技术？

这个问题，就相当于为什么要学习算法，因为大部分人在工作中都很少用到这些算法和高级的数据机构。武侠讲究内外兼修才是集大成着。算法就是内功，可以不用，不可以没有。算法更多的是理解和推到的过程，这就是为什么很多学数学和物理专业的学生，可以在计算机行业做的很好，因为他们的数学好，可以很好的理解各种推到过程和算法原理。最后一句话，知其然而后知其所以然，技术更好的成长。

02

解决Top K

这篇文章，我采用总分的结构进行写作，我们每次都会抛出一个问题，这个问题对应的海量数据处理的一个方面，我们从下面几个角度分析：

1、对应海量数据处理的哪个技术，从时间角度和空间角度考虑

2、分析这个问题，如何解决

3、提出解决方案，进行分析

4、详细讲解这处理这个问题时，用到的技术，例如什么是堆，hash等

2.1 抛出问题：寻找热门查询

任何的搜索引擎（百度、Google等）都会将用户的查询记录到日志文件。对于百度这种公司，我们知道每天有很多Query查询，假设有100G的日志文件，只有一台4G内存的电脑，现在让你统计某一天热门查询的Top 100. （Top 100的统计是很有用意义的，可以提供给用户，知道目前什么是最热门的，关注热点，例如金庸老先生的去世，现在应该就是热门。）

2.2 分析问题

根据题目的描述，我们有100G日志文件，只有一台4G的电脑，这是空间不足的问题，我们需要分而治之。

1、划分文件，将100G日志文件划分成K的小文件。K >= 100G / 4G = 25。这里我们去K=50（为什么不取25呢？），将所有的Query划分到50个小文件中，然后统计每一个小文件中的Query的频率，之后合并结果，得到最后的Top 100的Query。

2、需要我们处理的两个点：划分和合并。

划分：保证相同的Query划分到同一个小文件中。

统计：统计每个小文件中Query的频率

合并：如何快速的合并得到结果。

划分的时候我们需要用到一个叫做hash的技术，两步走，

3、hash(string) = key_index,

4、File_index = Key_index % K(50)

划分

设计一个hash函数，需要保证的正string -> index的转换，这里不需要考虑冲突，只有保证相同的string对应一个key_index即可，一个好的hash函数会将均匀分布的数据，均匀分布到不同的文件中去。常用的Hash函数和原理

const unsigned int BIG_MOD = 1000003;inline unsigned int hash_code(std::string&& key){unsigned int value = 0;for(int i = 0; i < key.size(); i++) {31 + (unsigned int) key[i];        value %= BIG_MOD;    }return}      

统计

这里给出两种方法， hash_map和Trie数。每一个小文件有一个输出结果，这里我们只需要输出前Top 100频率进行。

Hash_map这个原理跟前面的提到的hash函数基本一样，只是需要解决冲突问题，之后会在别的文章中专门提出。C++的结构map，或者Java中Hashmap或者Python中的dict基本使用方式一样。Map[query] += 1.

HashMap的不足在于我们空间使用多，对于查询这种Query，很多的查询都是一样的，我们可以使用Trie树来解救，这是一个前缀树的结果，例如

Querys = {“我爱你”，“爱你们”，“我”，“我”，“我爱你“，”金庸“}，构造的树的格式如需：

数据结构

const int MAXN = 10000;struct TreeNodestringintintstruct TreeNode *next[MAXN];};      

具体的Trie树细节，这里就不在继续展开，可以搜索相关文章，后续可能会继续退出Trie树的相关文章。

基于上述两种方法，我们都可以直接得到Top 100的结果。输出文件格式如下：

Query1 Count1

。

。

。

Queryi Counti

合并

读取所有的结果在内存中，根据Count排序取前100，时间复杂度是O(nlogn),n是所有个数n=50*100. 但是注意到我们只要前k个最大的，我可以使用堆排序，使用一个叫做最小堆的问题。维护k(100)大小的最小堆，每次插入新的元素，去掉最小的元素，时间复杂度O(k + (n-k)logk),比排序小很多。

这里同样可以使用Trie树，和上述的方式一样，注意这可以转化一个取第k个大小的问题，我们也可以使用快速排序中划分函数，进行找到第k个，前面的就是我们需要的目标。

结束

到这里我们的问题已经可以结束了，但是却有几个问题需要提出来。

这真的是热门Query统计吗？百度等公司是这么做的吗？相似的Query怎么处理？如何实时的更新热门榜单呢？等等的问题，需要我们思考。

Hash划分的时候，划分文件不平衡怎么办？如何保证平均划分？

 Trie树和倒排索引 

3.1 倒排索引 

倒排索引是一种索引方法，常用在搜索引擎中，这个数据结构是根据属性值来确定记录的位置。对于一批文档，我们的属性值就是关键字，对应值是包含该属性的文档的ID或者文化的位置。

例如

T0T1T2      

构建倒排索引

a: {0,1,2}b: {0,2}c: {0,2}d: {1}e: {1}      

检索的时候可以根据关键字的交集或者并集进行检索，可以看出，倒排索引就是正向索引的相反。原理其实很简单，可以通过学习或者问题的性质，来发现什么时候使用倒排碎索引，最重要的倒排索引怎么优化，在内存中和文件上如何分配，才能满足快速的检索。倒排索引的构建可以根据自己的业务，决定需要存储什么信息，但是属性值是确定的，对应的集合中可以保留出现的次数等信息。

3.2 字典树

字典树，Trie树是一种前缀树，我们之前也有介绍过，一般应用在快速查询中，例如搜索提示，当你输入前半部分，会提示后半部分的内容。字典树用一句话表示就是根据字符串的前缀构成的树结构。

格式定义

template<typenamestruct TreeNodeint flag; // {1,0}1:表示存在，0:表示不存在int count: // 表示这个字符串出现的次数struct TreeNode **childs; // 索引的孩子节点    T value;};      

搜索字典项目的方法为：(来自百度百科)

从根结点开始一次搜索；

取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；

在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。

迭代过程……

在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

3.3 应用实例

1、串的快速检索

给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

2、“串”排序

给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出

用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

3、最长公共前缀

对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为当时公共祖先问题。

4、搜索引擎

一个搜索引擎执行的目标就是优化查询的速度：找到某个单词在文档中出现的地方。以前，正向索引开发出来用来存储每个文档的单词的列表，接着掉头来开发了一种反向索引。 正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。实际上，时间、内存、处理器等等资源的限制，技术上正向索引是不能实现的。为了替代正向索引的每个文档的单词列表，能列出每个查询的单词所有所在文档的列表的反向索引数据结构开发了出来。随着反向索引的创建，如今的查询能通过立即的单词标示迅速获取结果（经过随机存储）。随机存储也通常被认为快于顺序存储。

作者简介

xiaoran，Datawhale团队成员， 中科院硕士，百度算法工程师，推荐系统、搜索引擎爱好者。研究方向：图像识别。个人经历：ccf大数据计算智能大赛前25名，秋招中拿到百度、阿里、头条等多家公司的算法offer。

生活如此，问题不大

喵~

—  E N D  —

图片/伊小雪

排版/无多

Datawhale