招来与排行思路整理

学习《集体智慧编程》第4章的思绪整理:

本章的紧要性内容就是起家一个效仿的全文检索引擎,紧要的大步子为:1.追寻网页,2.成立目录,3.对网页举办搜索
4.开外办法对寻找结果举行排名

一、检索网页:紧要使用python写了一个爬虫软件,通过爬取一个网站上链接来不断的扩充爬取的情节。紧要采纳了python的urllib库和BeautifulSoup库。这一部分相比较简单,焦点代码如下:

def crawl(self,pages,depth=2):
        for i  in range(depth):
            newpages=set()
            for page in pages:
                try:
                    c=request.urlopen(page)
                except:
                    print('Could not open %s' %page)
                    continue
                soup=BeautifulSoup(c.read(),'html5lib')
                self.addtoindex(page,soup)

                links=soup('a')
                for link in links:
                    if ('href' in dict(link.attrs)):
                        url=urljoin(page,link['href'])
                        if url.find("'")!=-1:
                            continue
                        url=url.split(' ')[0]#去掉位置信息
                        if url[0:4]=='http' and not self.isindexed(url):
                            newpages.add(url)
                        linkText=self.gettextonly(link)
                        self.addlinkref(page,url,linkText)
                self.dbcommit()
            pages=newpages    ####位置!!!将一个网页里面的连接保存起来

此地运用了广度优先搜索形式

二、建立目录

1.sqlite数据库的施用:

在python2.x版本中需要团结下载安装这几个数据库,然则在python3.x中我们只需要
import sqlite3即可。首先需要修改类的部分内建函数:

###初始化crawler类并且传入数据库名称
    def __init__(self,dbname):
        self.con=sqlite3.connect(dbname)
    def __del__(self):
        self.con.close()
    def dbcommit(self):
        self.con.commit()

然后建立数据库,这里首先需要准备5张数据库表,分别为:urllist(保存的是曾经过索引的url列表)、wordlist(保存的是单词列表)、wordlocation(保存的是单词在文档中的所处的地方列表)、link(保存多少个Url
ID 指明从一个表到另一张表的连年关系)
linkwords(利用了字段wordid和linkid记录了什么样单词和链接实际相关),并且成立部分索引完整的数据库schema如下图:

sqlite 1

切切实实代码如下:

def createindextables(self):
        # self.con.execute('drop table if exists urllist,wordlist,wordlocation,link,linkwords')
        self.con.execute('create table urllist(url)')
        self.con.execute('create table wordlist(word)')
        self.con.execute('create table wordlocation(urlid,wordid,location)')
        self.con.execute('create table link(fromid INTEGER ,toid INTEGER )')
        self.con.execute('create table linkwords(wordid,linkid)')
        self.con.execute('create index wordidx on wordlist(word)')
        self.con.execute('create index urlidx on urllist(url)')
        self.con.execute('create index wordurlidx on wordlocation(wordid)')
        self.con.execute('create index urltoidx on link(toid)')
        self.con.execute('create index urlfromidx on link(fromid) ')
        self.dbcommit()

2.在网页中搜索单词,此处仍然使用了BeautifulSoup的精锐功能,将网页中的所有的文字音讯提取出来,去掉一部分标签,属性之类的。然后开展单词的分词。在此地的单词分词都是针对性英文单词的,关于粤语单词的分词,有个名为jieba的库可以实现。感兴趣的可以看一下:https://github.com/fxsjy/jieba/tree/jieba3k

 ##从一个Html网页中抓取文字(不带标签的)
    def gettextonly(self,soup):
        v=soup.string
        if v==None:
            c=soup.contents  ####把content是错误的写成了content
            resulttext=''
            for t in c:
                subtext=self.gettextonly(t)
                resulttext+=subtext+'\n'
            return resulttext
        else:
            return v.strip()



    ###根据任何非空白字符进行分词处理
    def separatewords(self,text):
        ##该方法仅仅局限于分英文单词
        splitter=re.compile('\\W*')
        return [s.lower() for s in splitter.split(text) if s!=' ']
        ###中文的应用了jieba库,关于该库可以参见https://github.com/fxsjy/jieba/tree/jieba3k
        # return (list(jieba.cut_for_search(text))) ##从一个Html网页中抓取文字(不带标签的)
    def gettextonly(self,soup):
        v=soup.string
        if v==None:
            c=soup.contents  ####把content是错误的写成了content
            resulttext=''
            for t in c:
                subtext=self.gettextonly(t)
                resulttext+=subtext+'\n'
            return resulttext
        else:
            return v.strip()



    ###根据任何非空白字符进行分词处理
    def separatewords(self,text):
        ##该方法仅仅局限于分英文单词
        splitter=re.compile('\\W*')
        return [s.lower() for s in splitter.split(text) if s!=' ']
        ###中文的应用了jieba库,关于该库可以参见https://github.com/fxsjy/jieba/tree/jieba3k
        # return (list(jieba.cut_for_search(text)))

