Archive for 算法-编程

#-*-coding:utf-8-*-
import urllib2, urllib, cookielib
import re
import getpass
import sqlite3
import random
import time

class Discuz:
    def __init__(self,user,pwd,args):
        self.username = user
        self.password = pwd
        self.args = args
        self.regex = {
            'loginreg':'',
            'replyreg':'',
            'tidreg': '[\s\S]+?'
        }
        self.conn = None
        self.cur = None
        self.islogin = False
        self.login()
        self.InitDB()

    def login(self):
        try:
            loginPage = urllib2.urlopen(self.args['loginurl']).read()
            formhash = re.search(self.regex['loginreg'], loginPage)
            formhash = formhash.group(1)
            #print 'login formhash:', formhash
            print 'start login...'
            cj = cookielib.CookieJar()
            opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(cj))
            user_agent = 'Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; Mozilla/4.0 \
                    (compatible; MSIE 6.0; Windows NT 5.1; SV1) ; .NET CLR 2.0.507'
            opener.addheaders = [('User-agent', user_agent)]
            urllib2.install_opener(opener)
            logindata = urllib.urlencode({
                'cookietime':    2592000,
                'formhash': formhash,
                'loginfield':'username',
                'username':    self.username,
                'password':    self.password,
                'questionid':    0,
                'referer': self.args['referer']
                })
            request = urllib2.Request(self.args['loginsubmiturl'],logindata)
            response = urllib2.urlopen(request)
            self.islogin = True
            print 'login success...'
        except Exception,e:
                print 'loggin error: %s' % e

    def PostReply(self, fid, tid, content):
        try:
            sql = "select * from post where fid='%s' and tid='%s'" % (fid,tid)
            self.cur.execute(sql)
            if self.cur.rowcount == -1:
                tidurl = self.args['tidurl'] % tid
                replysubmiturl = self.args['replysubmiturl'] % (fid,tid)
                tidPage = urllib2.urlopen(tidurl).read()
                formhash = re.search(self.regex['replyreg'], tidPage)
                formhash = formhash.group(1)
                #print 'reply formhash:', formhash
                print 'start reply...'
                replydata = urllib.urlencode({
                    'formhash': formhash,
                    'message': content,
                    'subject': '',
                    'usesig':'1'
                })
                request = urllib2.Request(replysubmiturl,replydata)
                response = urllib2.urlopen(request)
                sql = "insert into post values ('%s', '%s', '%d')" % (fid, tid, 1)
                self.cur.execute(sql)
                self.conn.commit()
                print 'reply success for [%s]' % tidurl
            else:
                print 'Skip! Thread:%s is already replied...' % tid
        except Exception, e:
                print 'reply error: %s' % e

    def GetTids(self, fid):
        if self.islogin:
            fidurl = self.args['fidurl'] % fid
            response = urllib2.urlopen(fidurl)
            content = response.read()
            tids = re.findall(self.regex['tidreg'], content)
            return tids
        else:
            print 'Error Please Login...'

    def InitDB(self):
        self.conn = sqlite3.connect('data.db')
        self.cur = self.conn.cursor()
        sql = '''create table if not exists post (
            fid text,
            tid text,
            replied integer)'''
        self.cur.execute(sql)
        self.conn.commit()

if __name__ == '__main__':
    username = raw_input('username:').strip()
    password = getpass.getpass('password:').strip()
    args = {
            'loginurl': 'http://www.xxx.com/logging.php?action=login',
            'loginsubmiturl': 'http://www.xxx.com/logging.php?action=login&loginsubmit=yes',
            'fidurl': 'http://www.xxx.com/forum-%s-1.html',
            'tidurl': 'http://www.xxx.com/thread-%s-1-1.html',
            'replysubmiturl': 'http://www.xxx.com/post.php?action=reply&replysubmit=yes&infloat=yes&handlekey=fastpost&fid=%s&tid=%s',
            'referer':'http://www.xxx.com/index.php'
    }
    dz = Discuz(username, password,args)
    fid = '45'
    tids = dz.GetTids('45')
    replylist = [
            u'不错,支持一下,呵呵',
            u'已阅,顶一下',
            u'看看,顶你,呵呵',
            u'多谢分享,顶一下',
            u'说的不错,支持一下',
            u'提着水桶到处转,哪里缺水哪里灌! ',
            u'你太油菜了!'
    ]
    for tid in tids:
        content = random.choice(replylist)
        content = content.encode('gbk')
        dz.PostReply('45',tid, content)
        time.sleep(20)
