基于快速相似度的PageRank方法

摘要

本发明公开一种基于快速相似度的PageRank方法。该方法将PageRank算法和改进的汉明距离相似度算法相结合，提出一种新的网页排序方法。PageRank算法是一种单纯研究网页链接的算法，容易出现主题漂移的问题。针对这一问题本算法提出了两点改进：①结合汉明距离相似度算法，计算检索词和网页文本的相似度，提高搜索的查准率。②为提高搜索的查全率，需改进汉明距离相似度算法，增加搜索检索词的同义词，扩大搜索的范围。根据上述两点，得到快速相似度PageRank算法的计算公式，从查全率和查准率两方面满足搜索的要求。

主权项

1.一种基于快速相似度的PageRank方法，其特征在于具体构建方法如下：步骤10从网络中获取各个网页的链接关系；步骤20将链接关系进行预处理，计算得到网页的入度和出度；解析网页，获取网页的标题。再将网页网址、入度、出度和网页标题建立索引；步骤30根据索引库中的内容，计算各网页的PageRank值，计算公式为：$\mathrm{PR}\left(u\right)=d\underset{v\in B\left(u\right)}{\Sigma }\mathrm{PR}\left(v\right)/N\left(v\right)+(1-d)$式中参数：u是一个网页，B(u)是指向网页u的网页集合，N(v)是指网页v向外的链接数，d是衰减因子，通常取0.85；步骤40根据输入的检索词，计算网页标题与检索词的相似度：$\mathrm{Sim}(U,Q)=1-\underset{k=1}{\overset{n}{\Sigma }}{x}_k\oplus y_k/n$式中参数：x_k，y_k分别表示网页U的标题对应的码字和查寻式Q对应的码字中第k位的分量，它们的值为0或1；0表示在某位置上U不存在与检索词或检索词的同义词，1则表示存在；n为码子的长度，为模2加(异或)运算；步骤50根据上述的计算可以得到快速相似度PageRank的计算公式：$\mathrm{rel}(U,Q)=\mathrm{PR}\left(U\right)·\mathrm{Sim}(U,Q)·(1-\frac{s}{2n})$式中参数：rel(U，Q)是快速相似度PageRank值；PR(U)是网页U的PageRank值；Sim(U，Q)是网页标题和检索词的相似度值；s是标记U中存在同义词的个数；n为网页标题码字的长度。