倒排索引源于实际应用中需要根据属性值（字段）来查找记录（所在的文件位置）。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。
目前主流的索引技术有三种：倒排索引、后缀数组以及签名。后缀数组虽然快，但是维护困难，代价高昂，不适合作为搜索引擎的索引。而签名的速度和性能都不如倒排索引。因此倒排索引是各种搜索引擎中被主要使用的一种索引技术，同时也是搜索引擎的一个核心技术。
建立倒排索引的步骤一般为：
1) 建立前向索引
假设有网页P1，P2，……，Pn，网页中的每一个关键字为W1，W2，……，Wn，每个关键字在网页出现的次数对应为N1，N2，……，Nn，关键字Wi在某一网页中出现的位置记录为数组POSi = <pos1, pos2, …, posk>。
那么，通过中文分词工具将网页逐一分解成关键字序列之后，就能按如下格式建立前向索引了：
Pi = {[N1, W1, POS1], [N1, W1, POS2], …, [Nj, Wj,POSj], …, [Nn, Wn, POSn]}
其中位置数组POSi = <pos1,pos2,…,posk>相互独立；Ni = 0（出现次数为0）的关键字Wi可以被舍弃而不出现在索引序列中。
2) 通过前向索引建立倒排索引
可见，前向索引是通过网页名来索引关键字及其位置（网页→关键字）。而在搜索引擎的应用中，实际上需要的是通过关键字来检索它所出现过的网页中的位置（关键字→网页），正好与前向索引相反。因此需要将前向索引转换成倒排索引。
实现中，可以通过将网页和关键字分别编号，建立矩阵Index[i][j]。其中i表示编号为i的网页，j表示编号为j的关键字，Index[i][j]表示关键字j在网页i中出现的次数与位置对象。
然后依次扫描每个关键字，按照下列各式建立倒排索引：
Wi = {[N1, P1, POS1], [N1, P1, POS2], …, [Nj, Pj,POSj], …, [Nn, Pn, POSn]}
其中Nj表示关键字Wi在网页Pj中出现的次数，POSj表示关键字Wi在网页Pj中出现的位置数组。
2. 向量空间模型向量空间模型是通过特征向量将索引抽象为表示文本文件集合的代数模型的一种方式。抽象的目的是通过向量间的计算进行信息过滤、相关性排序等。
向量空间模型通常是基于关键词的，并且通过关键词在网页库各文件中出现的频率计算每个网页的特征向量。同时，可以给查询式中的每个分词（关键字）附加权重，以设定查询的偏好。
定义上，网页库中的各个文件和查询式都将用向量来表示，每个向量中向量项的顺序与倒排索引中关键字出现的顺序相同。对于文件：
Dj = <dj1, dj2, …, dji, …, djn>
向量Dj表示编号为j的网页文件的特性向量。其中，向量项dji表示关键字i在文件j中的TFIDF权重，其计算过程如下：
1) 计算关键字i在文件j中出现的次数，记为TFji
2) 计算包含关键字i的文件的个数，记为DFi
3) 计算关键字i的反文档频率IDFi = log (M/ DFi)，其中M为文件总数
4) 计算dji = TFIDFji = TFji * DFi
对于查询式：
Q = <q1, q2, …, qi, …, qn>
按照倒排索引中关键字的顺序逐个比较查询式中的中文分词。对于索引中第i个关键字，若它出现中查询式中，则qi = 1；否则qi = 0。另外，也可以手动给查询式中特定词项赋予权重，以达到设定偏好的目的。
向量空间D = <D1, D2, …, Dm>与查询式向量Q计算完毕后，即可进行相似度计算。若采用的是余弦相似度，则需逐一扫描向量空间中的每一个向量，计算它与Q的夹角，公式如下：
将计算所得的余弦值进行排序，即可得到相关性排序的结果。
3. 网络爬虫（深度优先策略）网络爬虫是Web信息的采集器，它通过网页之间的链接关系从网络中自动下载网页数据，并且跟随网页中的链接不断向所需要的网页扩展。不同类型的信息检索系统因为其对资源性质的要求而有不同的技术需求。
爬取网页的一般过程如下：
1) 从一个URL种子集合开始搜索，将其全部存入某一集合数据结构之中；
2) 从该数据结构中取出一个URL，建立网络连接；
3) 远程读取网页数据并转存到本地；
4) 解析网页，提取出其中包含的URL，将其存入数据结构中；
5) 若数据结构中仍有URL或者下载的网页数量未达到下载上限，则返回2)，否则结束爬取。
在爬取过程中，需要注意如下几个问题：
一、 采用深度优先搜索策略进行爬取时，存取URL的数据结构选用栈；
二、 为了避免网页重复，在爬虫中需要维护一个哈希表，用来保存已经访问过的URL；当2)取出URL之后，将其与哈希表比对，判断哈希表中是否存在该URL，若存在则直接跳到5)，而不再对该网页进行下载；
三、 出于对中文编码格式不统一的考虑，读取网页和保存网页的过程一律采用字节流，而不采用字符流；解析网页的步骤同时析取出网页的编码方式，并加以保存；
四、 爬取规模较小，可以不采用多线程；如需采用多线程，则需要对URL栈添加同步锁以保证线程安全。
4. 中文内容提取大部分网页中除了包含它的主要有用信息以外，还包含了许多噪声信息，例如导航、无用链接、广告等。另外，由于网络爬虫中并未对病态网页进行处理，因此有些网页中可能只包含一些脚本数据，而并没有正文信息。在这种情况下，在建立索引之前，还需要从给定的网页文件中抽取出有用的中文正文信息。这也是爬虫将网页保存到本地的目的。
若网页的格式相对较为单一，则可采用简单的文字加标签技术进行分析。其基本算法思想为：通过<div>或<table>标签切分内容块，通过中文标点符号（，。！）发现正文，通过链接数在正文中占的比例判断是否是噪声。
对任一网页进行中文内容提取的一般步骤如下：
1) 去除部分噪声：通过遍历网页，去掉特定的无用标签及标签中的内容，如<select>、<img>、<script>、<span>等；
2) 提取最内层的<div>或<table>块，建立内容块序列；
3) 逐一扫描内容块，每个内容块的正文权值 = (标点符号数 – 0.3 * 链接数) / (1 + 0.2 * n)，其中n表示该内容块中包含的<form>和<input>标签数量；
4) 扫描完成后，选取正文权值最大的内容块，抽取出其中的纯文本；
5) 比较纯文本的长度，短于设定值（假定为20个字）的将判断为病态页面，予以舍弃。
5. 指纹去重完成正文提取的文本数据在保存为缓存文件以便建立倒排索引之前，需要进行网页去重。原因是网络中可能出现多个域名对应同一个网站或者网站间的互相转载。去重的目的是尽量使建立索引的文本库中的各个文本文件彼此独立，相互不同，提高搜索的有效性。
内容相同的网页主要分为三种情况：
1) 网页正文完全相同；
2) 网页正文大部分相同，只有少量变动；
3) 一个网页的正文是另一个网页正文的一部分。
对于简单的垂直搜索引擎，可只针对第一种情况进行分析，则只需采用计算正文MD5指纹的方式判断网页正文是否已经存在。其一般步骤如下：
1) 在中文内容提取中维护一个哈希表，用于保存正文的MD5指纹；
2) 对于提取完成的一段正文，将其作为字符串，计算其MD5值；
3) 判断该MD5是否已存在于哈希表中，若存在，则舍弃正文，反之则将其MD5值存入哈希表中。
HDU 1728 逃离迷宫 http://acm.hdu.edu.cn/showproblem.php?pid=1728
对于代码31行，为什么等于不能随便剪掉
如果剪掉就会出现下图结果：
【假如转弯数k=1,起点终点如图】
那么如果你的代码是优先向右搜索就会出错
红色的线是先搜的，由于最多转一次弯，所以不合题意；
蓝色是后搜的，因为遇到转弯数相等所以不往下走了了，但是继续走是可以满足题意输出"yes"的
Problem : 1728 ( 逃离迷宫 ) Judge Status : Accepted
RunId : 8244627 Language : C++ Author : luotianyu520
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
#include <iostream>
using namespace std;
#define inf 0x3fffffff//无穷大
#define M 105//数组大小
//1、wan用于转弯数剪枝;2、step用于步数兼职,就不用visit标记访问了
int r,c,ex,ey,k,wan[M][M];//行数，列数，终点x，终点y，弯数
char map[M][M];//接收控制台字符串
int x_move[4] = {-1, 0, 1, 0};//四方向移动
int y_move[4] = {0, 1, 0, -1};//四方向移动
bool flag; //判断成功
void dfs(int x,int y,int dir)//dir 为当前方向
{
if(x==ex&&y==ey)
{
if(wan[x][y]<=k)
flag=true;
return ;
}
if(wan[x][y]>k)//转弯数超过k不再往下走
return;
//x!=ex && y!=ey 说民必须至少转一次弯，但是已经不能再转了
if(wan[x][y]==k&&x!=ex&&y!=ey)
return ;
for (int i=0;i<4;i++)
{
int tx=x+x_move[i];
int ty=y+y_move[i];
if(tx<0||tx>=r||ty<0||ty>=c)//若出界
continue;
//转弯数相等不再剪枝,所以wan[tx][ty]<wan[x][y]而不是<=
if(map[tx][ty]=='*'||wan[tx][ty]<wan[x][y])//剪枝拐弯数:下一步转弯数小于前一步拐弯数,说明已遍历且更优，无须再遍历
continue;
if(dir!=-1&&i!=dir&&wan[tx][ty]<wan[x][y]+1)//剪枝拐弯数:此拐弯举动,若下一步原有拐弯数比当前步进入该处拐弯数小,说明已遍历且更优，无须再遍历
continue;
if(dir!=-1&&i!=dir)
wan[tx][ty]=wan[x][y]+1;//拐弯了
else
wan[tx][ty]=wan[x][y];//没拐弯,拐弯数不变
dfs(tx,ty,i);
if(flag)
return ;
}
}
int main()
{
int t,i,j,sx,sy;//sx,xy是起点
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&r,&c);
for(i=0;i<r;i++)
scanf("%s",map[i]);
scanf("%d%d%d%d%d",&k,&sy,&sx,&ey,&ex);//到此,结束一趟控制台数据
sx--,sy--,ex--,ey--;//我从0开始编号,而题目是从1开始
for (i=0;i<r;i++)
for (j=0;j<c;j++)
wan[i][j]=inf;//初始化转弯数和步数无穷大
wan[sx][sy]=0;//到达起点转弯数0
flag=false;
dfs(sx,sy,-1);//dir=-1表示：一开始走任意方向
if(flag)
puts("yes");
else puts("no");
}
return 0;
}
#include <iostream>
using namespace std;
#define inf 0x3fffffff//无穷大
#define M 105//数组大小
//1、wan用于转弯数剪枝;2、step用于步数兼职,就不用visit标记访问了
int r,c,ex,ey,k,wan[M][M];//行数，列数，终点x，终点y，弯数
char map[M][M];//接收控制台字符串
int x_move[4] = {-1, 0, 1, 0};//四方向移动
int y_move[4] = {0, 1, 0, -1};//四方向移动
bool flag; //判断成功
void dfs(int x,int y,int dir)//dir 为当前方向
{
if(x==ex&&y==ey)
{
if(wan[x][y]<=k)
flag=true;
return ;
}
if(wan[x][y]>k)//转弯数超过k不再往下走
return;
//x!=ex && y!=ey 说民必须至少转一次弯，但是已经不能再转了
if(wan[x][y]==k&&x!=ex&&y!=ey)
return ;
for (int i=0;i<4;i++)
{
int tx=x+x_move[i];
int ty=y+y_move[i];
if(tx<0||tx>=r||ty<0||ty>=c)//若出界
continue;
//转弯数相等不再剪枝,所以wan[tx][ty]<wan[x][y]而不是<=
if(map[tx][ty]=='*'||wan[tx][ty]<wan[x][y])//剪枝拐弯数:下一步转弯数小于前一步拐弯数,说明已遍历且更优，无须再遍历
continue;
if(dir!=-1&&i!=dir&&wan[tx][ty]<wan[x][y]+1)//剪枝拐弯数:此拐弯举动,若下一步原有拐弯数比当前步进入该处拐弯数小,说明已遍历且更优，无须再遍历
continue;
if(dir!=-1&&i!=dir)
wan[tx][ty]=wan[x][y]+1;//拐弯了
else
wan[tx][ty]=wan[x][y];//没拐弯,拐弯数不变
dfs(tx,ty,i);
if(flag)
return ;
}
}
int main()
{
int t,i,j,sx,sy;//sx,xy是起点
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&r,&c);
for(i=0;i<r;i++)
scanf("%s",map[i]);
scanf("%d%d%d%d%d",&k,&sy,&sx,&ey,&ex);//到此,结束一趟控制台数据
sx--,sy--,ex--,ey--;//我从0开始编号,而题目是从1开始
for (i=0;i<r;i++)
for (j=0;j<c;j++)
wan[i][j]=inf;//初始化转弯数和步数无穷大
wan[sx][sy]=0;//到达起点转弯数0
flag=false;
dfs(sx,sy,-1);//dir=-1表示：一开始走任意方向
if(flag)
puts("yes");
else puts("no");
}
return 0;
}
从1.4版开始，Subversion Server就自带Windows服务程序，通过执行简单的命令，即可注册为服务方式运行。本文中，主要阐述两个问题：如何将Subversion注册成windows服务；如何实现Http方式访问Svn服务器。
本文中所使用的命令及配置文件，可以从如下URL下载：http://download.csdn.net/detail/attagain/5334595
一、如何以Windows服务方式运行Subversion
1、注册服务的前提条件
A、Subversion安装路径为：“C:\Program Files (x86)\Subversion”
B、Subversion的repository路径为："E:\svn_server_repository"
2、执行命令，创建Svn的Windows服务
命令行内容：
sc create svnservice binpath= "\"C:\Program Files (x86)\Subversion\bin\svnserve.exe\" --service -r E:\svn_server_repository" displayname= "SVNService" depend= Tcpip start= auto
命令解释：
binpath= "\"C:\Program Files (x86)\Subversion\bin\svnserve.exe\" --service -r E:\svn_server_repository"----指定创建服务运行程序的路径及参数（注意：如果路径为带有空格字符时，需要使用双引号括起。其中，【\"】，引号转义符；【\"C:\Program Files (x86)\Subversion\bin\svnserve.exe\"】，Subversion注册服务需要运行的可执行程序路径；【--service】，以服务的方式运行；【-r E:\svn_server_repository】，指定Subversion的repository路径）。
displayname= "SVNService"----注册的windows服务显示名称。
depend= Tcpip ----服务所依赖的网络协议。
start= auto ----系统启动，服务自动运行。
3、删除Svn服务的方法（仅当卸载服务时使用）
命令行内容：
sc delete svnservice
4、服务的启动和停止
服务启动命令行内容：
sc start SVNService
服务停止命令行内容：
sc stop SVNService
注：Windows服务的更多操作，可以借助于【services.msc】，在图形化界面中进行。
5、创建Subversion的repository并配置权限
A、在路径【E:\svn_server_repository】下，创建想要的repository目录，比如：PG_01_01_00001_ag.fw
B、切换到目录【E:\svn_server_repository\PG_01_01_00001_ag.fw】，借助于TortoiseSVN工具菜单下的命令【create repository here】，执行创建repository命令，同时执行【create folder structure】，生成【trunk】（基线库）、【branches】（分支库）、【tags】（标签库）三个目录。当然，我们用的最多的还是第一个，如果没有branches和tags的应用，完全可以不执行B的操作。
C、在目录【E:\svn_server_repository\PG_01_01_00001_ag.fw\conf】下，设置权限信息
文件【svnserver.conf】，添加或打开如下设置：
anon-access = none
password-db = passwd
authz-db = authz
文件【authz】，添加如下设置（针对每个文件夹，设置具体权限）：
[groups]
group_adm = lihaijun
group_leader = lihaijun
group_developer = lihaijun
[/]
@group_adm = rw
@group_leader = rw
@group_developer = rw
[/00. Custom document]
@group_leader = r
@group_developer = r
[/01. Management]
@group_leader = rw
@group_developer = r
[/02. Specification]
@group_leader = rw
@group_developer = rw
[/03. Schedule]
@group_leader = rw
@group_developer = r
[/04. Design]
@group_leader = rw
@group_developer = rw
[/05. Make]
@group_leader = rw
@group_developer = rw
[/06. Test]
@group_leader = rw
@group_developer = rw
[/07. Product]
@group_leader = rw
@group_developer = rw
[/08. Quality]
@group_leader = rw
@group_developer = rw
[/09. Open Issue]
@group_leader = rw
@group_developer = rw
[/10. Companion plan]
@group_leader = rw
@group_developer = rw
[/11. Meeting]
@group_leader = rw
@group_developer = rw
[/20. Reference]
@group_leader = rw
@group_developer = rw
[/21. Tools]
@group_leader = rw
@group_developer = r
[/30. Baseline]
@group_leader = rw
@group_developer = rw
文件【authz】，添加具体用户密码信息。
6、客户端连接，从svnserver签出目录，执行批处理创建客户端目录结构。
客户端批处理内容如下：
mkdir "00. Custom document"
mkdir "01. Management"
mkdir "02. Specification"
mkdir "03. Schedule"
mkdir "04. Design"
mkdir "05. Make"
mkdir "06. Test"
mkdir "07. Product"
mkdir "08. Quality"
mkdir "09. Open Issue"
mkdir "10. Companion plan"
mkdir "11. Meeting"
mkdir "20. Reference"
mkdir "21. Tools"
mkdir "30. Baseline"
二、如何使用Apache httpd server，以Http方式访问Svn
1、安装httpd-2.2.17-win32-x86-no_ssl.msi，假定安装路径为【C:\Program Files (x86)\Apache Software Foundation\Apache2.2】。
2、根据【CollabNet】提供的Subversion服务器程序，修改httpd.conf文件。
主要添加内容如下：
LoadModule dav_module modules/mod_dav.so
LoadModule dav_svn_module modules/mod_dav_svn.so
<Location /svn>
DAV svn
SVNParentPath E:\svn_server_repository
</Location>
3、将【CollabNet】提供的Subversion服务器程序中的【mod_dav_svn.so】程序，复制到【C:\Program Files (x86)\Apache Software Foundation\Apache2.2\modules】中。
到此，配置已经完成。
本文中所使用的命令及配置文件，可以从如下URL下载：http://download.csdn.net/detail/attagain/5334595