辰景青岛网站建设,网站开发我们都能解决,中小企业管理软件排名,从事建站业务还有前景吗前言#xff1a;本文是对博文http://blog.csdn.net/v_july_v/article/details/7085669的总结和引用 一#xff0c;什么是倒排索引 问题描述#xff1a;文档检索系统#xff0c;查询那些文件包含了某单词#xff0c;比如常见的学术论文的关键字搜索。 基本原理及要点#…前言本文是对博文http://blog.csdn.net/v_july_v/article/details/7085669的总结和引用 一什么是倒排索引 问题描述文档检索系统查询那些文件包含了某单词比如常见的学术论文的关键字搜索。 基本原理及要点为何叫倒排索引一种索引方法被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。 以英文为例下面是要被索引的文本 T0 it is what it is T1 what is it T2 it is a banana 我们就能得到下面的反向文件索引 a: {2} banana: {2} is: {0, 1, 2} it: {0, 1, 2} what: {0, 1} 检索的条件what,is和it将对应集合的交集。 正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中文档占据了中心的位置每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词而反向索引则是单词指向了包含它的文档很容易看到这个反向的关系。本章要介绍这样一个问题对倒排索引中的关键词进行编码。那么这个问题将分为两个个步骤 首先要提取倒排索引内词典文件中的关键词对提取出来的关键词进行编码。本章采取hash编码的方式。既然要用hash编码那么最重要的就是要解决hash冲突的问题下文会详细介绍。 有一点必须提醒读者的是倒排索引包含词典和倒排记录表两个部分词典一般有词项或称为关键词和词项频率即这个词项或关键词出现的次数倒排记录表则记录着上述词项或关键词所出现的位置或出现的文档及网页ID等相关信息。 24.1、正排索引与倒排索引 咱们先来看什么是倒排索引以及倒排索引与正排索引之间的区别 我们知道搜索引擎的关键步骤就是建立倒排索引所谓倒排索引一般表示为一个关键词然后是它的频度出现的次数位置出现在哪一篇文章或网页中及有关的日期作者等信息它相当于为互联网上几千亿页网页做了一个索引好比一本书的目录、标签一般。读者想看哪一个主题相关的章节直接根据目录即可找到相关的页面。不必再从书的第一页到最后一页一页一页的查找。 接下来阐述下正排索引与倒排索引的区别 一般索引正排索引 正排表是以文档的ID为关键字表中记录文档中每个字的位置信息查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。正排表结构如图1所示这种组织方法在建立索引的时候结构比较简单建立比较方便且易于维护;因为索引是基于文档建立的若是有新的文档假如直接为该文档建立一个新的索引块挂接在原来索引文件的后面。若是有文档删除则直接找到该文档号文档对因的索引信息将其直接删除。但是在查询的时候需对所有的文档进行扫描以确保没有遗漏这样就使得检索时间大大延长检索效率低下。 尽管正排表的工作原理非常的简单但是由于其检索效率太低除非在特定情况下否则实用性价值不大。 倒排索引 倒排表以字或词为关键字进行索引表中关键字所对应的记录表项记录了出现这个字或词的所有文档一个表项就是一个字表段它记录该文档的ID和字符在该文档中出现的位置情况。由于每个字或词对应的文档数量在动态变化所以倒排表的建立和维护都较为复杂但是在查询的时候由于可以一次得到查询关键字所对应的所有文档所以效率高于正排表。在全文检索中检索的快速响应是一个最为关键的性能而索引建立由于在后台进行尽管效率相对低一些但不会影响整个搜索引擎的效率。 倒排表的结构图如图2 倒排表的索引信息保存的是字或词后继数组模型、互关联后继数组模型条在文档内的位置在同一篇文档内相邻的字或词条的前后关系没有被保存到索引文件内。 24.2、倒排索引中提取关键词 倒排索引是搜索引擎之基石。建成了倒排索引后用户要查找某个query如在搜索框输入某个关键词“结构之法”后搜索引擎不会再次使用爬虫又一个一个去抓取每一个网页从上到下扫描网页看这个网页有没有出现这个关键词而是会在它预先生成的倒排索引文件中查找和匹配包含这个关键词“结构之法”的所有网页。找到了之后再按相关性度排序最终把排序后的结果显示给用户。 如下即是一个倒排索引文件不全我们把它取名为big_index文件中每一较短的不包含有“#####”符号的便是某个关键词及这个关键词的出现次数。现在要从这个大索引文件中提取出这些关键词--Firelf---11-Winter-.007007天降杀机02Chan..如何做到呢一行一行的扫描整个索引文件么 何意之前已经说过倒排索引包含词典和倒排记录表两个部分词典一般有词项或称为关键词和词项频率即这个词项或关键词出现的次数倒排记录表则记录着上述词项或关键词所出现的位置或出现的文档及网页ID等相关信息。 最简单的讲就是要提取词典中的词项关键词--Firelf---11-Winter-.007007天降杀机02Chan...。 --Firelf--关键词 8出现次数 我们可以试着这么解决通过查找#####便可判断某一行出现的词是不是关键词但如果这样做的话便要扫描整个索引文件的每一行代价实在巨大。如何提高速度呢对了关键词后面的那个出现次数为我们问题的解决起到了很好的作用如下注释所示 // 本身没有##### 的行判定为关键词行后跟这个关键词的行数N即词项频率 // 接下来截取关键词--Firelf--然后读取后面关键词的行数N // 再跳过N行滤过和避免扫描中间的倒排记录表信息 // 读取下一个关键词.. 有朋友指出上述方法虽然减少了扫描的行数但并没有减少I0开销。读者是否有更好地办法欢迎随时交流。 24.2、为提取出来的关键词编码 爱思考的朋友可能会问上述从倒排索引文件中提取出那些关键词词项的操作是为了什么呢其实如我个人微博上12月12日所述的Hash词典编码 词典文件的编码1、词典怎么生成存储和构造词典2、如何运用hash对输入的汉字进行编码3、如何更好的解决冲突即不重复以及追加功能。具体例子为事先构造好词典文件后输入一个词要求找到这个词的编码然后将其编码输出。且要有不断能添加词的功能不得重复。 步骤应该是如下1、读索引文件2、提取索引中的词出来3、词典怎么生成存储和构造词典4、词典文件的编码不重复与追加功能。编码比如输入中国他的编码可以为10001然后输入银行他的编码可以为10002。只要实现不断添加词功能以及不重复即可词典类的大文件hash最重要的是怎样避免冲突。 也就是说现在我要对上述提取出来后的关键词进行编码采取何种方式编码呢暂时用hash函数编码。编码之后的效果将是每一个关键词都有一个特定的编码如下图所示与上文big_index文件比较一下便知 --Firelf-- 对应编码为135942 -11 对应编码为106101 .... 但细心的朋友一看上图便知其中第34~39行显示有重复的编码那么如何解决这个不重复编码的问题呢 用hash表编码但其极易产生冲突碰撞为什么请看 哈希表是一种查找效率极高的数据结构很多语言都在内部实现了哈希表。PHP中的哈希表是一种极为重要的数据结构不但用于表示Array数据类型还在Zend虚拟机内部用于存储上下文环境信息执行上下文的变量及函数均使用哈希表结构存储。 理想情况下哈希表插入和查找操作的时间复杂度均为O(1)任何一个数据项可以在一个与哈希表长度无关的时间内计算出一个哈希值key然后在常量时间内定位到一个桶术语bucket表示哈希表中的一个位置。当然这是理想情况下因为任何哈希表的长度都是有限的所以一定存在不同的数据项具有相同哈希值的情况此时不同数据项被定为到同一个桶称为碰撞collision。 哈希表的实现需要解决碰撞问题碰撞解决大体有两种思路 第一种是根据某种原则将被碰撞数据定为到其它桶例如线性探测——如果数据在插入时发生了碰撞则顺序查找这个桶后面的桶将其放入第一个没有被使用的桶第二种策略是每个桶不是一个只能容纳单个数据项的位置而是一个可容纳多个数据的数据结构例如链表或红黑树所有碰撞的数据以某种数据结构的形式组织起来。 不论使用了哪种碰撞解决策略都导致插入和查找操作的时间复杂度不再是O(1)。以查找为例不能通过key定位到桶就结束必须还要比较原始key即未做哈希之前的key是否相等如果不相等则要使用与插入相同的算法继续查找直到找到匹配的值或确认数据不在哈希表中。 PHP是使用单链表存储碰撞的数据因此实际上PHP哈希表的平均查找复杂度为O(L)其中L为桶链表的平均长度而最坏复杂度为O(N)此时所有数据全部碰撞哈希表退化成单链表。下图PHP中正常哈希表和退化哈希表的示意图。 哈希表碰撞攻击就是通过精心构造数据使得所有数据全部碰撞人为将哈希表变成一个退化的单链表此时哈希表各种操作的时间均提升了一个数量级因此会消耗大量CPU资源导致系统无法快速响应请求从而达到拒绝服务攻击DoS的目的。 可以看到进行哈希碰撞攻击的前提是哈希算法特别容易找出碰撞如果是MD5或者SHA1那基本就没戏了幸运的是也可以说不幸的是大多数编程语言使用的哈希算法都十分简单这是为了效率考虑因此可以不费吹灰之力之力构造出攻击数据.上述五段文字引自http://www.codinglabs.org/html/hash-collisions-attack-on-php.html。 24.4、暴雪的Hash算法 值得一提的是在解决Hash冲突的时候搞的焦头烂额结果今天上午在自己的博客内的一篇文章十一、从头到尾彻底解析Hash表算法内找到了解决办法网上流传甚广的暴雪的Hash算法。 OK接下来咱们回顾下暴雪的hash表算法 “接下来咱们来具体分析一下一个最快的Hash表算法。我们由一个简单的问题逐步入手有一个庞大的字符串数组然后给你一个单独的字符串让你从这个数组中查找是否有这个字符串并找到它你会怎么做有一个方法最简单老老实实从头查到尾一个一个比较直到找到为止我想只要学过程序设计的人都能把这样一个程序作出来但要是有程序员把这样的程序交给用户我只能用无语来评价或许它真的能工作但...也只能如此了。最合适的算法自然是使用HashTable哈希表先介绍介绍其中的基本知识所谓Hash一般是一个整数通过某种算法可以把一个字符串压缩 成一个整数。当然无论如何一个32位整数是无法对应回一个字符串的但在程序中两个字符串计算出的Hash值相等的可能非常小下面看看在MPQ中的Hash算法 函数prepareCryptTable以下的函数生成一个长度为0x500合10进制数1280的cryptTable[0x500] 01.//函数prepareCryptTable以下的函数生成一个长度为0x500合10进制数1280的cryptTable[0x500]
02.void prepareCryptTable()
03.{
04. unsigned long seed 0x00100001, index1 0, index2 0, i;
05.
06. for( index1 0; index1 0x100; index1 )
07. {
08. for( index2 index1, i 0; i 5; i, index2 0x100 )
09. {
10. unsigned long temp1, temp2;
11.
12. seed (seed * 125 3) % 0x2AAAAB;
13. temp1 (seed 0xFFFF) 0x10;
14.
15. seed (seed * 125 3) % 0x2AAAAB;
16. temp2 (seed 0xFFFF);
17.
18. cryptTable[index2] ( temp1 | temp2 );
19. }
20. }
21.} 函数HashString以下函数计算lpszFileName 字符串的hash值其中dwHashType 为hash的类型 01.//函数HashString以下函数计算lpszFileName 字符串的hash值其中dwHashType 为hash的类型
02.unsigned long HashString(const char *lpszkeyName, unsigned long dwHashType )
03.{
04. unsigned char *key (unsigned char *)lpszkeyName;
05. unsigned long seed1 0x7FED7FED;
06. unsigned long seed2 0xEEEEEEEE;
07. int ch;
08.
09. while( *key ! 0 )
10. {
11. ch *key;
12. seed1 cryptTable[(dwHashType8) ch] ^ (seed1 seed2);
13. seed2 ch seed1 seed2 (seed25) 3;
14. }
15. return seed1;
16.} Blizzard的这个算法是非常高效的被称为One-Way Hash( A one-way hash is a an algorithm that is constructed in such a way that deriving the original string (set of strings, actually) is virtually impossible)。举个例子字符串unitneutralacritter.grp通过这个算法得到的结果是0xA26067F3。 是不是把第一个算法改进一下改成逐个比较字符串的Hash值就可以了呢答案是远远不够要想得到最快的算法就不能进行逐个的比较通常是构造一个哈希表(Hash Table)来解决问题哈希表是一个大数组这个数组的容量根据程序的要求来定义 例如1024每一个Hash值通过取模运算 (mod) 对应到数组中的一个位置这样只要比较这个字符串的哈希值对应的位置有没有被占用就可以得到最后的结果了想想这是什么速度是的是最快的O(1)现在仔细看看这个算法吧 01.typedef struct
02.{
03. int nHashA;
04. int nHashB;
05. char bExists;
06. ......
07.} SOMESTRUCTRUE;
08.//一种可能的结构体定义 函数GetHashTablePos下述函数为在Hash表中查找是否存在目标字符串有则返回要查找字符串的Hash值无则return -1. 01.//函数GetHashTablePos下述函数为在Hash表中查找是否存在目标字符串有则返回要查找字符串的Hash值无则return -1.
02.int GetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable )
03.//lpszString要在Hash表中查找的字符串lpTable为存储字符串Hash值的Hash表。
04.{
05. int nHash HashString(lpszString); //调用上述函数HashString返回要查找字符串lpszString的Hash值。
06. int nHashPos nHash % nTableSize;
07.
08. if ( lpTable[nHashPos].bExists !strcmp( lpTable[nHashPos].pString, lpszString ) )
09. { //如果找到的Hash值在表中存在且要查找的字符串与表中对应位置的字符串相同
10. return nHashPos; //返回找到的Hash值
11. }
12. else
13. {
14. return -1;
15. }
16.} 看到此我想大家都在想一个很严重的问题“如果两个字符串在哈希表中对应的位置相同怎么办”,毕竟一个数组容量是有限的这种可能性很大。解决该问题的方法很多我首先想到的就是用“链表”,感谢大学里学的数据结构教会了这个百试百灵的法宝我遇到的很多算法都可以转化成链表来解决只要在哈希表的每个入口挂一个链表保存所有对应的字符串就OK了。事情到此似乎有了完美的结局如果是把问题独自交给我解决此时我可能就要开始定义数据结构然后写代码了。 然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。” “MPQ使用文件名哈希表来跟踪内部的所有文件。但是这个表的格式与正常的哈希表有一些不同。首先它没有使用哈希作为下标把实际的文件名存储在表中用于验证实际上它根本就没有存储文件名。而是使用了3种不同的哈希一个用于哈希表的下标两个用于验证。这两个验证哈希替代了实际文件名。 当然了这样仍然会出现2个不同的文件名哈希到3个同样的哈希。但是这种情况发生的概率平均是1:18889465931478580854784这个概率对于任何人来说应该都是足够小的。现在再回到数据结构上Blizzard使用的哈希表没有使用链表而采用顺延的方式来解决问题。”下面咱们来看看这个网上流传甚广的暴雪hash算法 函数GetHashTablePos中lpszString 为要在hash表中查找的字符串lpTable 为存储字符串hash值的hash表nTableSize 为hash表的长度 表nTableSize 为hash表的长度 01.//函数GetHashTablePos中lpszString 为要在hash表中查找的字符串lpTable 为存储字符串hash值的hash表nTableSize 为hash表的长度
02.int GetHashTablePos( char *lpszString, MPQHASHTABLE *lpTable, int nTableSize )
03.{
04. const int HASH_OFFSET 0, HASH_A 1, HASH_B 2;
05.
06. int nHash HashString( lpszString, HASH_OFFSET );
07. int nHashA HashString( lpszString, HASH_A );
08. int nHashB HashString( lpszString, HASH_B );
09. int nHashStart nHash % nTableSize;
10. int nHashPos nHashStart;
11.
12. while ( lpTable[nHashPos].bExists )
13. {
14.// 如果仅仅是判断在该表中时候存在这个字符串就比较这两个hash值就可以了不用对结构体中的字符串进行比较。
15.// 这样会加快运行的速度减少hash表占用的空间这种方法一般应用在什么场合
16. if ( lpTable[nHashPos].nHashA nHashA
17. lpTable[nHashPos].nHashB nHashB )
18. {
19. return nHashPos;
20. }
21. else
22. {
23. nHashPos (nHashPos 1) % nTableSize;
24. }
25.
26. if (nHashPos nHashStart)
27. break;
28. }
29. return -1;
30.} 上述程序解释 计算出字符串的三个哈希值一个用来确定位置另外两个用来校验)察看哈希表中的这个位置哈希表中这个位置为空吗如果为空则肯定该字符串不存在返回-1。如果存在则检查其他两个哈希值是否也匹配如果匹配则表示找到了该字符串返回其Hash值。移到下一个位置如果已经移到了表的末尾则反绕到表的开始位置起继续查询 看看是不是又回到了原来的位置如果是则返回没找到回到3。 24.4、不重复Hash编码 有了上面的暴雪Hash算法。咱们的问题便可解决了。不过有两点必须先提醒读者1、Hash表起初要初始化2、暴雪的Hash算法对于查询那样处理可以但对插入就不能那么解决。 关键主体代码如下 01.//函数prepareCryptTable以下的函数生成一个长度为0x500合10进制数1280的cryptTable[0x500]
02.void prepareCryptTable()
03.{
04. unsigned long seed 0x00100001, index1 0, index2 0, i;
05.
06. for( index1 0; index1 0x100; index1 )
07. {
08. for( index2 index1, i 0; i 5; i, index2 0x100)
09. {
10. unsigned long temp1, temp2;
11. seed (seed * 125 3) % 0x2AAAAB;
12. temp1 (seed 0xFFFF)0x10;
13. seed (seed * 125 3) % 0x2AAAAB;
14. temp2 (seed 0xFFFF);
15. cryptTable[index2] ( temp1 | temp2 );
16. }
17. }
18.}
19.
20.//函数HashString以下函数计算lpszFileName 字符串的hash值其中dwHashType 为hash的类型
21.unsigned long HashString(const char *lpszkeyName, unsigned long dwHashType )
22.{
23. unsigned char *key (unsigned char *)lpszkeyName;
24. unsigned long seed1 0x7FED7FED;
25. unsigned long seed2 0xEEEEEEEE;
26. int ch;
27.
28. while( *key ! 0 )
29. {
30. ch *key;
31. seed1 cryptTable[(dwHashType8) ch] ^ (seed1 seed2);
32. seed2 ch seed1 seed2 (seed25) 3;
33. }
34. return seed1;
35.}
36.
37./
38.//function: 哈希词典 编码
39.//parameter:
40.//author: lei.zhou
41.//time: 2011-12-14
42./
43.MPQHASHTABLE TestHashTable[nTableSize];
44.int TestHashCTable[nTableSize];
45.int TestHashDTable[nTableSize];
46.key_list test_data[nTableSize];
47.
48.//直接调用上面的hashstringnHashPos就是对应的HASH值。
49.int insert_string(const char *string_in)
50.{
51. const int HASH_OFFSET 0, HASH_C 1, HASH_D 2;
52. unsigned int nHash HashString(string_in, HASH_OFFSET);
53. unsigned int nHashC HashString(string_in, HASH_C);
54. unsigned int nHashD HashString(string_in, HASH_D);
55. unsigned int nHashStart nHash % nTableSize;
56. unsigned int nHashPos nHashStart;
57. int ln, ires 0;
58.
59. while (TestHashTable[nHashPos].bExists)
60. {
61.// if (TestHashCTable[nHashPos] (int) nHashC TestHashDTable[nHashPos] (int) nHashD)
62.// break;
63.// //...
64.// else
65. //如之前所提示读者的那般暴雪的Hash算法对于查询那样处理可以但对插入就不能那么解决
66. nHashPos (nHashPos 1) % nTableSize;
67.
68. if (nHashPos nHashStart)
69. break;
70. }
71.
72. ln strlen(string_in);
73. if (!TestHashTable[nHashPos].bExists (ln nMaxStrLen))
74. {
75. TestHashCTable[nHashPos] nHashC;
76. TestHashDTable[nHashPos] nHashD;
77.
78. test_data[nHashPos] (KEYNODE *) malloc (sizeof(KEYNODE) * 1);
79. if(test_data[nHashPos] NULL)
80. {
81. printf(10000 EMS ERROR !!!!\n);
82. return 0;
83. }
84.
85. test_data[nHashPos]-pkey (char *)malloc(ln1);
86. if(test_data[nHashPos]-pkey NULL)
87. {
88. printf(10000 EMS ERROR !!!!\n);
89. return 0;
90. }
91.
92. memset(test_data[nHashPos]-pkey, 0, ln1);
93. strncpy(test_data[nHashPos]-pkey, string_in, ln);
94. *((test_data[nHashPos]-pkey)ln) 0;
95. test_data[nHashPos]-weight nHashPos;
96.
97. TestHashTable[nHashPos].bExists 1;
98. }
99. else
100. {
101. if(TestHashTable[nHashPos].bExists)
102. printf(30000 in the hash table %s !!!\n, string_in);
103. else
104. printf(90000 strkey error !!!\n);
105. }
106. return nHashPos;
107.} 接下来要读取索引文件big_index对其中的关键词进行编码为了简单起见直接一行一行扫描读写没有跳过行数了 01.void bigIndex_hash(const char *docpath, const char *hashpath)
02.{
03. FILE *fr, *fw;
04. int len;
05. char *pbuf, *p;
06. char dockey[TERM_MAX_LENG];
07.
08. if(docpath NULL || *docpath \0)
09. return;
10.
11. if(hashpath NULL || *hashpath \0)
12. return;
13.
14. fr fopen(docpath, rb); //读取文件docpath
15. fw fopen(hashpath, wb);
16. if(fr NULL || fw NULL)
17. {
18. printf(open read or write file error!\n);
19. return;
20. }
21.
22. pbuf (char*)malloc(BUFF_MAX_LENG);
23. if(pbuf NULL)
24. {
25. fclose(fr);
26. return ;
27. }
28.
29. memset(pbuf, 0, BUFF_MAX_LENG);
30.
31. while(fgets(pbuf, BUFF_MAX_LENG, fr))
32. {
33. len GetRealString(pbuf);
34. if(len 1)
35. continue;
36. p strstr(pbuf, #####);
37. if(p ! NULL)
38. continue;
39.
40. p strstr(pbuf, );
41. if (p NULL)
42. {
43. printf(file contents error!);
44. }
45.
46. len p - pbuf;
47. dockey[0] 0;
48. strncpy(dockey, pbuf, len);
49.
50. dockey[len] 0;
51.
52. int num insert_string(dockey);
53.
54. dockey[len] ;
55. dockey[len1] \0;
56. char str[20];
57. itoa(num, str, 10);
58.
59. strcat(dockey, str);
60. dockey[lenstrlen(str)1] \0;
61. fprintf (fw, %s\n, dockey);
62.
63. }
64. free(pbuf);
65. fclose(fr);
66. fclose(fw);
67.} 主函数已经很简单了如下 01.int main()
02.{
03. prepareCryptTable(); //Hash表起初要初始化
04.
05. //现在要把整个big_index文件插入hash表以取得编码结果
06. bigIndex_hash(big_index.txt, hashpath.txt);
07. system(pause);
08.
09. return 0;
10.} 程序运行后生成的hashpath.txt文件如下 如上所示采取暴雪的Hash算法并在插入的时候做适当处理当再次对上文中的索引文件big_index进行Hash编码后冲突问题已经得到初步解决。当然还有待更进一步更深入的测试。 后续添上数目索引1~10000... 后来又为上述文件中的关键词编了码一个计数的内码不过奇怪的是同样的代码在Dev C 与VS2010上运行结果却不同左边dev上计数从1开始VS上计数从“1994014002”开始如下图所示 在上面的bigIndex_hashcode函数的基础上修改如下即可得到上面的效果 01.void bigIndex_hashcode(const char *in_file_path, const char *out_file_path)
02.{
03. FILE *fr, *fw;
04. int len, value;
05. char *pbuf, *pleft, *p;
06. char keyvalue[TERM_MAX_LENG], str[WORD_MAX_LENG];
07.
08. if(in_file_path NULL || *in_file_path \0) {
09. printf(input file path error!\n);
10. return;
11. }
12.
13. if(out_file_path NULL || *out_file_path \0) {
14. printf(output file path error!\n);
15. return;
16. }
17.
18. fr fopen(in_file_path, r); //读取in_file_path路径文件
19. fw fopen(out_file_path, w);
20.
21. if(fr NULL || fw NULL)
22. {
23. printf(open read or write file error!\n);
24. return;
25. }
26.
27. pbuf (char*)malloc(BUFF_MAX_LENG);
28. pleft (char*)malloc(BUFF_MAX_LENG);
29. if(pbuf NULL || pleft NULL)
30. {
31. printf(allocate memory error!);
32. fclose(fr);
33. return ;
34. }
35.
36. memset(pbuf, 0, BUFF_MAX_LENG);
37.
38. int offset 1;
39. while(fgets(pbuf, BUFF_MAX_LENG, fr))
40. {
41. if (--offset 0)
42. continue;
43.
44. if(GetRealString(pbuf) 1)
45. continue;
46.
47. p strstr(pbuf, #####);
48. if(p ! NULL)
49. continue;
50.
51. p strstr(pbuf, );
52. if (p NULL)
53. {
54. printf(file contents error!);
55. }
56.
57. len p - pbuf;
58.
59. // 确定跳过行数
60. strcpy(pleft, p1);
61. offset atoi(pleft) 1;
62.
63. strncpy(keyvalue, pbuf, len);
64. keyvalue[len] \0;
65. value insert_string(keyvalue);
66.
67. if (value ! -1) {
68.
69. // key value中插入空格
70. keyvalue[len] ;
71. keyvalue[len1] \0;
72.
73. itoa(value, str, 10);
74. strcat(keyvalue, str);
75.
76. keyvalue[lenstrlen(str)1] ;
77. keyvalue[lenstrlen(str)2] \0;
78.
79. keysize;
80. itoa(keysize, str, 10);
81. strcat(keyvalue, str);
82.
83. // 将key value写入文件
84. fprintf (fw, %s\n, keyvalue);
85.
86. }
87. }
88. free(pbuf);
89. fclose(fr);
90. fclose(fw);
91.} 第二部分于给定的文档生成倒排索引 第一节、索引的构建方法 根据信息检索导论Christtopher D.Manning等著王斌译一书给的提示我们可以选择两种构建索引的算法BSBI算法与SPIMI算法。 BSBI算法基于磁盘的外部排序算法此算法首先将词项映射成其ID的数据结构如Hash映射。而后将文档解析成词项ID-文档ID对并在内存中一直处理直到累积至放满一个固定大小的块空间为止我们选择合适的块大小使之能方便加载到内存中并允许在内存中快速排序快速排序后的块转换成倒排索引格式后写入磁盘。 建立倒排索引的步骤如下 将文档分割成几个大小相等的部分对词项ID-文档ID进行排序将具有同一词项ID的所有文档ID放到倒排记录表中其中每条倒排记录仅仅是一个文档ID将基于块的倒排索引写到磁盘上。此算法假如说最后可能会产生10个块。其伪码如下 [cpp] view plaincopyprint? BSBI NDEXConSTRUCTION() n - 0 while(all documents have not been processed) do n-n1 block - PARSENEXTBLOCK() //文档分析 BSBI-INVERT(block) WRITEBLOCKTODISK(block,fn) MERGEBLOCKS(f1,...,fn;fmerged) BSBI NDEXConSTRUCTION()
n - 0
while(all documents have not been processed)do n-n1block - PARSENEXTBLOCK() //文档分析BSBI-INVERT(block)WRITEBLOCKTODISK(block,fn)MERGEBLOCKS(f1,...,fn;fmerged) 基于块的排序索引算法该算法将每个块的倒排索引文件存入文件f1,...,fn中最后合并成fmerged如果该算法应用最后一步产生了10个块那么接下来便会将10个块索引同时合并成一个索引文件。 合并时同时打开所有块对应的文件内存中维护了为10个块准备的读缓冲区和一个为最终合并索引准备的写缓冲区。每次迭代中利用优先级队列如堆结构或类似的数据结构选择最小的未处理的词项ID进行处理。如下图所示图片引自深入搜索引擎--海里信息的压缩、索引和查询梁斌译分块索引分块排序最终全部合并说实话跟MapReduce还是有些类似的 读入该词项的倒排记录表并合并合并结果写回磁盘中。需要时再次从文件中读入数据到每个读缓冲区基于磁盘的外部排序算法的更多可以参考程序员编程艺术第十章、如何给10^7个数据量的磁盘文件排序。 BSBI算法主要的时间消耗在排序上选择什么排序方法呢简单的快速排序足矣其时间复杂度为ON*logN其中N是所需要排序的项词项ID-文档ID对的数目的上界。 SPIMI算法内存式单遍扫描索引算法 与上述BSBI算法不同的是SPIMI使用词项而不是其ID它将每个块的词典写入磁盘对于写一块则重新采用新的词典只要硬盘空间足够大它能索引任何大小的文档集。 倒排索引 词典关键词或词项词项频率倒排记录表。建倒排索引的步骤如下 从头开始扫描每一个词项-文档ID信息对遇一词构建索引继续扫描若遇一新词则再建一新索引块加入词典通过Hash表实现同时建一新的倒排记录表若遇一旧词则找到其倒排记录表的位置添加其后在内存内基于分块完成排序后合并分块写入磁盘。其伪码如下 [cpp] view plaincopyprint? SPIMI-Invert(Token_stream) output.fileNEWFILE() dictionary NEWHASH() while (free memory available) do token -next(token_stream) //逐一处理每个词项-文档ID对 if term(token) !(- dictionary then postings_list AddToDictionary(dictionary,term(token)) //如果词项是第一次出现那么加入hash词典同时建立一个新的倒排索引表 else postings_list GetPostingList(dictionary,term(token)) //如果不是第一次出现那么直接返回其倒排记录表在下面添加其后 if full(postings_list) then postings_list DoublePostingList(dictionary,term(token)) AddToPosTingsList (postings_list,docID(token)) //SPIMI与BSBI的区别就在于此前者直接在倒排记录表中增加此项新纪录 sorted_terms - SortTerms(dictionary) WriteBlockToDisk(sorted_terms,dictionary,output_file) return output_file SPIMI-Invert(Token_stream)
output.fileNEWFILE()
dictionary NEWHASH()
while (free memory available)do token -next(token_stream) //逐一处理每个词项-文档ID对if term(token) !(- dictionarythen postings_list AddToDictionary(dictionary,term(token)) //如果词项是第一次出现那么加入hash词典同时建立一个新的倒排索引表else postings_list GetPostingList(dictionary,term(token)) //如果不是第一次出现那么直接返回其倒排记录表在下面添加其后if full(postings_list)then postings_list DoublePostingList(dictionary,term(token))AddToPosTingsList (postings_list,docID(token)) //SPIMI与BSBI的区别就在于此前者直接在倒排记录表中增加此项新纪录
sorted_terms - SortTerms(dictionary)
WriteBlockToDisk(sorted_terms,dictionary,output_file)
return output_file SPIMI与BSBI的主要区别 SPIMI当发现关键词是第一次出现时会直接在倒排记录表中增加一项与BSBI算法不同。同时与BSBI算法一开始就整理出所有的词项ID-文档ID并对它们进行排序的做法不同而这恰恰是BSBI的做法这里的每个倒排记录表都是动态增长的也就是说倒排记录表的大小会不断调整同时扫描一遍就可以实现全体倒排记录表的收集。 SPIMI这样做有两点好处: 由于不需要排序操作因此处理的速度更快由于保留了倒排记录表对词项的归属关系因此能节省内存词项的ID也不需要保存。这样每次单独的SPIMI-Invert调用能够处理的块大小可以非常大整个倒排索引的构建过程也可以非常高效。 但不得不提的是由于事先并不知道每个词项的倒排记录表大小算法一开始只能分配一个较小的倒排记录表空间每次当该空间放满的时候就会申请加倍的空间 与此同时自然而然便会浪费一部分空间当然此前因为不保存词项ID倒也省下一点空间总体而言算作是抵销了。 不过至少SPIMI所用的空间会比BSBI所用空间少。当内存耗尽后包括词典和倒排记录表的块索引将被写到磁盘上但在此之前为使倒排记录表按照词典顺序来加快最后的合并操作所以要对词项进行排序操作。 小数据量与大数据量的区别 在小数据量时有足够的内存保证该创建过程可以一次完成 数据规模增大后可以采用分组索引然后再归并索 引的策略。该策略是 建立索引的模块根据当时运行系统所在的计算机的内存大小将索引分为 k 组使得每组运算所需内存都小于系统能够提供的最大使用内存的大小。按照倒排索引的生成算法生成 k 组倒排索引。然后将这 k 组索引归并即将相同索引词对应的数据合并到一起就得到了以索引词为主键的最终的倒排文件索引即反向索引。为了测试的方便本文针对小数据量进行从正排文档到倒排索引文件的实现。而且针对大数量的K路归并算法或基于磁盘的外部排序算法本编程艺术系列第十章中已有详细阐述。 第二节、Hash表的构建与实现 如下给定如下图所示的正排文档每一行的信息分别为中间用##########隔开文档ID、订阅源子频道、 频道分类、 网站类ID大频道、时间、 md5、文档权值、关键词、作者等等。 要求基于给定的上述正排文档。生成如第二十四章所示的倒排索引文件注关键词所在的文章如果是同一个日期的话是挨在同一行的用“#”符号隔开 我们知道为网页建立全文索引是网页预处理的核心部分包括分析网页和建立倒排文件。二者是顺序进行先分析网页后建立倒排文件也称为反向索引如图所示 正如上图粗略所示我们知道倒排索引创建的过程如下 写爬虫抓取相关的网页而后提取相关网页或文章中所有的关键词分词找出所有单词过滤不相干的信息如广告等信息构建倒排索引关键词文章ID 出现次数 出现的位置生成词典文件 频率文件 位置文件压缩。建相关的数据结构 根据给定的正排文档我们可以建立如下的两个结构体表示这些信息文档ID、订阅源子频道、 频道分类、 网站类ID大频道、时间、 md5、文档权值、关键词、作者等等。如下所示 01.typedef struct key_node
02.{
03. char *pkey; // 关键词实体
04. int count; // 关键词出现次数
05. int pos; // 关键词在hash表中位置
06. struct doc_node *next; // 指向文档结点
07.}KEYNODE, *key_list;
08.
09.key_list key_array[TABLE_SIZE];
10.
11.typedef struct doc_node
12.{
13. char id[WORD_MAX_LEN]; //文档ID
14. int classOne; //订阅源子频道
15. char classTwo[WORD_MAX_LEN]; //频道分类
16. int classThree; //网站类ID大频道
17. char time[WORD_MAX_LEN]; //时间
18. char md5[WORD_MAX_LEN]; //md5
19. int weight; //文档权值
20. struct doc_node *next;
21.}DOCNODE, *doc_list; 我们知道通过第二十四章的暴雪的Hash表算法可以比较好的避免相关冲突的问题。下面我们再次引用其代码 基于暴雪的Hash之上的改造算 01.//函数prepareCryptTable以下的函数生成一个长度为0x100的cryptTable[0x100]
02.void PrepareCryptTable()
03.{
04. unsigned long seed 0x00100001, index1 0, index2 0, i;
05.
06. for( index1 0; index1 0x100; index1 )
07. {
08. for( index2 index1, i 0; i 5; i, index2 0x100)
09. {
10. unsigned long temp1, temp2;
11. seed (seed * 125 3) % 0x2AAAAB;
12. temp1 (seed 0xFFFF)0x10;
13. seed (seed * 125 3) % 0x2AAAAB;
14. temp2 (seed 0xFFFF);
15. cryptTable[index2] ( temp1 | temp2 );
16. }
17. }
18.}
19.
20.//函数HashString以下函数计算lpszFileName 字符串的hash值其中dwHashType 为hash的类型
21.unsigned long HashString(const char *lpszkeyName, unsigned long dwHashType )
22.{
23. unsigned char *key (unsigned char *)lpszkeyName;
24. unsigned long seed1 0x7FED7FED;
25. unsigned long seed2 0xEEEEEEEE;
26. int ch;
27.
28. while( *key ! 0 )
29. {
30. ch *key;
31. seed1 cryptTable[(dwHashType8) ch] ^ (seed1 seed2);
32. seed2 ch seed1 seed2 (seed25) 3;
33. }
34. return seed1;
35.}
36.
37.//按关键字查询如果成功返回hash表中索引位置
38.key_list SearchByString(const char *string_in)
39.{
40. const int HASH_OFFSET 0, HASH_C 1, HASH_D 2;
41. unsigned int nHash HashString(string_in, HASH_OFFSET);
42. unsigned int nHashC HashString(string_in, HASH_C);
43. unsigned int nHashD HashString(string_in, HASH_D);
44. unsigned int nHashStart nHash % TABLE_SIZE;
45. unsigned int nHashPos nHashStart;
46.
47. while (HashTable[nHashPos].bExists)
48. {
49. if (HashATable[nHashPos] (int) nHashC HashBTable[nHashPos] (int) nHashD)
50. {
51. break;
52. //查询与插入不同此处不需修改
53. }
54. else
55. {
56. nHashPos (nHashPos 1) % TABLE_SIZE;
57. }
58.
59. if (nHashPos nHashStart)
60. {
61. break;
62. }
63. }
64.
65. if( key_array[nHashPos] strlen(key_array[nHashPos]-pkey))
66. {
67. return key_array[nHashPos];
68. }
69.
70. return NULL;
71.}
72.
73.//按索引查询如果成功返回关键字此函数在本章中没有被用到可以忽略
74.key_list SearchByIndex(unsigned int nIndex)
75.{
76. unsigned int nHashPos nIndex;
77. if (nIndex TABLE_SIZE)
78. {
79. if(key_array[nHashPos] strlen(key_array[nHashPos]-pkey))
80. {
81. return key_array[nHashPos];
82. }
83. }
84.
85. return NULL;
86.}
87.
88.//插入关键字如果成功返回hash值
89.int InsertString(const char *str)
90.{
91. const int HASH_OFFSET 0, HASH_A 1, HASH_B 2;
92. unsigned int nHash HashString(str, HASH_OFFSET);
93. unsigned int nHashA HashString(str, HASH_A);
94. unsigned int nHashB HashString(str, HASH_B);
95. unsigned int nHashStart nHash % TABLE_SIZE;
96. unsigned int nHashPos nHashStart;
97. int len;
98.
99. while (HashTable[nHashPos].bExists)
100. {
101. nHashPos (nHashPos 1) % TABLE_SIZE;
102.
103. if (nHashPos nHashStart)
104. break;
105. }
106.
107. len strlen(str);
108. if (!HashTable[nHashPos].bExists (len WORD_MAX_LEN))
109. {
110. HashATable[nHashPos] nHashA;
111. HashBTable[nHashPos] nHashB;
112.
113. key_array[nHashPos] (KEYNODE *) malloc (sizeof(KEYNODE) * 1);
114. if(key_array[nHashPos] NULL)
115. {
116. printf(10000 EMS ERROR !!!!\n);
117. return 0;
118. }
119.
120. key_array[nHashPos]-pkey (char *)malloc(len1);
121. if(key_array[nHashPos]-pkey NULL)
122. {
123. printf(10000 EMS ERROR !!!!\n);
124. return 0;
125. }
126.
127. memset(key_array[nHashPos]-pkey, 0, len1);
128. strncpy(key_array[nHashPos]-pkey, str, len);
129. *((key_array[nHashPos]-pkey)len) 0;
130. key_array[nHashPos]-pos nHashPos;
131. key_array[nHashPos]-count 1;
132. key_array[nHashPos]-next NULL;
133. HashTable[nHashPos].bExists 1;
134. return nHashPos;
135. }
136.
137. if(HashTable[nHashPos].bExists)
138. printf(30000 in the hash table %s !!!\n, str);
139. else
140. printf(90000 strkey error !!!\n);
141. return -1;
142.} 有了这个Hash表接下来我们就可以把词插入Hash表进行存储了。 第三节、倒排索引文件的生成与实现 Hash表实现了存于HashSearch.h中还得编写一系列的函数如下所示所有代码还只是初步实现了功能稍后在第四部分中将予以改进与优化 [cpp] view plaincopyprint? //处理空白字符和空白行 int GetRealString(char *pbuf) { int len strlen(pbuf) - 1; while (len 0 (pbuf[len] (char)0x0d || pbuf[len] (char)0x0a || pbuf[len] || pbuf[len] \t)) { len--; } if (len 0) { *pbuf \0; return len; } pbuf[len1] \0; return len 1; } //重新strcoll字符串比较函数 int strcoll(const void *s1, const void *s2) { char *c_s1 (char *)s1; char *c_s2 (char *)s2; while (*c_s1 *c_s2) { if (*c_s1 \0) { return 0; } } return *c_s1 - *--c_s2; } //从行缓冲中得到各项信息将其写入items数组 void GetItems(char *move, int count, int wordnum) { char *front move; bool flag false; int len; move strstr(move, #####); if (*(move 5) #) { flag true; } if (move) { len move - front; strncpy(items[count], front, len); } items[count][len] \0; count; if (flag) { move move 10; } else { move move 5; } } //保存关键字相应的文档内容 doc_list SaveItems() { doc_list infolist (doc_list) malloc(sizeof(DOCNODE)); strcpy_s(infolist-id, items[0]); infolist-classOne atoi(items[1]); strcpy_s(infolist-classTwo, items[2]); infolist-classThree atoi(items[3]); strcpy_s(infolist-time, items[4]); strcpy_s(infolist-md5, items[5]); infolist-weight atoi(items[6]); return infolist; } //得到目录下所有文件名 int GetFileName(char filename[][FILENAME_MAX_LEN]) { _finddata_t file; long handle; int filenum 0; //C:\Users\zhangxu\Desktop\CreateInvertedIndex\data if ((handle _findfirst(C:\\Users\\zhangxu\\Desktop\\CreateInvertedIndex\\data\\*.txt, file)) -1) { printf(Not Found\n); } else { do { strcpy_s(filename[filenum], file.name); } while (!_findnext(handle, file)); } _findclose(handle); return filenum; } //以读方式打开文件如果成功返回文件指针 FILE* OpenReadFile(int index, char filename[][FILENAME_MAX_LEN]) { char *abspath; char dirpath[] {data\\}; abspath (char *)malloc(ABSPATH_MAX_LEN); strcpy_s(abspath, ABSPATH_MAX_LEN, dirpath); strcat_s(abspath, FILENAME_MAX_LEN, filename[index]); FILE *fp fopen (abspath, r); if (fp NULL) { printf(open read file error!\n); return NULL; } else { return fp; } } //以写方式打开文件如果成功返回文件指针 FILE* OpenWriteFile(const char *in_file_path) { if (in_file_path NULL) { printf(output file path error!\n); return NULL; } FILE *fp fopen(in_file_path, w); if (fp NULL) { printf(open write file error!\n); } return fp; } //处理空白字符和空白行
int GetRealString(char *pbuf)
{int len strlen(pbuf) - 1;while (len 0 (pbuf[len] (char)0x0d || pbuf[len] (char)0x0a || pbuf[len] || pbuf[len] \t)) {len--;}if (len 0) {*pbuf \0;return len;}pbuf[len1] \0;return len 1;
}//重新strcoll字符串比较函数
int strcoll(const void *s1, const void *s2)
{char *c_s1 (char *)s1;char *c_s2 (char *)s2;while (*c_s1 *c_s2){if (*c_s1 \0) {return 0;}}return *c_s1 - *--c_s2;
}//从行缓冲中得到各项信息将其写入items数组
void GetItems(char *move, int count, int wordnum)
{char *front move;bool flag false;int len;move strstr(move, #####);if (*(move 5) #) {flag true;}if (move) {len move - front;strncpy(items[count], front, len);}items[count][len] \0;count;if (flag) {move move 10;} else {move move 5;}
}//保存关键字相应的文档内容
doc_list SaveItems()
{doc_list infolist (doc_list) malloc(sizeof(DOCNODE));strcpy_s(infolist-id, items[0]);infolist-classOne atoi(items[1]);strcpy_s(infolist-classTwo, items[2]);infolist-classThree atoi(items[3]);strcpy_s(infolist-time, items[4]);strcpy_s(infolist-md5, items[5]); infolist-weight atoi(items[6]);return infolist;
}//得到目录下所有文件名
int GetFileName(char filename[][FILENAME_MAX_LEN])
{_finddata_t file;long handle;int filenum 0;//C:\Users\zhangxu\Desktop\CreateInvertedIndex\dataif ((handle _findfirst(C:\\Users\\zhangxu\\Desktop\\CreateInvertedIndex\\data\\*.txt, file)) -1) {printf(Not Found\n);} else {do {strcpy_s(filename[filenum], file.name);} while (!_findnext(handle, file));} _findclose(handle);return filenum;
}//以读方式打开文件如果成功返回文件指针
FILE* OpenReadFile(int index, char filename[][FILENAME_MAX_LEN])
{char *abspath;char dirpath[] {data\\};abspath (char *)malloc(ABSPATH_MAX_LEN);strcpy_s(abspath, ABSPATH_MAX_LEN, dirpath);strcat_s(abspath, FILENAME_MAX_LEN, filename[index]);FILE *fp fopen (abspath, r);if (fp NULL) {printf(open read file error!\n);return NULL;} else {return fp;}
}//以写方式打开文件如果成功返回文件指针
FILE* OpenWriteFile(const char *in_file_path)
{if (in_file_path NULL) {printf(output file path error!\n);return NULL;}FILE *fp fopen(in_file_path, w);if (fp NULL) {printf(open write file error!\n);}return fp;
} 最后主函数编写如下 [cpp] view plaincopyprint? int main() { key_list keylist; char *pbuf, *move; int filenum GetFileName(filename); FILE *fr; pbuf (char *)malloc(BUF_MAX_LEN); memset(pbuf, 0, BUF_MAX_LEN); FILE *fw OpenWriteFile(index.txt); if (fw NULL) { return 0; } PrepareCryptTable(); //初始化Hash表 int wordnum 0; for (int i 0; i filenum; i) { fr OpenReadFile(i, filename); if (fr NULL) { break; } // 每次读取一行处理 while (fgets(pbuf, BUF_MAX_LEN, fr)) { int count 0; move pbuf; if (GetRealString(pbuf) 1) continue; while (move ! NULL) { // 找到第一个非#的字符 while (*move #) move; if (!strcmp(move, )) break; GetItems(move, count, wordnum); } for (int i 7; i count; i) { // 将关键字对应的文档内容加入文档结点链表中 if (keylist SearchByString(items[i])) //到hash表内查询 { doc_list infolist SaveItems(); infolist-next keylist-next; keylist-count; keylist-next infolist; } else { // 如果关键字第一次出现则将其加入hash表 int pos InsertString(items[i]); //插入hash表 keylist key_array[pos]; doc_list infolist SaveItems(); infolist-next NULL; keylist-next infolist; if (pos ! -1) { strcpy_s(words[wordnum], items[i]); } } } } } // 通过快排对关键字进行排序 qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll); // 遍历关键字数组将关键字及其对应的文档内容写入文件中 for (int i 0; i WORD_MAX_NUM; i) { keylist SearchByString(words[i]); if (keylist ! NULL) { fprintf(fw, %s %d\n, words[i], keylist-count); doc_list infolist keylist-next; for (int j 0; j keylist-count; j) { //文档ID订阅源子频道 频道分类 网站类ID大频道 时间 md5文档权值 fprintf(fw, %s %d %s %d %s %s %d\n, infolist-id, infolist-classOne, infolist-classTwo, infolist-classThree, infolist-time, infolist-md5, infolist-weight); infolist infolist-next; } } } free(pbuf); fclose(fr); fclose(fw); system(pause); return 0; } int main()
{ key_list keylist; char *pbuf, *move; int filenum GetFileName(filename); FILE *fr; pbuf (char *)malloc(BUF_MAX_LEN); memset(pbuf, 0, BUF_MAX_LEN); FILE *fw OpenWriteFile(index.txt); if (fw NULL) { return 0; } PrepareCryptTable(); //初始化Hash表 int wordnum 0; for (int i 0; i filenum; i) { fr OpenReadFile(i, filename); if (fr NULL) { break; } // 每次读取一行处理 while (fgets(pbuf, BUF_MAX_LEN, fr)) { int count 0; move pbuf; if (GetRealString(pbuf) 1) continue; while (move ! NULL) { // 找到第一个非#的字符 while (*move #) move; if (!strcmp(move, )) break; GetItems(move, count, wordnum); } for (int i 7; i count; i) { // 将关键字对应的文档内容加入文档结点链表中 if (keylist SearchByString(items[i])) //到hash表内查询 { doc_list infolist SaveItems(); infolist-next keylist-next; keylist-count; keylist-next infolist; } else { // 如果关键字第一次出现则将其加入hash表 int pos InsertString(items[i]); //插入hash表 keylist key_array[pos]; doc_list infolist SaveItems(); infolist-next NULL; keylist-next infolist; if (pos ! -1) { strcpy_s(words[wordnum], items[i]); } } } } } // 通过快排对关键字进行排序 qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll); // 遍历关键字数组将关键字及其对应的文档内容写入文件中 for (int i 0; i WORD_MAX_NUM; i) { keylist SearchByString(words[i]); if (keylist ! NULL) { fprintf(fw, %s %d\n, words[i], keylist-count); doc_list infolist keylist-next; for (int j 0; j keylist-count; j) { //文档ID订阅源子频道 频道分类 网站类ID大频道 时间 md5文档权值 fprintf(fw, %s %d %s %d %s %s %d\n, infolist-id, infolist-classOne, infolist-classTwo, infolist-classThree, infolist-time, infolist-md5, infolist-weight); infolist infolist-next; } } } free(pbuf); fclose(fr); fclose(fw); system(pause); return 0;
} 程序编译运行后生成的倒排索引文件为index.txt其与原来给定的正排文档对照如下 有没有发现关键词奥恰洛夫出现在的三篇文章是同一个日期1210的貌似与本文开头指定的倒排索引格式要求不符因为第二部分开头中已明确说明“注关键词所在的文章如果是同一个日期的话是挨在同一行的用“#”符号隔开”。OK有疑问是好事代表你思考了请直接转至下文第4部分。 第四节、程序需求功能的改进 4.1、对相同日期与不同日期的处理 细心的读者可能还是会注意到在第二部分开头中要求基于给定的上述正排文档。生成如第二十四章所示的倒排索引文件是下面这样子的即是 也就是说上面建索引的过程本该是如下的 与第一部分所述的SMIPI算法有什么区别对的就在于对在同一个日期的出现的关键词的处理。如果是遇一旧词则找到其倒排记录表的位置相同日期添加到之前同一日期的记录之后第一个记录的后面记下同一日期的记录数目不同日期另起一行新增记录。 相同单个日期根据文档权值排序不同日期根据时间排序 代码主要修改如下 [cpp] view plaincopyprint? //function: 对链表进行冒泡排序 void ListSort(key_list keylist) { doc_list p keylist-next; doc_list final NULL; while (true) { bool isfinish true; while (p-next ! final) { if (strcmp(p-time, p-next-time) 0) { SwapDocNode(p); isfinish false; } p p-next; } final p; p keylist-next; if (isfinish || p-next final) { break; } } } int main() { key_list keylist; char *pbuf, *move; int filenum GetFileName(filename); FILE *frp; pbuf (char *)malloc(BUF_MAX_LEN); memset(pbuf, 0, BUF_MAX_LEN); FILE *fwp OpenWriteFile(index.txt); if (fwp NULL) { return 0; } PrepareCryptTable(); int wordnum 0; for (int i 0; i filenum; i) { frp OpenReadFile(i, filename); if (frp NULL) { break; } // 每次读取一行处理 while (fgets(pbuf, BUF_MAX_LEN, frp)) { int count 0; move pbuf; if (GetRealString(pbuf) 1) continue; while (move ! NULL) { // 找到第一个非#的字符 while (*move #) move; if (!strcmp(move, )) break; GetItems(move, count, wordnum); } for (int i 7; i count; i) { // 将关键字对应的文档内容加入文档结点链表中 // 如果关键字第一次出现则将其加入hash表 if (keylist SearchByString(items[i])) { doc_list infolist SaveItems(); infolist-next keylist-next; keylist-count; keylist-next infolist; } else { int pos InsertString(items[i]); keylist key_array[pos]; doc_list infolist SaveItems(); infolist-next NULL; keylist-next infolist; if (pos ! -1) { strcpy_s(words[wordnum], items[i]); } } } } } // 通过快排对关键字进行排序 qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll); // 遍历关键字数组将关键字及其对应的文档内容写入文件中 int rownum 1; for (int i 0; i WORD_MAX_NUM; i) { keylist SearchByString(words[i]); if (keylist ! NULL) { doc_list infolist keylist-next; char date[9]; // 截取年月日 for (int j 0; j keylist-count; j) { strncpy_s(date, infolist-time, 8); date[8] \0; strncpy_s(infolist-time, date, 9); infolist infolist-next; } // 对链表根据时间进行排序 ListSort(keylist); infolist keylist-next; int *count new int[WORD_MAX_NUM]; memset(count, 0, WORD_MAX_NUM); strcpy_s(date, infolist-time); int num 0; // 得到单个日期的文档数目 for (int j 0; j keylist-count; j) { if (strcmp(date, infolist-time) 0) { count[num]; } else { count[num]; } strcpy_s(date, infolist-time); infolist infolist-next; } fprintf(fwp, %s %d %d\n, words[i], num 1, rownum); WriteFile(keylist, num, fwp, count); rownum; } } free(pbuf); // fclose(frp); fclose(fwp); system(pause); return 0; } //function: 对链表进行冒泡排序
void ListSort(key_list keylist)
{doc_list p keylist-next;doc_list final NULL;while (true){bool isfinish true;while (p-next ! final) {if (strcmp(p-time, p-next-time) 0){SwapDocNode(p);isfinish false;}p p-next;}final p;p keylist-next;if (isfinish || p-next final) {break;}}
}int main()
{key_list keylist;char *pbuf, *move;int filenum GetFileName(filename);FILE *frp;pbuf (char *)malloc(BUF_MAX_LEN);memset(pbuf, 0, BUF_MAX_LEN);FILE *fwp OpenWriteFile(index.txt);if (fwp NULL) {return 0;}PrepareCryptTable();int wordnum 0;for (int i 0; i filenum; i){frp OpenReadFile(i, filename);if (frp NULL) {break;}// 每次读取一行处理while (fgets(pbuf, BUF_MAX_LEN, frp)){int count 0;move pbuf;if (GetRealString(pbuf) 1)continue;while (move ! NULL){// 找到第一个非#的字符while (*move #)move;if (!strcmp(move, ))break;GetItems(move, count, wordnum);}for (int i 7; i count; i) {// 将关键字对应的文档内容加入文档结点链表中// 如果关键字第一次出现则将其加入hash表if (keylist SearchByString(items[i])) {doc_list infolist SaveItems();infolist-next keylist-next;keylist-count;keylist-next infolist;} else {int pos InsertString(items[i]);keylist key_array[pos];doc_list infolist SaveItems();infolist-next NULL;keylist-next infolist;if (pos ! -1) {strcpy_s(words[wordnum], items[i]);}}}}}// 通过快排对关键字进行排序qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll);// 遍历关键字数组将关键字及其对应的文档内容写入文件中int rownum 1;for (int i 0; i WORD_MAX_NUM; i) {keylist SearchByString(words[i]);if (keylist ! NULL) {doc_list infolist keylist-next;char date[9];// 截取年月日for (int j 0; j keylist-count; j){strncpy_s(date, infolist-time, 8);date[8] \0;strncpy_s(infolist-time, date, 9);infolist infolist-next;}// 对链表根据时间进行排序ListSort(keylist);infolist keylist-next;int *count new int[WORD_MAX_NUM];memset(count, 0, WORD_MAX_NUM);strcpy_s(date, infolist-time);int num 0;// 得到单个日期的文档数目for (int j 0; j keylist-count; j){if (strcmp(date, infolist-time) 0) {count[num];} else {count[num];}strcpy_s(date, infolist-time);infolist infolist-next;}fprintf(fwp, %s %d %d\n, words[i], num 1, rownum);WriteFile(keylist, num, fwp, count);rownum;}}free(pbuf);
// fclose(frp);fclose(fwp);system(pause);return 0;
} 修改后编译运行生成的index.txt文件如下 4.2、为关键词添上编码 如上图所示已经满足需求了。但可以再在每个关键词的背后添加一个计数表示索引到了第多少个关键词 第五节、算法的二次改进 5.1、省去二次Hash 针对本文评论下读者的留言做了下思考自觉可以省去二次hash [cpp] view plaincopyprint? for (int i 7; i count; i) { // 将关键字对应的文档内容加入文档结点链表中 //也就是说当查询到hash表中没有某个关键词之,后便会插入 //而查询的时候search会调用hashstring得到了nHashC nHashD //插入的时候又调用了一次hashstring得到了nHashAnHashB //而如果查询的时候是针对同一个关键词查询的所以也就是说nHashCnHashD与nHashAnHashB是相同的无需二次hash //所以若要改进改的也就是下面这个if~else语句里头。July2011.12.30。 if (keylist SearchByString(items[i])) //到hash表内查询 { doc_list infolist SaveItems(); infolist-next keylist-next; keylist-count; keylist-next infolist; } else { // 如果关键字第一次出现则将其加入hash表 int pos InsertString(items[i]); //插入hash表 keylist key_array[pos]; doc_list infolist SaveItems(); infolist-next NULL; keylist-next infolist; if (pos ! -1) { strcpy_s(words[wordnum], items[i]); } } } } } // 通过快排对关键字进行排序 qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll); for (int i 7; i count; i) { // 将关键字对应的文档内容加入文档结点链表中 //也就是说当查询到hash表中没有某个关键词之,后便会插入 //而查询的时候search会调用hashstring得到了nHashC nHashD //插入的时候又调用了一次hashstring得到了nHashAnHashB //而如果查询的时候是针对同一个关键词查询的所以也就是说nHashCnHashD与nHashAnHashB是相同的无需二次hash //所以若要改进改的也就是下面这个if~else语句里头。July2011.12.30。 if (keylist SearchByString(items[i])) //到hash表内查询 { doc_list infolist SaveItems(); infolist-next keylist-next; keylist-count; keylist-next infolist; } else { // 如果关键字第一次出现则将其加入hash表 int pos InsertString(items[i]); //插入hash表 keylist key_array[pos]; doc_list infolist SaveItems(); infolist-next NULL; keylist-next infolist; if (pos ! -1) { strcpy_s(words[wordnum], items[i]); } } } } } // 通过快排对关键字进行排序 qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll); 5.2、除去排序针对不同日期的记录直接插入 [cpp] view plaincopyprint? //对链表进行冒泡排序。这里可以改成快速排序等到统计完所有有关这个关键词的文章之后才能对他集体快排。 //但其实完全可以用插入排序不同日期的根据时间的先后找到插入位置进行插入 //假如说已有三条不同日期的记录 A B C //来了D后发现D在C之前B之后那么就必须为它找到B C之间的插入位置 //A B D C。July、2011.12.31。 void ListSort(key_list keylist) { doc_list p keylist-next; doc_list final NULL; while (true) { bool isfinish true; while (p-next ! final) { if (strcmp(p-time, p-next-time) 0) //不同日期的按最早到最晚排序 { SwapDocNode(p); isfinish false; } p p-next; } final p; p keylist-next; if (isfinish || p-next final) { break; } } } //对链表进行冒泡排序。这里可以改成快速排序等到统计完所有有关这个关键词的文章之后才能对他集体快排。
//但其实完全可以用插入排序不同日期的根据时间的先后找到插入位置进行插入
//假如说已有三条不同日期的记录 A B C
//来了D后发现D在C之前B之后那么就必须为它找到B C之间的插入位置
//A B D C。July、2011.12.31。
void ListSort(key_list keylist)
{doc_list p keylist-next;doc_list final NULL;while (true){bool isfinish true;while (p-next ! final) {if (strcmp(p-time, p-next-time) 0) //不同日期的按最早到最晚排序{SwapDocNode(p);isfinish false;}p p-next;}final p;p keylist-next;if (isfinish || p-next final) {break;}}
} 综上5.1、5.2两节免去冒泡排序和省去二次hash和免去冒泡排序修改后如下 [cpp] view plaincopyprint? for (int i 7; i count; i) { // 将关键字对应的文档内容加入文档结点链表中 // 如果关键字第一次出现则将其加入hash表 InitHashValue(items[i], hashvalue); if (keynode SearchByString(items[i], hashvalue)) { doc_list infonode SaveItems(); doc_list p keynode-next; // 根据时间由早到晚排序 if (strcmp(infonode-time, p-time) 0) { //考虑infonode插入keynode后的情况 infonode-next p; keynode-next infonode; } else { //考虑其他情况 doc_list pre p; p p-next; while (p) { if (strcmp(infonode-time, p-time) 0) { p p-next; pre pre-next; } else { break; } } infonode-next p; pre-next infonode; } keynode-count; } else { int pos InsertString(items[i], hashvalue); keynode key_array[pos]; doc_list infolist SaveItems(); infolist-next NULL; keynode-next infolist; if (pos ! -1) { strcpy_s(words[wordnum], items[i]); } } } } } // 通过快排对关键字进行排序 qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll); for (int i 7; i count; i) { // 将关键字对应的文档内容加入文档结点链表中 // 如果关键字第一次出现则将其加入hash表 InitHashValue(items[i], hashvalue); if (keynode SearchByString(items[i], hashvalue)) { doc_list infonode SaveItems(); doc_list p keynode-next; // 根据时间由早到晚排序 if (strcmp(infonode-time, p-time) 0) { //考虑infonode插入keynode后的情况 infonode-next p; keynode-next infonode; } else { //考虑其他情况 doc_list pre p; p p-next; while (p) { if (strcmp(infonode-time, p-time) 0) { p p-next; pre pre-next; } else { break; } } infonode-next p; pre-next infonode; } keynode-count; } else { int pos InsertString(items[i], hashvalue); keynode key_array[pos]; doc_list infolist SaveItems(); infolist-next NULL; keynode-next infolist; if (pos ! -1) { strcpy_s(words[wordnum], items[i]); } } } } } // 通过快排对关键字进行排序 qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll); 修改后编译运行的效果图如下用了另外一份更大的数据文件进行测试 转载于:https://www.cnblogs.com/javaspring/archive/2012/08/14/2656226.html
