By

Contents
  1. 1. 前言
  2. 2. 分而治之的解法
  3. 3. BitMap
    1. 3.1. 问题实例
  4. 4. Bloom Fliter
    1. 4.1. 原理
    2. 4.2. 哈希函数个数的选取
    3. 4.3. 优点
    4. 4.4. 缺点
    5. 4.5. 应用
    6. 4.6. 扩展：压缩布隆过滤器
    7. 4.7. 扩展：用于解决规模增长问题的过滤器
  5. 5. Trie树
    1. 5.1. 应用
      1. 5.1.1. 2、词频统计Trie树常被搜索引擎系统用于文本词频统计 。
      2. 5.1.2. 3、字符串排序
      3. 5.1.3. 4、前缀匹配
      4. 5.1.4. 5、作为其他数据结构和算法的辅助结构
  6. 6. 倒排索引(Inverted index)
    1. 6.1. 方法介绍
    2. 6.2. 问题实例

前言

海量数据通常由于数据量太大，无法在较短时间内结局，或者无法一次性装入内存中，因此需要搭配一些方法和数据结构。

  • 针对时间问题，可采用数据结构：布隆过滤器、哈希、位图、堆、数据库、倒排索引、Trie树等
  • 针对空间问题，可以采用分而治之、哈希映射的方法。

此外，针对单机和集群：

  • 单机是指处理装载数据的机器有限，只需要考虑CPU、内存和硬盘之间的交互

  • 集群是指机器多台，适合分布式处理或并行计算，更多考虑节点与节点之间的交互。

    一般来说处理方法分为以下十种：

    1. 哈希分治
    2. simhash算法
    3. 外排序
    4. Mapreduce
    5. 多层划分
    6. 位图
    7. 布隆过滤器
    8. Trie树
    9. 数据库
    10. 倒排索引

分而治之的解法

