通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单,我们来做个测试,就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下:

            String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;
            String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;

            long t1 = System.currentTimeMillis();

            for (int i = 0; i < 1000000; i++) {
                   int dis = StringUtils .getLevenshteinDistance(s1, s2);
            }

            long t2 = System.currentTimeMillis();

            System. out .println(" 耗费时间: " + (t2 - t1) + "  ms ");

耗费时间: 4266 ms

大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:

  • 1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。

  • 2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。

  • 3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。

  • 4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。

  • 5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。

整个过程图为:

simhash计算过程图

大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

通过simhash计算结果为:

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的

现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 1010100110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。

未完待续:

1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?

2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?

simhash_hammingdistance

参考:
Detecting near-duplicates for web crawling.

Similarity estimation techniques from rounding algorithms.

http://en.wikipedia.org/wiki/Locality_sensitive_hashing

http://en.wikipedia.org/wiki/Hamming_distance

simHash 简介以及 java 实现

simhash原理推导

原创文章,转载请注明: 转载自LANCEYAN.COM

本文链接地址: 海量数据相似度计算之simhash和海明距离

上一篇文章《社会化海量数据采集框架搭建》提到如何搭建一个社会化采集系统架构,讲架构一般都比较虚,这一篇讲一下如何实战用低成本服务器做到日流水千万级数据的分布式采集系统。

有这样一个采集系统的需求,达成指标: 需要采集30万关键词的数据 、微博必须在一个小时采集到、覆盖四大微博(新浪微博、腾讯微博、网易微博、搜狐微博)。为了节约客户成本,硬件为普通服务器:E5200 双核 2.5G cpu, 4 G DDR3 1333内存,硬盘 500G SATA 7200转硬盘。数据库为mysql。在这样的条件下我们能否实现这个系统目标?当然如果有更好的硬件不是这个文章阐述的内容。现通过采集、存储来说明一下如何实现:

一、采集,目标是在一个小时内把30万关键词对应的数据从四大微博采集下来,能够使用的机器配置就是上面配置的普通服务器。采集服务器对硬盘没有太多要求,属于cpu密集型运算,需耗费一些内存。评估下来硬件资源不是瓶颈,看下获取数据的接口有什么问题?

  • 1、通过各大微博的搜索api。就比如新浪微博API针对一个服务器IP的请求次数,普通权限限制是一个小时1w次,最高权限合作授权一个小时4w次。使用应用时还需要有足够的用户,单用户每个应用每小时访问1000次,最高权限4w次需要40个用户使用你的应用。达到30w关键词,至少需要8个应用,如果每个关键词需要访问3页,总共需要24个合作权限的应用。实际操作我们是不可能为这个项目做到开发24个合作权限的应用,所以这个方式不是很合适。新浪微博API限制参考链接

  • 2、通过各大微博的最新微博收集数据,微博刚推出的时候,各大微博都有微博广场,可以把最新的微博都收集下来,然后通过分词,如果出现了30万关键词中的一个就留下,其他就丢弃掉。不过现在除了腾讯微博和搜狐微博有微博广场类似的功能,新浪微博和网易微博已经没有这项功能了。另按照新浪微博之前公布的数据,注册用户已经超过5亿,每小时超过1亿条微博,如果全量采集对数据存储是个大的考验,也需要大量的系统资源,实际采集了一亿条,也许就1000w条有用,浪费了9000w条数据的资源。

  • 3、通过各大微博的网页搜索,可见即可抓的方式,结合反监控系统模块模拟人的正常行为操作,搜索30万关键词数据,使资源最大化利用。为了保证在一个小时采集到,需要采用分布式多线程模式抓取,并发采集。并发的时候不能从同一个ip或者同一个ip网段出去,保证对方不会监测到我们的爬虫。

我们最后采用了第三种方式,目前运行状况为通过30w关键词搜索得到的所有微博加在一起总量1000多w条每天,新浪和腾讯最多,新浪微博略胜一筹。使用了6台普通PC服务器,就算一台机器7000元,总共4万元硬件设备解决采集硬件问题。整体部署图为:

海量采集系统部署图

