Big Data - Fuzzy Search Url (Bloom Filter)
给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？
Bloom Filter就被广泛用于拼写检查，数据库系统中。。。可以实现数据字典，进行数据的判重，或者集合求交集
基本原理及要点
An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions with a uniform random distribution.
很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。
所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。
Bloom Filter可以用来实现数据字典，进行数据的判重，或者集合求交集.
Solution
Of course we can always use 【分治+trie树/hash+小顶堆】 standard solution, but for Fuzzy search, BF is the best.
4G = 232 大概是40亿 x 8大概是340亿bit，n = 50亿，如果按出错率0.01算需要的大概是480亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。
Find Common Elements in 2 Lists
Traditional solution: 2 pointers, Hash
Big Data: Bloom filter
Find Similar Library Books
给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？
Bloom Filter就被广泛用于拼写检查，数据库系统中。。。可以实现数据字典，进行数据的判重，或者集合求交集
基本原理及要点
An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions with a uniform random distribution.
很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。
所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。
Bloom Filter可以用来实现数据字典，进行数据的判重，或者集合求交集.
Solution
Of course we can always use 【分治+trie树/hash+小顶堆】 standard solution, but for Fuzzy search, BF is the best.
4G = 232 大概是40亿 x 8大概是340亿bit，n = 50亿，如果按出错率0.01算需要的大概是480亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。
Traditional solution: 2 pointers, Hash
Big Data: Bloom filter
Find Similar Library Books
link
有很大一个电子图书馆，里面每本书的每一页都是OCR转换出来的text，所有每页大 约有5%的error（转换错误，错误分割单词，跳脱。。。）。设计一个方法判定图书馆 里是否有完全一样的书（duplicate），或者将来有书进来时判定同样的书是否已存在。
Solution
Very large string matching, we mush use hashing or similar technique. Since books have error, we need to do fuzzy search/matching. Bloom filter is designed to do this!
有很大一个电子图书馆，里面每本书的每一页都是OCR转换出来的text，所有每页大 约有5%的error（转换错误，错误分割单词，跳脱。。。）。设计一个方法判定图书馆 里是否有完全一样的书（duplicate），或者将来有书进来时判定同样的书是否已存在。
Solution
Very large string matching, we mush use hashing or similar technique. Since books have error, we need to do fuzzy search/matching. Bloom filter is designed to do this!
