|
倒排索引的概念很简单：就是将文件中的单词作为关键字，然后建立单词与文件的映射关系。当然，你还可以添加文件中单词出现的频数等信息。倒排索引是搜索引擎中一个很基本的概念，几乎所有的搜索引擎都会使用到倒排索引。
1.2 准备工作
5个源文件
Test0.txt, Test1.txt,Test2.txt, Test3.txt, Test4.txt
里面包含了一些英文句子，由单词组成，空格分开
Index.txt
由文件ID和文件的绝对路径构成，一个文件占一行
Result.txt
显示结果的文件，倒排索引表将在里面显示出来，单词后面跟的文件ID
1.3算法描述
使用C++的STL中的MAP存储索引表，string 存储单词，vector存储文件ID，循环读入文件，将文件中的单词一个一个读入进来，再添加上文件ID，直到所有的文件都被处理完。遍历索引表MAP,输出结果。
字典树建立，例程将26个字母映射成0~25的数字，每读入一个的单词插入单词的同时建立起字典树，每个字母有26个后继，用malloc动态分配空间，
该程序将求出输入以某个字符串为前缀的单词数量。
只能分割英文单词，建立索引表，中文词组无法分割出来
没有添加对符号的处理，符号只能随其紧挨的单词一起出现
没有统计单词频率信息
没有将单词统一处理成为它们的原型，增加了索引表的长度
因为map默认按键值弱排序，因此输出的结果是按单词的字典序输出
index.txt,result.txt是用freopen重定向打开的，这2个文件必须在源代码的同一目录下才能运行成功。
源输入文件是以绝对路径保存在index.txt中，移植运行时需改变路径
源代码：
/*
Author: lentty
created:2013-03-15 21:36
language:C++
*/
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
map<string,vector<int> > indextable;//倒排索引表
void init() //初始化表
{
indextable.clear();
}
int main()
{
//重定向从index.txt中读入，输出到result.txt，index.txt,result.txt都是在当前目录下
freopen("index.txt","r",stdin);
freopen("result.txt","w",stdout);
init();
int id; //文件名
string filepath; //文件路径名
while(cin>>id>>filepath)//从index中读入文件名和文件路径名
{
ifstream fin(filepath.c_str());//打开文件路径下的文件，参数应是c风格的字符串
string s;
while(fin>>s)//一个单词一个单词地读入
{
indextable[s].push_back(id);//把当前单词对应的文件名加入到单词对应的ID数组中
}
}
map<string,vector<int> >::iterator map_it;//索引表迭代器
map_it=indextable.begin();
while(map_it!=indextable.end())//遍历整个索引表输出，因为MAP的键值是严格弱排序，因此输出是字典序
{
string tmp=map_it->first;
cout<<tmp<<" ";
for(int i=0;i!=indextable[tmp].size();i++)
cout<<indextable[tmp][i]<<" ";
cout<<endl;
map_it++;
}
return 0;
}
运行结果：
Ability 4
Algorithmic 3
AnalysisPrinciple 3
Benjamin 2
Data 3
Database 3
Discrete 3
English 4
I 3 3 4
Initiative, 4
Mathematics 0 3
Operating 3
Peirce 2
Practical 1
Structure 3
System 3 3
The 2
There 2
Through 1
Willing 4
a 1
ability. 4
abstraction 1
activity 1
and 0 1 1 1 2 4 4 4 4
are 2
as 2
basic 4
been 1
calculation, 1
called 2
change. 0
chengdu 3
communication 4
cooperation 4
counting, 1
creations. 2
debate 2
development. 4
enthusiasm 4
etc. 3
evolved 1
exist 2
filesdocuments. 4
for 1 4
from 1
good 4 4
habits, 4
has 1
have 3 4
human 1 2
independent 4
is 0 2
knowledge, 4
learn 4
learned 3
logical 1
love 3
mathematical 2
mathematician 2
mathematics 1 1
measurement, 1
motions 1
naturally 2
numbers 2
objects 2
objects. 1
of 0 1 1 1 3
or 2
over 2
physical 1
points 2
professional 4
programming 4
progress. 4
quantity, 0
read 4
reasoning, 1
shapes 1
skill, 4
software 4
space, 0
structure, 0
study 0 1
style 4
such 2
systematic 1
the 0 1 1 1
to 4 4
use 1
well-knit 4
whether 2
write 4
| 
转播