二、存储,采集下来的数据如何处理?首先存储采集数据是个密集写的操作,普通硬盘是否能够支持,mysql数据库软件能否支持,未来量突然增加如何应对?再就是评估存储空间,每天增量这么多需要耗费大量的存储资源,如何存放并且易扩展。

  • 1、如何存储。正常来说我们上面配置的服务器,mysql使用myisam引擎一张表最多20w,使用innodb引擎最多400w,如果超过这个数量,查询更新速度奇慢。这里我们采用一个比较取巧的做法,使用mysql的innodb存储引擎做了一层缓存库,这个缓存库有两个缓存表,每个表只存储少于300w的数据,有一张表多于300w的数据就切换到另一张表插入直到超过300w再切换回去。切换成功后,把多于300w数据的表truncate掉,记得一定要没有数据插入的时候再truncate,防止数据丢失。这里一定要用truncate,不能使用delete,因为delete需要查询,要用到索引读写,并且delete还会写数据库log耗费磁盘IO,存储空间也没有释放。truncate和drop是操作数据库删除数据比较好的做法。由于有两个表作为数据插入表,使用数据库表的自增id并不太合适,需要一个高速的唯一自增Id服务器提供生成分布式ID。另数据库完全可以关闭写事务日志 ,提高性能,因为抓取的数据当时丢失再启动抓取就可以了, 这样数据库可以保持在一个比较高性能的情况完成插入操作。抓取缓存表结果如图:

  • 抓取缓存表结构图

  • 2、存储空间。插入后的数据需要保存下来,不能在超过300w后被truncate掉了。我们需要有个程序在达到300万时被truncate掉之前把数据同步走,存放到另外一个库上(我们叫做结果库,结果库也是使用innodb引擎)。不过我们每天采集的数据1000多万,按天递增,mysql一张表一天就撑爆了,我们这个表不是写操作密集型,所以结果库可以存储多点数据,设定上限500w,但是500万还是存不下1000万数据。我们需要对mysql最终结果分库分表。将数据先按照时间分机器分库,再按照数据源分表,比如201301通过hash计算的数据存放在一个机器,201302通过hash计算在另一个机器。到了机器后再按照天或者半天分表,比如表名为 weibo_2013020101 、weibo_2013020112。weibo_2013020101表示2月1日上午一个表,weibo_2013020112表示2月1日下午一个表。光这样分了还是不够,1000w/2=500w,经不起压力扩展。我们还需要把表再拆分,比如weibo_2013020101 拆成 weibo_2013020101_1(新浪微博)、weibo_2013020101_2(腾讯微博)、weibo_2013020101_3(网易微博)、weibo_2013020101_4(搜狐微博)。这样一张表平均就存放 500w/4 = 125w 条数据,远远小于500w上限,还可以应对未来突发的增长。再从存储空间来算,就算一条微博数据为1k,一天 1000w*1k=10G,硬盘500G最多存放50天的数据,所以我们规划机器的时候可以挂接多一点硬盘,或者增加机器。结果库分表如图:

  • 分库分表结构图

按照这样的架构,我们使用开源免费软件、低成本服务器搭建的千万级数据采集系统在生产运转良好。

原创文章,转载请注明: 转载自LANCEYAN.COM

本文链接地址: 实战低成本服务器搭建千万级数据采集系统

随着BIG DATA大数据概念逐渐升温,如何搭建一个能够采集海量数据的架构体系摆在大家眼前。如何能够做到所见即所得的无阻拦式采集、如何快速把不规则页面结构化并存储、如何满足越来越多的数据采集还要在有限时间内采集。这篇文章结合我们自身项目经验谈一下。

我们来看一下作为人是怎么获取网页数据的呢?

1、打开浏览器,输入网址url访问页面内容。
2、复制页面内容的标题、作者、内容。
3、存储到文本文件或者excel。

从技术角度来说整个过程主要为 网络访问、扣取结构化数据、存储。我们看一下用java程序如何来实现这一过程。

import java.io.IOException;
import org.apache.commons.httpclient.HttpClient;
import org.apache.commons.httpclient.HttpException;
import org.apache.commons.httpclient.HttpStatus;
import org.apache.commons.httpclient.methods.GetMethod;
import org.apache.commons.lang.StringUtils;