1.海量日志数据，提取出某日访问百度次数最多的那个IP

  1. 寻找热门查询，300万个查询字符串中统计最热门的10个查询
  1. 把大文件映射(取模映射)成m个不重复的小文件（意思是同一个词/IP/URL不会出现在多个文件中）。
  2. hash_map统计
    当大文件转化成了小文件，那么我们便可以采用hash_map(ip, value)来分别对小文件中的词/IP/URL进行频率统计（O（n）时间），再找出每个小文件中出现频率最大的词/IP/URL。
    如果是字符串的话可以用trie树，关键字域存该查询串出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度）。
  3. 堆/快速排序
    统计出个$mxk$个频率最大的 词/IP/URL 后，维护大小为k的堆（求频率最大用最小堆，反之亦然）,费时$O(klogk+（m-k）logk）=O(m*logk)$ (前一项是建堆，后一项是调整堆)，输出k个值。
    当然这个步骤也可以用归并排序（内排与外排相结合）或者快排。

删除海量字符串里面的重复可以用trie树，set，hashmap。

BitMap

海量数据排序解法

  1. 位图
  2. 外排序，多路归并排序

简单的说就是用数组存放若有数据就标志为1或true，若不存在标志为0或false。比如1，2，2，5，这里最大值为5，0至5中不存0，3，4，所以：
Array[0]=0，Array[1]=1，Array[2]=2，Array[3]=0，Array[4]=0，Array[5]=1
上面数中由于2有两个，所以用int存数组的值，不用boolean型，这样如果有多个同样的数字可以用值表示个数。如上面Array[2]=2，就表示2有2个。

这样排序就方便多了，比如上面开始是{2,5,2,1}这样一无序数组A。找出最大值：5.即用来作位图排序的数组B要申请的大小为5.循环这个数组，把数组A的值用作数组B的下标,如果存在就把值加1，即数组B的值为对应的个数。

1
2
3
4
for (int i : A) {
       B[i]++;
}

这样B的值最后同上面的Array一样。把B值大于0的输出就是排好序的了。如上面的数组大于0依次有：1，2，2，5.

从上面可以看出位图排序至少要注意两点：
1、 最大值和最小值之间不能相差太大，否则浪费空间。
2、 如果有负数，上面要转换一下，最申请的空间大小为max-min+1，数组B的下标也要作对应的转换，输出前也要转换回去。如int[] arr = { 1, 3, -3, 0, 0};

同时，java中也有对应的实现，java.util.BitSet.

问题实例

1、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数

解法一：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

解法二：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。”

2、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

解法一：可以用位图/Bitmap的方法，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。

Bloom Fliter

来源：http://www.xuebuyuan.com/2063892.html

原理

其实很简答，但是很聪明。
维基里面有个下例子的图，对这个问题讲的很清楚

对于一个元素，判断它是否存在于集合内，我们用不同的hash算法去算他，比如有3个，假设每一个算出来都是一个数吧，以这个数为下标，我们就把位数组里面相应的数设置为1，因为位数组只能设置为0或者1。3个hash函数算完后，我们得到三个下标，看着三个下标里面的元素是否是1，是1就在里面，如果有一个为0就不在里面。插入的方式也就是将相应的下标设置为1。

总的来说，bloom filter以低概率的错误（将“不在”集合内的元素判定为“在”）换取时间和空间。

哈希函数个数的选取

Hash函数的个数k不是越大越好，k如何取，才能使得f最小？

也就是让一半的位空着时候效果最好，最终推导结果是 k=In2 * (m/n)
K个hash越相互独立效果越好。

优点

具有很好的空间和时间效率（只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题）
不存在false negative (漏报)，就是说如果元素存在的话，必能得到正确的结果

缺点

不能删除已储存的元素
元素越多，false positive rate(误报率)越大，也就说将不存在的元素判定为存在。（常见的补救方法：增加一个白名单，存储可能被误判的元素）

应用

其可以用来实现数据字典，进行数据的判重，或者集合求交集。
下面是例子：

  • 垃圾邮件过滤中的黑白名单
  • 爬虫(Crawler)的网址判重模块,url 去重
  • Proxy cache命中查询
  • Bigtable、Hadoop、Cassandra、Hbase
  • 封包路由
  • 分布式环境中，用于资源定位

下面详细的阐述一个例子，先是插入：

为了存储一亿个电子邮件地址
建立一个含有十六亿二进制比特，也就是两亿字节
将十六亿的比特全部设置为0
我们用八个不同的哈希函数，以电子邮件地址为键，算出值，有8个（也许不是数字）
我们再一个哈希函数，分别以这8个值为键，会得到8个数值（范围为1到十六亿的某个数字）
以上一步算出的8个数值为下标，将这8个位置的二进制都设置为1（存储了一个地址）
查询时只需要用类似的方法得到相应电子邮件的8个数值，以其为下标看二进制是否都设置为了1，如果设置为了1，那么这个电子邮件就存在在这个表中。

还有一种方法是利用berkeley db来存储url，Berkeley db是一种基于key-value存储的非关系数据库引擎，能够大大提高url判重的效率。

1、给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

分析：如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import java.util.BitSet;
/**
 * 就是这个过滤器，有插入、查询等功能，可以设置位集的大小。虽然有删除功能，但是最好不要用
 * @author chouyou
 *
 */
public class bloomFilter {
    private int defaultSize = 5000 << 10000;// <<是移位运算
    /**
     * 从basic的使用来看，hashCode最后的结果会产生一个int类型的数，而这个int类型的数的范围就是0到baisc
     * 所以basic的的值为defaultsize减一
     */
    private int basic = defaultSize -1;
    private BitSet bits = new BitSet(defaultSize);//初始化一个一定大小的位集
    
    public bloomFilter(){
    }
    /**
     * 针对一个key，用8个不同的hash函数，产生8个不同的数，数的范围0到defaultSize-1
     * 以这个8个数为下标，将位集中的相应位置设置成1
     * @return
     */
    private int[] indexInSet(element ele){
        int[] indexes = new int[8];
        for (int i = 0;i<8;i++){
        	indexes[i] = hashCode(ele.getKey(),i);
        }
        return indexes;
    }
    /**
     * 添加一个元素到位集内
     */
    private void add(element ele){
        if(exist(ele)){
            System.out.println("已经包含("+ele.getKey()+")");
            return;
        }
        int keyCode[] = indexInSet(ele);
        for (int i = 0;i<8;i++){
        	bits.set(keyCode[i]);
        }
    }
    /**
     * 判断是否存在
     * @return
     */
    private boolean exist(element ele){
        int keyCode[] = indexInSet(ele);
        if(bits.get(keyCode[0])
        		&&bits.get(keyCode[1])
                &&bits.get(keyCode[2])
                &&bits.get(keyCode[3])
                &&bits.get(keyCode[4])
                &&bits.get(keyCode[5])
                &&bits.get(keyCode[6])
                &&bits.get(keyCode[7])){
            return true; 
        }
        return false;
    }
    /**
     * 要进行集合删除某个元素
     * 那么在位集中将相应的下标设置为0即可
     * 但是这样岂不是有可能会让影响到别的元素，因为多个元素公用一个下标呀
     * 那样岂不是让别的元素也不存在了么
     * 经查证，这就是bloom Filter的缺点，不能删除元素。
     * @return
     */
    private boolean deleteElement(element ele){
        if(exist(ele)){
            int keyCode[] = indexInSet(ele);
            for (int i = 0;i<8;i++){
            	bits.clear(keyCode[i]);
            }
            return true;
        }
        return false;
    }
    /**
     * Q传入不同的Q就可以得到简单的不同的hash函数
     */
    private int hashCode(String key,int Q){
        int h = 0;
        int off = 0;
        char val[] = key.toCharArray();
        int len = key.length();
        for (int i = 0; i < len; i++) {
            h = (30 + Q) * h + val[off++];
        }
        return changeInteger(h);
    }
    
    private int changeInteger(int h) {
        return basic & h;//&是位与运算符
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
    	bloomFilter f=new bloomFilter();
        element ele = new element("blog.csdn.net/zy825316");
        System.out.println("位集大小："+f.defaultSize);
        f.add(ele);
        System.out.println(f.exist(ele));
        f.deleteElement(ele);
        System.out.println(f.exist(ele));
    }
}
	/**
	 * 位集里面的每一个元素
	 * @author chouyou
	 *
	 */
	public class element {
	    private String key = null;
		public element(String key){
	        this.setKey(key);
	    }
		public String getKey() {
			return key;
		}
		public void setKey(String key) {
			this.key = key;
		}
	}

扩展：压缩布隆过滤器

由于标准Bloom Filter在f最小时，任意位为0的概率为1/2，所以，为了更好的在网络上传输Bloom Filter，可以对Bloom Filter进行压缩，能得到约69.3%

扩展：用于解决规模增长问题的过滤器

  • 拆分型布鲁姆过滤器
  • 动态布鲁姆过滤器
  • 可扩展布鲁姆过滤器
  • 多维Bloom Filter
    用多个标准布鲁姆过滤器表示多维集合的单属性域。多过滤器共同完成元素的表示及是否属于集合的查询判断

Trie树

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。如下图：

上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质：

1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符互不相同。

应用

###1、字符串检索检索
查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较：

* 如果沿路比较，发现不同的字符，则表示该字符串在集合中不存在。
* 如果所有的字符全部比较完并且全部相同，还需判断最后一个节点的标志位（标记该节点是否代表一个关键字）。

1
2
3
4
5
struct trie_node
{
bool isKey; // 标记该节点是否代表一个关键字
trie_node *children[26]; // 各个子节点
};

2、词频统计Trie树常被搜索引擎系统用于文本词频统计 。

1
2
3
4
5
struct trie_node
{
    int count;   // 记录该节点代表的单词的个数
    trie_node *children[26]; // 各个子节点 
};

思路：为了实现词频统计，我们修改了节点结构，用一个整型变量count来计数。对每一个关键字执行插入操作，若已存在，计数加1，若不存在，插入后count置1。
注意：第一、第二种应用:字符串检索和词频统计也都可以用 hash table 来做。

3、字符串排序

Trie树可以对大量字符串按字典序进行排序，思路也很简单：遍历一次所有关键字，将它们全部插入trie树，树的每个结点的所有儿子很显然地按照字母表排序，然后先序遍历输出Trie树中所有关键字即可。

4、前缀匹配

例如：找出一个字符串集合中所有以ab开头的字符串。我们只需要用所有字符串构造一个trie树，然后输出以a->b->开头的路径上的关键字即可。
trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

5、作为其他数据结构和算法的辅助结构

如后缀树，AC自动机等。

倒排索引(Inverted index)

方法介绍

倒排索引是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射，常被应用于搜索引擎和关键字查询的问题中。

以英文为例，下面是要被索引的文本：

T0 = "it is what it is"  
T1 = "what is it"  
T2 = "it is a banana"

我们就能得到下面的反向文件索引：

"a":      {2}
"banana": {2}
"is":     {0, 1, 2}
"it":     {0, 1, 2}
"what":   {0, 1}

检索的条件”what”,”is”和”it”将对应集合的交集。

正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。

问题实例

1、文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索

Contents
  1. 1. 前言
  2. 2. 分而治之的解法
  3. 3. BitMap
    1. 3.1. 问题实例
  4. 4. Bloom Fliter
    1. 4.1. 原理
    2. 4.2. 哈希函数个数的选取
    3. 4.3. 优点
    4. 4.4. 缺点
    5. 4.5. 应用
    6. 4.6. 扩展：压缩布隆过滤器
    7. 4.7. 扩展：用于解决规模增长问题的过滤器
  5. 5. Trie树
    1. 5.1. 应用
      1. 5.1.1. 2、词频统计Trie树常被搜索引擎系统用于文本词频统计 。
      2. 5.1.2. 3、字符串排序
      3. 5.1.3. 4、前缀匹配
      4. 5.1.4. 5、作为其他数据结构和算法的辅助结构
  6. 6. 倒排索引(Inverted index)
    1. 6.1. 方法介绍
    2. 6.2. 问题实例