- 下面简单说下过程: 首先是得到了login的post地址:http://www.xxx.com/logging.php?action=login&loginsubmit=yes 几个关键的parameter是
formhash cookietime formhash loginfield password questionid referer username
  • cookietime 浏览器自动给的是 2592000
  • loginfield 默认的username
  • password 密码
  • questionid 这个貌似是登录时的回答问题,这个论坛没有强制回答所以用默认的0
  • referer 这个则是引用地址 http://www.xxx.com/index.php
  • username 用户名
  • formhash 最后这个貌似这个是随机的,不固定,可也是个关键参数,所以就直接用正则查找之
args = {
            'loginurl': 'http://www.xxx.com/logging.php?action=login',
            'loginsubmiturl': 'http://www.xxx.com/logging.php?action=login&loginsubmit=yes',
            'fidurl': 'http://www.xxx.com/forum-%s-1.html',
            'tidurl': 'http://www.xxx.com/thread-%s-1-1.html',
            'replysubmiturl': 'http://www.xxx.com/post.php?action=reply&replysubmit=yes&infloat=yes&handlekey=fastpost&fid=%s&tid=%s',
            'referer':'http://www.xxx.com/index.php'
    }
  • loginurl为登录面页,用于获得formhash的值
  • loginsubmiturl为post登录参数的地址
  • fidurl这个是版块的ID,url中%s那里即为fid,这样的url http://www.xxx.com/forum-45-1.html,fid即为45
  • tidurl是帖子的id,查找方法同上
  • replysubmiturl这个是回复帖子post参数的url,要定位一个帖子前提得知道fid和tid
  • referer这个是引用地址,用网站的首页即可

Continue

对于大部分论坛,我们想要抓取其中的帖子分析,首先需要登录,否则无法查看。 这是因为 HTTP 协议是一个无状态(Stateless)的协议,服务器如何知道当前请求连接的用户是否已经登录了呢?有两种方式: 在URI 中显式地使用 Session ID; 利用 Cookie,大概过程是登录一个网站后会在本地保留一个 Cookie,当继续浏览这个网站的时候,浏览器会把 Cookie 连同地址请求一起发送过去。 Python 提供了相当丰富的模块,所以对于这种网络操作只要几句话就可以完成。我以登录 QZZN 论坛为例,事实上下面的程序几乎所有的 PHPWind 类型的论坛都是适用的。

# -*- coding: GB2312 -*-

from urllib import urlencode
import cookielib, urllib2

# cookie
cj = cookielib.LWPCookieJar()
opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(cj))
urllib2.install_opener(opener)

# Login
user_data = {'pwuser': '你的用户名',
             'pwpwd': '你的密码',
             'step':'2'
            }
url_data = urlencode(user_data)
login_r = opener.open("http://bbs.qzzn.com/login.php", url_data)
一些注释: urllib2 显然是比 urllib 高级一点的模块,里面包括了如何使用 Cookies。 在 urllib2 中,每个客户端可以用一个 opener 来抽象,每个 opener 又可以增加多个 handler 来增强其功能。 在构造 opener 时指定了 HTTPCookieProcessor 做为 handler,因此这个 handler 支持 Cookie。 使用 isntall_opener 后,调用 urlopen 时会使用这个 opener。 如果不需要保存 Cookie,cj 这个参数可以省略。 user_data 存放的就是登录所需要的信息,在登录论坛的时候把这个信息传递过去就行了。 urlencode 功能是把字典 user_data 编码成"?pwuser=username&pwpwd=password"的形式,这样做是为了使程序易读一些。 最后一个问题是,pwuser、pwpwd 这类的名字是从哪儿来的,这就要分析需要登录的网页了。我们知道,一般的登录界面都是一个表单,节选如下: 从这里可以看出,我们需要输入的用户名密码对应的就是 pwuser 和 pwpwd,而 step 对应的则是登录(这个是尝试出来的)。
... 用户名 UID 马上注册 密 码 找回密码 ...
注意到,这个论坛表单采用的是 post 方式,如果是 get 方式则本文的方法就需要变动一下,不能直接 open,而是应该首先 Request,然后再 open。更详细的请看手册...

