信息检索与搜索引擎技术-实验3-倒排索引、正排索引.doc

XXXX大学信息工程与自动化学院学生实验报告
课程名称：信息检索与搜索引擎技术

实验项目名称
倒排索引、正排索引
指导教师

教师评语

教师签名：
年 月 日
一、上机目的及内容
1.上机目的
熟悉索引的作用和重要性；
熟悉正排索引和倒排索引及其建立；
2.上机内容
对 Doc1:清华/大学/清华/主页 Doc2:世纪/清华 Doc3:北京/大学
建立正排索引和倒排索引
二、实验环境
Windows操作系统 PC机一台，MyEclipse
三、 实验原理
将词项集合建立成为倒排索引的过程分为两个步骤:首先要将文本词项集合处理成正排索引,在建立正排索引的时候把词项列表的结构建立起来;然后再有正排索引建立成倒排索引.
正排索引的建立方法:
1. 顺序扫描集合中的词项.
2. 当遇到在文档中第一次出现的词项时,要更新词项表,如果词项列表中已近含有这个词,则把改词的DF加1,否则添加这个词项,置DF为1.
3. 然后处理词项,生成词项的出现记录信息,插入到对应词项的Hit List中。
正排索引建立完成之后，依照索引中的WordID 为单位，将DocID进行填充，然后按照WordID对所有单位进行从小到大的排序，就可以得到基本的倒排索引。要得到由WordID为键值的索引项，只需要再将WordID和DocID的存贮位置互换，并按照WordID进行归并即可。最后再将词项列表中的Pointer指针置为指向对应词项的索引项存储地址。这样得到的索引就可以用来进行检索了。
四、 实验记录
package com.liu.suoyin;
import java.util.*;
public class Suoyin {
public static void main(String[] args) {
Zhengpai zp=suoyin();
daopai(zp);
}
public static Zhengpai suoyin(){
String[][] doc ={{"清华","大学","清华","主页"},{"世纪","清华"},{"北京","大学"}};
List<Cixiang> cixiang=new ArrayList<Cixiang>();
List<Jilu> jilu=new ArrayList<Jilu>();
for(int i=0;i<doc.length;i++)
for(int j=0;j<doc[i].length;j++){

if(cixiang.size()==0){
Cixiang ci=new Cixiang();
ci.worldID=0;
ci.term=doc[i][j];
ci.DF=1;
ci.doc=i;
cixiang.add(ci);

Jilu jl=new Jilu();
jl.docID=i;
jl.wordID=0;
jl.NoOfHit=1;
jl.HitLise.add(j);
jilu.add(jl);
}else{
int k;
for(k=0;k<cixiang.size();k++){
Cixiang ci=(Cixiang)cixiang.get(k);
if(ci.term.equals(doc[i][j])){
if(ci.doc!=i)
ci.DF++;
cixiang.set(k,ci);
int m;
for( m=jilu.size()-1;m>-1;m--){
if(ci.doc==jilu.get(jilu.size()-1).docID && ci.worldID==jilu.get(m).wordID){
Jilu jl=jilu.get(m);
jl.HitLise.add(j);
jl.NoOfHit++;
jilu.set(m,jl);
break;
}
if(m==0){
Jilu jl=new Jilu();
jl.docID=i;
jl.wordID=ci.worldID;
jl.NoOfHit=1;
jl.HitLise.add(j);
jilu.add(jl);
}
}
break;
}
}
if(k==(cixiang.size())){
Cixiang ci=new Cixiang();
ci.worldID=cixiang.size();
ci.term=doc[i][j];
ci.DF=1;
cixiang.add(ci);
Jilu jl=new Jilu();
jl.docID=i;
jl.wordID=ci.worldID;
jl.NoOfHit=1;
jl.HitLise.add(j);
jilu.add(jl);
}
}
}
System.out.println("worldID Term DF");
for(int l=0;l<cixiang.size();l++){

System.out.print(((Cixiang)cixiang.get(l)).worldID+"\t");
System.out.print(((Cixiang)cixiang.get(l)).term+"\t");
System.out.println(((Cixiang)cixiang.get(l)).DF);
}
System.out.println();
System.out.println("DocID WorldID No.ofHit Hitlist");
for(int l=0;l<jilu.size();l++){
System.out.print("doc"+(1+((Jilu)jilu.get(l)).docID)+"\t");
System.out.print(((Jilu)jilu.get(l)).wordID+"\t");
System.out.print(((Jilu)jilu.get(l)).NoOfHit+"\t ");
for(int m=0;m<((Jilu)jilu.get(l)).HitLise.size();m++)
System.out.print( (int)((Jilu)jilu.get(l)).HitLise.get(m)+" ");
System.out.println();
}
Zhengpai zhengpai=new Zhengpai();
zhengpai.cixiang=cixiang;
zhengpai.jilu=jilu;
return zhengpai;
}
public static void daopai(Zhengpai zp){
List<Cixiang> cixiang=new ArrayList<Cixiang>();
List<Jilu> jilu=new ArrayList<Jilu>();
for(int i=0;i<zp.cixiang.size();i++){
Cixiang ci=zp.cixiang.get(i);
for(int j=0;j<zp.jilu.size();j++){
if(i==zp.jilu.get(j).wordID){
jilu.add(zp.jilu.get(j));
}
}
cixiang.add(ci);
}
for(int i=0;i<cixiang.size();i++){
int k=0;
for(int j=0;j<jilu.size();j++){

if(i==jilu.get(j).wordID){
if(cixiang.get(i).pointer[0]==-1){
cixiang.get(i).pointer[0]=j;
}
k=j;
}
}
cixiang.get(i).pointer[1]=k;
}
System.out.println();
System.out.println("worldID Term DF pointer");
for(int l=0;l<cixiang.size();l++){

System.out.print(((Cixiang)cixiang.get(l)).worldID+"\t");
System.out.print(((Cixiang)cixiang.get(l)).term+"\t");
System.out.print(((Cixiang)cixiang.get(l)).DF+" ");
System.out.println(((Cixiang)cixiang.get(l)).pointer[0]+","+((Cixiang)cixiang.get(l)).pointer[1]);
}
System.out.println("\nWorldID DocID No.ofHit Hitlist");
for(int l=0;l<jilu.size();l++){
System.out.print(((Jilu)jilu.get(l)).wordID+"\t");
System.out.print("doc"+(1+((Jilu)jilu.get(l)).docID)+"\t");
System.out.print(((Jilu)jilu.get(l)).NoOfHit+"\t ");
for(int m=0;m<((Jilu)jilu.get(l)).HitLise.size();m++)
System.out.print( (int)((Jilu)jilu.get(l)).HitLise.get(m)+" ");
System.out.println();
}
}
}
class Cixiang{
int worldID;
String term;
int DF;
int doc;
int[] pointer={-1,-1};
}
class Zhengpai{
List<Cixiang> cixiang=new ArrayList<Cixiang>();
List<Jilu> jilu=new ArrayList<Jilu>();
}
class Jilu{
int docID;
int wordID;
int NoOfHit;
List<Integer> HitLise=new ArrayList<Integer>();
}

运行结果：
a. 正排索引

b. 倒排索引

四、实验总结
倒排索引源于实际应用中需要根据属性的值来查找记录。倒排索引不是由记录来确定属性值，而是由属性值来确定记录的位置的。
-6-