本站原创
摘要：倒排文件作为现代大规模搜索引擎工作的一个核心技术，其原理简单，具备灵活高效的特点，具体体现在其根据需要可做到适当的变通。本文通过在给定搜索引擎系统内部参数的前提下对其吞吐率的研究，建立一种倒排文件性能模型，该模型有效地提高了倒排文件的运行效率。
关键词：倒排文件；搜索引擎；性能模型；信息检索
：A
Web Log Mining Based on the Weight of the Technical Analysis Page
CHEN Hao
（Guangdong Technical College of Water Resources and Electric Engineering， Guangzhou510925， China）
Abstract：Inverted file as a core technology of the modern largescale search engine. The principle is simple， with a flexible and efficient features. Reflected in needed to do the appropriate modifications. This article by the premise of the internal parameters of a given search engine system throughput. Establishment of a performance model of the inverted file. The model can effectively improve the operating efficiency of the inverted file.
Key words：inverted file；search engine；performance model；information retrieval
1引言
评价一个大规模信息检索系统，有两个方面基本的考虑：效果和效率。效果也称之为质量，指检索返回结果集合的准确性、相关性和完整性。效率即为性能，其中最重要的指标就是查询响应时间和吞吐率。
倒排文件是大型信息检索中使用最为广泛的文件索引方法。所谓“倒排”表示依据检索属性来列举相关文件，是计算机科学中基本的信息查询方法之一，并在数字图书馆和搜索引擎中广为使用。本文通过对倒排文件算法的深入研究，提出了一种性能模型，为倒排文件及其实现的效果做了详细的分析研究，倒排文件的性能得以提高。
2倒排文件的概念
所谓倒排文件是描述一个词项集合元素即TERMS和一个文
DOCS={d1，d2，…dN}，TERMS={t1，t2，…，tM}
在以“文档”为出发点时，称之为di中包含哪些tj，也可理解为某一个tj在di文档中出现了多少次。而“倒排文件”直接给出的是一个tj出现在哪些di中，进而还可以有它在某一个di中出现在哪些位置，包含多少次。用PL（tj）表示tj出现于其中的文档记录的集合，称为对应于tj的倒排表，下面是信息检索研究中常用的几个相关量。
N：文档集合的大小
M：词项集合的大小
Sj=|PL（tj）|：词项tj所涉及文档的个数
DF（tj）=SjN：词项tj的文档频率
IDF（tj）=—lgDF（tj）：倒置文档频率；其值越小表示出现频率越高。
fi，j ：第j个词项tj在第i个文档di中出现的次数
TN=∑Ni=1∑Mj=1fi，j：系统所有文档分解后包含词项的总量
TF（tj）=∑Ni=1fi，jTN：词项tj在所有文档中出现的频度
ITF（tj）=—lgTF（tj）：倒置词频；越小表示出现频率越高
作为数据结构，倒排文件分为两部分：第一部分是由不同词项组成的索引，称为词表，第二部分由每个词项出现过的文档集合构成，称为记录文件，每个词项的对应部分称为倒排表，可以通过词表访问。具体倒排文件结构图如下图1所示：
图1倒排文件结构图
其中左边是词表，中间是记录文件。对应于词表的每一项，记录文件中有若干个倒排表，一半长度记为sj；统计分布为p（i）。至于PL（tj）的每一项，取决于信息检索的方式，对应内容则会有不同，在此用d表示其平均数据量，k表示查询的到达量，r表示响应时间要求，B表示系统的最大输出能力。
3倒排文件的一种性能模型
所谓性能模型，在此就是要给出关于N、M、p（i）、d、B、r和k的一种关系，从而能够在给定系统内部参数的条件下对其外部行为即吞吐率进行估计。
在此需要对p（i）和B，以及几个检测设做以下说明：
p（i）代表倒排表长度的统计分布函数，即M×p（i）的长度表示i的记录表的个数，i∈[0，N]。由此倒排表的平均长度为α=∑Ni=0i×p（i）=1M∑Mj=1Sj
B是支持倒排文件运行的下层系统的瓶颈带宽。取决于不同的情况，可能是磁盘的I/0带宽，也可能是网络带宽。
计算技术与自动化2012年9月
第31卷第3期陈浩：基于倒排文件中一种性能模型的研究
本文讨论性能模块的依据是根据同时到达的查询量k，得到一个数据量D，然后看能否得到DB≤r，由此检测设q1，q2，…，qk都是单纯的，即它们都直接属于集合TERMS且都是随机、独立分布的。通过考察k个查询所导致的输出数据量D。每个查询都可能落到M个词项中的任何一个中，k个查询可能涉及M的任何1，2，…，或者k项，于是对应不同的数据量。若能算出涉及i项的概率，记作fM，k（i），i=1，2，…，k，则有D=一个倒排表的平均数据量×k个并发查询平均涉及的倒排表个数=d×∑Ni=0i×p（i）×∑ki=1i×fM，k（i）=d×α×∑ki=1i×fM，k（i）下面集中考虑fM，k（i）
首先k个查询随机落在M个词项的所有可能总数，相当于从集合{1，2，…，k}到{1，2，…，M}的映射个数即Mk。
接着对i=1，2，…，k，考察k个查询恰好落在i个倒排表上的情况，这相当于是考虑集合{1，2，…，k}的i划分的个数，再加上这个i个倒排表可能落在M中的任意i个上；前者即第二类斯特林数S（k，i）。查询在不同倒排表之间是可区分的，因此需要考虑排列，于是得到：
fM，k（i）=S（k，i）×PiMMk，i=1，2，…，k
D=d×α×∑ki=1i×S（k，i）×PiMMk
其中，S（k+1，i）=i×S（k，i）+S（k，i—1），S（k，0）=0，S（k，1）=S（k，k）=1，Mk=∑ki=0S（k，i）×PiM由此得到
∑ki=1i×S（k，i）×PiM
=∑ki=1[S（k+1，i）—S（k，i—1）]×PiM
=∑ki=1S（k+1，i）×PiM—∑ki=1S（k，i—1）×PiM
=∑k+1i=1S（k+1，i）×PiM—S（k+1，k+1）×
Pk+1M—M×∑ki=1S（k，i—1）×Pi—1M—1
=Mk+1—Pk+1M—
M∑k+1i=1S（k，i—1）×Pi—1M—1—S（k，k）×PkM—1
=Mk+1—Pk+1M—M×（M—1）k+M×PkM—1
=Mk+1—M×（M—1）k
=M×Mk—（M—1）k
所以
D=d×α×M×Mk—（M—1）kMk
=d×α×M×1—1—1Mk （1）
式1即为我们得到的一种倒排文件性能的基本模型。上式中直接给出的是k个并发查询所导致的数据量。
4数据在磁盘和内存之间的移动
搜索引擎对文档信息检索的支持粒度，可分为“全文索引”和“非全文索引”两类。非全文索引只需告知哪些文档含有特定的词项，而全文索引则还需要给出该词项在相关文档中出现的位置等信息，多次出现就多次记录。上式公式中d的大小在全文索引情况下和词项在不同文档中出现的平均次数成比例，即∑Mj=1∑Ni=1fi，jN×M，而在非全文索引情况下则基本上是常数，记做c一般为几个字节。
这里将d×α一并考虑。对于每一个倒排表对应于一个具体
d×α=c×α非全文索引c×α+TNM全文索引（2）
上式中，c表示为记录一个词项在文档中一次出现位置信息所需的数据量。其中的符号所代表的量的数量级有些具体的概念是有必要的，以部分中文搜索引擎为例，c≈101，α≈105，M≈5×104，N≈3×107，TN≈1010。非全文索引的倒排表数据量在106数量级，而全文索引是它的若干倍。由此估算，作为整个倒排文件的记录文件，即使非全文索引，内存也是放不下的。
另外，α作为倒排文件中倒排表长度的平均值，也就是和词表中词项的文档频率相关的一个量，即α=∑Mj=1N×DF（tJ）M。由于TF和DF常常是和应用相关的统计量，可以在具体实现之前进行估计，从而使得在设计倒排表应用时就能根据公式1对查询导致的数据量有个估算。
在倒排文件查询处理算法中，系统要将用户查询中单词项对应的倒排表读到内存中执行集合操作，因此倒排表的长度将首先影响操作执行的时间。当索引网页量增加时，高频词项的倒排表将急剧膨胀，占用大量I/0带宽、内存空间以及CPU时间，严重降低系统效率。理想情况下，所有词项的频率应该尽可能低，而且大小相近，使得所有倒排表保持同步增长，系统性能不会因为一部分单词记录表的长度快速增长而受损。而实际情况中，词项的频率分布和文件的语言有关。
5英语单词和汉语字符实例分析
本文以CCF中国计算机学会统计出的英语单词和汉语单字的频率作为原始数据进行分析，将所有单词按照它们的ITF（IDF）值从小到大排列，赋予[0，T]的序号x作为坐标图的横轴，ITF（IDF）值作为坐标图的纵轴，即可得到单词的ITF（IDF）分布图。两个统计结果都是按照单词的出现频率从高到低排序，如下表1中即是对数据抽样的结果，表示降低到某一个频率数值时的单词序号。
表1英汉词频统计排序对照表
频率
英语单词
汉语字符
0.1%
103
252
0.07%
148
348
0.05%
220
475
0.02%
632
867
0.01%
1285
1215
0.007%
1780
1400
0.005%
2381
1609
0.002%
5474
2210
0.001%
6713
2676
由此得出使用的汉字比英语单词要少的多，汉语的高频字比英语的高频单词要多，低频词则反之。在万分之一频率处，两者的数量近似。在十万分之一处，英语有六千多个单词，汉语单字却不到三千个。根据表1绘制出的ITF分布如下图2所示：
图2英语单词和汉语字符的ITF分布图
其中两条曲线在接近ITF=4处相交，汉语字符的曲线毕英语单词的曲线要陡峭的多。这种特性决定了索引同样数量的单词即TN相等，汉语字符的倒排表平均长度要大于英语单词，并且伴随着TN的增长而加速增长。
6结论
在实际的查询中词项的频率决定要读取的记录表长度，为了得到它们和搜索引擎吞吐量的关系，必须顾及出搜索引擎运行时查询词项的平均频率。因此，本文公式1中关于D的表达式，只要M相对于k较大，都是很有效的，这个结果和预期值相符。
参考文献
张志刚.基于网页的信息系统的一种预处理过程[M].北京：北京大学，2011.
Baldi P，Frasconi P，Smyth P.2010. Modeling the Internet and the Web， probabilistic methods and algorithms. John Wiley.
[3]Persin M，Zobel J，Sacks—Dis R.Filered document retrieval with frequencysorted indexes[J]. Journal of the American Society for Information Science，2010，47：749—764.
[4]Lei M，et al.Improved relevance ranking in WebGather[J].Journal of Computer Science and Technology，2010，16：410—417.
[5]China Internet Network Information Center.2011.（中国互联网络信息中心） [EB/OL].http：//nic.net.cn
关键词：倒排文件；搜索引擎；性能模型；信息检索
：A
Web Log Mining Based on the Weight of the Technical Analysis Page
CHEN Hao
（Guangdong Technical College of Water Resources and Electric Engineering， Guangzhou510925， China）
Abstract：Inverted file as a core technology of the modern largescale search engine. The principle is simple， with a flexible and efficient features. Reflected in needed to do the appropriate modifications. This article by the premise of the internal parameters of a given search engine system throughput. Establishment of a performance model of the inverted file. The model can effectively improve the operating efficiency of the inverted file.
Key words：inverted file；search engine；performance model；information retrieval
1引言
评价一个大规模信息检索系统，有两个方面基本的考虑：效果和效率。效果也称之为质量，指检索返回结果集合的准确性、相关性和完整性。效率即为性能，其中最重要的指标就是查询响应时间和吞吐率。
倒排文件是大型信息检索中使用最为广泛的文件索引方法。所谓“倒排”表示依据检索属性来列举相关文件，是计算机科学中基本的信息查询方法之一，并在数字图书馆和搜索引擎中广为使用。本文通过对倒排文件算法的深入研究，提出了一种性能模型，为倒排文件及其实现的效果做了详细的分析研究，倒排文件的性能得以提高。
2倒排文件的概念
所谓倒排文件是描述一个词项集合元素即TERMS和一个文
源于：论文范例www.udooo.com
档集合元素即DOCS对应关系的数据结构，记为：DOCS={d1，d2，…dN}，TERMS={t1，t2，…，tM}
在以“文档”为出发点时，称之为di中包含哪些tj，也可理解为某一个tj在di文档中出现了多少次。而“倒排文件”直接给出的是一个tj出现在哪些di中，进而还可以有它在某一个di中出现在哪些位置，包含多少次。用PL（tj）表示tj出现于其中的文档记录的集合，称为对应于tj的倒排表，下面是信息检索研究中常用的几个相关量。
N：文档集合的大小
M：词项集合的大小
Sj=|PL（tj）|：词项tj所涉及文档的个数
DF（tj）=SjN：词项tj的文档频率
IDF（tj）=—lgDF（tj）：倒置文档频率；其值越小表示出现频率越高。
fi，j ：第j个词项tj在第i个文档di中出现的次数
TN=∑Ni=1∑Mj=1fi，j：系统所有文档分解后包含词项的总量
TF（tj）=∑Ni=1fi，jTN：词项tj在所有文档中出现的频度
ITF（tj）=—lgTF（tj）：倒置词频；越小表示出现频率越高
作为数据结构，倒排文件分为两部分：第一部分是由不同词项组成的索引，称为词表，第二部分由每个词项出现过的文档集合构成，称为记录文件，每个词项的对应部分称为倒排表，可以通过词表访问。具体倒排文件结构图如下图1所示：
图1倒排文件结构图
其中左边是词表，中间是记录文件。对应于词表的每一项，记录文件中有若干个倒排表，一半长度记为sj；统计分布为p（i）。至于PL（tj）的每一项，取决于信息检索的方式，对应内容则会有不同，在此用d表示其平均数据量，k表示查询的到达量，r表示响应时间要求，B表示系统的最大输出能力。
3倒排文件的一种性能模型
所谓性能模型，在此就是要给出关于N、M、p（i）、d、B、r和k的一种关系，从而能够在给定系统内部参数的条件下对其外部行为即吞吐率进行估计。
在此需要对p（i）和B，以及几个检测设做以下说明：
p（i）代表倒排表长度的统计分布函数，即M×p（i）的长度表示i的记录表的个数，i∈[0，N]。由此倒排表的平均长度为α=∑Ni=0i×p（i）=1M∑Mj=1Sj
B是支持倒排文件运行的下层系统的瓶颈带宽。取决于不同的情况，可能是磁盘的I/0带宽，也可能是网络带宽。
计算技术与自动化2012年9月
第31卷第3期陈浩：基于倒排文件中一种性能模型的研究
本文讨论性能模块的依据是根据同时到达的查询量k，得到一个数据量D，然后看能否得到DB≤r，由此检测设q1，q2，…，qk都是单纯的，即它们都直接属于集合TERMS且都是随机、独立分布的。通过考察k个查询所导致的输出数据量D。每个查询都可能落到M个词项中的任何一个中，k个查询可能涉及M的任何1，2，…，或者k项，于是对应不同的数据量。若能算出涉及i项的概率，记作fM，k（i），i=1，2，…，k，则有D=一个倒排表的平均数据量×k个并发查询平均涉及的倒排表个数=d×∑Ni=0i×p（i）×∑ki=1i×fM，k（i）=d×α×∑ki=1i×fM，k（i）下面集中考虑fM，k（i）
首先k个查询随机落在M个词项的所有可能总数，相当于从集合{1，2，…，k}到{1，2，…，M}的映射个数即Mk。
接着对i=1，2，…，k，考察k个查询恰好落在i个倒排表上的情况，这相当于是考虑集合{1，2，…，k}的i划分的个数，再加上这个i个倒排表可能落在M中的任意i个上；前者即第二类斯特林数S（k，i）。查询在不同倒排表之间是可区分的，因此需要考虑排列，于是得到：
fM，k（i）=S（k，i）×PiMMk，i=1，2，…，k
D=d×α×∑ki=1i×S（k，i）×PiMMk
其中，S（k+1，i）=i×S（k，i）+S（k，i—1），S（k，0）=0，S（k，1）=S（k，k）=1，Mk=∑ki=0S（k，i）×PiM由此得到
∑ki=1i×S（k，i）×PiM
=∑ki=1[S（k+1，i）—S（k，i—1）]×PiM
=∑ki=1S（k+1，i）×PiM—∑ki=1S（k，i—1）×PiM
=∑k+1i=1S（k+1，i）×PiM—S（k+1，k+1）×
Pk+1M—M×∑ki=1S（k，i—1）×Pi—1M—1
=Mk+1—Pk+1M—
M∑k+1i=1S（k，i—1）×Pi—1M—1—S（k，k）×PkM—1
=Mk+1—Pk+1M—M×（M—1）k+M×PkM—1
=Mk+1—M×（M—1）k
=M×Mk—（M—1）k
所以
D=d×α×M×Mk—（M—1）kMk
=d×α×M×1—1—1Mk （1）
式1即为我们得到的一种倒排文件性能的基本模型。上式中直接给出的是k个并发查询所导致的数据量。
4数据在磁盘和内存之间的移动
搜索引擎对文档信息检索的支持粒度，可分为“全文索引”和“非全文索引”两类。非全文索引只需告知哪些文档含有特定的词项，而全文索引则还需要给出该词项在相关文档中出现的位置等信息，多次出现就多次记录。上式公式中d的大小在全文索引情况下和词项在不同文档中出现的平均次数成比例，即∑Mj=1∑Ni=1fi，jN×M，而在非全文索引情况下则基本上是常数，记做c一般为几个字节。
这里将d×α一并考虑。对于每一个倒排表对应于一个具体
源于：毕业设计论文范文www.udooo.com
的词项tj而言，它的数据量在全文索引情况下正比于N×DF（tj）+TN×TF（tj），前一部分是倒排表中文档号和频率占用的长度，后一部分是位置信息占用的长度。因为TN要远大于N，所以系统中每个词项倒排表的长度主要是由它的词频率TF和数据规模TN决定的。非全文索引的情况下则只有N×DF（tj）。在平均情况下：d×α=c×α非全文索引c×α+TNM全文索引（2）
上式中，c表示为记录一个词项在文档中一次出现位置信息所需的数据量。其中的符号所代表的量的数量级有些具体的概念是有必要的，以部分中文搜索引擎为例，c≈101，α≈105，M≈5×104，N≈3×107，TN≈1010。非全文索引的倒排表数据量在106数量级，而全文索引是它的若干倍。由此估算，作为整个倒排文件的记录文件，即使非全文索引，内存也是放不下的。
另外，α作为倒排文件中倒排表长度的平均值，也就是和词表中词项的文档频率相关的一个量，即α=∑Mj=1N×DF（tJ）M。由于TF和DF常常是和应用相关的统计量，可以在具体实现之前进行估计，从而使得在设计倒排表应用时就能根据公式1对查询导致的数据量有个估算。
在倒排文件查询处理算法中，系统要将用户查询中单词项对应的倒排表读到内存中执行集合操作，因此倒排表的长度将首先影响操作执行的时间。当索引网页量增加时，高频词项的倒排表将急剧膨胀，占用大量I/0带宽、内存空间以及CPU时间，严重降低系统效率。理想情况下，所有词项的频率应该尽可能低，而且大小相近，使得所有倒排表保持同步增长，系统性能不会因为一部分单词记录表的长度快速增长而受损。而实际情况中，词项的频率分布和文件的语言有关。
5英语单词和汉语字符实例分析
本文以CCF中国计算机学会统计出的英语单词和汉语单字的频率作为原始数据进行分析，将所有单词按照它们的ITF（IDF）值从小到大排列，赋予[0，T]的序号x作为坐标图的横轴，ITF（IDF）值作为坐标图的纵轴，即可得到单词的ITF（IDF）分布图。两个统计结果都是按照单词的出现频率从高到低排序，如下表1中即是对数据抽样的结果，表示降低到某一个频率数值时的单词序号。
表1英汉词频统计排序对照表
频率
英语单词
汉语字符
0.1%
103
252
0.07%
148
348
0.05%
220
475
0.02%
632
867
0.01%
1285
1215
0.007%
1780
1400
0.005%
2381
1609
0.002%
5474
2210
0.001%
6713
2676
由此得出使用的汉字比英语单词要少的多，汉语的高频字比英语的高频单词要多，低频词则反之。在万分之一频率处，两者的数量近似。在十万分之一处，英语有六千多个单词，汉语单字却不到三千个。根据表1绘制出的ITF分布如下图2所示：
图2英语单词和汉语字符的ITF分布图
其中两条曲线在接近ITF=4处相交，汉语字符的曲线毕英语单词的曲线要陡峭的多。这种特性决定了索引同样数量的单词即TN相等，汉语字符的倒排表平均长度要大于英语单词，并且伴随着TN的增长而加速增长。
6结论
在实际的查询中词项的频率决定要读取的记录表长度，为了得到它们和搜索引擎吞吐量的关系，必须顾及出搜索引擎运行时查询词项的平均频率。因此，本文公式1中关于D的表达式，只要M相对于k较大，都是很有效的，这个结果和预期值相符。
参考文献
张志刚.基于网页的信息系统的一种预处理过程[M].北京：北京大学，2011.
Baldi P，Frasconi P，Smyth P.2010. Modeling the Internet and the Web， probabilistic methods and algorithms. John Wiley.
[3]Persin M，Zobel J，Sacks—Dis R.Filered document retrieval with frequencysorted indexes[J]. Journal of the American Society for Information Science，2010，47：749—764.
[4]Lei M，et al.Improved relevance ranking in WebGather[J].Journal of Computer Science and Technology，2010，16：410—417.
[5]China Internet Network Information Center.2011.（中国互联网络信息中心） [EB/OL].http：//nic.net.cn