当前位置:   article > 正文

轻量级文本搜索引擎的后台设计、实现与优化_建立网页库和网页偏移库

建立网页库和网页偏移库

转载请注明:转载 from http://blog.csdn.net/u011239443/article/details/51655480

框架

见:http://r.photo.store.qq.com/psb?/V12VvuOZ2vxbmG/M2gzPWfnBLS8buBT*16Y2xm9QkAAp8TmePOlIPC1MlM!/r/dFMAAAAAAAAA

 

1.1 生成库——词频库、词语索引库

 

流程:

 

项目包:

 

 

1.1.1 生成库——中文语料文件

 

主要流程:

中科院分词系统  ICTCLAS 的使用,例子:

杭州市长春药店。  -》   杭州市/ns 长春/nz 药店/n 。

 

 

1.1.2 生成库——词频库

 

数据结构:

1 hash_map<string ,  int ,  MyHashFn >

 

例子

 

 

1.1.3 生成库——词语索引库

 

数据结构:

1 hash_map<string ,  set<string> ,  MyHashFn >

 

例子

 
 

1.1.3 生成库——词语索引库

 
UTF-8编码

截取一个汉字,UTF-8可根据汉字的第一个字节移位推出长度

  1字节 0xxxxxxx 
  2字节 110xxxxx 10xxxxxx 
  3字节 1110xxxx 10xxxxxx 10xxxxxx 
  4字节 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 

1 if(word[i] & (1 << 4))        
2     key = word.substr(i, 4);            
3 else if(word[i] & (1 << 5))        
4     key = word.substr(i, 3);            
5 else if(word[i] & (1 << 6))        
6     key = word.substr(i, 2);            
7 else    
8     key = word.substr(i, 1);

 

 

 

 

1.2 生成库——网页库、网页偏移库

 

流程:

 

项目包

 
 
 

1.2.1 生成库——网页库

 

网页记录:

一行一条网页记录( string )

网页记录格式:

<doc><docid>网页号</docid>

<docurl>网页URL</docurl>

<doctitle>网页标题</doctitle>

<doccontent>网页内容</doccontent></doc>

 

数据结构

1 struct Page
2 {
3    int ID;
4    string  url,title,content;
5 };
1 hash_map< int , Page> 

 

例子:

 
 
 

1.2.1 生成库——网页偏移库

 

偏移记录:

一行一条偏移记录

偏移记录格式:

Page_ID    偏移量    本页大小

 

数据结构

1 hash_map<int, std::pair<int, int> >

 

例子:

 

 

 

 

1.3 生成库——网页去重、建立倒排索引

 

流程:

 

 

项目包:

 
 
 

1.3.1 生成库——网页去重

 

Top-K 算法:

•将每张网页频数top10的单词作为该网页的特征。若词频一样,则按字符序。
•两网页特征相似度 >= 60% , 则两网页重复。
 
 
 

1.3.2 生成库——建立倒排索引

 

索引:

一行一条索引

索引格式:

词语  Page_ID  词频  权值  Page_ID 词频  权值   ……

 

数据结构:

1 hash_map<std::string, std::set<std::pair<int, double> >, MyHashFn>

 

例子:

 

权值的计算:

•1、TF*IDF框架
•TF(Term Frequency) 词频
•DF (Document Frequency) 词语出现的文档数目
•N  总共的文档数目
•IDF (Invert Document Frequency) 逆文档频率

              

•IDF (Invert Document Frequency) 逆文档频率

          IDF反映了一个特征词在整个文档集合中的情况,出现的愈多IDF值越低,这个词区分不同文档的能力越差。

  大量实验表明使用以下公式效果更好:

                    

 

向量空间模型:

•Cosine相似度计算

      若词语W在包含100个词语的A网页中出现了50次,在包含1000个词语的B网页出现了100次,显然A中W的权值应该更大,但是计算结果却相反。因此,应该对权值进行标准化:                

            

 

 

 

 