public class HttpCrawler {
       public static void main(String[] args) {

            String content = null ;
             try {
                  HttpClient httpClient = new HttpClient();
                   //1、网络请求
                  GetMethod method = new GetMethod("http://www.baidu.com" );
                   int statusCode = httpClient.executeMethod(method);
                   if (statusCode == HttpStatus. SC_OK) {
                        content = method.getResponseBodyAsString();
                         //结构化扣取
                        String title = StringUtils.substringBetween(content, "<title>" , "</title>" );
                         //存储
                        System. out .println(title);
                  }

            } catch (HttpException e) {
                  e.printStackTrace();
            } catch (IOException e) {
                  e.printStackTrace();
            } finally {
            }
      }
}

通过这个例子,我们看到通过httpclient获取数据,通过字符串操作扣取标题内容,然后通过system.out输出内容。大家是不是感觉做一个爬虫也还是蛮简单呢。这是一个基本的入门例子,我们再详细介绍怎么一步一步构建一个分布式的适用于海量数据采集的爬虫框架。

整个框架应该包含以下部分,资源管理、反监控管理、抓取管理、监控管理。看一下整个框架的架构图:

社会化海量数据抓取组件图

  • 资源管理指网站分类体系、网站、网站访问url等基本资源的管理维护;
  • 反监控管理指被访问网站(特别是社会化媒体)会禁止爬虫访问,怎么让他们不能监控到我们的访问时爬虫软件,这就是反监控机制了;

  • 一个好的采集框架,不管我们的目标数据在哪儿,只要用户能够看到都应该能采集到。所见即所得的无阻拦式采集,无论是否需要登录的数据都能够顺利采集。现在大部分社交网站都需要登录,为了应对登录的网站要有模拟用户登录的爬虫系统,才能正常获取数据。不过社会化网站都希望自己形成一个闭环,不愿意把数据放到站外,这种系统也不会像新闻等内容那么开放的让人获取。这些社会化网站大部分会采取一些限制防止机器人爬虫系统爬取数据,一般一个账号爬取不了多久就会被检测出来被禁止访问了。那是不是我们就不能爬取这些网站的数据呢?肯定不是这样的,只要社会化网站不关闭网页访问,正常人能够访问的数据,我们也能访问。说到底就是模拟人的正常行为操作,专业一点叫“反监控”。

    那一般网站会有什么限制呢?

    一定时间内单IP访问次数,没有哪个人会在一段持续时间内过快访问,除非是随意的点着玩,持续时间也不会太长。可以采用大量不规则代理IP来模拟。

    一定时间内单账号访问次数,这个同上,正常人不会这么操作。可以采用大量行为正常的账号,行为正常就是普通人怎么在社交网站上操作,如果一个人一天24小时都在访问一个数据接口那就有可能是机器人了。

    如果能把账号和IP的访问策略控制好了,基本可以解决这个问题了。当然对方网站也会有运维会调整策略,说到底这是一个战争,躲在电脑屏幕后的敌我双方,爬虫必须要能感知到对方的反监控策略进行了调整,通知管理员及时处理。未来比较理想应该是通过机器学习算法自动完成策略调整,保证抓取不间断。

  • 抓取管理指通过url,结合资源、反监控抓取数据并存储;我们现在大部分爬虫系统,很多都需要自己设定正则表达式,或者使用htmlparser、jsoup等软件来硬编码解决结构化抓取的问题。不过大家在做爬虫也会发现,如果爬取一个网站就去开发一个类,在规模小的时候还可以接受,如果需要抓取的网站成千上万,那我们不是要开发成百上千的类。为此我们开发了一个通用的抓取类,可以通过参数驱动内部逻辑调度。比如我们在参数里指定抓取新浪微博,抓取机器就会调度新浪微博网页扣取规则抓取节点数据,调用存储规则存储数据,不管什么类型最后都调用同一个类来处理。对于我们用户只需要设置抓取规则,相应的后续处理就交给抓取平台了。

  • 整个抓取使用了 xpath、正则表达式、消息中间件、多线程调度框架(参考)。xpath 是一种结构化网页元素选择器,支持列表和单节点数据获取,他的好处可以支持规整网页数据抓取。我们使用的是google插件 XPath Helper,这个玩意可以支持在网页点击元素生成xpath,就省去了自己去查找xpath的功夫,也便于未来做到所点即所得的功能。正则表达式补充xpath抓取不到的数据,还可以过滤一些特殊字符。消息中间件,起到抓取任务中间转发的目的,避免抓取和各个需求方耦合。比如各个业务系统都可能抓取数据,只需要向消息中间件发送一个抓取指令,抓取平台抓完了会返回一条消息给消息中间件,业务系统在从消息中间件收到消息反馈,整个抓取完成。多线程调度框架之前提到过,我们的抓取平台不可能在同一时刻只抓一个消息的任务;也不可能无限制抓取,这样资源会耗尽,导致恶性循环。这就需要使用多线程调度框架来调度多线程任务并行抓取,并且任务的数量,保证资源的消耗正常。

    不管怎么模拟总还是会有异常的,这就需要有个异常处理模块,有些网站访问一段时间需要输入验证码,如果不处理后续永远返回不了正确数据。我们需要有机制能够处理像验证码这类异常,简单就是有验证码了人为去输入,高级一些可以破解验证码识别算法实现自动输入验证码的目的。

    扩展一下 :所见即所得我们是不是真的做到?规则配置也是个重复的大任务?重复网页如何不抓取?

    1、有些网站利用js生成网页内容,直接查看源代码是一堆js。 可以使用mozilla、webkit等可以解析浏览器的工具包解析js、ajax,不过速度会有点慢。
    2、网页里有一些css隐藏的文字。使用工具包把css隐藏文字去掉。
    3、图片flash信息。 如果是图片中文字识别,这个比较好处理,能够使用ocr识别文字就行,如果是flash目前只能存储整个url。
    4、一个网页有多个网页结构。如果只有一套抓取规则肯定不行的,需要多个规则配合抓取。
    5、html不完整,不完整就不能按照正常模式去扣取。这个时候用xpath肯定解析不了,我们可以先用htmlcleaner清洗网页后再解析。
    6、 如果网站多起来,规则配置这个工作量也会非常大。如何帮助系统快速生成规则呢?首先可以配置规则可以通过可视化配置,比如用户在看到的网页想对它抓取数据,只需要拉开插件点击需要的地方,规则就自动生成好了。另在量比较大的时候可视化还是不够的,可以先将类型相同的网站归类,再通过抓取的一些内容聚类,可以统计学、可视化抓取把内容扣取出几个版本给用户去纠正,最后确认的规则就是新网站的规则。这些算法后续再讲。这块再补充一下(多谢zicjin建议)

    背景:如果我们需要抓取的网站很多,那如果靠可视化配置需要耗费大量的人力,这是个成本。并且这个交给不懂html的业务去配置准确性值得考量,所以最后还是需要技术做很多事情。那我们能否通过技术手段可以帮助生成规则减少人力成本,或者帮助不懂技术的业务准确的把数据扣取下来并大量复制。

    方案:先对网站分类,比如分为新闻、论坛、视频等,这一类网站的网页结构是类似的。在业务打开需要扣取的还没有录入我们规则库的网页时,他先设定这个页面的分类(当然这个也可以机器预先判断,他们来选择,这一步必须要人判断下),有了分类后,我们会通过“统计学、可视化判断”识别这一分类的字段规则,但是这个是机器识别的规则,可能不准确,机器识别完后,还需要人在判断一下。判断完成后,最后形成规则才是新网站的规则

    7、对付重复的网页,如果重复抓取会浪费资源,如果不抓需要一个海量的去重判断缓存。判断抓不抓,抓了后存不存,并且这个缓存需要快速读写。常见的做法有bloomfilter、相似度聚合、分类海明距离判断。

  • 监控管理指不管什么系统都可能出问题,如果对方服务器宕机、网页改版、更换地址等我们需要第一时间知道,这时监控系统就起到出现了问题及时发现并通知联系人。

目前这样的框架搭建起来基本可以解决大量的抓取需求了。通过界面可以管理资源、反监控规则、网页扣取规则、消息中间件状态、数据监控图表,并且可以通过后台调整资源分配并能动态更新保证抓取不断电。不过如果一个任务的处理特别大,可能需要抓取24个小时或者几天。比如我们要抓取一条微博的转发,这个转发是30w,那如果每页线性去抓取耗时肯定是非常慢了,如果能把这30w拆分很多小任务,那我们的并行计算能力就会提高很多。不得不提的就是把大型的抓取任务hadoop化,废话不说直接上图:

社会化海量数据抓取组件图

今天先写到这里,后续再介绍下 日均千万大型采集项目实战。

原创文章,转载请注明: 转载自LANCEYAN.COM

本文链接地址: 社会化海量数据采集爬虫框架搭建