3、加入索引,将网页以及拥有的单词出席索引,在网页和单词之间确立关联,并且保留单词在文档中的地方。在本例中,文档的地点就是在列表中的索引号

 ###为每个网页建立索引
    def addtoindex(self,url,soup):
        if self.isindexed(url):
            return
        print ("Indexing:"+url)

        ##获取每个单词
        text=self.gettextonly(soup)
        words=self.separatewords(text)

        ##得到URL的id
        urlid=self.getentryid('urllist','url',url)
        ##将每个单词与该url相关联
        for i in range(len(words)):
            word=words[i]
            if word in ignorewords:
                continue
            wordid=self.getentryid('wordlist','word',word)####此处出现错误
            self.con.execute("insert into wordlocation(urlid,wordid,location) values (%d,%d,%d)" % (urlid, wordid, i)

三、查询

 def getmatcheows(self,q):
        ###构造查询的字符串
        fieldlist='w0.urlid'
        tablelist=''
        clauselist=''
        wordids=[]

        ##根据空格拆分单词
        words=q.split(' ')
        print(words)
        tablenumber=0

        for word in words:
         # Get the word ID
            wordrow=self.con.execute(
            "select rowid from wordlist where word='%s'" % word).fetchone()
            if wordrow!=None:
                wordid=wordrow[0]
                wordids.append(wordid)
                if tablenumber>0:
                    tablelist+=','
                    clauselist+=' and '
                    clauselist+='w%d.urlid=w%d.urlid and ' % (tablenumber-1,tablenumber)
                fieldlist+=',w%d.location' % tablenumber
                tablelist+='wordlocation w%d' % tablenumber
                clauselist+='w%d.wordid=%d' % (tablenumber,wordid)
                tablenumber+=1

        # Create the query from the separate parts
        fullquery='select %s from %s where %s' % (fieldlist,tablelist,clauselist)
        print (fullquery)
        cur=self.con.execute(fullquery)
        rows=[row for row in cur]

        return rows,wordids

四、排名

1.遵照内容的名次:评价度量包括以下两种:单词频度,文档地方,单词距离

首先大家要设定一个归一化函数,对结果开展归一化处理,使得他们拥有相同的值域和变化趋势。

###归一化函数 返回一个介于0~1之间的值
    def normalizescores(self,scores,smallIsBetter=0):
        vsmall=0.00001  #避免被零整除
        if smallIsBetter:
            minscore=min(scores.values())
            return dict([(u,float(minscore)/max(vsmall,l)) for (u,l) in scores.items()])
        else:
            maxscore=max(scores.values())
            if maxscore==0:maxscore=vsmall
            return dict([(u,float(c)/maxscore) for(u,c) in scores.items()])

 基于内容的排行的算法属于传统的先前时期搜索引擎使用的度量模式。其两种评价度量的代码分别如下:

###单词频度作为评价度量
    def frequencyscore(self,rows):
        count=dict([row[0],0] for row in rows)
        for row in rows:
            count[row[0]]+=1
        return self.normalizescores(count)

    ###文档位置
    def locationscore(self,rows):
        locations=dict([row[0],1000000] for row in rows)
        for row in rows:
            loc=sum(row[1:])
            if loc<locations[row[0]]:
                locations[row[0]]=loc

        return self.normalizescores(locations,smallIsBetter=1)
    #单词距离
    def distancescore(self,rows):
        ###如果仅有两个单词,则得分都一样
        if len(rows[0])<=2:
            return dict([(row[0],1.0) for row in rows ])
        ###初始化字典,并且填入一个很大的数字
        mindistance=dict([(row[0],1000000) for row in rows])

        for row in rows:
            dist=sum([abs(row[i]-row[i-1]) for i in range(2,len(row))])
            if dist<mindistance[row[0]]:
                mindistance[row[0]]=dist
        return self.normalizescores(mindistance,smallIsBetter=1)

2.著名的PageRank算法

sqlite,Google使用的算法,为每一个网页都给以了一个只是网页根本程度的评价值。网页的基本点是依指向该网页的富有的任何网页的首要以及这个网页所涵盖的连接数求得的。

PageRank 使用一个阻尼因子:0.85

关于该算法的具体内容,可以活动百度。。。也得以查阅http://www.cnblogs.com/FengYan/archive/2011/11/12/2246461.html的博文

代码实现:

 ####PageRank
    def calculatepagerank(self,iteration=20):
        ###清除当前的PageRank表
        self.con.execute("drop table if exists pagerank")
        self.con.execute("create table pagerank(urlid primary key,score)")
        ####初始化每一个url,令其PageRank值为1
        self.con.execute("insert into pagerank select rowid,1.0 from urllist")
        self.dbcommit()

        for i in range(iteration):
            print('Iteration %d' %(i))
            for(urlid,) in self.con.execute("select rowid from urllist"):
                pr=0.15 #(最小值)
                ##循环遍历指向当前网页的所有其他网页

                for(linker,) in self.con.execute("select distinct fromid from link where toid=%d" %urlid):
                    ###得到相应的PR值
                    linkingpr=self.con.execute("select score from pagerank where urlid=%d" %linker).fetchone()[0]

                    ###求得总的链接数
                    linkingcount=self.con.execute("select count(*) from link where fromid=%d " %linker).fetchone()[0]
                    pr+=0.85*(linkingpr/linkingcount)
                self.con.execute("update pagerank set score=%f where urlid=%d" %(pr,urlid))
            self.dbcommit()

 

网站地图xml地图