Continue

 # -*- coding: utf-8 -*-  
 import re  
 import urllib  
 import urllib2  
 import cookielib  
   
 #获取CSDN博客标题和正文  
 url = "http://blog.csdn.net/[username]/archive/2010/07/05/5712850.aspx"  
 sock = urllib.urlopen(url)  
 html = sock.read()  
 sock.close()  
 content = re.findall('(?<=blogstory">).*(?=

Continue

  学用python也有3个多月了,用得最多的还是各类爬虫脚本:写过抓代理本机验证的脚本,写过在discuz论坛中自动登录自动发贴的脚本,写过自动收邮件的脚本,写过简单的验证码识别的脚本,本来想写google music的抓取脚本的,结果有了强大的gmbox,也就不用写了。 - 这些脚本有一个共性,都是和web相关的,总要用到获取链接的一些方法,再加上simplecd这个半爬虫半网站的项目,累积不少爬虫抓站的经验,在此总结一下,那么以后做东西也就不用重复劳动了。 1.最基本的抓站

import urllib2
content = urllib2.urlopen(‘http://XXXX’).read()
2.使用代理服务器 这在某些情况下比较有用,比如IP被封了,或者比如IP访问的次数受到限制等等。
import urllib2
proxy_support = urllib2.ProxyHandler({'http':'http://XX.XX.XX.XX:XXXX'})
opener = urllib2.build_opener(proxy_support, urllib2.HTTPHandler)
urllib2.install_opener(opener)
content = urllib2.urlopen('http://XXXX').read()
3.需要登录的情况 登录的情况比较麻烦我把问题拆分一下: - 3.1 cookie的处理
import urllib2, cookielib
cookie_support= urllib2.HTTPCookieProcessor(cookielib.CookieJar())
opener = urllib2.build_opener(cookie_support, urllib2.HTTPHandler)
urllib2.install_opener(opener)
content = urllib2.urlopen('http://XXXX').read()
是的没错,如果想同时用代理和cookie,那就加入proxy_support然后operner改为
opener = urllib2.build_opener(proxy_support, cookie_support, urllib2.HTTPHandler)
3.2 表单的处理 登录必要填表,表单怎么填?首先利用工具截取所要填表的内容 比如我一般用firefox+httpfox插件来看看自己到底发送了些什么包 这个我就举个例子好了,以verycd为例,先找到自己发的POST请求,以及POST表单项:
python爬虫抓站
可以看到verycd的话需要填username,password,continueURI,fk,login_submit这几项,其中fk是 随机生成的(其实不太随机,看上去像是把epoch时间经过简单的编码生成的),需要从网页获取,也就是说得先访问一次网页,用正则表达式等工具截取返回 数据中的fk项。continueURI顾名思义可以随便写,login_submit是固定的,这从源码可以看出。还有 username,password那就很显然了。 - 好的,有了要填写的数据,我们就要生成postdata  
import urllib
postdata=urllib.urlencode({
    'username':'XXXXX',
    'password':'XXXXX',
    'continueURI':'http://www.verycd.com/',
    'fk':fk,
    'login_submit':'登录'
})
然后生成http请求,再发送请求:
req = urllib2.Request(
    url = 'http://secure.verycd.com/signin/*/http://www.verycd.com/',
    data = postdata
)
result = urllib2.urlopen(req).read()
3.3 伪装成浏览器访问 某些网站反感爬虫的到访,于是对爬虫一律拒绝请求 这时候我们需要伪装成浏览器,这可以通过修改http包中的header来实现
headers = {
    'User-Agent':'Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.1.6) Gecko/20091201 Firefox/3.5.6'
}
req = urllib2.Request(
    url = 'http://secure.verycd.com/signin/*/http://www.verycd.com/',
 data = postdata,
    headers = headers
)
- 3.4 反”反盗链” 某些站点有所谓的反盗链设置,其实说穿了很简单,就是检查你发送请求的header里面,referer站点是不是他自己,所以我们只需要像3.3一样,把headers的referer改成该网站即可,以黑幕著称地cnbeta为例:
headers = {
    'Referer':'http://www.cnbeta.com/articles'
}
headers是一个dict数据结构,你可以放入任何想要的header,来做一些伪装。例如,有些自作聪明的网站总喜欢窥人隐私,别人通过代理 访问,他偏偏要读取header中的X-Forwarded-For来看看人家的真实IP,没话说,那就直接把X-Forwarde-For改了吧,可以 改成随便什么好玩的东东来欺负欺负他,呵呵。 - 3.5 终极绝招 有时候即使做了3.1-3.4,访问还是会被据,那么没办法,老老实实把httpfox中看到的headers全都写上,那一般也就行了。 再不行,那就只能用终极绝招了,selenium直接控制浏览器来进行访问,只要浏览器可以做到的,那么它也可以做到。类似的还有pamie,watir,等等等等。 - 4.多线程并发抓取 单线程太慢的话,就需要多线程了,这里给个简单的线程池模板 这个程序只是简单地打印了1-10,但是可以看出是并发地。
from threading import Thread
from Queue import Queue
from time import sleep
#q是任务队列
#NUM是并发线程总数
#JOBS是有多少任务
q = Queue()
NUM = 2
JOBS = 10
#具体的处理函数,负责处理单个任务
def do_somthing_using(arguments):
    print arguments
#这个是工作进程,负责不断从队列取数据并处理
def working():
    while True:
        arguments = q.get()
        do_somthing_using(arguments)
        sleep(1)
        q.task_done()
#fork NUM个线程等待队列
for i in range(NUM):
    t = Thread(target=working)
    t.setDaemon(True)
    t.start()
#把JOBS排入队列
for i in range(JOBS):
    q.put(i)
#等待所有JOBS完成
q.join()
5.验证码的处理 碰到验证码咋办?这里分两种情况处理: - 1.google那种验证码,凉拌 - 2.简单的验证码:字符个数有限,只使用了简单的平移或旋转加噪音而没有扭曲的,这种还是有可能可以处理的,一般思路是旋转的转回来,噪音去掉,然后划分单个字符,划分好了以后再通过特征提取的方法(例如PCA)降维并生成特征库,然后把验证码和特征库进行比较。这个比较复杂,一篇博文是说不完的,这里就不展开了,具体做法请弄本相关教科书好好研究一下。 - 3.事实上有些验证码还是很弱的,这里就不点名了,反正我通过2的方法提取过准确度非常高的验证码,所以2事实上是可行的。 - 6.总结 基本上我遇到过的所有情况,用以上方法都顺利解决了,不太清楚还有没有其他漏掉的情况,所以本文到这里就完成了,以后要是碰上其他情况,再补充相关方法好了:)

Continue

在2011年的BlackHat DC 2011大会上Ryan Barnett给出了一段关于XSS的示例javascript代码: ($=[$=[]][(__=!$+$)[_=-~-~-~$]+({}+$)[_/_]+($$=($_=!''+$)[_/_]+$_[+$])])()[__[_/_]+__[_+~$]+$_[_]+$$](_/_) 这是一段完全合法的javascript代码,效果相当于alert(1)。它可以在大部分浏览器上运行。(虽然目前我测试过手头的浏览器都能运行,但理论上不能保证所有浏览器都能正确运行,原因见下文) 这段代码的好处(对于黑客)是,它不包含任何字符或数字,可以逃过某些过滤器的检查。比如说,如果假定一个AJAX请求将返回一个只包含数字的JSON,于是很可能会简单判断了一下其中不含字母就直接eval了,结果给黑客们留下了后门。上面的代码功能很简单,只是alert(1),但使用同样的原理,完全可以干出更复杂的事,例如alert(document.cookie)。更重要的是,这段代码再一次提醒我,黑客的想象力是无限的……正如Ryan Barnett的演讲标题:"XSS:The only rule is no rule"。 那么这段代码是如何工作的呢? 我们可以把它分为两个部分来理解: 第一部分: ($=[$=[]][(__=!$+$)[_=-~-~-~$]+({}+$)[_/_]+($$=($_=!''+$)[_/_]+$_[+$])])() 第二部分: [__[_/_]+__[_+~$]+$_[_]+$$](_/_) 其中第一部分是核心,我们首先对它进行分析,先缩进一下: ($= [$=[]][ (__=!$+$)[_=-~-~-~$] + ({}+$)[_/_] + ($$= ($_=!''+$)[_/_] + $_[+$]) ] )() 显然,最外层是(...)()形式的函数调用,我们需要看看这里究竟调用了什么函数,返回了什么。下一步,我们把原来代码中赋值表达式提取出来,将其改写为以下等价形式: $ = []; //1 __ = !$+$; //2 _ = -~-~-~$; //3 $_=!''+$; //4 $$ = $_[_/_] + $_[+$]; //5 $= [$][ __[_] + //6 ({}+$)[_/_] + //7 $$ //8 ]; //9 $(); //10 现在来一行行看: 1. $先赋值为一个空数组 (后面会被覆盖) 2. __ = ![] + [] = false + [] = "false" 这里利用了javascript运算的强制类型转换特性。首先空数组是一个非null值,因此![]的结果是false(布尔型)。在计算false + []时,由于数组对象无法与其他值相加,在加法之前会先做一个toString的转换,空数组的toString就是"",因此事实上在计算false + ""。这时false被自动转换为字符串。最终结果是"false"+"" = "false"。 **换句话说,在$为空数组时,使用 “+$”的方式可以将任何一个值转为字符串** 3. 在计算~[]时,~需要一个数字操作数,空数组无法直接转换为数字,则作为0处理。因此~[] = ~0 = -1。 参考: ~3 = -4 ~[3] = -4 ~[3,2] = -1 (无法转为数字) ~"3" = -4 ~"abc" = -1 因此: _ = -~-~-~[] = -~-~-(-1) = -~-~1 = -~-(-2) = -~2 = -(-3) = 3 理论上,可以用这种方式得出1-9所有数字 4. !''是true,使用+$将其变为字符串 "true" 5. 这里需要注意的是,之前一直用“值+[]”来获得“值”的字符串形式。而“+[]”则是0(正号导致[]被自动转换为数值0)。因此:$$ = "true"[3/3] + "true"[+[]] = "true"[1] + "true"[0] = "rt" 6. __[_] = "false"[3] = "s" 7. ({} + [])导致空对象{}被转换为字符串"[object Object]", 因此({}+$)[_/_] = "[object Object]"[1] = "o" 9. 这里把$覆盖为 [[]]["s"+"o"+"rt"]。注意这里[[]]本身是一个包含空数组的数组,其实对这一步来说,任何一个数组都没有关系(不一定要是嵌套数组),但作者巧妙地把$的首次赋值式放在了数组内部,使代码更为紧凑。最终结果是,$ = [[]]["sort"] = [[]].sort = Array.prototype.sort。 10. 调用$(),作为整个表达式最终的取值。需要注意,$是全局范围的,是window的一个属性,相当于window.$。而Array.prototype.sort会返回this。对于window.$来说,this就是window。因此,整个第一部分的值,就是window本身!当然,这个过程的正确运作依赖于当前浏览器的Array.prototype.sort实现能对this为window的情况容错。 通过第一部分,我们已经获得将任何值转换为字符串的简单方法,并能产生任意的数值,理论上就可以从javascript的取值系统中提取出大部分字母(不知道是不是全部,需要考证)。并且,我们获取到了window的引用。下面就可以开始上下其手,为所欲为了。木哈哈哈哈哈! 可以看出,上面的第10步是与浏览器的具体实现相关的,因此也存在着某些浏览器下需要对代码作出修改的可能。 现在看第二部分,事实上已经非常明朗了,唯一需要注意的是,现在$是一个函数,因此~$ = ~0 (无法直接转换为数字则作为0处理) = -1。 [__[_/_]+__[_+~$]+$_[_]+$$](_/_) = ["false"[1]+"false"[3+(-1)]+"true"[3]+"rt"](1) = ["a"+"l"+"e"+"rt"](1) 所以,整条式子相当于: window["alert"](1) 最后只想再感慨一次:黑客的想象力是无限的。理解代码并不难,问题是一开始时他们是怎么能想出来的。。。

Continue

尤其是利用”异或“运算,实现交换两个值,而不用临时变量。 通常我们交换两个值,都是用一个临时的变量temp,拿交换a,b的值为例,通常的做法是:temp = a;a = b;b = temp;不过利用位运算,真的是方便很多: 假如 a = 3,b = 4。想将a和b的值互换,可以用一下赋值语句实现: a = a ^ b; b = b ^ a; a = a ^ b; 下面用竖式进行简单说明:(10进制化为二进制) a = 011 (^) b = 100 则 a = 111(a ^ b的结果赋值给a,a已变成了7) (^) b = 100 则 b = 011(b^a的结果赋给b,b已经变成了3) (^) a = 111 则 a = 100(a^b的结果赋给a,a已经变成了4) 从上面的竖式可以清楚的看到利用异或运算实现两个值交换的基本过程。 下面从深层次剖析一下: 1.对于开始的两个赋值语句,a = a ^ b,b = b ^ a,相当于b = b ^ (a ^ b) = a ^ b ^ b,而b ^ b 显然等于0。因此b = a ^ 0,显然结果为a。 2. 同理可以分析第三个赋值语句,a = a ^ b = (a ^ b) ^ a = b 注:1.^ 即”异或“运算符。它的意思是判断两个相应的位值是否为”异“,为”异"(值不同)就取真(1);否则为假(0)。 2.^运算符的特点是与0异或,保持原值;与本身异或,结果为0。

Continue

几个比较大的在线提交系统(Online Judge)里面有大量历年的竞赛题目,注册一个ID,然后用自己熟悉的语言(一般有Pascal/C /C++/Java)写好源代码提交即可,会实时返回信息告诉你是否正确。采用黑箱测试,系统里有一套标准的输入输出数据(对外保密,而且通常数据很多很 怪),你的程序的输出和标准输出完全符合即可。常见的返回信息有AC(Accepted,通过)WA(Wrong Answer,输出有错 误)TLE(Time Limit Exceeded,超时)MLE(Memory Limit Exceeded,内存溢 出)RE(Runtime Error,发生实时错误)等,只有AC了才算做对一题。这里只是一个简要介绍,请大家在做题时先看看各网站上的 FAQ,Enjoy it~~~ 杭电acm http://acm.hdu.edu.cn 编程爱好者ACM题库 http://www.programfan.com/acm/ Enjoy ACM Life http://acm.asus.com.cn 清华ACM http://acm.lib.tsinghua.edu.cn 浙江大学 Online Judge(ZOJ) http://acm.zju.edu.cn 国内最早也是最有名气的OJ,有很多高手在上面做题。特点是数据比较刁钻,经常会有你想不到的边界数据,很能考验思维的全面性,现在我主要在这个OJ上做题 北京大学 Online Judge(POJ) http://acm.pku.edu.cn/JudgeOnline/ 建立较晚,但题目加得很快,现在题数和ZOJ不相上下,特点是举行在线比赛比较多,数据比ZOJ上的要弱,有时候同样的题同样的程序,在ZOJ上WA,在POJ上就能AC 西班牙Valladolid大学 Online Judge(UVA) http://online-judge.uva.es/problemset/ 世界上最大最有名的OJ,题目巨多而且巨杂,数据也很刁钻,全世界的顶尖高手都在上面。据说如果你能在UVA上AC一千道题以上,就尽管向IBM、微软什么的发简历吧,绝对不会让你失望的。 俄罗斯Ural立大学 Online Judge(URAL) http://acm.timus.ru/ 也是一个老牌的OJ,题目不多,但题题经典。 UsacoGate Online Judge(USACO) http://ace.delos.com/usacogate 全美计算机奥林匹克竞赛(USACO)的训练网站,特点是做完一关才能继续往下做,与前面的OJ不同的是测试数据可以看到,并且做对后可以看标准解答,所 以如果大家刚开始的时候在上面那些OJ上总WA却找不到原因的话,可以试着来这里做做,看看测试数据一般是从什么地方阴你的。

Continue