分类

类型:
不限 游戏开发 计算机程序开发 Android开发 网站开发 笔记总结 其他
评分:
不限 10 9 8 7 6 5 4 3 2 1
原创:
不限
年份:
不限 2018 2019

技术文章列表

  • 机器学习 18、聚类算法-Kmeans

    前文链接:https://write-bug.com/article/2530.html
    上节 我们暂时实现了一下单机版推荐系统,并且串了下知识,这节介绍下聚类,说起聚类就得先提下监督和非监督式学习:

    监督式学习:我们之前学习的分类、回归问题中的排序模型LR、Softmax,包括后面的dnn,dt等等都是需要数据事先有一个标签label作为新特征的分类
    非监督式学习:而这个有些类似之前的推荐算法,并没有特定的类别作为比对

    而今天学习的算法聚类算法也是非监督式学习。
    聚类是什么?之前对于文本分类来说,需要事先设定好类别标签对新文本进行概率分类、对label对比,而这里的聚类则可以既不需要设定类别,也不需要事先设定文本中心,其可自动将数据划分到不同的类中,使相似的数据划分到相同的类中,这种方法可应用到几乎所有分类中,用户聚类、商品聚类、生物特征、基因、图像聚类等等分类。
    比如说,随机系统中有10000篇文章,我只告诉系统分为多少个类,其他什么都不告诉,这个系统就可以自动操作完成。
    事实上,就是对特征的向量化及空间划分。
    向量化如果想对一个文章、物品等作聚类,那聚类之前,如何表示文章呢?
    向量
    比如之前的tfidf,用一个向量来表示物品之后作cos、内积、计算质心等等
    质心:各个向量的点构成的空间的中心,即每个点到这个点的最短平均距离
    A:(a1, a2, a3)B:(b1, b2, b3)C:(c1, c2, c3)质心=( (a1+b1+c1)/3, (a2+b2+c2/3, (a3+b3+c3)/3)距离矩阵、相似度矩阵
    此矩阵就像之前的推荐算法中的矩阵,各个pair相似度的矩阵
    评估如何评估聚类效果?
    内部方法
    同类尽可能相似,不同类尽可能不相似

    分子为对象到质心距离和,越小越好
    分母为质心距离,越大越好
    外部方法(准确P、召回R)
    之前利用pr曲线找到最好的分类面,但是需要有监督的情况下才能用,这里如果想用,在特定情况下,比如说文章有固定标签,用这种方法训练后再告诉label评估效果,但是工作中几乎遇到的都是无标签的,所以这种方法是很鸡肋的方法,工作中基本用内部方法解决。
    F=PR /(P+R)聚类类别层次聚类


    自底向上凝聚聚类,从不同的对象凝聚结果形成聚合节点,成树状
    自顶向下分裂聚类,从一个对象分裂结果形成分裂节点,成树状

    优点:

    可通过阈值灵活控制类个数
    层次用于概念聚类,分类后人工对其打标签,抽象概念。

    凝聚实现:

    将每个对象样本分为一类,得到N个类
    找到最接近的两个类合并为一个类:两层for循环遍历所有样本,计算cos相似度
    重新计算新类与旧类之间距离:类别之间距离和类别与对象之间距离的计算方式一般使用组合链的方式进行计算:即类中质心距离(平均距离),而与之相对的有单链(最近距离)和全链(最远距离)两种方式,一般工作中就直接使用组合链方式
    重复直到最后合并为一个类
    复杂度O(n^3)

    非层次聚类:Kmeans
    层次聚类是一种需要将向量两两比较聚类的方法,但这种方法的计算时间过长,影响效率,而Kmeans是随机选择对象作为类别中心,然后优化这些中心点的位置,使尽可能收敛到和真实中心一致的算法。
    步骤:

    任意选择K个点作为初始聚类中心 (初始化类个数)
    根据每个聚类的中心,计算每个对象与这些中心的距离(cos、欧式距离),并根据 最小距离重新对相应对象进行划分

    欧式距离:A:(a1, a2, a3) B:(b1, b2, b3)距离=sqrt((a1-b1)^2 + (a2-b2)^2 + (a3-b3)^2 )
    重新计算每个聚类的中心 (更新质心计算)
    当满足一定条件,如类别划分不再发生变化时,算法终止,否则 继续步骤2和3
    复杂度:O(Ktn^2)K个点,n个对象,t次循环,n次计算质心

    之前介绍时为什么说是向量化并分割空间,下面这个图每个点都是空间中的向量点,把两个中心点相连,中心分割的垂线就是分割面,再迭代更新质心位置,从而分割空间


    一定条件:

    轮数
    WCSS损失函数:最小化簇内对象到质心的距离平方和

    wcss变小,即空间变化不剧烈

    缺点:过于依赖初始点选择,可能导致的结果大不一样
    解决方法:只能多训练几轮,求质心平均值或者选择最小的wcss的模型。
    模型:最终计算结果的K个中心点向量
    K选择,业务场景:
    举例:半个性化推荐,即热榜推荐列表只有一部分是个性化对用户的推荐(如视频网站首页上半部),但是当用户上亿,但热榜或首页展示目录只有10个,候选集合只有100个的时候怎么办?如何给大量的用户也做一个模糊的推荐?如何在100个候选集合中选择10个作为推荐列表?
    对上亿用户作聚类,可以随意聚几千个类,再用这几千个类的向量和每个物品向量作cos,选出分数前10的物品向量作为此用户类的候选集合。
    用户向量化:利用历史行为作用户画像:token作向量
    层次 vs Kmeans

    从上面两张图,我们可以看到右面Kmeans算法的暴力分割和缺点,在生活中的数据大部分都是球面原始数据,也是Kmeans的强项,左面的那种长条数据只能用层次聚类分辨出来,而与此同时左面五颜六色的单点都是噪音数据,前面说过层次聚类非常耗时,并且我们事先并不知道数据的分布,所以部分解决办法就是增加K类个数。
    Kmeans粒度比较粗,层次粒度比较细。
    聚类这种发现规律的分类效果永远无法赶上分类回归那种有监督式的效果,即有老师无老师的区别。如果效果不好,可以适当增加K个数增加准确率。
    0 留言 2019-05-29 15:55:53 奖励16点积分
  • 【Cocos Creator实战教程(3)】——TiledMap(瓦片地图)组件 精华

    1. 前言瓦片地图是由一张一张的正方形小图片拼接成的地图,例如炸弹人,QQ堂都是非常典型的瓦片游戏。瓦片地图(Tile Map) 不但生成简单,并且可以灵活的用于Cocos2d-x引擎。不论你的游戏是角色扮演游戏, 平台动作游戏或仿打砖块游戏,这些游戏地图可以使用开源的瓦片地图编辑器Tiled Map Editor生成并保存为TMX文件格式,被Cocos2d-x支持。
    2. 步骤2.1 安装Tiled Map Editoredit(编辑)->preferences(参数)里面可以设置语言
    2.2 TiledMap制作新建一张地图

    建立三个图层和一个对象层并将资源图块导入 (最下面的图层将显示在最下面)



    ground层:用ground图块填充满(按住鼠标左键)
    barriers层:用barrier图块
    stars层:用star图块

    最终效果如下图

    选择players对象层,在如图位置插入两个图块对象,并更改名称如图

    给星星添加一个属性

    保存为tmx文件,和图片文件放在一起
    2.3 Cocos Creator中使用TiledMap:
    新建一个TiledMapTest工程,创建一个Game场景
    将刚才生成的tmx文件和相关图片一起添加到工程
    将map.tmx文件拖入层级管理器或者属性编辑器,就会自动生成map节点以及其子节点(也就是图层节点)【没有对象层节点】
    最后将player(安卓小机器人)图片拖入(位置随意),创建player节点,并使其为map节点的子节点。
    调整map和player节点的锚点都为(0,0)也就是左下角
    创建map.js脚本添加到map节点

    cc.Class({ extends: cc.Component, properties: { }, // use this for initialization onLoad: function () { this.player = this.node.getChildByName('player'); this.loadMap(); cc.systemEvent.on(cc.SystemEvent.EventType.KEY_DOWN, this.onKeyDown, this); }, onKeyDown:function(event){ var newTile = cc.p(this.playerTile.x, this.playerTile.y); switch(event.keyCode) { case cc.KEY.up: newTile.y -= 1; break; case cc.KEY.down: newTile.y += 1; break; case cc.KEY.left: newTile.x -= 1; break; case cc.KEY.right: newTile.x += 1; break; default: return; } this.tryMoveToNewTile(newTile); }, //加载地图文件时调用 loadMap: function () { //初始化地图位置 this.node.setPosition(cc.visibleRect.bottomLeft); //地图 this.tiledMap = this.node.getComponent(cc.TiledMap); //players对象层 let players = this.tiledMap.getObjectGroup('players'); //startPoint和endPoint对象 let startPoint = players.getObject('startPoint'); let endPoint = players.getObject('endPoint'); //像素坐标 let startPos = cc.p(startPoint.offset.x, startPoint.offset.y); let endPos = cc.p(endPoint.offset.x, endPoint.offset.y); //障碍物图层和星星图层 this.barriers = this.tiledMap.getLayer('barriers'); this.stars = this.tiledMap.getLayer('stars'); //出生Tile和结束Tile this.playerTile = this.startTile = this.getTilePos(startPos); this.endTile = this.getTilePos(endPos); //更新player位置 this.updatePlayerPos(); }, tryMoveToNewTile: function(newTile) { let width = this.tiledMap.node.width; let height = this.tiledMap.node.height; if (newTile.x < 0 || newTile.x >= width) return; if (newTile.y < 0 || newTile.y >= height) return; if (this.barriers.getTileGIDAt(newTile)) {//GID=0,则该Tile为空 cc.log('This way is blocked!'); return false; } this.tryCatchStar(newTile); this.playerTile = newTile; this.updatePlayerPos(); if (cc.pointEqualToPoint(this.playerTile, this.endTile)) { cc.log('succeed'); } }, tryCatchStar: function(newTile){ let GID = this.stars.getTileGIDAt(newTile); let prop = this.tiledMap.getPropertiesForGID(GID); if (this.stars.getTileGIDAt(newTile)) {//GID=0,则该Tile为空 this.stars.removeTileAt(newTile); } }, //将像素坐标转化为瓦片坐标 getTilePos: function(posInPixel) { let mapSize = this.node.getContentSize(); let tileSize = this.tiledMap.getTileSize(); let x = Math.floor(posInPixel.x / tileSize.width); let y = Math.floor(posInPixel.y / tileSize.height); return cc.p(x, y); }, updatePlayerPos: function() { let pos = this.barriers.getPositionAt(this.playerTile); this.player.setPosition(pos); },});
    最终如下图:

    3. 总结#CC.TiledMap:~properties:tmxFile//地图文件mapLoaded//地图加载是调用的函数~function:getMapSize()//setMapSize()//getTileSize()//setTileSize()//getLayer(name)//returns TieldLayergetObjectGroup(name)//returns TMXObjectGroupgetPropertiesForGID(GID)//returns Object(属性字典)#CC.TieldLayer getPositionAt(pos)//returns Vec2(像素坐标) 参数是瓦片坐标removeTileAt(pos)//瓦片坐标getTileGIDAt(pos)//returns Number(全局唯一标识,0为空)getTileAt(pos)//returns _ccsg.Sprite //removeChild(sprite);setTileGID(gid,pos)//相当于在pos位置添加GID的图块(原来的图块删除)getTileSize()//setTleSize()//getMapTileSize()#TMXObjectGroup:~properties:~function:var getObject(var objectName)//返回属性字典#_ccsg.Sprite://cocos js 里的Sprite,继承自CC.Node,而不是组件~properties:xywidthheightopacity...//节点的属性都有~function:var setSpriteFrame(var spriteFrameName)var runAction(var action) ...//节点的方法都有

    图块放置的位置是基于像素坐标,而图块在map中的索引是基于瓦片坐标(整数),所以在脚本文件中要适时转变
    对象层的对象(比如我们上面做的两个player point),在Cocos Creator中是不会显示的
    对象层记录的是位置信息,图层记录的是图片信息
    .tmx文件其实保存的图块的一种映射关系,所以图块文件和地图文件要始终放在一起,不然可能会显示出错
    GID是图块在一个地图文件中的唯一ID,(图块指的是右下角的图块文件,每一个图块都不相同,瓦片指的指地图中的块,可以是相同的图块),GID为0说明该Tile的图块为空
    当利用getPropertiesForGID(GID)之类的方法时,得到的返回值是属性字典,可以直接通过点方法得到其属性值,属性值都是字符串类型
    当用到getTileAt(pos)时,得到的返回值是Cocos2d 的Sprite,而不是Cocos Creator的Sprite,相关方法可以查找Cocos2d js的API,需要注意的一点是,Cocos2d的Sprite是继承自节点的,而不是组件式,所以我们可以直接这样写“mySprite.x = 100”而不是“mySprite.node.x = 100”
    地图中同一层只能使用一张图集里的图块

    注意:本教程资源部分来源于网络
    2 留言 2018-11-24 18:06:17 奖励15点积分
  • 计算机视觉现代优化方法

    1. 概述本次实验中,我基于OpenCV,实现了一个二维图像配准工具,全部代码均为自行实现,OpenCV用于计算图像变换与相似度。
    该工具能够将一幅图像进行变换,并与另一幅图像相匹配。支持包括平移、旋转(含平移、缩放)、仿射与透视共四种变换,使用L1、L2、无穷范数作为优化的目标函数,实现了暴力算法、梯度下降法、模拟退火算法来求解该优化问题。
    2. 应用问题如果两幅图像,它们是在同一场景、不同角度下拍摄的,那么,存在一种图像变换,使得其中一幅图像经过变换后,能与另一图像大部分重合。
    上述图像变换被称为配准(registration)T,被变换的图像被称为参考图像I_M,另一图像被称为目标图像I_F。优化的目标是使变换后的参考图像T(I_M)与目标图像I_F的差异尽可能低。
    最简单的图像变换是平移变换,需要确定两个参数: x和 y; 旋转变换通常与缩放、平移共同进行,需要确定四个参数: x、y、theta、scale; 仿射变换将矩形图像线性映射至一个平行四边形,需要确定三个坐标点,共六个参数,三个坐标点分别表示原图左上、右上、左下角变换至新图像的坐标位置; 透视变换与仿射变换相似,不同的是原图像的四个顶点可变换至任意的四边形,所以需要确定四个坐标点,共八个参数。此外,也有更为精细的图像变换方法,但相比于上述简单变换,其参数较多,难以优化,故本次实验不予考虑。
    对于图像相似度,需针对使用场景选择合适的度量方法。本实验中,实现的方法有L1(1范数)、L2(2范数)、无穷范数三种。
    总的来说,问题可以总结为如下步骤:

    输入参考图像、目标图像;
    选择合适的变换,确定参数范围;
    设置初始参数,在这个参数下变换参考图像,并计算与目标图像的差异;
    调整参数,使上述差异达到最小值;
    输出最优参数作为配准变换。

    3. 数据来源本实验使用在实验室拍摄的四张照片作为测试数据。














    4. 实现算法4.1 软件界面本实验搭建了一个二维图像配准工具。”主界面”可进行配准的各项设置,并展示参考图像与目标图像:

    “结果界面”会在运行配准之后弹出,分左中右三栏,分别为变换后的参考图像、变换后的参考图像与目标图像的对比(会交替显示两图像)、目标函数优化曲线:

    4.2 优化算法在上述基础上实现了三种优化算法,分别是暴力算法、梯度下降法、模拟退火算法。执行算法前,首先会在Registration::initialize()函数中针对不同变换方式,初始化变换的各项参数,例如旋转变换(四个参数):
    params.resize(4); // cx cy angle scalelimits.resize(4);steps.resize(4);limits[0] = std::make_pair(-c / 2, c / 2);limits[1] = std::make_pair(-r / 2, r / 2);limits[2] = std::make_pair(-180, 180);limits[3] = std::make_pair(0.5, 2);for (int i = 0; i < params.size(); i++) { params[i] = limits[i].first;}steps[0] = 1;steps[1] = 1;steps[2] = 1;steps[3] = 0.01;
    其中params表示参数数组,limits表示各个参数的取值范围,steps表示各个参数邻域的步长。
    暴力算法使用深度优先搜索遍历整个可行解空间,可求解出全局的最优解:
    void Registration::optimizeNaive(int pos) { if (pos >= params.size()) { completeIteration(); return; } for (float i = limits[pos].first; i <= limits[pos].second; i += steps[pos]) { params[pos] = i; optimizeNaive(pos + 1); }}
    梯度下降法在每轮迭代中,寻找当前最优解的邻域中最优的可行解,并以此代替最优解,直到邻域中没有比当前解更好的解为止。我实现的函数中,某个可行解的邻域定义为将第i个参数增加或减少steps[i]得到的可行解的集合(i为某个随机参数的序号)。因梯度下降法与初始值选取密切相关,选择不当会导致陷入局部最优解,我在函数中增加了一个外循环,每轮循环随机选择一组初始值,并开始一轮新的梯度下降:
    void Registration::optimizeGD() { for (int i = 0; i < 10000; i++) { double tmp_loss = 1e30; double cur_loss = 1e30; for (int j = 0; j < params.size(); j++) { // give random start values params[j] = random(limits[j].first, limits[j].second); } while (true) { std::vector<float> old = params; std::vector<float> best = params; for (int pos = 0; pos < params.size(); pos++) { params[pos] = old[pos] + steps[pos]; optimizeGDHelper(best, cur_loss); params[pos] = old[pos] - steps[pos]; optimizeGDHelper(best, cur_loss); params[pos] = old[pos]; } if (tmp_loss == cur_loss) { break; } tmp_loss = cur_loss; params = best; completeIteration(); } completeIteration(); }}void Registration::optimizeGDHelper(std::vector<float>& best, double& cur_loss) { applyTransform(); double s = getSimilarity(trans_img, tar_img, similarity_type); if (s < cur_loss) { cur_loss = s; best = params; }}
    模拟退火算法与梯度下降法相比,具有跳出局部最优解的能力。当温度较低时,算法不容易跳出局部最优解,从而退化为梯度下降法。所以,如果在温度下降到很低时没能跳入最优解附近,算法同样会收敛于局部最优解。因此,与上述梯度下降法的代码类似,我也使用了一层外循环,用于生成多个随机初始参数:
    void Registration::optimizeSA() { for (int i = 0; i < 10000; i++) { for (int j = 0; j < params.size(); j++) { // give random start values params[j] = random(limits[j].first, limits[j].second); } applyTransform(); double fi = getSimilarity(trans_img, tar_img, similarity_type); double temp = 10; double r = 0.99; int k = 1000; while (k > 0) { // select a random neighbor int len = params.size(); int r1 = rand() % len; double r2 = random(1, 10) * ((rand() % 2) * 2 - 1); params[r1] += r2 * steps[r1]; applyTransform(); double fj = getSimilarity(trans_img, tar_img, similarity_type); double delta = fj - fi; if (random(0, 1) < exp(-delta / temp)) { // jump to this neighbor completeIteration(iter % 10 == 0); fi = fj; } else { params[r1] -= r2 * steps[r1]; } temp *= r; k--; } completeIteration(); }}
    4.3 实现细节
    计算图像变换、图像相似度需要遍历图像每一像素,这一过程是较为耗时的。对此,代码中将图像先缩小至原有尺寸的1/10,即,像素数变为原来的1/100,再进行变换、相似度计算。最终再恢复至原有图像尺寸。
    图像变换后,其周围可能出现空白区域(下图),在计算图像相似度时,这一区域也是需要计算的(否则会倾向于生成全是边界的图像),所以需要填补这一区域。我使用的方法是计算全图像的平均颜色,并以平均颜色填补。


    5. 实验结果与分析5.1 目标函数值可视化下图展示了4号图片到1号图片的平移变换的优化目标函数值。平移变换有两个参数,所以可以映射到二维空间。使用上述暴力算法计算出参考图像平移至所有位置,计算其目标函数值,便得到如下的可视化结果。
    从图中可以看出目标函数最优值(最小值)位于图像中间附近,有局部最优值,但该函数较为光滑,因此可认为性质较好。

    5.2 结果5.2.1 暴力算法暴力算法效率较低,所以只进行了平移变换、旋转变换的实验。其中,平移变换约耗时3秒,旋转变换耗时数分钟。
    该算法可以确保找到最优解,可作为其他算法的验证手段。
    下图是枚举平移变换参数时,相似度函数的变化曲线:

    5.2.2 梯度下降法下图是使用梯度下降法优化仿射变换配准问题的结果,在迭代至5000轮左右时,已经找到较好的结果。这里,每一轮迭代指的是找到一个新的最优值,或开启一次新的梯度下降。
    右侧的蓝色曲线表示梯度下降过程的目标函数值变化,可以看出,在每轮梯度下降过程内,目标函数值能够快速下降。

    5.2.3 模拟退火算法下图使用了模拟退火算法来计算5.2.2中相同的优化问题以便对比。该方法约在4000轮左右取得一个较好的解,更好的解出现在50000轮左右。
    相比于梯度下降法,模拟退火在每轮迭代中不需要计算所有邻域解,而梯度下降计算数量为参数个数*2,所以模拟退火的迭代速度高于梯度下降。
    为了使两次模拟退火之间可以区分,我在两次模拟退火的能量函数之间插入了一个峰值。观察蓝色曲线可以发现,每次运行模拟退火时,前期能量函数波动较大(因为跳到更差的解的几率很大),在后期逐渐趋于稳定,类似梯度下降的结果。

    5.3 参数调整三种算法中,只有模拟退火算法有需要调整的参数。包括迭代次数k、初始温度temp与温度衰减系数r。
    k控制何时停止迭代,根据曲线取值即可。
    起初不知道如何设置初始温度与衰减系数,将温度设置得很高,衰减也很快,然后发现优化效果不如梯度下降法。分析各个参数的作用与模拟退火算法的优势之后,我得到结论:

    初始温度应与目标函数值在同一量级;
    衰减系数应调整到使得温度在进行了一半的迭代轮数之后下降到足够低,进而使得优化只向更优的可行解跳跃。

    最终的曲线和期望一致,一开始有较大的波动,随后逐渐稳定直至收敛。
    5.4 分析与结论本次实验我得到了如下结论:

    经过对比试验,对于二维照片配准问题,使用2范数作为相似性度量函数的效果较好,其次是1范数。
    参数空间的邻域结构非常重要。例如仿射变换矩阵尺寸为2*3,有六个参数,若直接优化这六个参数,则优化结果较差,很难收敛到最优解。原因可能是这六个参数的现实意义不够明确(例如,增大第一个参数会使图像怎样变化),且参数之间存在较大关联性(例如,同时增大第一个、第五个参数,作用是放大图像,而只改变一个则图像会变得不自然)。仿射变换的另一种表示方式是,原图像的左上、右上、左下三个顶点分别变换到了新图像的哪些位置,同样需要六个参数描述,但这些参数的可解释性更强,目标函数也更容易优化至最优。实验发现,选择合适的参数能够让目标函数的性质更好,更容易收敛到全局最优解。
    模拟退火算法在图像配准问题上的优势不明显。对于特别不光滑的目标函数,梯度下降算法是无能无力的,因为选择一个随机初始值下降至全局最优值的概率非常低。而模拟退火算法有助于跳出这些波动,相比梯度下降法更容易得到最优解。但是对于图像配准问题,其目标函数性质较好,局部最优解较少。于是,多次使用梯度下降算法也能够找到全局最优解,模拟退火算法的优势难以体现。
    0 留言 2019-06-16 23:22:40 奖励20点积分
  • 基于python构建搜索引擎系列——(六)系统展示及总结

    系统展示前几个博客已经介绍完搜索引擎的所有功能,为了实现更好的用户体验,需要一个web界面。这一部分是另一个队员做的,我这里借用他的代码。
    我们利用开源的Flask Web框架搭建了展示系统,搜索引擎只需要两个界面,一个是搜索界面,另一个是展示详细新闻的页面(实际搜索引擎没有这个页面)。编写好这两个模板页面并调用前面给出的接口,得到数据,展示出来就可以。
    这一部分没有太多需要讲解的算法,直接上效果图(点击图片可以查看大图)。


    由于数据量不大,只有1000条新闻,所以第一页中后面几个结果相关度就不是很高了。但是经过测试,在大数据量的情况下,不论是搜索的速度、准确率、召回率以及推荐阅读的相关度,都达到了不错的效果。
    总结至此,整个新闻搜索引擎构建完毕,总体效果令人满意,不过还是有很多可以改进的地方。下面总结一下本系统的优点和不足。
    优点倒排索引存储方式。因为不同词项的倒排记录表长度一般不同,所以没办法以常规的方式存入关系型数据库。通过将一个词项的倒排记录表序列化成一个字符串再存入数据库,读取的时候通过反序列化获得相关数据,整个结构类似于邻接表的形式。
    推荐阅读实现方式。利用特征提取的方法,用25个关键词表示一篇新闻,大大减小了文档词项矩阵规模,提高计算效率的同时不影响推荐新闻相关性。
    借用了Reddit的热度公式,融合了时间因素。
    不足构建索引时,为了降低索引规模,提高算法速度,我们将纯数字词项过滤了,同时忽略了词项大小写。虽然索引规模下降了,但是牺牲了搜索引擎的正确率。
    构建索引时,采用了jieba的精确分词模式,比如句子“我来到北京清华大学”的分词结果为“我/ 来到/ 北京/ 清华大学”,“清华大学”作为一个整体被当作一个词项,如果搜索关键词是“清华”,则该句子不能匹配,但显然这个句子和“清华”相关。所以后续可以采用结巴的搜索引擎分词模式,虽然索引规模增加了,但能提升搜索引擎的召回率。
    在推荐阅读模块,虽然进行了维度约减,但是当数据量较大时(数十万条新闻),得到的文档词项矩阵也是巨大的,会远远超过现有PC的内存大小。所以可以先对新闻进行粗略的聚类,再在类内计算两两cosine相似度,得到值得推荐的新闻。
    在热度公式中,虽然借用了Reddit的公式,大的方向是正确的,但是引入了参数k1k1和k2k2,而且将其简单的设置为1。如果能够由专家给出或者经过机器学习训练得到,则热度公式的效果会更好。
    本文转载自:

    http://bitjoy.net/2016/01/09/introduction-to-building-a-search-engine-6
    http://bitjoy.net/2016/01/09/introduction-to-building-a-search-engine-7
    1 留言 2019-06-06 17:05:21 奖励12点积分
  • 基于python构建搜索引擎系列——(五)推荐阅读 精华

    虽然主要的检索功能实现了,但是我们还需要一个“推荐阅读”的功能。当用户浏览某条具体新闻时,我们在页面底端给出5条和该新闻相关的新闻,也就是一个最简单的推荐系统。

    推荐模块的思路是度量两两新闻之间的相似度,取相似度最高的前5篇新闻作为推荐阅读的新闻。
    我们前面讲过,一篇文档可以用一个向量表示,向量中的每个值是不同词项t在该文档d中的词频tf。但是一篇较短的文档(如新闻)的关键词并不多,所以我们可以提取每篇新闻的关键词,用这些关键词的tfidf值构成文档的向量表示,这样能够大大减少相似度计算量,同时保持较好的推荐效果。
    jieba分词组件自带关键词提取功能,并能返回关键词的tfidf值。所以对每篇新闻,我们先提取tfidf得分最高的前25个关键词,用这25个关键词的tfidf值作为文档的向量表示。由此能够得到一个1000*m的文档词项矩阵M,矩阵每行表示一个文档,每列表示一个词项,m为1000个文档的所有互异的关键词(大概10000个)。矩阵M当然也是稀疏矩阵。
    得到文档词项矩阵M之后,我们利用sklearn的pairwise_distances函数计算M中行向量之间的cosine相似度,对每个文档,得到与其最相似的前5篇新闻id,并把结果写入数据库。
    推荐阅读模块的代码如下:
    from os import listdirimport xml.etree.ElementTree as ETimport jiebaimport jieba.analyseimport sqlite3import configparserfrom datetime import *import mathimport pandas as pdimport numpy as npfrom sklearn.metrics import pairwise_distancesclass RecommendationModule: stop_words = set() k_nearest = [] config_path = '' config_encoding = '' doc_dir_path = '' doc_encoding = '' stop_words_path = '' stop_words_encoding = '' idf_path = '' db_path = '' def __init__(self, config_path, config_encoding): self.config_path = config_path self.config_encoding = config_encoding config = configparser.ConfigParser() config.read(config_path, config_encoding) self.doc_dir_path = config['DEFAULT']['doc_dir_path'] self.doc_encoding = config['DEFAULT']['doc_encoding'] self.stop_words_path = config['DEFAULT']['stop_words_path'] self.stop_words_encoding = config['DEFAULT']['stop_words_encoding'] self.idf_path = config['DEFAULT']['idf_path'] self.db_path = config['DEFAULT']['db_path'] f = open(self.stop_words_path, encoding = self.stop_words_encoding) words = f.read() self.stop_words = set(words.split('\n')) def write_k_nearest_matrix_to_db(self): conn = sqlite3.connect(self.db_path) c = conn.cursor() c.execute('''DROP TABLE IF EXISTS knearest''') c.execute('''CREATE TABLE knearest (id INTEGER PRIMARY KEY, first INTEGER, second INTEGER, third INTEGER, fourth INTEGER, fifth INTEGER)''') for docid, doclist in self.k_nearest: c.execute("INSERT INTO knearest VALUES (?, ?, ?, ?, ?, ?)", tuple([docid] + doclist)) conn.commit() conn.close() def is_number(self, s): try: float(s) return True except ValueError: return False def construct_dt_matrix(self, files, topK = 200): jieba.analyse.set_stop_words(self.stop_words_path) jieba.analyse.set_idf_path(self.idf_path) M = len(files) N = 1 terms = {} dt = [] for i in files: root = ET.parse(self.doc_dir_path + i).getroot() title = root.find('title').text body = root.find('body').text docid = int(root.find('id').text) tags = jieba.analyse.extract_tags(title + '。' + body, topK=topK, withWeight=True) #tags = jieba.analyse.extract_tags(title, topK=topK, withWeight=True) cleaned_dict = {} for word, tfidf in tags: word = word.strip().lower() if word == '' or self.is_number(word): continue cleaned_dict[word] = tfidf if word not in terms: terms[word] = N N += 1 dt.append([docid, cleaned_dict]) dt_matrix = [[0 for i in range(N)] for j in range(M)] i =0 for docid, t_tfidf in dt: dt_matrix[i][0] = docid for term, tfidf in t_tfidf.items(): dt_matrix[i][terms[term]] = tfidf i += 1 dt_matrix = pd.DataFrame(dt_matrix) dt_matrix.index = dt_matrix[0] print('dt_matrix shape:(%d %d)'%(dt_matrix.shape)) return dt_matrix def construct_k_nearest_matrix(self, dt_matrix, k): tmp = np.array(1 - pairwise_distances(dt_matrix[dt_matrix.columns[1:]], metric = "cosine")) similarity_matrix = pd.DataFrame(tmp, index = dt_matrix.index.tolist(), columns = dt_matrix.index.tolist()) for i in similarity_matrix.index: tmp = [int(i),[]] j = 0 while j < k: max_col = similarity_matrix.loc[i].idxmax(axis = 1) similarity_matrix.loc[i][max_col] = -1 if max_col != i: tmp[1].append(int(max_col)) #max column name j += 1 self.k_nearest.append(tmp) def gen_idf_file(self): files = listdir(self.doc_dir_path) n = float(len(files)) idf = {} for i in files: root = ET.parse(self.doc_dir_path + i).getroot() title = root.find('title').text body = root.find('body').text seg_list = jieba.lcut(title + '。' + body, cut_all=False) seg_list = set(seg_list) - self.stop_words for word in seg_list: word = word.strip().lower() if word == '' or self.is_number(word): continue if word not in idf: idf[word] = 1 else: idf[word] = idf[word] + 1 idf_file = open(self.idf_path, 'w', encoding = 'utf-8') for word, df in idf.items(): idf_file.write('%s %.9f\n'%(word, math.log(n / df))) idf_file.close() def find_k_nearest(self, k, topK): self.gen_idf_file() files = listdir(self.doc_dir_path) dt_matrix = self.construct_dt_matrix(files, topK) self.construct_k_nearest_matrix(dt_matrix, k) self.write_k_nearest_matrix_to_db()if __name__ == "__main__": print('-----start time: %s-----'%(datetime.today())) rm = RecommendationModule('../config.ini', 'utf-8') rm.find_k_nearest(5, 25) print('-----finish time: %s-----'%(datetime.today()))
    这个模块的代码量最多,主要原因是需要构建文档词项矩阵,并且计算k邻居矩阵。矩阵数据结构的设计需要特别注意,否则会严重影响系统的效率。我刚开始把任务都扔给了pandas.DataFrame,后来发现当两个文档向量合并时,需要join连接操作,当数据量很大时,非常耗时,所以改成了先用python原始的list存储,最后一次性构造一个完整的pandas.DataFrame,速度比之前快了不少。
    本文转载自:http://bitjoy.net/2016/01/09/introduction-to-building-a-search-engine-5
    1 留言 2019-06-03 15:49:20 奖励14点积分
  • 基于python构建搜索引擎系列——(四)检索模型 精华

    构建好倒排索引之后,就可以开始检索了。
    检索模型有很多,比如向量空间模型、概率模型、语言模型等。其中最有名的、检索效果最好的是基于概率的BM25模型。
    给定一个查询Q和一篇文档d,d对Q的BM25得分公式为:

    公式中变量含义如下:

    qtf:查询中的词频
    tf:文档中的词频
    ld:文档长度
    avg_l:平均文档长度
    N:文档数量
    df:文档频率
    b,k1,k3:可调参数

    这个公式看起来很复杂,我们把它分解一下,其实很容易理解。第一个公式是外部公式,一个查询Q可能包含多个词项,比如“苹果手机”就包含“苹果”和“手机”两个词项,我们需要分别计算“苹果”和“手机”对某个文档d的贡献分数w(t,d),然后将他们加起来就是整个文档d相对于查询Q的得分。
    第二个公式就是计算某个词项t在文档d中的得分,它包括三个部分。第一个部分是词项t在查询Q中的得分,比如查询“中国人说中国话”中“中国”出现了两次,此时qtf=2,说明这个查询希望找到的文档和“中国”更相关,“中国”的权重应该更大,但是通常情况下,查询Q都很短,而且不太可能包含相同的词项,所以这个因子是一个常数,我们在实现的时候可以忽略。
    第二部分类似于TFIDF模型中的TF项。也就是说某个词项t在文档d中出现次数越多,则t越重要,但是文档长度越长,tf也倾向于变大,所以使用文档长度除以平均长度ld/avg_l起到某种归一化的效果,k1和b是可调参数。
    第三部分类似于TFIDF模型中的IDF项。也就是说虽然“的”、“地”、“得”等停用词在某文档d中出现的次数很多,但是他们在很多文档中都出现过,所以这些词对d的贡献分并不高,接近于0;反而那些很稀有的词如”糖尿病“能够很好的区分不同文档,这些词对文档的贡献分应该较高。
    所以根据BM25公式,我们可以很快计算出不同文档t对查询Q的得分情况,然后按得分高低排序给出结果。
    下面是给定一个查询句子sentence,根据BM25公式给出文档排名的函数:
    def result_by_BM25(self, sentence): seg_list = jieba.lcut(sentence, cut_all=False) n, cleaned_dict = self.clean_list(seg_list) BM25_scores = {} for term in cleaned_dict.keys(): r = self.fetch_from_db(term) if r is None: continue df = r[1] w = math.log2((self.N - df + 0.5) / (df + 0.5)) docs = r[2].split('\n') for doc in docs: docid, date_time, tf, ld = doc.split('\t') docid = int(docid) tf = int(tf) ld = int(ld) s = (self.K1 * tf * w) / (tf + self.K1 * (1 - self.B + self.B * ld / self.AVG_L)) if docid in BM25_scores: BM25_scores[docid] = BM25_scores[docid] + s else: BM25_scores[docid] = s BM25_scores = sorted(BM25_scores.items(), key = operator.itemgetter(1)) BM25_scores.reverse() if len(BM25_scores) == 0: return 0, [] else: return 1, BM25_scores
    首先将句子分词得到所有查询词项,然后从数据库中取出词项对应的倒排记录表,对记录表中的所有文档,计算其BM25得分,最后按得分高低排序作为查询结果。
    类似的,我们还可以对所有文档按时间先后顺序排序,越新鲜的新闻排名越高;还可以按新闻的热度排序,越热门的新闻排名越高。
    关于热度公式,我们认为一方面要兼顾相关度,另一方面也要考虑时间因素,所以是BM25打分和时间打分的一个综合。
    比较有名的热度公式有两个,一个是Hacker News的,另一个是Reddit的,他们的公式分别为:


    可以看出,他们都是将新闻/评论的一个原始得分和时间组合起来,只是一个用除法,一个用加法。所以我们也依葫芦画瓢,”自创“了一个简单的热度公式:

    用BM25得分加上新闻时间和当前时间的差值的倒数,k1k1和k2k2也是可调参数。
    按时间排序和按热度排序的函数和按BM25打分排序的函数类似,这里就不贴出来了,详细情况可以看我的项目News_IR_Demo。
    至此,搜索引擎的搜索功能已经实现了,你可以试着修改./web/search_engine.py的第167行的关键词,看看搜索结果是否和你预想的排序是一样的。不过由于我们的数据量只有1000个新闻,并不能涵盖所有关键词,更多的测试可以留给大家线下完成。
    本文转载自:http://bitjoy.net/2016/01/07/introduction-to-building-a-search-engine-4
    1 留言 2019-06-01 15:29:45 奖励14点积分
  • 基于python构建搜索引擎系列——(三)构建索引 精华

    目前正是所谓的“大数据”时代,数据量多到难以计数,怎样结构化的存储以便于分析计算,是当前的一大难题。上一篇博客我们简单抓取了1000个搜狐新闻数据,搜索的过程就是从这1000个新闻中找出和关键词相关的新闻来,那么怎样快速搜索呢,总不可能依次打开xml文件一个字一个字的找吧,这时就需要借助倒排索引这个强大的数据结构。
    在讲倒排索引之前,我们先介绍一下布尔检索。布尔检索只是简单返回包含某个关键词的文档,比如查询“苹果手机”,则返回所有包含“苹果”和“手机”关键词的文档,布尔检索并不对返回结果排序,所以有可能返回的第一个文档是“某个男孩边吃苹果边玩手机…“。
    实现布尔检索并不难,我们需要构建一个如下图的词项文档矩阵:

    每行对应一个词项,每列对应一个文档,如果该值为1,表示该行词项出现在该列文档中。比如词项”苹果“出现在doc1和doc3文档中,如果我们要找同时出现”苹果“和”手机“的文档,只需把他们对应的向量取出来进行”与“操作,此为101&011=001,所以doc3同时出现了”苹果“和”手机“两个关键词,我们将其返回。
    布尔检索虽然很快,但是它也有很多缺陷,比如不能对结果排序,词项只有出现和不出现两种状态,但是一篇文档中出现10次“苹果“和只出现1次”苹果“,他们的相关度肯定是不相同的。所以需要对布尔检索进行改进。
    在扫描文档时,不但记录某词项出现与否,还记录该词项出现的次数,即词项频率(tf);同时我们记录该文档的长度(ld),以及某词项在不同文档中出现的次数,即文档频率(df)。

    这样我们就得到了如上图的倒排索引。左边部分被称为词典,存储的是1000个新闻中所有不同的词项;右边部分被称为倒排记录表,存储的是出现Term_i的那些文档信息。倒排索引中存储的变量都是为了给后续检索模型使用。
    讲到这里,我们需要解决如下几个问题。

    怎样得到一篇文档中的所有词项。给我们一篇新闻稿子,人类很容易分辨出”苹果“和”手机“是两个不同的词项,但是计算机怎么知道是这两个词呢?为什么不是”苹”、”国手“和”机“呢?这就需要进行中文分词,我们可以借助开源的jieba中文分词组件来完成,jieba分词能够将一个中文句子切成一个个词项,这样我们就可以统计tf, df了。
    有些词,如”的“、”地“、”得“、”如果“等,几乎每篇文档都会出现,他们起不到很好的区分文档的效果,这类词被称为”停用词“,我们需要把他们去掉。去停词的步骤可以在jieba分词之后完成。
    怎样存储倒排记录表。假设1000个文档共有20000个不同的词项,如果用类似图1的矩阵形式存储,需要耗费100020000=210^7个存储单元,但是图1往往是一个稀疏矩阵,因为一个文档中可能只出现了200个不同的词项,剩余的19800个词项都是空的。用矩阵方式存储时空效率都不高。所以我们可以采用图2的方式,词典用B-树或hash存储,倒排记录表用邻接链表存储方式,这样能大大减少存储空间。如果我们要将图2保存到数据库,可以对倒排记录表序列化成一个长的字符串,写入到一个单元格,读取的时候再反序列化。比如每个Doc内部用’\t’连接,Doc之间用’\n’连接,读取的时候split即可。

    倒排索引构建算法使用内存式单遍扫描索引构建方法(SPIMI),其实就是依次对每篇新闻进行分词,如果出现新的词项则插入到词典中,否则将该文档的信息追加到词项对应的倒排记录表中。SPIMI的伪代码如下:
    SPIMI-Invert(token_stream) output_file = NEWFILE() dictionary = NEWHASH() while(free memory available) do token ← next(token_stream) // 即不在词典中 if term(token) !∈dictionary // 加入词典并返回词典位置 then postings_list = AddToDictionary(dictionary, term(token)) // 找到词典位置 else postings_list = GetPostingList(dictionary, term(token)) // 关键词对应存储倒排文档的数据结构可用空间是否已满 if full(postings_list) // 重新分配关键词对应存储倒排文档的数据结构可用空间 使其变为原来2倍 then postings_list = DoublePostingList(dictinary, term(token)) // 将文档信息放入倒排表中 AddToPostingsList(postings_list,docId(token))//对词典排序(便于以后合并词典)sorted_terms ← SortTerms(dictionary)// 将倒排信息写入磁盘WriteBlockToDisk(sorted_terms, dictionary, output_file)return output_file
    下面是构建索引的所有代码:
    from os import listdirimport xml.etree.ElementTree as ETimport jiebaimport sqlite3import configparserclass Doc: docid = 0 date_time = '' tf = 0 ld = 0 def __init__(self, docid, date_time, tf, ld): self.docid = docid self.date_time = date_time self.tf = tf self.ld = ld def __repr__(self): return(str(self.docid) + '\t' + self.date_time + '\t' + str(self.tf) + '\t' + str(self.ld)) def __str__(self): return(str(self.docid) + '\t' + self.date_time + '\t' + str(self.tf) + '\t' + str(self.ld))class IndexModule: stop_words = set() postings_lists = {} config_path = '' config_encoding = '' def __init__(self, config_path, config_encoding): self.config_path = config_path self.config_encoding = config_encoding config = configparser.ConfigParser() config.read(config_path, config_encoding) f = open(config['DEFAULT']['stop_words_path'], encoding = config['DEFAULT']['stop_words_encoding']) words = f.read() self.stop_words = set(words.split('\n')) def is_number(self, s): try: float(s) return True except ValueError: return False def clean_list(self, seg_list): cleaned_dict = {} n = 0 for i in seg_list: i = i.strip().lower() if i != '' and not self.is_number(i) and i not in self.stop_words: n = n + 1 if i in cleaned_dict: cleaned_dict[i] = cleaned_dict[i] + 1 else: cleaned_dict[i] = 1 return n, cleaned_dict def write_postings_to_db(self, db_path): conn = sqlite3.connect(db_path) c = conn.cursor() c.execute('''DROP TABLE IF EXISTS postings''') c.execute('''CREATE TABLE postings (term TEXT PRIMARY KEY, df INTEGER, docs TEXT)''') for key, value in self.postings_lists.items(): doc_list = '\n'.join(map(str,value[1])) t = (key, value[0], doc_list) c.execute("INSERT INTO postings VALUES (?, ?, ?)", t) conn.commit() conn.close() def construct_postings_lists(self): config = configparser.ConfigParser() config.read(self.config_path, self.config_encoding) files = listdir(config['DEFAULT']['doc_dir_path']) AVG_L = 0 for i in files: root = ET.parse(config['DEFAULT']['doc_dir_path'] + i).getroot() title = root.find('title').text body = root.find('body').text docid = int(root.find('id').text) date_time = root.find('datetime').text seg_list = jieba.lcut(title + '。' + body, cut_all=False) ld, cleaned_dict = self.clean_list(seg_list) AVG_L = AVG_L + ld for key, value in cleaned_dict.items(): d = Doc(docid, date_time, value, ld) if key in self.postings_lists: self.postings_lists[key][0] = self.postings_lists[key][0] + 1 # df++ self.postings_lists[key][1].append(d) else: self.postings_lists[key] = [1, [d]] # [df, [Doc]] AVG_L = AVG_L / len(files) config.set('DEFAULT', 'N', str(len(files))) config.set('DEFAULT', 'avg_l', str(AVG_L)) with open(self.config_path, 'w', encoding = self.config_encoding) as configfile: config.write(configfile) self.write_postings_to_db(config['DEFAULT']['db_path'])if __name__ == "__main__": im = IndexModule('../config.ini', 'utf-8') im.construct_postings_lists()
    运行之后会在./data/下生成一个ir.db数据库文件,这就是构建好的索引数据库。
    本文转载自:http://bitjoy.net/2016/01/07/introduction-to-building-a-search-engine-3
    1 留言 2019-05-30 14:51:46 奖励15点积分
  • 基于python构建搜索引擎系列——(二)网络爬虫 精华

    网络爬虫又称网络蜘蛛、Web采集器等,它是一种按照一定的规则,自动地抓取万维网信息的程序或者脚本。
    我们在设计网络爬虫的时候需要注意两点:

    鲁棒性:Web中有些服务器会制造采集器陷阱(spider traps),这些陷阱服务器实际上是Web页面的生成器,它能在某个域下生成无数网页,从而使采集器陷入到一个无限的采集循环中去。采集器必须能从这些陷阱中跳出来。当然,这些陷阱倒不一定都是恶意的,有时可能是网站设计疏忽所导致的结果
    礼貌性:Web服务器具有一些隐式或显式的政策来控制采集器访问它们的频率。设计采集器时必须要遵守这些代表礼貌性的访问政策

    采集器的基本架构如下图所示。

    基本上是”抓取→分析→得到新的URL→再抓取→再分析”这样一个死循环过程。
    以上内容摘自王斌老师翻译的《信息检索导论》课本。
    由于我们要做的是一个新闻搜索引擎,所以抓取的是新闻数据,对于爬虫,网上也有很多的开源程序,如nutch等,Github上还有人专门开发了抓取新闻的组件newspaper,可以很方便的提取新闻标题、正文、时间等信息。不过用python写爬虫也是分分钟的事情,下面我们一起来试一试。
    首先找一个新闻网站,为简单起见,要找那种结构清晰、html代码便于解析的门户网站,比如搜狐新闻、参考消息等。
    搜狐新闻的国内要闻列表如下:

    结构非常清楚,左边是带URL的标题,右边括号里有新闻时间。这一页列表就有200条新闻,如果我们要获取1000条,只要不断模拟点击下一页即可。下一页的URL也只是在首页的基础上加上_xxx.shtml,xxx就是不同的页码。
    查看列表的html源码,得知列表都在类名为newsblue1的td中,所以只需要解析html源码就可以得到新闻标题、URL和时间,python解析html可以用BeautifulSoup包,非常方便。
    进入到新闻详细页面,正文部分如下:

    查看html源码,正文位于类名为text clear的div中,据此可以很方便的提取新闻正文。
    得到一条新闻的所有数据之后,我们需要将之结构化成xml文件,借助相应的xml包可以很方便的完成这项工作。xml格式定义如下:
    <?xml version="1.0" encoding="utf-8"?><doc> <id></id> <url></url> <title></title> <datetime></datetime> <body></body></doc>
    注意爬虫需要访问网络,难免会出现一些异常,所以捕获异常是非常有必要的。另外,搜狐每篇新闻正文后面都会有一段’//‘开始的注释,这个需要过滤掉,短于140个字的新闻我也过滤掉了。整个搜索系统的配置参数都存储在config.ini文件中。
    下面是完整的python 3.4+代码:
    from bs4 import BeautifulSoupimport urllib.requestimport xml.etree.ElementTree as ETimport configparserdef get_news_pool(root, start, end): news_pool = [] for i in range(start,end,-1): page_url = '' if i != start: page_url = root +'_%d.shtml'%(i) else: page_url = root + '.shtml' try: response = urllib.request.urlopen(page_url) except Exception as e: print("-----%s: %s-----"%(type(e), page_url)) continue html = response.read() soup = BeautifulSoup(html) td = soup.find('td', class_ = "newsblue1") a = td.find_all('a') span = td.find_all('span') for i in range(len(a)): date_time = span[i].string url = a[i].get('href') title = a[i].string news_info = ['2016-'+date_time[1:3]+'-'+date_time[4:-1]+':00',url,title] news_pool.append(news_info) return(news_pool)def crawl_news(news_pool, min_body_len, doc_dir_path, doc_encoding): i = 1 for news in news_pool: try: response = urllib.request.urlopen(news[1]) except Exception as e: print("-----%s: %s-----"%(type(e), news[1])) continue html = response.read() soup = BeautifulSoup(html) try: body = soup.find('div', class_ = "text clear").find('div').get_text() except Exception as e: print("-----%s: %s-----"%(type(e), news[1])) continue if '//' in body: body = body[:body.index('//')] body = body.replace(" ", "") if len(body) <= min_body_len: continue doc = ET.Element("doc") ET.SubElement(doc, "id").text = "%d"%(i) ET.SubElement(doc, "url").text = news[1] ET.SubElement(doc, "title").text = news[2] ET.SubElement(doc, "datetime").text = news[0] ET.SubElement(doc, "body").text = body tree = ET.ElementTree(doc) tree.write(doc_dir_path + "%d.xml"%(i), encoding = doc_encoding, xml_declaration = True) i += 1if __name__ == '__main__': config = configparser.ConfigParser() config.read('../config.ini', 'utf-8') root = 'http://news.sohu.com/1/0903/61/subject212846158' news_pool = get_news_pool(root, 854, 849) crawl_news(news_pool, 140, config['DEFAULT']['doc_dir_path'], config['DEFAULT']['doc_encoding']) print('done!')
    本文转载自:http://bitjoy.net/2016/01/04/introduction-to-building-a-search-engine-2
    1 留言 2019-05-28 20:16:43 奖励13点积分
  • 大数据 17、单机推荐系统

    前文链接:https://write-bug.com/article/2491.html
    通过前面介绍的算法基础,我们可以利用CB、CF算法作召回和粗排,利用LR作精排打分,最后关联出特定用户正在收听的特定音乐的推荐集合,最终形成可视化页面。

    上图是推荐系统的base版本,可通过前几节的知识串接起来,后面会陆续介绍可替换的组件及更多业务情况。
    我们可以看到用户在页面浏览时,可以通过点击、收听等行为我们进行user_id,item_id的收集,与此同时,我们使用用户的行为信息对检索引擎进行检索,即召回阶段的计算结果,之后我们需要对返回的候选集合进行精排,通过lr对用户特征+物品元数据信息作回归打分从而把筛选的候选集合再次排序,实现个性化。
    项目流程:
    1.数据准备
    用户画像数据:user_profile.datauserid,性别,年龄,收入,地域
    物品(音乐)元数据:music_metaitemid,name,desc,时长,地域,标签
    用户行为数据:user_watch_pref.smluserid,itemid,该用户对该物品的收听时长,点击时间(小时)

    首先,将3份数据融合到一份数据中,python gen_base.py 代码解析数据,实现对数据的拼接;得到数据merge_base.data。

    输入:user_profile.data music_meta user_watch_pref.sml 三份数据
    输出:merge_base.data 拼接后的数据

    也可用hive处理:
    create external table user_profile(user_id string,sex string,age string,money string,place string) row format delimited fields terminated by ',';load data local inpath '/usr/local/src/code/recsys_test/data/user_profile.data' into table user_profile;create external table music_meta(item_id string,name string,desc string,hour string,place string,tag string) row format delimited fields terminated by '\001';load data local inpath '/usr/local/src/code/recsys_test/data/music_meta' into table music_meta;create external table user_watch_pref (user_id string,item_id string,listen_hour string,hour string) row format delimited fields terminated by '\001';load data local inpath '/usr/local/src/code/recsys_test/data/ user_watch_pref.sml ' into table user_watch_pref;3张表数据融合为一份数据user_watch_pref user_id,item_id,listen_hour,hour,user_profile sex,age,money,placemusic_meta name,desc,hour,placeinsert overwrite directory '/data' row format delimited fields terminated by ',' select distinct(a.user_id),a.item_id,a.listen_hour,a.hour,c.sex,c.age,c.money, c.place,b.name,b.desc,b.hour,b.placefrom user_watch_pref as a, user_profile as c,music_meta as bwhere a.user_id = c.user_id and a.item_id=b.item_id;
    2.召回、CB算法在学习推荐算法时,我们可以发现,不管是cb还是cf都可以通过对mr倒排式的协同过滤算法对数据进行处理,只是token item_id,score和user item_id,score 的区别。
    以token itemid score形式整理训练数据
    gen_cb_train.py 我们这里的代码对item的name,desc,tag进行分词并给予不同的权重便可以形成我们的数据。

    输入:merge_base.data 总数据
    输出:cb_train.data 3列数据

    要点:对item_id 进行去重,对不同元数据分词分数给予不同权重,如果音乐名字、描述、标签中出现相同的token,我们就把相应的分数乘各自的权重相加,如果不相同便加入token字典
    RATIO_FOR_NAME = 0.9RATIO_FOR_DESC = 0.1RATIO_FOR_TAGS = 0.05用协同过滤算法跑出item-item数据 mr_cf倒排式
    最后得到基于cb的ii矩阵,这里我也用hive弄了下,但是没想到怎么整理出ii矩阵:
    cb_train.datatoken,item_id,tfidfcreate external table cb_train (token string,item_id string,tfidf string) row format delimited fields terminated by ',';load data local inpath '/usr/local/src/code/recsys_test/data/cb_train.data into table cb_train;token,item_id,scoresum(sqrt(sum(s^2))):select token,item_id,sum(power(tfidf,2)) over(partition by item_id) as scorefrom cb_train order by item_id limit 100;s/sum(sqrt(sum(s^2))):insert overwrite directory '/data/cb_z' row format delimited fields terminated by ',' select t.token,t.item_id,cb_train.tfidf/sqrt(score) as f_scorefrom(select token,item_id,sum(power(tfidf,2)) over(partition by item_id) as scorefrom cb_train)t,cb_trainwhere t.item_id=cb_train.item_id and t.token = cb_train.token;limit 300;暂存:token,item_id,scorecreate external table cb_train_score (token string,item_id string,score string) row format delimited fields terminated by ',';load data inpath '/data/cb_z/000000_0'into table cb_train_score;对数据格式化,item-> item list形式,整理出KV形式
    gen_reclist.py并标记数据计算算法:

    输入:cb.result ii矩阵
    输出:cb_reclist.redis 粗排、标记、聚合

    类似如下数据:
    SET CB_5305109176 726100303:0.393048_953500302:0.393048_6193109237:0.348855灌库(redis)
    下载redis-2.8.3.tar.gz安装包,进行源码编译,执行make,然后会在src目录中,得到bin文件(redis-server 服务器,redis-cli 客户端)。
    启动redis server服务:
    ]# ./src/redis-server然后换一个终端执行:]# ./src/redis-cli,连接服务
    接下来灌数据(批量灌):
    需要安装unix2dos(格式转换)
    ]# cat cb_reclist.redis | /usr/local/src/redis-2.8.3/src/redis-cli --pipe验证:
    ]# ./src/redis-cli执行:
    127.0.0.1:6379> get CB_5305109176"726100303:0.393048_953500302:0.393048_6193109237:0.348855"3.召回、CF算法以userid itemid score形式整理训练数据 gen_cf_train.py
    得到userid对item的最终分数,即user收听时长表示对item的喜欢分数 score = float(t_finished) / float(t_all)
    用协同过滤算法跑出item-item数据 mr_cf,最后得到基于cf的ii矩阵
    对数据格式化,item-> item list形式,整理出KV形式
    unix2dos cf_reclist.redis灌库
    cat cf_reclist.redis | /usr/local/src/redis-2.8.3/src/redis-cli –pipe与上面cb算法一样流程.
    4.为lr模型作特征提取:
    user: gender、age
    item:name_token
    输入:merge_base.data
    输出:

    samples.data 特征提取数据user_feature.data 用户特征数据,为使用模型作数据准备item_feature.data 物品特征数据,为使用模型作数据准备name_id.dict 为包装数据作准备

    这里的label值用用户的收听时长来作判断:
    # label info label = float(watch_time) / float(total_time) final_label = '0' if label >= 0.82: final_label = '1' elif label <= 0.3: final_label = '0' else: continue用户特征分数初始化为1,物品特征分数运用jieba分词的idf作为初始分数
    形成如下数据:



    模型使用时,只有w,b 怎么使用,我需要有个库去存储user_fea、item_fea。实时拼接出特征,再通过model预测。
    用sk-learn进行模型训练,得到w,b。解析samples数据,还原矩阵:

    target_list:存储每个样本的label标签
    fea_row_list:存储样本行信息
    fea_col_list:存储样本列信息
    data_list:存储真实数据score

    转换数据并分割数据集:
    fea_datasets = csr_matrix((data, (row, col)), shape=(row_idx, max_col + 1))x_train, x_test, y_train, y_test = train_test_split(fea_datasets, target_list, test_size=0.2, random_state=0) # 28分为测试集及训练集训练
    x_train, x_test, y_train, y_test = load_data()model = LogisticRegression(penalty='l1')model.fit(x_train, y_train)for w_list in model.coef_: for w in w_list: print >> ff_w, "w: ", w for b in model.intercept_: print >> ff_b, "b: ", b print "precision: ", model.score(x_test, y_test)#预测print "MSE: ", np.mean((model.predict(x_test) - y_test) ** 2)#误差平方根auc评估
    for y in y_test: print >> ff_t, yfor y in model.predict_proba (x_test): print >> ff_p, y
    评估:auc:paste T.txt P.txt >auc.txt,awk无图形测试:但是需要回归的浮点分数不能用分类的label
    回归:model.predict_proba()
    分类:model.predict() :0&1

    5.推荐引擎及可视化通过前面的层层处理,我们得到了user&item特定的候选集合如何随意来了一个用户推荐个性化呢?

    解析请求:userid,itemid,pyweb模拟页面
    加载模型:加载排序模型(model.w,model.b),加载并解析数据
    检索候选集合:利用cb,cf去redis里面检索数据库,得到候选集合。截断粗排候选集合,得到item_list
    获取用户特征:userid
    获取物品特征:itemid,这两步用到上面说的特征库
    打分(逻辑回归),排序。对拼接出的特征进行检索wx计算,更新分数,并通过sigmoid函数压缩分数
    top-n过滤
    数据包装(itemid->name),返回

    之后,再把最终的候选集合列表,post到前端页面。
    此上,即为单机版本的推荐系统实现,但是在工作中思路大概是这样,只是拓宽了算法组件、机器、备份、分流等等东西,需要多个部门共同协作。
    0 留言 2019-05-27 18:11:17 奖励14点积分
  • 基于WinInet实现的HTTP文件下载 精华

    背景之前写过的网络数据传输的小程序都是基于Socket去写的,所以,如果要用Socket传输数据到网站,还需要根据域名获取服务器的IP地址,然后再建立连接,传输数据。虽然,Socket也可以实现网络传输,但是,总感觉不是很方便。所以,后来随着知识面的拓展,了解到Windows还专门提供了WinInet网络库,封装了比较简便的接口,去实现HTTP和FTP等传输协议的数据传输。
    本文就是基于WinInet网络库,实现通过HTTP传输协议下载文件功能的小程序。现在,就把开发过程的思路和编程分享给大家。
    主要函数介绍介绍HTTP下载文件使用到的主要的WinInet库中的API函数。
    1. InternetOpen介绍
    函数声明
    HINTERNET InternetOpen(In LPCTSTR lpszAgent,In DWORD dwAccessType,In LPCTSTR lpszProxyName,In LPCTSTR lpszProxyBypass,In DWORD dwFlags);
    参数lpszAgent指向一个空结束的字符串,该字符串指定调用WinInet函数的应用程序或实体的名称。使用此名称作为用户代理的HTTP协议。dwAccessType指定访问类型,参数可以是下列值之一:



    Value
    Meaning




    INTERNET_OPEN_TYPE_DIRECT
    使用直接连接网络


    INTERNET_OPEN_TYPE_PRECONFIG
    获取代理或直接从注册表中的配置,使用代理连接网络


    INTERNETOPEN_TYPE_PRECONFIG WITH_NO_AUTOPROXY
    获取代理或直接从注册表中的配置,并防止启动Microsoft JScript或Internet设置(INS)文件的使用


    INTERNET_OPEN_TYPE_PROXY
    通过代理的请求,除非代理旁路列表中提供的名称解析绕过代理,在这种情况下,该功能的使用



    lpszProxyName指针指向一个空结束的字符串,该字符串指定的代理服务器的名称,不要使用空字符串;如果dwAccessType未设置为INTERNET_OPEN_TYPE_PROXY,则此参数应该设置为NULL。
    lpszProxyBypass指向一个空结束的字符串,该字符串指定的可选列表的主机名或IP地址。如果dwAccessType未设置为INTERNET_OPEN_TYPE_PROXY的 ,参数省略则为NULL。
    dwFlags参数可以是下列值的组合:



    VALUE
    MEANING




    INTERNET_FLAG_ASYNC
    使异步请求处理的后裔从这个函数返回的句柄


    INTERNET_FLAG_FROM_CACHE
    不进行网络请求,从缓存返回的所有实体,如果请求的项目不在缓存中,则返回一个合适的错误,如ERROR_FILE_NOT_FOUND


    INTERNET_FLAG_OFFLINE
    不进行网络请求,从缓存返回的所有实体,如果请求的项目不在缓存中,则返回一个合适的错误,如ERROR_FILE_NOT_FOUND



    返回值成功:返回一个有效的句柄,该句柄将由应用程序传递给接下来的WinInet函数。失败:返回NULL。

    2. InternetConnect介绍
    函数声明
    HINTERNET WINAPI InternetConnect( HINTERNET hInternet, LPCTSTR lpszServerName, INTERNET_PORT nServerPort, LPCTSTR lpszUserName, LPCTSTR lpszPassword, DWORD dwService, DWORD dwFlags, DWORD dwContext);
    参数说明hInternet:由InternetOpen返回的句柄。lpszServerName:连接的ip或者主机名nServerPort:连接的端口。lpszUserName:用户名,如无置NULL。lpszPassword:密码,如无置NULL。dwService:使用的服务类型,可以使用以下

    INTERNET_SERVICE_FTP = 1:连接到一个 FTP 服务器上INTERNET_SERVICE_GOPHER = 2INTERNET_SERVICE_HTTP = 3:连接到一个 HTTP 服务器上
    dwFlags:文档传输形式及缓存标记。一般置0。dwContext:当使用回叫信号时, 用来识别应用程序的前后关系。返回值成功返回非0。如果返回0。要InternetCloseHandle释放这个句柄。

    3. HttpOpenRequest介绍
    函数声明
    HINTERNET HttpOpenRequest( _In_ HINTERNET hConnect, _In_ LPCTSTR lpszVerb, _In_ LPCTSTR lpszObjectName, _In_ LPCTSTR lpszVersion, _In_ LPCTSTR lpszReferer, _In_ LPCTSTR *lplpszAcceptTypes, _In_ DWORD dwFlags, _In_ DWORD_PTR dwContext);
    参数
    hConnect:由InternetConnect返回的句柄。
    lpszVerb:一个指向某个包含在请求中要用的动词的字符串指针。如果为NULL,则使用“GET”。
    lpszObjectName:一个指向某个包含特殊动词的目标对象的字符串的指针。通常为文件名称、可执行模块或者查找标识符。
    lpszVersion:一个指向以null结尾的字符串的指针,该字符串包含在请求中使用的HTTP版本,Internet Explorer中的设置将覆盖该参数中指定的值。如果此参数为NULL,则该函数使用1.1或1.0的HTTP版本,这取决于Internet Explorer设置的值。
    lpszReferer:一个指向指定了包含着所需的URL (pstrObjectName)的文档地址(URL)的指针。如果为NULL,则不指定HTTP头。
    lplpszAcceptTypes:一个指向某空终止符的字符串的指针,该字符串表示客户接受的内容类型。如果该字符串为NULL,服务器认为客户接受“text/*”类型的文档 (也就是说,只有纯文本文档,并且不是图片或其它二进制文件)。内容类型与CGI变量CONTENT_TYPE相同,该变量确定了要查询的含有相关信息的数据的类型,如HTTP POST和PUT。
    dwFlags:dwFlags的值可以是下面一个或者多个。



    价值
    说明




    INTERNET_FLAG_DONT_CACHE
    不缓存的数据,在本地或在任何网关。 相同的首选值INTERNET_FLAG_NO_CACHE_WRITE。


    INTERNET_FLAG_EXISTING_CONNECT
    如果可能的话,重用现有的连接到每个服务器请求新的请求而产生的InternetOpenUrl创建一个新的会话。 这个标志是有用的,只有对FTP连接,因为FTP是唯一的协议,通常在同一会议执行多个操作。 在Win 32 API的缓存一个单一的Internet连接句柄为每个HINTERNET处理产生的InternetOpen。


    INTERNET_FLAG -超链接
    强制重载如果没有到期的时间也没有最后修改时间从服务器在决定是否加载该项目从网络返回。


    INTERNET_FLAG_IGNORE_CERT_CN_INVALID
    禁用的Win32上网功能的SSL /厘为基础的打击是从给定的请求服务器返回的主机名称证书检查。 Win32的上网功能用来对付证书由匹配主机名和HTTP请求一个简单的通配符规则比较简单的检查。


    INTERNET_FLAG_IGNORE_CERT_DATE_INVALID
    禁用的Win32上网功能的SSL /厘为基础的HTTP请求适当的日期,证书的有效性检查。


    INTERNET_FLAG_IGNORE_REDIRECT_TO_HTTP
    禁用的Win32上网功能能够探测到这种特殊类型的重定向。 当使用此标志,透明的Win32上网功能允许对HTTP重定向的URL从HTTPS。


    INTERNET_FLAG_IGNORE_REDIRECT_TO_HTTPS
    禁用的Win32上网功能能够探测到这种特殊类型的重定向。 当使用此标志,透明的Win32上网功能允许从HTTP重定向到HTTPS网址。


    INTERNET_FLAG_KEEP_CONNECTION
    使用保持活动语义,如果有的话,给HTTP请求连接。 这个标志是必需的微软网络(MSN),NT LAN管理器(NTLM)和其他类型的身份验证。


    INTERNET_FLAG_MAKE_PERSISTENT
    不再支持。


    INTERNET_FLAG_MUST_CACHE_REQUEST
    导致一个临时文件如果要创建的文件不能被缓存。 相同的首选值INTERNET_FLAG_NEED_FILE。


    INTERNET_FLAG_NEED_FILE
    导致一个临时文件如果要创建的文件不能被缓存。


    INTERNET_FLAG_NO_AUTH
    不尝试HTTP请求身份验证自动。


    INTERNET_FLAG_NO_AUTO_REDIRECT
    不自动处理HTTP请求重定向只。


    INTERNET_FLAG_NO_CACHE_WRITE
    不缓存的数据,在本地或在任何网关。


    INTERNET_FLAG_NO_COOKIES
    不会自动添加Cookie标头的请求,并不会自动添加返回的Cookie的HTTP请求的Cookie数据库。


    INTERNET_FLAG_NO_UI
    禁用cookie的对话框。


    INTERNET_FLAG_PASSIVE
    使用被动FTP语义FTP文件和目录。


    INTERNET_FLAG_RAW_DATA
    返回一个数据WIN32_FIND_DATA结构时,FTP目录检索信息。 如果这个标志,或者未指定代理的电话是通过一个CERN,InternetOpenUrl返回的HTML版本的目录。


    INTERNET_FLAG_PRAGMA_NOCACHE
    强制要求被解决的原始服务器,即使在代理缓存的副本存在。


    INTERNET_FLAG_READ_PREFETCH
    该标志目前已停用。


    INTERNET_FLAG_RELOAD
    从导线获取数据,即使是一个本地缓存。


    INTERNET_FLAG_RESYNCHRONIZE
    重整HTTP资源,如果资源已被修改自上一次被下载。 所有的FTP资源增值。


    INTERNET_FLAG_SECURE
    请确保在使用SSL或PCT线交易。 此标志仅适用于HTTP请求。



    dwContext:OpenRequest操作的上下文标识符。

    4. InternetReadFile介绍
    函数声明
    BOOL InternetReadFile( __in HINTERNET hFile,__out LPVOID lpBuffer,__in DWORD dwNumberOfBytesToRead,__out LPDWORD lpdwNumberOfBytesRead);
    参数

    hFile[in]
    由InternetOpenUrl,FtpOpenFile, 或HttpOpenRequest函数返回的句柄.
    lpBuffer[out]
    缓冲器指针
    dwNumberOfBytesToRead[in]
    欲读数据的字节量。
    lpdwNumberOfBytesRead[out]
    接收读取字节量的变量。该函数在做任何工作或错误检查之前都设置该值为零

    返回值成功:返回TRUE,失败,返回FALSE

    程序设计原理该部分讲解下程序设计的原理以及实现的流程,让大家有个宏观的认识。原理是:

    首先,使用 InternetCrackUrl 函数分解URL,从URL中提取网站的域名、路径以及URL的附加信息等。关于 InternetCrackUrl 分解URL的介绍和实现,可以参考本站上的的 “URL分解之InternetCrackUrl” 这篇文章
    使用 InternetOpen 建立会话,获取会话句柄
    使用 InternetConnect 与网站建立连接,获取连接句柄
    设置HTTP的访问标志,使用 HttpOpenRequest 打开HTTP的“GET”请求
    使用 HttpSendRequest 发送访问请求
    根据返回的Response Header的数据中,获取将要接收数据的长度
    使用 InternetReadFile 接收数据
    关闭句柄,释放资源

    其中,上面的 8 个步骤中,要注意的就是第 6 步,获取返回的数据长度,是从响应信息头中的获取“Content-Length: ”(注意有个空格)这个字段的数据。
    编程实现1. 导入WinInet库#include <WinInet.h>#pragma comment(lib, "WinInet.lib")
    2. HTTP文件下载编程实现// 数据下载// 输入:下载数据的URL路径// 输出:下载数据内容、下载数据内容长度BOOL Http_Download(char *pszDownloadUrl, BYTE **ppDownloadData, DWORD *pdwDownloadDataSize){ // INTERNET_SCHEME_HTTPS、INTERNET_SCHEME_HTTP、INTERNET_SCHEME_FTP等 char szScheme[MAX_PATH] = { 0 }; char szHostName[MAX_PATH] = { 0 }; char szUserName[MAX_PATH] = { 0 }; char szPassword[MAX_PATH] = { 0 }; char szUrlPath[MAX_PATH] = { 0 }; char szExtraInfo[MAX_PATH] = { 0 }; ::RtlZeroMemory(szScheme, MAX_PATH); ::RtlZeroMemory(szHostName, MAX_PATH); ::RtlZeroMemory(szUserName, MAX_PATH); ::RtlZeroMemory(szPassword, MAX_PATH); ::RtlZeroMemory(szUrlPath, MAX_PATH); ::RtlZeroMemory(szExtraInfo, MAX_PATH); // 分解URL if (FALSE == Http_UrlCrack(pszDownloadUrl, szScheme, szHostName, szUserName, szPassword, szUrlPath, szExtraInfo, MAX_PATH)) { return FALSE; } // 数据下载 HINTERNET hInternet = NULL; HINTERNET hConnect = NULL; HINTERNET hRequest = NULL; DWORD dwOpenRequestFlags = 0; BOOL bRet = FALSE; unsigned char *pResponseHeaderIInfo = NULL; DWORD dwResponseHeaderIInfoSize = 2048; BYTE *pBuf = NULL; DWORD dwBufSize = 64 * 1024; BYTE *pDownloadData = NULL; DWORD dwDownloadDataSize = 0; DWORD dwRet = 0; DWORD dwOffset = 0; do { // 建立会话 hInternet = ::InternetOpen("WinInetGet/0.1", INTERNET_OPEN_TYPE_PRECONFIG, NULL, NULL, 0); if (NULL == hInternet) { Http_ShowError("InternetOpen"); break; } // 建立连接 hConnect = ::InternetConnect(hInternet, szHostName, INTERNET_DEFAULT_HTTP_PORT, szUserName, szPassword, INTERNET_SERVICE_HTTP, 0, 0); if (NULL == hConnect) { Http_ShowError("InternetConnect"); break; } // 打开并发送HTTP请求 dwOpenRequestFlags = INTERNET_FLAG_IGNORE_REDIRECT_TO_HTTP | INTERNET_FLAG_KEEP_CONNECTION | INTERNET_FLAG_NO_AUTH | INTERNET_FLAG_NO_COOKIES | INTERNET_FLAG_NO_UI; if (0 < ::lstrlen(szExtraInfo)) { // 注意此处的连接 ::lstrcat(szUrlPath, szExtraInfo); } hRequest = ::HttpOpenRequest(hConnect, "GET", szUrlPath, NULL, NULL, NULL, dwOpenRequestFlags, 0); if (NULL == hRequest) { Http_ShowError("HttpOpenRequest"); break; } // 发送请求 bRet = ::HttpSendRequest(hRequest, NULL, 0, NULL, 0); if (FALSE == bRet) { Http_ShowError("HttpSendRequest"); break; } // 接收响应的报文信息头(Get Response Header) pResponseHeaderIInfo = new unsigned char[dwResponseHeaderIInfoSize]; if (NULL == pResponseHeaderIInfo) { break; } ::RtlZeroMemory(pResponseHeaderIInfo, dwResponseHeaderIInfoSize); bRet = ::HttpQueryInfo(hRequest, HTTP_QUERY_RAW_HEADERS_CRLF, pResponseHeaderIInfo, &dwResponseHeaderIInfoSize, NULL); if (FALSE == bRet) { Http_ShowError("HttpQueryInfo"); break; }#ifdef _DEBUG printf("[HTTP_Download_ResponseHeaderIInfo]\n\n%s\n\n", pResponseHeaderIInfo);#endif // 从 中字段 "Content-Length: "(注意有个空格) 获取数据长度 bRet = Http_GetContentLength((char *)pResponseHeaderIInfo, &dwDownloadDataSize); if (FALSE == bRet) { break; } // 接收报文主体内容(Get Response Body) pBuf = new BYTE[dwBufSize]; if (NULL == pBuf) { break; } pDownloadData = new BYTE[dwDownloadDataSize]; if (NULL == pDownloadData) { break; } ::RtlZeroMemory(pDownloadData, dwDownloadDataSize); do { ::RtlZeroMemory(pBuf, dwBufSize); bRet = ::InternetReadFile(hRequest, pBuf, dwBufSize, &dwRet); if (FALSE == bRet) { Http_ShowError("InternetReadFile"); break; } ::RtlCopyMemory((pDownloadData + dwOffset), pBuf, dwRet); dwOffset = dwOffset + dwRet; } while (dwDownloadDataSize > dwOffset); // 返回数据 *ppDownloadData = pDownloadData; *pdwDownloadDataSize = dwDownloadDataSize; } while (FALSE); // 关闭 释放 if (NULL != pBuf) { delete[]pBuf; pBuf = NULL; } if (NULL != pResponseHeaderIInfo) { delete[]pResponseHeaderIInfo; pResponseHeaderIInfo = NULL; } if (NULL != hRequest) { ::InternetCloseHandle(hRequest); hRequest = NULL; } if (NULL != hConnect) { ::InternetCloseHandle(hConnect); hConnect = NULL; } if (NULL != hInternet) { ::InternetCloseHandle(hInternet); hInternet = NULL; } return bRet;}
    程序测试在main函数中,调用上述封装好的函数,下载文件进行测试。
    main函数为:
    int _tmain(int argc, _TCHAR* argv[]){ char szHttpDownloadUrl[] = "http://www.demongan.com/source/ccc/dasanxia/520.zip"; BYTE *pHttpDownloadData = NULL; DWORD dwHttpDownloadDataSize = 0; // HTTP下载 if (FALSE == Http_Download(szHttpDownloadUrl, &pHttpDownloadData, &dwHttpDownloadDataSize)) { return 1; } // 将下载数据保存成文件 Http_SaveToFile("http_downloadsavefile.zip", pHttpDownloadData, dwHttpDownloadDataSize); // 释放内存 delete []pHttpDownloadData; pHttpDownloadData = NULL; system("pause"); return 0;}
    测试结果:
    根据返回的Response Header知道,成功下载22761460字节大小的数据。

    查看目录,有22228KB大小的“http_downloadsavefile.zip”文件成功生成,所以,数据下载成功。

    总结基于WinInet库的HTTP下载文件原理并不复杂,但是,因为涉及较多的API,每个API的执行都需要依靠上一个API成功执行返回的数据。所以,要仔细检查。如果出错,也要耐心调试,根据返回的错误码,结合程序前后部分的代码,仔细分析原因。
    参考参考自《Windows黑客编程技术详解》一书
    2 留言 2018-12-20 17:46:07 奖励13点积分
  • 基于python构建搜索引擎系列——(一)简介 精华

    我们上网用得最多的一项服务应该是搜索,不管大事小情,都喜欢百度一下或谷歌一下,那么百度和谷歌是怎样从浩瀚的网络世界中快速找到你想要的信息呢,这就是搜索引擎的艺术,属于信息检索的范畴。
    这学期学习了《现代信息检索》课程,使用的是Stanford的教材Introduction to Information Retrieval,网上有电子版,大家可以参考。
    本课程的大作业是完成一个新闻搜索引擎,要求是这样的:定向采集3-4个新闻网站,实现这些网站信息的抽取、索引和检索。网页数目不少于10万条。能按相关度、时间和热度(需要自己定义)进行排序,能实现相似新闻的自动聚类。
    截止日期12月31日,我们已经在规定时间完成了该系统,自认为检索效果不错,所以在此把过程记录如下,欢迎讨论。
    网上有很多开源的全文搜索引擎,比如Lucene、Sphinx、Whoosh等,都提供了很好的API,开发者只需要调用相关接口就可以实现一个全功能的搜索引擎。不过既然学习了IR这门课,自然要把相关技术实践一下,所以我们打算自己实现一个搜索引擎。
    这是简介部分,主要介绍整个搜索引擎的思路和框架。

    上图为本搜索引擎的框架图。首先爬虫程序从特定的几个新闻网站抓取新闻数据,然后过滤网页中的图片、视频、广告等无关元素,抽取新闻的主体内容,得到结构化的xml数据。然后一方面使用内存式单遍扫描索引构建方法(SPIMI)构建倒排索引,供检索模型使用;另一方面根据向量空间模型计算两两新闻之间的余弦相似度,供推荐模块使用。最后利用概率检索模型中的BM25公式计算给定关键词下的文档相关性评分,BM25打分结合时间因素得到热度评分,根据评分给出排序结果。
    在后续博文中,我会详细介绍每个部分的实现。
    使用方法
    安装python 3.4+环境
    安装lxml html解析器,命令为pip install lxml
    安装jieba分词组件,命令为pip install jieba
    安装Flask Web框架,命令为pip install Flask
    进入web文件夹,运行main.py文件
    打开浏览器,访问 http://127.0.0.1:5000 输入关键词开始测试

    如果想抓取最新新闻数据并构建索引,一键运行./code/setup.py,再按上面的方法测试。
    本文转载自:http://bitjoy.net/2016/01/04/introduction-to-building-a-search-engine-1
    1 留言 2019-05-26 11:34:24 奖励12点积分
  • 高德底图 根据行政区域名 加载边界到地图中(JS)

    高德底图 根据行政区域名 加载边界到地图中(JS)
    代码:
    function map_map1(place){ //初始化地图对象,加载地图 var map = new AMap.Map("map", { resizeEnable: true, center: [117.000923, 36.675807], zoom: 6 }); var district = null; var polygons=[]; //加载行政区划插件 if(!district){ //实例化DistrictSearch var opts = { subdistrict: 0, //获取边界不需要返回下级行政区 extensions: 'all', //返回行政区边界坐标组等具体信息 level: 'district' //查询行政级别为 市 }; } district = new AMap.DistrictSearch(opts); //行政区查询 district.setLevel('district'); district.search(place, function(status, result) { map.remove(polygons)//清除上次结果 polygons = []; var bounds = result.districtList[0].boundaries; if (bounds) { for (var i = 0, l = bounds.length; i < l; i++) { //生成行政区划polygon var polygon = new AMap.Polygon({ strokeWeight: 1, path: bounds[i], fillOpacity: 0.4, fillColor: '#80d8ff', strokeColor: '#0091ea' }); polygons.push(polygon); } } map.add(polygons) map.setFitView(polygons);//视口自适应 });};
    0 留言 2019-05-22 22:57:53 奖励3点积分
  • 枚举并删除系统上Minifilter回调

    背景我们学习内核 Rootkit 编程,那么肯定会接触到各种无 HOOK 回调函数的设置,这些回调函数都是官方为我们做好的接口,我们直接调用就好。这些回调使用方便,运行在底层,功能强大,而且非常稳定。很多杀软、游戏保护等就是设置这些回调,实现对计算机的监控的。
    既然可以设置回调,自然也可以删除回调。如果是自己程序设置的回调,当然可以很容易删除。但是,我们要做的是要枚举系统上存在的回调,不管是不是自己程序创建的,然后,并对这些回调进行删除,使其失效。
    本文要介绍的是枚举并删除系统上 Minifilter 回调,支持 32 位和 64 位、Win7 到 Win10 全平台系统。现在,我把实现的过程和原理整理成文档,分享给大家。
    函数介绍FltEnumerateFilters 函数
    列举系统中所有注册的 Minifilter 驱动程序。
    函数声明
    NTSTATUS FltEnumerateFilters( _Out_ PFLT_FILTER *FilterList, _In_ ULONG FilterListSize, _Out_ PULONG NumberFiltersReturned);
    参数

    FilterList [out]指向调用者分配的缓冲区的指针,该缓冲区接收不透明的过滤器指针数组。此参数是可选的,如果FilterListSize参数的值为零,则该参数可以为NULL。如果FilterListSize在输入上为零,并且FilterList为NULL,则NumberFiltersReturned参数将接收找到的 Minifilter 驱动程序的数量。FilterListSize [in]FilterList参数指向的缓冲区可以容纳的不透明过滤器指针数。该参数是可选的,可以为零。如果FilterListSize在输入上为零,并且FilterList为NULL,则NumberFiltersReturned参数将接收找到的 Minifilter 驱动程序的数量。NumberFiltersReturned [out]指向调用者分配的变量,该变量接收FilterList参数指向的数组中返回的不透明过滤器指针数。如果FilterListSize参数值太小,并且FilterList在输入上不为NULL,FltEnumerateFilters将返回STATUS_BUFFER_TOO_SMALL,并将NumberFiltersReturn设置为指向找到的minifilter驱动程序的数量。此参数是必需的,不能为NULL。
    返回值

    成功,则返回 STATUS_SUCCESS;失败,则返回其它 NTSTATUS 错误码。

    实现原理枚举 Minifilter 驱动程序的回调,并不像枚举进程回调、线程回调、模块加载回调、注册表回调、对象回调那样,需要我们自己逆向寻找数组或是链表的地址,因为,Minifilter 驱动程序提供了 FltEnumerateFilters 内核函数给我们,用来获取系统上所有注册成功的 Minifilter 回调。
    FltEnumerateFilters 函数可以获取系统上所有注册成功的 Minifilter 的过滤器对象指针数组 PFLT_FILTER *。PFLT_FILTER 数据类型在不同的系统上,它的定义是不同的。下面是我们使用 WinDbg 获取 Win10 x64 上的结构定义:
    lkd> dt fltmgr!_FLT_FILTER +0x000 Base : _FLT_OBJECT +0x030 Frame : Ptr64 _FLTP_FRAME +0x038 Name : _UNICODE_STRING +0x048 DefaultAltitude : _UNICODE_STRING +0x058 Flags : _FLT_FILTER_FLAGS +0x060 DriverObject : Ptr64 _DRIVER_OBJECT +0x068 InstanceList : _FLT_RESOURCE_LIST_HEAD +0x0e8 VerifierExtension : Ptr64 _FLT_VERIFIER_EXTENSION +0x0f0 VerifiedFiltersLink : _LIST_ENTRY +0x100 FilterUnload : Ptr64 long +0x108 InstanceSetup : Ptr64 long +0x110 InstanceQueryTeardown : Ptr64 long +0x118 InstanceTeardownStart : Ptr64 void +0x120 InstanceTeardownComplete : Ptr64 void +0x128 SupportedContextsListHead : Ptr64 _ALLOCATE_CONTEXT_HEADER +0x130 SupportedContexts : [7] Ptr64 _ALLOCATE_CONTEXT_HEADER +0x168 PreVolumeMount : Ptr64 _FLT_PREOP_CALLBACK_STATUS +0x170 PostVolumeMount : Ptr64 _FLT_POSTOP_CALLBACK_STATUS +0x178 GenerateFileName : Ptr64 long +0x180 NormalizeNameComponent : Ptr64 long +0x188 NormalizeNameComponentEx : Ptr64 long +0x190 NormalizeContextCleanup : Ptr64 void +0x198 KtmNotification : Ptr64 long +0x1a0 SectionNotification : Ptr64 long +0x1a8 Operations : Ptr64 _FLT_OPERATION_REGISTRATION +0x1b0 OldDriverUnload : Ptr64 void +0x1b8 ActiveOpens : _FLT_MUTEX_LIST_HEAD +0x208 ConnectionList : _FLT_MUTEX_LIST_HEAD +0x258 PortList : _FLT_MUTEX_LIST_HEAD +0x2a8 PortLock : _EX_PUSH_LOCK
    其中,成员 Operations 就存储着 Minifilter 过滤器对象对应的回调信息,数据类型是 FLT_OPERATION_REGISTRATION,该结构是固定的。在头文件 fltKernel.h 里有 FLT_OPERATION_REGISTRATION 结构体定义:
    typedef struct _FLT_OPERATION_REGISTRATION { UCHAR MajorFunction; FLT_OPERATION_REGISTRATION_FLAGS Flags; PFLT_PRE_OPERATION_CALLBACK PreOperation; PFLT_POST_OPERATION_CALLBACK PostOperation; PVOID Reserved1;} FLT_OPERATION_REGISTRATION, *PFLT_OPERATION_REGISTRATION;
    从结构体里面可知,从中可获取 Minifilter 驱动程序的消息类型 MajorFunction,操作前回调函数地址 PreOperation,操作后回调函数地址 PostOperation 等信息。
    所以,遍历系统上所有的 Minifilter 回调,原理就是:

    调用 FltEnumerateFilters 内核函数获取系统上注册成功的 Minifilter 驱动程序的过滤器对象指针数组 PFLT_FILTER *。然后,我们遍历过滤器对象指针 PFLT_FILTER,从中可以获取 Operations 成员的数据,数据类型为 FLT_OPERATION_REGISTRATION,可以从中获取 Minifilter 回调信息。
    要注意的是,由于不同的系统,FLT_FILTER 数据结构的定义都不相同,所以成员 Operations 在数据结构中的偏移也是不固定的。下面是我使用 WinDbg 逆向各个系统中 FLT_FILTER 的数据结构定义,总结出来的 Operations 偏移大小:




    Win 7
    Win 8.1
    Win 10




    32 位
    0xCC
    0xD4
    0xE4


    64 位
    0x188
    0x198
    0x1A8



    删除回调我们可以通过上述介绍的方法,枚举系统中的回调函数。其中,我们不能调用 FltUnregisterFilter 函数删除 Minifilter 回调,因为微软规定 FltUnregisterFilter 函数只能在 Minifilter 自身的驱动程序中调用,不能在其它的驱动程序中调用使用。所以,要删除回调函数可以有 2 种方式。

    直接修改 FLT_OPERATION_REGISTRATION 数据结构中的操作前回调函数和操作后回调函数的地址数据,使其指向我们自己定义的空回调函数地址。这样,当触发回调函数的时候,执行的是我们自己的空回调函数。修改回调函数的前几字节内存数据,写入直接返回指令 RET,不进行任何操作。
    编码实现声明头文件 fltKernel.h:
    #include <fltKernel.h>
    导入库文件 FltMgr.lib:
    右击项目“属性” --> 链接器 --> 输入 --> 在“附加依赖项”中添加 FltMgr.lib。
    遍历 Minifilter 回调// 遍历回调BOOLEAN EnumCallback(){ NTSTATUS status = STATUS_SUCCESS; ULONG ulFilterListSize = 0; PFLT_FILTER *ppFilterList = NULL; ULONG i = 0; LONG lOperationsOffset = 0; PFLT_OPERATION_REGISTRATION pFltOperationRegistration = NULL; // 获取 Minifilter 过滤器Filter 的数量 FltEnumerateFilters(NULL, 0, &ulFilterListSize); // 申请内存 ppFilterList = (PFLT_FILTER *)ExAllocatePool(NonPagedPool, ulFilterListSize *sizeof(PFLT_FILTER)); if (NULL == ppFilterList) { DbgPrint("ExAllocatePool Error!\n"); return FALSE; } // 获取 Minifilter 中所有过滤器Filter 的信息 status = FltEnumerateFilters(ppFilterList, ulFilterListSize, &ulFilterListSize); if (!NT_SUCCESS(status)) { DbgPrint("FltEnumerateFilters Error![0x%X]\n", status); return FALSE; } DbgPrint("ulFilterListSize=%d\n", ulFilterListSize); // 获取 PFLT_FILTER 中 Operations 偏移 lOperationsOffset = GetOperationsOffset(); if (0 == lOperationsOffset) { DbgPrint("GetOperationsOffset Error\n"); return FALSE; } // 开始遍历 Minifilter 中各个过滤器Filter 的信息 __try { for (i = 0; i < ulFilterListSize; i++) { // 获取 PFLT_FILTER 中 Operations 成员地址 pFltOperationRegistration = (PFLT_OPERATION_REGISTRATION)(*(PVOID *)((PUCHAR)ppFilterList[i] + lOperationsOffset)); __try { // 同一过滤器下的回调信息 DbgPrint("-------------------------------------------------------------------------------\n"); while (IRP_MJ_OPERATION_END != pFltOperationRegistration->MajorFunction) { if (IRP_MJ_MAXIMUM_FUNCTION > pFltOperationRegistration->MajorFunction) // MajorFunction ID Is: 0~27 { // 显示 DbgPrint("[Filter=%p]IRP=%d, PreFunc=0x%p, PostFunc=0x%p\n", ppFilterList[i], pFltOperationRegistration->MajorFunction, pFltOperationRegistration->PreOperation, pFltOperationRegistration->PostOperation); } // 获取下一个消息回调信息 pFltOperationRegistration = (PFLT_OPERATION_REGISTRATION)((PUCHAR)pFltOperationRegistration + sizeof(FLT_OPERATION_REGISTRATION)); } DbgPrint("-------------------------------------------------------------------------------\n"); } __except (EXCEPTION_EXECUTE_HANDLER) { DbgPrint("[2_EXCEPTION_EXECUTE_HANDLER]\n"); } } } __except (EXCEPTION_EXECUTE_HANDLER) { DbgPrint("[1_EXCEPTION_EXECUTE_HANDLER]\n"); } // 释放内存 ExFreePool(ppFilterList); ppFilterList = NULL; return TRUE;}
    移除 Minifilter 回调// 移除回调NTSTATUS RemoveCallback(PFLT_FILTER pFilter){ LONG lOperationsOffset = 0; PFLT_OPERATION_REGISTRATION pFltOperationRegistration = NULL; // 开始遍历 过滤器Filter 的信息 // 获取 PFLT_FILTER 中 Operations 成员地址 pFltOperationRegistration = (PFLT_OPERATION_REGISTRATION)(*(PVOID *)((PUCHAR)pFilter + lOperationsOffset)); __try { // 同一过滤器下的回调信息 while (IRP_MJ_OPERATION_END != pFltOperationRegistration->MajorFunction) { if (IRP_MJ_MAXIMUM_FUNCTION > pFltOperationRegistration->MajorFunction) // MajorFunction ID Is: 0~27 { // 替换回调函数 pFltOperationRegistration->PreOperation = New_MiniFilterPreOperation; pFltOperationRegistration->PostOperation = New_MiniFilterPostOperation; // 显示 DbgPrint("[Filter=%p]IRP=%d, PreFunc=0x%p, PostFunc=0x%p\n", pFilter, pFltOperationRegistration->MajorFunction, pFltOperationRegistration->PreOperation, pFltOperationRegistration->PostOperation); } // 获取下一个消息回调信息 pFltOperationRegistration = (PFLT_OPERATION_REGISTRATION)((PUCHAR)pFltOperationRegistration + sizeof(FLT_OPERATION_REGISTRATION)); } } __except (EXCEPTION_EXECUTE_HANDLER) { DbgPrint("[EXCEPTION_EXECUTE_HANDLER]\n"); } return STATUS_SUCCESS;}
    获取 Operations 偏移// 获取 Operations 偏移LONG GetOperationsOffset(){ RTL_OSVERSIONINFOW osInfo = { 0 }; LONG lOperationsOffset = 0; // 获取系统版本信息, 判断系统版本 RtlGetVersion(&osInfo); if (6 == osInfo.dwMajorVersion) { if (1 == osInfo.dwMinorVersion) { // Win7#ifdef _WIN64 // 64 位 // 0x188 lOperationsOffset = 0x188;#else // 32 位 // 0xCC lOperationsOffset = 0xCC;#endif } else if (2 == osInfo.dwMinorVersion) { // Win8#ifdef _WIN64 // 64 位#else // 32 位#endif } else if (3 == osInfo.dwMinorVersion) { // Win8.1#ifdef _WIN64 // 64 位 // 0x198 lOperationsOffset = 0x198;#else // 32 位 // 0xD4 lOperationsOffset = 0xD4;#endif } } else if (10 == osInfo.dwMajorVersion) { // Win10#ifdef _WIN64 // 64 位 // 0x1A8 lOperationsOffset = 0x1A8;#else // 32 位 // 0xE4 lOperationsOffset = 0xE4;#endif } return lOperationsOffset;}
    程序测试在 Win7 32 位系统下,驱动程序正常执行:

    在 Win8.1 32 位系统下,驱动程序正常执行:

    在 Win10 32 位系统下,驱动程序正常执行:

    在 Win7 64 位系统下,驱动程序正常执行:

    在 Win8.1 64 位系统下,驱动程序正常执行:

    在 Win10 64 位系统下,驱动程序正常执行:

    总结我们可以调用 FltEnumerateFilters 来获取系统上所有 Minifilter 驱动程序的过滤器对象,并从中 PFLT_FILTER 经过一定的偏移获取 Operations 成员数据,里面存储着回调信息。其中,不同统统的 FLT_FILTER 定义都不同,所以,Operations 成员的偏移也不相同。大家也不用记忆这些偏移大小,如果需要用到,可以随时使用 WinDbg 来进行逆向查看就好。
    删除回调常用就有 2 种方式,自己根据需要选择一种使用即可。
    参考参考自《Windows黑客编程技术详解》一书
    1 留言 2019-05-20 15:55:10 奖励16点积分
  • 基于ObRegisterCallbacks实现的线程和进程监控及其保护

    背景要实现监控系统线程和进程,并实现对指定线程和进程的保护,在 32 位系统上可以使用 HOOK 技术,HOOK 相关的函数来实现。但是,到了 64 位平台上,就不能继续按常规的 HOOK 方法去实现了。
    好在 Windows 给我们提供了 ObRegisterCallbacks 内核函数来注册系统回调,可以用来注册系统线程回调,监控系统的线程创建、退出等情况,而且还能进行控制;也可以用来注册系统进程回调,可以监控系统的进程创建、退出等情况,而且也能进行控制。这使得我们实现保护指定线程、进程不被结束,提供了可能。
    现在,我就对程序的实现过程和原理进行整理,形成文档,分享给大家。
    函数介绍ObRegisterCallbacks 函数
    注册线程、进程和桌面句柄操作的回调函数。
    函数声明
    NTSTATUS ObRegisterCallbacks( _In_ POB_CALLBACK_REGISTRATION CallBackRegistration, _Out_ PVOID *RegistrationHandle);
    参数

    CallBackRegistration [in]指向指定回调例程列表和其他注册信息的OB_CALLBACK_REGISTRATION结构的指针。RegistrationHandle [out]指向变量的指针,该变量接收一个标识已注册的回调例程集合的值。 调用者将此值传递给ObUnRegisterCallbacks例程以注销该回调集。
    返回值

    成功,则返回 STATUS_SUCCESS,否则,返回其它 NTSTATUS 错误码。
    备注

    驱动程序必须在卸载之前注销所有回调例程。 您可以通过调用ObUnRegisterCallbacks例程来注销回调例程。

    OB_CALLBACK_REGISTRATION 结构体
    typedef struct _OB_CALLBACK_REGISTRATION { USHORT Version; USHORT OperationRegistrationCount; UNICODE_STRING Altitude; PVOID RegistrationContext; OB_OPERATION_REGISTRATION *OperationRegistration;} OB_CALLBACK_REGISTRATION, *POB_CALLBACK_REGISTRATION;
    成员

    Version请求的对象回调注册版本。 驱动程序应指定OB_FLT_REGISTRATION_VERSION。OperationRegistrationCountOperationRegistration数组中的条目数。Altitude指定驱动程序Altitude的Unicode字符串。一定要存在,不能置为空 NULL,可以任意指定。RegistrationContext当回调例程运行时,系统将RegistrationContext值传递给回调例程。 该值的含义是由驱动程序自定义的。OperationRegistration指向OB_OPERATION_REGISTRATION结构数组的指针。 每个结构指定ObjectPreCallback和ObjectPostCallback回调例程以及调用例程的操作类型。

    OB_OPERATION_REGISTRATION 结构体
    typedef struct _OB_OPERATION_REGISTRATION { POBJECT_TYPE *ObjectType; OB_OPERATION Operations; POB_PRE_OPERATION_CALLBACK PreOperation; POB_POST_OPERATION_CALLBACK PostOperation;} OB_OPERATION_REGISTRATION, *POB_OPERATION_REGISTRATION;
    成员

    ObjectType指向触发回调例程的对象类型的指针。 指定以下值之一:用于进程句柄操作的PsProcessType线程句柄操作的PsThreadType用于桌面句柄操作的ExDesktopObjectType。 此值在Windows 10中受支持,而不在早期版本的操作系统中。Operations指定以下一个或多个标志:OB_OPERATION_HANDLE_CREATE一个新的进程,线程或桌面句柄已被打开或将被打开。OB_OPERATION_HANDLE_DUPLICATE进程,线程或桌面句柄已被或将被复制。PreOperation指向ObjectPreCallback例程的指针。 在请求的操作发生之前,系统调用此例程。PostOperation指向ObjectPostCallback例程的指针。 在请求的操作发生后,系统调用此例程。

    IoThreadToProcess 函数
    返回指向指定线程的进程的指针。
    函数声明
    PEPROCESS IoThreadToProcess( _In_ PETHREAD Thread);
    参数

    Thread[in]要返回进程的指定线程对象。
    返回值

    返回线程对象对应的进程对象的指针。

    PsGetProcessId 函数
    返回与指定进程关联的进程标识符(进程ID)。
    函数声明
    HANDLE PsGetProcessId( _In_ PEPROCESS Process);
    参数

    Process[in]
    指向进程对象结构的指针。

    返回值

    返回进程ID。

    实现原理破解 ObRegisterCallbacks 函数的使用限制第一种方法在讲解怎么使用 ObRegisterCallbacks 函数来注册系统线程、进程回调的之前,先来讲解下 Windows 对这个函数做的限制:驱动程序必须有数字签名才能使用此函数。不过国外的黑客对此限制很不满,通过逆向 ObRegisterCallbacks,找到了破解这个限制的方法。经研究,内核通过 MmVerifyCallbackFunction 验证此回调是否合法, 但此函数只是简单的验证了一下 DriverObject->DriverSection->Flags 的值是不是为 0x20:
    nt!MmVerifyCallbackFunction+0x75: fffff800`01a66865 f6406820 test byte ptr [rax+68h],20h fffff800`01a66869 0f45fd cmovne edi,ebp
    所以破解方法非常简单,只要把 DriverObject->DriverSection->Flags 的值按位或 0x20 即可。其中,DriverSection 是指向 LDR_DATA_TABLE_ENTRY 结构的值,要注意该结构在 32 位和 64 位系统下的定义。
    // 注意32位与64位的对齐大小#ifndef _WIN64 #pragma pack(1) #endiftypedef struct _LDR_DATA_TABLE_ENTRY{ LIST_ENTRY InLoadOrderLinks; LIST_ENTRY InMemoryOrderLinks; LIST_ENTRY InInitializationOrderLinks; PVOID DllBase; PVOID EntryPoint; ULONG SizeOfImage; UNICODE_STRING FullDllName; UNICODE_STRING BaseDllName; ULONG Flags; USHORT LoadCount; USHORT TlsIndex; union { LIST_ENTRY HashLinks; struct { PVOID SectionPointer; ULONG CheckSum; }; }; union { ULONG TimeDateStamp; PVOID LoadedImports; }; PVOID EntryPointActivationContext; PVOID PatchInformation; LIST_ENTRY ForwarderLinks; LIST_ENTRY ServiceTagLinks; LIST_ENTRY StaticLinks;} LDR_DATA_TABLE_ENTRY, *PLDR_DATA_TABLE_ENTRY;#ifndef _WIN64 #pragma pack()#endif
    第二种方法使用此函数, 一定要设置 IMAGE_OPTIONAL_HEADER 中的 DllCharacterisitics 字段设置为:IMAGE_DLLCHARACTERISITICS_FORCE_INTEGRITY 属性,该属性是一个驱动强制签名属性。使用 VS2013 开发环境设置方式是:

    右击项目,选择属性;选中配置属性中的链接器,点击命令行;在其它选项中输入: /INTEGRITYCHECK 表示设置; /INTEGRITYCHECK:NO 表示不设置。
    这样,设置之后,驱动程序必须要进行驱动签名才可正常运行!
    调用 ObRegisterCallbacks 注册线程回调以及进程回调我们从上面的函数介绍中,可以知道大概的实现流程:

    首先,在调用 ObRegisterCallbacks 函数注册系统回调之前,我们要先对结构体 OB_CALLBACK_REGISTRATION 进行初始化。设置回调的版本 Version;设置回调的 Altitude,任意指定;设置回调函数的数量 OperationRegistrationCount;设置回调函数 OperationRegistration。其中,OperationRegistration 是一个 OB_OPERATION_REGISTRATION 结构体数组,里面存储着回调对象的类型、操作类型以及回调函数,它的数量要和 OperationRegistrationCount 对应。然后,再调用 ObRegisterCallbacks 进行注册,并保留系统回调对象句柄。最后,在不使用回调的时候,调用 ObUnRegisterCallbacks 函数传入系统回调对象句柄,删除回调。
    其中,线程回调和进程回调的注册,只有 OB_OPERATION_REGISTRATION 结构体的成员 ObjectType 不同。对于线程,ObjectType 为 PsThreadType;对于进程,ObjectType 为 PsProcessType。其它的操作及其含义,均相同。
    线程、进程回调函数中实现线程、进程保护由于在注册系统回调的时候,我们设置监控线程以及进程的操作类型为:OB_OPERATION_HANDLE_CREATE 和 OB_OPERATION_HANDLE_DUPLICATE。要想实现,拒绝结束线程或者进程的操作,我们只需从操作类型句柄信息中去掉相应的结束线程或者进程的权限即可:
    // OB_OPERATION_HANDLE_CREATE 操作类型pObPreOperationInfo->Parameters->CreateHandleInformation.DesiredAccess = 0;
    // OB_OPERATION_HANDLE_DUPLICATE 操作类型pObPreOperationInfo->Parameters->DuplicateHandleInformation.DesiredAccess = 0;
    那么,我们怎么从线程对象或者进程对象 pObPreOperationInfo->Object 中判断是否是保护线程或者进程呢。对于进程,我们可以调用 PsGetProcessImageFileName 函数,从进程结构对象获取进程名称进行判断。对于线程,我们可以通过 IoThreadToProcess 函数,根据线程结构对象获取相应的进程结构对象,再根据 PsGetProcessImageFileName 函数,从进程结构对象获取进程名称进行判断。
    编码实现破解 ObRegisterCallbacks 的使用限制// 编程方式绕过签名检查BOOLEAN BypassCheckSign(PDRIVER_OBJECT pDriverObject){#ifdef _WIN64 typedef struct _KLDR_DATA_TABLE_ENTRY { LIST_ENTRY listEntry; ULONG64 __Undefined1; ULONG64 __Undefined2; ULONG64 __Undefined3; ULONG64 NonPagedDebugInfo; ULONG64 DllBase; ULONG64 EntryPoint; ULONG SizeOfImage; UNICODE_STRING path; UNICODE_STRING name; ULONG Flags; USHORT LoadCount; USHORT __Undefined5; ULONG64 __Undefined6; ULONG CheckSum; ULONG __padding1; ULONG TimeDateStamp; ULONG __padding2; } KLDR_DATA_TABLE_ENTRY, *PKLDR_DATA_TABLE_ENTRY;#else typedef struct _KLDR_DATA_TABLE_ENTRY { LIST_ENTRY listEntry; ULONG unknown1; ULONG unknown2; ULONG unknown3; ULONG unknown4; ULONG unknown5; ULONG unknown6; ULONG unknown7; UNICODE_STRING path; UNICODE_STRING name; ULONG Flags; } KLDR_DATA_TABLE_ENTRY, *PKLDR_DATA_TABLE_ENTRY;#endif PKLDR_DATA_TABLE_ENTRY pLdrData = (PKLDR_DATA_TABLE_ENTRY)pDriverObject->DriverSection; pLdrData->Flags = pLdrData->Flags | 0x20; return TRUE;}
    注册线程回调// 设置线程回调函数NTSTATUS SetThreadCallbacks(){ NTSTATUS status = STATUS_SUCCESS; OB_CALLBACK_REGISTRATION obCallbackReg = { 0 }; OB_OPERATION_REGISTRATION obOperationReg = { 0 }; RtlZeroMemory(&obCallbackReg, sizeof(OB_CALLBACK_REGISTRATION)); RtlZeroMemory(&obOperationReg, sizeof(OB_OPERATION_REGISTRATION)); // 设置 OB_CALLBACK_REGISTRATION obCallbackReg.Version = ObGetFilterVersion(); obCallbackReg.OperationRegistrationCount = 1; obCallbackReg.RegistrationContext = NULL; RtlInitUnicodeString(&obCallbackReg.Altitude, L"321001"); obCallbackReg.OperationRegistration = &obOperationReg; // 设置 OB_OPERATION_REGISTRATION // Thread 和 Process 的区别所在 obOperationReg.ObjectType = PsThreadType; obOperationReg.Operations = OB_OPERATION_HANDLE_CREATE | OB_OPERATION_HANDLE_DUPLICATE; // Thread 和 Process 的区别所在 obOperationReg.PreOperation = (POB_PRE_OPERATION_CALLBACK)(&ThreadPreCall); // 注册回调函数 status = ObRegisterCallbacks(&obCallbackReg, &g_obThreadHandle); if (!NT_SUCCESS(status)) { DbgPrint("ObRegisterCallbacks Error[0x%X]\n", status); return status; } return status;}
    注册进程回调// 设置进程回调函数NTSTATUS SetProcessCallbacks(){ NTSTATUS status = STATUS_SUCCESS; OB_CALLBACK_REGISTRATION obCallbackReg = { 0 }; OB_OPERATION_REGISTRATION obOperationReg = { 0 }; RtlZeroMemory(&obCallbackReg, sizeof(OB_CALLBACK_REGISTRATION)); RtlZeroMemory(&obOperationReg, sizeof(OB_OPERATION_REGISTRATION)); // 设置 OB_CALLBACK_REGISTRATION obCallbackReg.Version = ObGetFilterVersion(); obCallbackReg.OperationRegistrationCount = 1; obCallbackReg.RegistrationContext = NULL; RtlInitUnicodeString(&obCallbackReg.Altitude, L"321000"); obCallbackReg.OperationRegistration = &obOperationReg; // 设置 OB_OPERATION_REGISTRATION // Thread 和 Process 的区别所在 obOperationReg.ObjectType = PsProcessType; obOperationReg.Operations = OB_OPERATION_HANDLE_CREATE | OB_OPERATION_HANDLE_DUPLICATE; // Thread 和 Process 的区别所在 obOperationReg.PreOperation = (POB_PRE_OPERATION_CALLBACK)(&ProcessPreCall); // 注册回调函数 status = ObRegisterCallbacks(&obCallbackReg, &g_obProcessHandle); if (!NT_SUCCESS(status)) { DbgPrint("ObRegisterCallbacks Error[0x%X]\n", status); return status; } return status;}
    线程回调函数// 线程回调函数OB_PREOP_CALLBACK_STATUS ThreadPreCall(PVOID RegistrationContext, POB_PRE_OPERATION_INFORMATION pObPreOperationInfo){ PEPROCESS pEProcess = NULL; // 判断对象类型 if (*PsThreadType != pObPreOperationInfo->ObjectType) { return OB_PREOP_SUCCESS; } // 获取线程对应的进程 PEPROCESS pEProcess = IoThreadToProcess((PETHREAD)pObPreOperationInfo->Object); // 判断是否市保护PID, 若是, 则拒绝结束线程 if (IsProtectProcess(pEProcess)) { // 操作类型: 创建句柄 if (OB_OPERATION_HANDLE_CREATE == pObPreOperationInfo->Operation) { if (1 == (1 & pObPreOperationInfo->Parameters->CreateHandleInformation.OriginalDesiredAccess)) { pObPreOperationInfo->Parameters->CreateHandleInformation.DesiredAccess = 0; } } // 操作类型: 复制句柄 else if (OB_OPERATION_HANDLE_DUPLICATE == pObPreOperationInfo->Operation) { if (1 == (1 & pObPreOperationInfo->Parameters->DuplicateHandleInformation.OriginalDesiredAccess)) { pObPreOperationInfo->Parameters->DuplicateHandleInformation.DesiredAccess = 0; } } } return OB_PREOP_SUCCESS;}
    进程回调函数// 进程回调函数OB_PREOP_CALLBACK_STATUS ProcessPreCall(PVOID RegistrationContext, POB_PRE_OPERATION_INFORMATION pObPreOperationInfo){ PEPROCESS pEProcess = NULL; // 判断对象类型 if (*PsProcessType != pObPreOperationInfo->ObjectType) { return OB_PREOP_SUCCESS; } // 获取进程结构对象 pEProcess = (PEPROCESS)pObPreOperationInfo->Object; // 判断是否市保护PID, 若是, 则拒绝结束进程 if (IsProtectProcess(pEProcess)) { // 操作类型: 创建句柄 if (OB_OPERATION_HANDLE_CREATE == pObPreOperationInfo->Operation) { if (1 == (1 & pObPreOperationInfo->Parameters->CreateHandleInformation.OriginalDesiredAccess)) { pObPreOperationInfo->Parameters->CreateHandleInformation.DesiredAccess = 0; } } // 操作类型: 复制句柄 else if (OB_OPERATION_HANDLE_DUPLICATE == pObPreOperationInfo->Operation) { if (1 == (1 & pObPreOperationInfo->Parameters->DuplicateHandleInformation.OriginalDesiredAccess)) { pObPreOperationInfo->Parameters->DuplicateHandleInformation.DesiredAccess = 0; } } } return OB_PREOP_SUCCESS;}
    程序测试在 Win7 32 位系统下,驱动程序正常执行:

    在 Win10 64 位系统下,驱动程序正常执行:

    总结其中要注意两个问题:
    一是,破解 ObRegisterCallbacks 函数的使用限制有两种方式,一种是通过编程来解决;一种是通过 VS 开发环境和数字签名来解决。在使用编程方式解决限制的时候,一定要注意 32 位与 64 位下,LDR_DATA_TABLE_ENTRY 结构体的对齐差别。
    二是,OB_CALLBACK_REGISTRATION 中的 Altitude 成员一定要存在,不能置为空 NULL,可以任意指定。
    参考参考自《Windows黑客编程技术详解》一书
    3 留言 2019-02-19 13:04:00 奖励7点积分
  • 基于MuPDF库实现PDF文件转换成PNG格式图片 精华

    背景之所以会接触MuPDF是因为,有位群友在Q群里提问,如何将PDF保存为.PNG图片格式。我一看到这个问题,就蒙了,因为我没有接触过类似的项目或程序。但是,作为一群之主的我,还是要给初学者一个答复的,所以便去网上搜索了相关信息,才了解到有MuPDF开源库的存在。
    MuPDF是一种轻量级的PDF,XPS和电子书阅读器。由各种平台的软件库,命令行工具和查看器组成。支持许多文档格式,如PDF,XPS,OpenXPS,CBZ,EPUB和FictionBook 2。
    后来,自己就根据网上搜索到的一些资料,实现了基于MuPDF库将PDF指定页转换成PNG格式图片的小程序。现在,我就把程序的实现思路和过程写成文档,分享给大家。
    实现思路对于MuPDF库的源码下载以及编译过程,可以参考本站的《使用VS2013编译MuPDF库》这篇文章。
    其实,在MuPDF库中就提供了这一个功能:将PDF指定页转换成PNG格式图片,所以,我们直接编译MuPDF提供的代码就可以了。
    示例程序代码位于MuPDF库源码的“docs”目录下的“example.c”文件,我们只需使用VS2013创建一个空项目,然后把“example.c”文件导入项目中,接着将“include”目录中的头文件以及编译出来的libmupdf.lib、libmupdf-js-none.lib、libthirdparty.lib导入文件中即可。
    其中,“example.c”中主要的函数就是 render 函数,我们主要是把参数传进render函数,就可以把pdf转换成png图片了。
    对于“example.c”的代码可以不用修改,直接编译运行即可。但是,为了方便演示,我们还是对“example.c”中的 main 函数进行修改。
    编码实现以下是“example.c”文件中 render 函数的源码:
    void render(char *filename, int pagenumber, int zoom, int rotation){ // Create a context to hold the exception stack and various caches. fz_context *ctx = fz_new_context(NULL, NULL, FZ_STORE_UNLIMITED); // Open the PDF, XPS or CBZ document. fz_document *doc = fz_open_document(ctx, filename); // Retrieve the number of pages (not used in this example). int pagecount = fz_count_pages(doc); // Load the page we want. Page numbering starts from zero. fz_page *page = fz_load_page(doc, pagenumber - 1); // Calculate a transform to use when rendering. This transform // contains the scale and rotation. Convert zoom percentage to a // scaling factor. Without scaling the resolution is 72 dpi. fz_matrix transform; fz_rotate(&transform, rotation); fz_pre_scale(&transform, zoom / 100.0f, zoom / 100.0f); // Take the page bounds and transform them by the same matrix that // we will use to render the page. fz_rect bounds; fz_bound_page(doc, page, &bounds); fz_transform_rect(&bounds, &transform); // Create a blank pixmap to hold the result of rendering. The // pixmap bounds used here are the same as the transformed page // bounds, so it will contain the entire page. The page coordinate // space has the origin at the top left corner and the x axis // extends to the right and the y axis extends down. fz_irect bbox; fz_round_rect(&bbox, &bounds); fz_pixmap *pix = fz_new_pixmap_with_bbox(ctx, fz_device_rgb(ctx), &bbox); fz_clear_pixmap_with_value(ctx, pix, 0xff); // A page consists of a series of objects (text, line art, images, // gradients). These objects are passed to a device when the // interpreter runs the page. There are several devices, used for // different purposes: // // draw device -- renders objects to a target pixmap. // // text device -- extracts the text in reading order with styling // information. This text can be used to provide text search. // // list device -- records the graphic objects in a list that can // be played back through another device. This is useful if you // need to run the same page through multiple devices, without // the overhead of parsing the page each time. // Create a draw device with the pixmap as its target. // Run the page with the transform. fz_device *dev = fz_new_draw_device(ctx, pix); fz_run_page(doc, page, dev, &transform, NULL); fz_free_device(dev); // Save the pixmap to a file. fz_write_png(ctx, pix, "out.png", 0); // Clean up. fz_drop_pixmap(ctx, pix); fz_free_page(doc, page); fz_close_document(doc); fz_free_context(ctx);}
    程序测试我们修改 main 函数直接调用上述函数接口, main 函数为:
    int main(int argc, char **argv){ // 文件路径 char filename[MAX_PATH] = "C:\\Users\\DemonGan\\Desktop\\test.pdf"; // 转换的页码数 int pagenumber = 1; // 缩放比例 int zoom = 100; // 旋转角度 int rotation = 0; // 处理 render(filename, pagenumber, zoom, rotation); system("pause"); return 0;}
    直接运行程序,目录下有 out.png 图片生成,打开图片查看内容,发现是 test.pdf 的第一页内容,所以转换成功。
    总结这个程序的实现,自己可以不用写代码就可以完成。因为MuPDF已经把接口都封装好了,而且也有示例程序可以直接调用。如果想要把界面做得更有好些,可以把程序写成界面程序,然后直接调用现在的这个 render 函数接口,进行转换即可。
    3 留言 2018-11-06 22:31:04 奖励15点积分
显示 15 到 30 ,共 15 条
eject