2.1 线程池资源

•网页  
1 hash_map< int , Page>

 

•网页偏移  
1 hash_map<int, std::pair<int, int> >

 

•倒排索引  
1 hash_map<std::string, std::set<std::pair<int, double> >, MyHashFn>

 

•词频  
1 map<string ,  int>

 

•词语索引  
1 map<string ,  set<string>>

 

•停用词 
1  hash_map<std::string, std::string, MyHashFn>

 

•Epoll Events 、 Socket
 
•工作线程、缓存保存线程
 
•线程池纠错缓存、线程池查询结果缓存
 
•任务队列            
1 class Task
2   {
3       public: 
4       int fd; //Socket描述符  
5       Task *next; //下一个任务
6   };
1  vector<Task>

 

 

 

 

2.2 Socket工作详细

•建立Socket
 
•注册Epoll
 
•监听到Socket描述符,accept客户端,注册读操作
 
•监听到读操作,添加任务
 
•监听到写操作,输出查询结果

 

 

 

2.3.1 工作线程工作详细——纠错模块

 

•编辑距离算法

指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

例子:

计算X字符串 与 Y字符串 的 编辑距离

dp[i][j] 为 X串的前i个字符 和 Y串的前j个字符 的编辑距离

1 if(X [i - 1] == Y[j - 1])       
2     dp[i][j] = dp[i - 1][j - 1];   //最后字符相同    
3 else
4 { 
5     int t1 = dp[i - 1][j];                   // 删除X第i个字符    
6     t1 = t1 < dp[i][j - 1] ? t1 : dp[i][j - 1];   //删除Y第j个字符    
7     t1 = t1 < dp[i - 1][j - 1] ? t1 : dp[i - 1][j - 1];//最后字符改相同
8     dp[i][j] = t1 + 1;
9 }

由于需要进行汉语的编辑距离计算,这里的char转变为string,string转变为vector<string>。

 

•取任务
 
•receive客户端
 
•分词
 
•分词优化、去停用词

  ICTCLAS分词系统进行分词后的结果可能导致错误,例如:

1、对分词结果去停用词,如“的”“了”“呢”

2、简单的错别字分词优化算法

    (1)当出现连续的单个汉字时,将其合并成一个词语

    (2)当出现不连续单个汉字,且不是第一个字时,把  它并入左边词语

优化结果:

 

•查询查询结果缓存
 
•若查到,根据查询结果集合生成JSON,注册写操作,结束工作
 
•若未查到,每个词语分别查询纠错缓存
 
•若查到,直接返回正确词语
 
•若未查到,进行纠错(如编辑距离相同,选最高的词频),更新纠错缓存
 
 
 

2.3.2 工作线程工作详细——查询模块

•再次查询查询结果缓存
 
•若查到,根据查询结果集合生成JSON,注册写操作,结束工作
 
•若未查到,查询包含所有关键词的页面
 
•建立向量空间模型,计算Cosine相似度
 
•排序,生成查询结果集合
 
•生成JSON,注册写操作,结束工作
 
•Cosine相似度计算

将查询语句的特征词的权值组成向量 a

网页中对应的特征词的权值组成向量 b

查询语句与该网页的Cosine相似度:

 

 

 

 

2.4 缓存保存线程工作详细

•纠错cache 
1 hash_map<string , string , MyHashFn >  //纠错前,纠错后

 

•查询结果cache 
1 map< set<string> ,vector<pair<int, vector<double> > >  > //   关键词集合,查询结果 
 
•定时扫描线程池中的工作线程

 

•每扫描一个工作线程,将工作线程中的cache内容覆盖写入线程池cache,再将线程池中的cache内容覆盖写入该工作线程

 

•扫描结束后,将线程池中的cache写回到磁盘


             

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/469710
推荐阅读
相关标签
  

闽ICP备14008679号