文档章节

bloom filter与dawgdic(一种trie树)

alexstocks
 alexstocks
发布于 2014/09/04 19:59
字数 1156
阅读 139
收藏 7

      我有一个做了一款移动浏览器的朋友。

      他有这样一个需求:当用户输入一个网站的url时候,移动浏览器需要识别这个网址是否是一个恶意网址。另外,他有一个恶意网址库。

      也许这样的解决方法有多种。

      其中一种就是把恶意网址库放在本地,移动浏览器拿到一个网址的时候就把它与网址库中的每个地址匹配一下,根据匹配与否来判断网址的是否为一个恶意地址。

      哦,我忘了补充的情况就是这个网址库中有150万条数据,压缩后23M,如果一个浏览器为了识别恶意网址这么一个功能而附加这么大的库,你会没有用户的。

      我刚开始给出的解决方法是bloom filter(bloom过滤器)。关于它的详细机理,吴军先生的《数学之美》中当有提及,我这里只给出一些参数值:数组大小是1500000 * 20 / 8 B(即bitset大小是数据项的20倍),hash function数目为13,误差率为万分之一。我用C++和Java分别实现了这个算法,测试后效果令人满意。数组大小只有4M多,再用zip压缩后大小只有2.8M。4G时代移动浏览器附带一个3M大小的库,个人以为是可以让人接受的。

     事情到此为止本该就此结束。朋友又有一个需求:当用户输入一个网址的前面一部分数据库的时候,浏览器要给出相关的最多十个相关网址。

     这个网址库当然就更大了,而且又要不断地更新,意味着不能放在本地。但是,每个人浏览的网站一般不会超过一百个吧,刚开始这个库可以为零,随着用户使用次数增多,统计一下缓存在本地就okay啦,这个不需要去服务器拉一大堆网址库下来。再说,真要是匹配不到也无所谓啦。

     我想到的算法是trie树。自己实现一个trie树当然是很蠢笨的事情,我去网上搜罗了一番,在stackoverflow上得到一个提示:dawgdic。它也自称是最优秀的trie树,查找速度最快,而且声称的字典库相对来说比二维数组实现的trie树还要节省空间。我在code.google.com上下载完代码后(最新代码是dawgdic-0.4.5.tar.gz,2011年),把它的example看了一遍,有如下功能:

     1 根据排列有序的数据,它可以构建出一个非常节省空间的dawg dictionary;

     2 它的dawg词典库的每一项可以只有一个key,也可以附带插入其value,即每个数据项是一个key-value对;

     3 根据构建好的词典它可以进行kv查询,即给出一个key,返回其value;

     4 如果只能给出key的一段前缀,它可以返回所有共同前缀的key,这些结果可以按照字母顺序排列后返回也可以按照value的大小排序后返回;

     5 如果只能给出key的一段后缀,它可以返回所有共同后缀的key,这些结果可以按照字母顺序排列后返回也可以按照value的大小排序后返回。

     根据以上特性,上面那个需求就稀里哗啦地解决了(^_^)。我们需要利用的特性是1、2和4。dawg字典的key当然是网址的url,其权值当然是浏览次数。由于dawg词典构建好了以后,不能进行modify,而用户对每个网址每一段时间内的浏览次数是变化的,这就需要没过一段时间内对这个dawg dictionary进行重新构建。

      其实上面只是简单地分别列举了两个算法的各自应用场景,其实这两个算法的应用范围非常广。如bloom filter就不说了,dawg树就可以用在搜索中的热搜索提示、一些英汉词典的词语搜索和输入法的个性化提示等。

      晚上吃完饭,写出此记,对自己最近一段时间的业余研究做一番总结,接着加班。

      附带声明:不经本人允许,诸如推酷“www.tuicool.com”这种垃圾抄袭网站不得转载本人的blog

© 著作权归作者所有

alexstocks

alexstocks

粉丝 21
博文 36
码字总数 38417
作品 2
海淀
私信 提问
海量数据处理的面试题

处理海量数据问题,无非就是: 分而治之/hash映射 + hash统计 + 堆/快速/归并排序; 双层桶划分 Bloom filter/Bitmap; Trie树/数据库/倒排索引; 外排序; 分布式处理之Hadoop/Mapreduce。 ...

tsmyk0715
2016/08/11
54
0
[转]海量数据处理的面试题的方法总结

处理海量数据问题,无非就是: 分而治之/hash映射 + hash统计 + 堆/快速/归并排序; Bloom filter/Bitmap; Trie树/数据库/倒排索引; 外排序; 分布式处理之hadoop/mapreduce。 本文接下来的...

十一11
2016/03/11
217
0
海量数据,数据挖掘,数据存储方法

现在对网络服务来讲,用户量是非常大的,用户信息或者其他数据也是非常巨大的,如何对海量数据进行存储,进行挖掘,进行筛选等问题,对服务器的响应效率来讲影响很大,关键要设计出良好的数据...

晨曦之光
2012/04/13
162
1
如何实现大数据集查询?Bloom Filter或许是你想要的

1、什么情况下需要布隆过滤器? 先来看几个比较常见的例子 字处理软件中,需要检查一个英语单词是否拼写正确 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上 在网络爬虫里,一个网址是否被访...

流川枫AI
2017/06/18
0
0
99%海量数据处理

http://blog.csdn.net/vjulyv/article/details/7382693 前言 一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,...

tantexian
2018/01/15
43
0

没有更多内容

加载失败,请刷新页面

加载更多

链表中环的入口节点

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。 思路: public ListNode EntryNodeOfLoop(ListNode pHead) { if (pHead == null || pHead.next == null) ...

Garphy
10分钟前
2
0
Spring5 源码分析-容器刷新-invokeBeanFactoryPostProcessors()方法

上一篇:Spring5 源码分析-容器刷新-prepareBeanFactory()方法 该方法主要完成以下功能: 1.实例化ConfigurationClassPostProcessor,并调用ConfigurationClassPostProcessor.postProcessBe...

特拉仔
10分钟前
3
0
为什么MySQL用B+树做索引

索引这个词,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述的很完整。本文就来从头到尾介绍下数据库的索引。...

小致Daddy
35分钟前
4
0
网站前台的三级联动数据封装

我在进行项目时候遇到了一个进行数据封装的一个功能,进行数据的封装的功能也挺复杂,来回试了好几十种方法.最后使用的是这种方法. 使用一个pojo进行封装两个数据,一个是list一个是实体类. 具体...

小天丶羽
38分钟前
4
0
创龙基于TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA的SPI FLASH、硬件加密芯片

TL437xF-EVM是一款广州创龙基于TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA设计的开发板,底板采用沉金无铅工艺的4层板设计,尺寸为240mm*130mm,它为用户提供了SOM-TL437xF核心板的测...

Tronlong创龙
40分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部