基于给定的文档生成倒排索引的编码与实践

作者：July、yansha。

出处：结构之法算法之道

引言

本周实现倒排索引。实现过程中，寻找资料，结果发现找份资料诸多不易：1、网上搜倒排索引实现，结果千篇一律，例子都是那几个同样的单词；2、到谷歌学术上想找点稍微有价值水平的资料，结果下篇论文还收费或者要求注册之类；3、大部分技术书籍只有理论，没有实践。于是，朋友戏言：网上一般有价值的东西不多。希望，本blog的出现能改变此现状。

在第二十四章、倒排索引关键词不重复Hash编码中，我们针对一个给定的倒排索引文件，提取出其中的关键词，然后针对这些关键词进行Hash不重复编码。本章，咱们再倒退一步，即给定一个正排文档（暂略过文本解析，分词等步骤，日后会慢慢考虑这些且一并予以实现），要求生成对应的倒排索引文件。同时，本章还是基于Hash索引之上（运用暴雪的Hash函数可以比较完美的解决大数据量下的冲突问题），日后自会实现B+树索引。

与此同时，本编程艺术系列逐步从为面试服务而转到实战性的编程当中了，教初学者如何编程，如何运用高效的算法解决实际应用中的编程问题，将逐步成为本编程艺术系列的主旨之一。

OK，接下来，咱们针对给定的正排文档一步一步来生成倒排索引文件，有任何问题，欢迎随时不吝赐教或批评指正。谢谢。

第一节、索引的构建方法

  • 根据信息检索导论（Christtopher D.Manning等著，王斌译）一书给的提示，我们可以选择两种构建索引的算法：BSBI算法，与SPIMI算法。

BSBI算法，基于磁盘的外部排序算法，此算法首先将词项映射成其ID的数据结构，如Hash映射。而后将文档解析成词项ID-文档ID对，并在内存中一直处理，直到累积至放满一个固定大小的块空间为止，我们选择合适的块大小，使之能方便加载到内存中并允许在内存中快速排序，快速排序后的块转换成倒排索引格式后写入磁盘。

建立倒排索引的步骤如下：

  • 将文档分割成几个大小相等的部分；
  • 对词项ID-文档ID进行排序；
  • 将具有同一词项ID的所有文档ID放到倒排记录表中，其中每条倒排记录仅仅是一个文档ID；
  • 将基于块的倒排索引写到磁盘上。

此算法假如说最后可能会产生10个块。其伪码如下：

  1. BSBI NDEXConSTRUCTION()
  2. n <- 0
  3. while(all documents have not been processed)
  4.     do n<-n+1
  5.         block <- PARSENEXTBLOCK()    //文档分析
  6.         BSBI-INVERT(block)
  7.         WRITEBLOCKTODISK(block,fn)
  8.         MERGEBLOCKS(f1,...,fn;fmerged)

（基于块的排序索引算法，该算法将每个块的倒排索引文件存入文件f1,…,fn中，最后合并成fmerged 如果该算法应用最后一步产生了10个块，那么接下来便会将10个块索引同时合并成一个索引文件。）

合并时，同时打开所有块对应的文件，内存中维护了为10个块准备的读缓冲区和一个为最终合并索引准备的写缓冲区。每次迭代中，利用优先级队列（如堆结构或类似的数据结构）选择最小的未处理的词项ID进行处理。如下图所示（图片引自深入搜索引擎—海里信息的压缩、索引和查询，梁斌译），分块索引，分块排序，最终全部合并（说实话，跟MapReduce还是有些类似的）：

基于给定的文档生成倒排索引的编码与实践 - 图1

读入该词项的倒排记录表并合并，合并结果写回磁盘中。需要时，再次从文件中读入数据到每个读缓冲区。

BSBI算法主要的时间消耗在排序上，选择什么排序方法呢，简单的快速排序足矣，其时间复杂度为O（N*logN），其中N是所需要排序的项（词项ID-文档ID对）的数目的上界。

SPIMI算法，内存式单遍扫描索引算法

与上述BSBI算法不同的是：SPIMI使用词项而不是其ID，它将每个块的词典写入磁盘，对于写一块则重新采用新的词典，只要硬盘空间足够大，它能索引任何大小的文档集。

倒排索引 = 词典（关键词或词项+词项频率）+倒排记录表。建倒排索引的步骤如下：

  • 从头开始扫描每一个词项-文档ID（信息）对，遇一词，构建索引；
  • 继续扫描，若遇一新词，则再建一新索引块（加入词典，通过Hash表实现，同时，建一新的倒排记录表）；若遇一旧词，则找到其倒排记录表的位置，添加其后
  • 在内存内基于分块完成排序，后合并分块；
  • 写入磁盘。

其伪码如下：

  1. SPIMI-Invert(Token_stream)
  2. output.file=NEWFILE()
  3. dictionary = NEWHASH()
  4. while (free memory available)
  5.     do token <-next(token_stream) //逐一处理每个词项-文档ID对
  6.         if term(token) !(- dictionary
  7.            /*如果词项是第一次出现，那么加入hash词典，同时，建立一个新的倒排索引表*/
  8.            then postings_list = AddToDictionary(dictionary,term(token))
  9.         /*如果不是第一次出现，那么直接返回其倒排记录表，在下面添加其后*/
  10.         else postings_list = GetPostingList(dictionary,term(token))
  11.     if full(postings_list)
  12.         then postings_list =DoublePostingList(dictionary,term(token))
  13.     /*SPIMI与BSBI的区别就在于此，前者直接在倒排记录表中增加此项新纪录*/
  14.     AddToPosTingsList (postings_list,docID(token))
  15. sorted_terms <- SortTerms(dictionary)
  16. WriteBlockToDisk(sorted_terms,dictionary,output_file)
  17. 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、文档权值、关键词、作者等等。 基于给定的文档生成倒排索引的编码与实践 - 图2

要求基于给定的上述正排文档。生成如第二十四章所示的倒排索引文件（注，关键词所在的文章如果是同一个日期的话，是挨在同一行的，用“#”符号隔开）： 基于给定的文档生成倒排索引的编码与实践 - 图3

我们知道：为网页建立全文索引是网页预处理的核心部分，包括分析网页和建立倒排文件。二者是顺序进行，先分析网页，后建立倒排文件（也称为反向索引），如图所示：

基于给定的文档生成倒排索引的编码与实践 - 图4

正如上图粗略所示，我们知道倒排索引创建的过程如下：

  • 写爬虫抓取相关的网页，而后提取相关网页或文章中所有的关键词；
  • 分词，找出所有单词；
  • 过滤不相干的信息（如广告等信息）；
  • 构建倒排索引，关键词=>（文章ID 出现次数 出现的位置）生成词典文件 频率文件 位置文件；
  • 压缩。

因为已经给定了正排文档，接下来，咱们跳过一系列文本解析，分词等中间步骤，直接根据正排文档生成倒排索引文档（幸亏有yansha相助，不然，寸步难行，其微博地址为：http://weibo.com/yanshazi，欢迎关注他）。

OK，闲不多说，咱们来一步一步实现吧。

建相关的数据结构

根据给定的正排文档，我们可以建立如下的两个结构体表示这些信息：文档ID、订阅源（子频道）、 频道分类、 网站类ID（大频道）、时间、 md5、文档权值、关键词、作者等等。如下所示：

  1. typedef struct key_node
  2. {
  3.     char *pkey;     // 关键词实体
  4.     int count;      // 关键词出现次数
  5.     int pos;        // 关键词在hash表中位置
  6.     struct doc_node *next;  // 指向文档结点
  7. }KEYNODE, *key_list;
  9. key_list key_array[TABLE_SIZE];
  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之上的改造算法

  1. //函数prepareCryptTable以下的函数生成一个长度为0x100的cryptTable[0x100]
  2. void PrepareCryptTable()
  3. {
  4.     unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
  6.     for( index1 = 0; index1 <0x100; index1++ )
  7.     {
  8.         for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100)
  9.         {
  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. }
  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;
  28.     while( *key != 0 )
  29.     {
  30.         ch = *key++;
  31.         seed1 = cryptTable[(dwHashType<<8) + ch] ^ (seed1 + seed2);
  32.         seed2 = ch + seed1 + seed2 + (seed2<<5) + 3;
  33.     }
  34.     return seed1;
  35. }
  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;
  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.         }
  59.         if (nHashPos == nHashStart)
  60.         {
  61.             break;
  62.         }
  63.     }
  65.     if( key_array[nHashPos] && strlen(key_array[nHashPos]->pkey))
  66.     {
  67.         return key_array[nHashPos];
  68.     }
  70.     return NULL;
  71. }
  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.     }
  85.     return NULL;
  86. }
  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;
  99.     while (HashTable[nHashPos].bExists)
  100.     {
  101.         nHashPos = (nHashPos + 1) % TABLE_SIZE;
  103.         if (nHashPos == nHashStart)
  104.             break;
  105.     }
  107.     len = strlen(str);
  108.     if (!HashTable[nHashPos].bExists && (len < WORD_MAX_LEN))
  109.     {
  110.         HashATable[nHashPos] = nHashA;
  111.         HashBTable[nHashPos] = nHashB;
  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.         }
  120.         key_array[nHashPos]->pkey = (char *)malloc(len+1);
  121.         if(key_array[nHashPos]->pkey == NULL)
  122.         {
  123.             printf("10000 EMS ERROR !!!!\n");
  124.             return 0;
  125.         }
  127.         memset(key_array[nHashPos]->pkey, 0, len+1);
  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.     }
  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中），还得编写一系列的函数，如下所示（所有代码还只是初步实现了功能，稍后在第四部分中将予以改进与优化）：

  1. //处理空白字符和空白行
  2. int GetRealString(char *pbuf)
  3. {
  4.     int len = strlen(pbuf) - 1;
  5.     while (len > 0 && (pbuf[len] == (char)0x0d || pbuf[len] == (char)0x0a || pbuf[len] == ' ' || pbuf[len] == '\t'))
  6.     {
  7.         len--;
  8.     }
  10.     if (len < 0)
  11.     {
  12.         *pbuf = '\0';
  13.         return len;
  14.     }
  15.     pbuf[len+1] = '\0';
  16.     return len + 1;
  17. }
  19. //重新strcoll字符串比较函数
  20. int strcoll(const void *s1, const void *s2)
  21. {
  22.     char *c_s1 = (char *)s1;
  23.     char *c_s2 = (char *)s2;
  24.     while (*c_s1 == *c_s2++)
  25.     {
  26.         if (*c_s1++ == '\0')
  27.         {
  28.             return 0;
  29.         }
  30.     }
  32.     return *c_s1 - *--c_s2;
  33. }
  35. //从行缓冲中得到各项信息，将其写入items数组
  36. void GetItems(char *&move, int &count, int &wordnum)
  37. {
  38.     char *front = move;
  39.     bool flag = false;
  40.     int len;
  41.     move = strstr(move, "#####");
  42.     if (*(move + 5) == '#')
  43.     {
  44.         flag = true;
  45.     }
  47.     if (move)
  48.     {
  49.         len = move - front;
  50.         strncpy(items[count], front, len);
  51.     }
  52.     items[count][len] = '\0';
  53.     count++;
  55.     if (flag)
  56.     {
  57.         move = move + 10;
  58.     } else
  59.     {
  60.         move = move + 5;
  61.     }
  62. }
  64. //保存关键字相应的文档内容
  65. doc_list SaveItems()
  66. {
  67.     doc_list infolist = (doc_list) malloc(sizeof(DOCNODE));
  68.     strcpy_s(infolist->id, items[0]);
  69.     infolist->classOne = atoi(items[1]);
  70.     strcpy_s(infolist->classTwo, items[2]);
  71.     infolist->classThree = atoi(items[3]);
  72.     strcpy_s(infolist->time, items[4]);
  73.     strcpy_s(infolist->md5, items[5]);
  74.     infolist->weight = atoi(items[6]);
  75.     return infolist;
  76. }
  78. //得到目录下所有文件名
  79. int GetFileName(char filename[][FILENAME_MAX_LEN])
  80. {
  81.     _finddata_t file;
  82.     long handle;
  83.     int filenum = 0;
  84.     //C:\Users\zhangxu\Desktop\CreateInvertedIndex\data
  85.     if ((handle = _findfirst("C:\\Users\\zhangxu\\Desktop\\CreateInvertedIndex\\data\\*.txt", &file)) == -1)
  86.     {
  87.         printf("Not Found\n");
  88.     }
  89.     else
  90.     {
  91.         do
  92.         {
  93.             strcpy_s(filename[filenum++], file.name);
  94.         } while (!_findnext(handle, &file));
  95.     }
  96.     _findclose(handle);
  97.     return filenum;
  98. }
  100. //以读方式打开文件，如果成功返回文件指针
  101. FILE* OpenReadFile(int index, char filename[][FILENAME_MAX_LEN])
  102. {
  103.     char *abspath;
  104.     char dirpath[] = {"data\\"};
  105.     abspath = (char *)malloc(ABSPATH_MAX_LEN);
  106.     strcpy_s(abspath, ABSPATH_MAX_LEN, dirpath);
  107.     strcat_s(abspath, FILENAME_MAX_LEN, filename[index]);
  109.     FILE *fp = fopen (abspath, "r");
  110.     if (fp == NULL)
  111.     {
  112.         printf("open read file error!\n");
  113.         return NULL;
  114.     }
  115.     else
  116.     {
  117.         return fp;
  118.     }
  119. }
  121. //以写方式打开文件，如果成功返回文件指针
  122. FILE* OpenWriteFile(const char *in_file_path)
  123. {
  124.     if (in_file_path == NULL)
  125.     {
  126.         printf("output file path error!\n");
  127.         return NULL;
  128.     }
  130.     FILE *fp = fopen(in_file_path, "w+");
  131.     if (fp == NULL)
  132.     {
  133.         printf("open write file error!\n");
  134.     }
  135.     return fp;
  136. }

最后，主函数编写如下：

  1. int main()
  2. {
  3.     key_list keylist;
  4.     char *pbuf, *move;
  5.     int filenum = GetFileName(filename);
  6.     FILE *fr;
  7.     pbuf = (char *)malloc(BUF_MAX_LEN);
  8.     memset(pbuf, 0, BUF_MAX_LEN);
  10.     FILE *fw = OpenWriteFile("index.txt");
  11.     if (fw == NULL)
  12.     {
  13.         return 0;
  14.     }
  16.     PrepareCryptTable();    //初始化Hash表
  18.     int wordnum = 0;
  19.     for (int i = 0; i < filenum; i++)
  20.     {
  21.         fr = OpenReadFile(i, filename);
  22.         if (fr == NULL)
  23.         {
  24.             break;
  25.         }
  27.         // 每次读取一行处理
  28.         while (fgets(pbuf, BUF_MAX_LEN, fr))
  29.         {
  30.             int count = 0;
  31.             move = pbuf;
  32.             if (GetRealString(pbuf) <= 1)
  33.                 continue;
  35.             while (move != NULL)
  36.             {
  37.                 // 找到第一个非'#'的字符
  38.                 while (*move == '#')
  39.                     move++;
  41.                 if (!strcmp(move, ""))
  42.                     break;
  44.                 GetItems(move, count, wordnum);
  45.             }
  47.             for (int i = 7; i < count; i++)
  48.             {
  49.                 // 将关键字对应的文档内容加入文档结点链表中
  50.                 if (keylist = SearchByString(items[i]))     //到hash表内查询
  51.                 {
  52.                     doc_list infolist = SaveItems();
  53.                     infolist->next = keylist->next;
  54.                     keylist->count++;
  55.                     keylist->next = infolist;
  56.                 }
  57.                 else
  58.                 {
  59.                     // 如果关键字第一次出现，则将其加入hash表
  60.                     int pos = InsertString(items[i]);       //插入hash表
  61.                     keylist = key_array[pos];
  62.                     doc_list infolist = SaveItems();
  63.                     infolist->next = NULL;
  64.                     keylist->next = infolist;
  65.                     if (pos != -1)
  66.                     {
  67.                         strcpy_s(words[wordnum++], items[i]);
  68.                     }
  69.                 }
  70.             }
  71.         }
  72.     }
  74.     // 通过快排对关键字进行排序
  75.     qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll);
  77.     // 遍历关键字数组，将关键字及其对应的文档内容写入文件中
  78.     for (int i = 0; i < WORD_MAX_NUM; i++)
  79.     {
  80.         keylist = SearchByString(words[i]);
  81.         if (keylist != NULL)
  82.         {
  83.             fprintf(fw, "%s %d\n", words[i], keylist->count);
  84.             doc_list infolist = keylist->next;
  85.             for (int j = 0; j < keylist->count; j++)
  86.             {
  87.                 //文档ID，订阅源（子频道） 频道分类 网站类ID（大频道） 时间  md5，文档权值
  88.                 fprintf(fw, "%s %d %s %d %s %s %d\n", infolist->id, infolist->classOne,
  89.                     infolist->classTwo, infolist->classThree, infolist->time, infolist->md5, infolist->weight);
  90.                 infolist = infolist->next;
  91.             }
  92.         }
  93.     }
  95.     free(pbuf);
  96.     fclose(fr);
  97.     fclose(fw);
  98.     system("pause");
  99.     return 0;
  100. }

程序编译运行后，生成的倒排索引文件为index.txt，其与原来给定的正排文档对照如下： 基于给定的文档生成倒排索引的编码与实践 - 图5

有没有发现关键词奥恰洛夫出现在的三篇文章是同一个日期1210的，貌似与本文开头指定的倒排索引格式要求不符？因为第二部分开头中，已明确说明：“注，关键词所在的文章如果是同一个日期的话，是挨在同一行的，用“#”符号隔开”。OK，有疑问是好事，代表你思考了，请直接转至下文第4部分。

第四节、程序需求功能的改进

对相同日期与不同日期的处理

细心的读者可能还是会注意到：在第二部分开头中，要求基于给定的上述正排文档。生成如第二十四章所示的倒排索引文件是下面这样子的，即是： 基于给定的文档生成倒排索引的编码与实践 - 图6

也就是说，上面建索引的过程本该是如下的： 基于给定的文档生成倒排索引的编码与实践 - 图7

与第一部分所述的SMIPI算法有什么区别？对的，就在于对在同一个日期的出现的关键词的处理。如果是遇一旧词，则找到其倒排记录表的位置：相同日期，添加到之前同一日期的记录之后（第一个记录的后面记下同一日期的记录数目）；不同日期，另起一行新增记录。

  • 相同（单个）日期，根据文档权值排序
  • 不同日期，根据时间排序

代码主要修改如下：

  1. //function: 对链表进行冒泡排序
  2. void ListSort(key_list keylist)
  3. {
  4.     doc_list p = keylist->next;
  5.     doc_list final = NULL;
  6.     while (true)
  7.     {
  8.         bool isfinish = true;
  9.         while (p->next != final) {
  10.             if (strcmp(p->time, p->next->time) < 0)
  11.             {
  12.                 SwapDocNode(p);
  13.                 isfinish = false;
  14.             }
  15.             p = p->next;
  16.         }
  17.         final = p;
  18.         p = keylist->next;
  19.         if (isfinish || p->next == final) {
  20.             break;
  21.         }
  22.     }
  23. }
  25. int main()
  26. {
  27.     key_list keylist;
  28.     char *pbuf, *move;
  29.     int filenum = GetFileName(filename);
  30.     FILE *frp;
  31.     pbuf = (char *)malloc(BUF_MAX_LEN);
  32.     memset(pbuf, 0, BUF_MAX_LEN);
  34.     FILE *fwp = OpenWriteFile("index.txt");
  35.     if (fwp == NULL) {
  36.         return 0;
  37.     }
  39.     PrepareCryptTable();
  41.     int wordnum = 0;
  42.     for (int i = 0; i < filenum; i++)
  43.     {
  44.         frp = OpenReadFile(i, filename);
  45.         if (frp == NULL) {
  46.             break;
  47.         }
  49.         // 每次读取一行处理
  50.         while (fgets(pbuf, BUF_MAX_LEN, frp))
  51.         {
  52.             int count = 0;
  53.             move = pbuf;
  54.             if (GetRealString(pbuf) <= 1)
  55.                 continue;
  57.             while (move != NULL)
  58.             {
  59.                 // 找到第一个非'#'的字符
  60.                 while (*move == '#')
  61.                     move++;
  63.                 if (!strcmp(move, ""))
  64.                     break;
  66.                 GetItems(move, count, wordnum);
  67.             }
  69.             for (int i = 7; i < count; i++) {
  70.                 // 将关键字对应的文档内容加入文档结点链表中
  71.                 // 如果关键字第一次出现，则将其加入hash表
  72.                 if (keylist = SearchByString(items[i])) {
  73.                     doc_list infolist = SaveItems();
  74.                     infolist->next = keylist->next;
  75.                     keylist->count++;
  76.                     keylist->next = infolist;
  77.                 } else {
  78.                     int pos = InsertString(items[i]);
  79.                     keylist = key_array[pos];
  80.                     doc_list infolist = SaveItems();
  81.                     infolist->next = NULL;
  82.                     keylist->next = infolist;
  83.                     if (pos != -1) {
  84.                         strcpy_s(words[wordnum++], items[i]);
  85.                     }
  86.                 }
  87.             }
  88.         }
  89.     }
  91.     // 通过快排对关键字进行排序
  92.     qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll);
  94.     // 遍历关键字数组，将关键字及其对应的文档内容写入文件中
  95.     int rownum = 1;
  96.     for (int i = 0; i < WORD_MAX_NUM; i++) {
  97.         keylist = SearchByString(words[i]);
  98.         if (keylist != NULL) {
  99.             doc_list infolist = keylist->next;
  101.             char date[9];
  103.             // 截取年月日
  104.             for (int j = 0; j < keylist->count; j++)
  105.             {
  106.                 strncpy_s(date, infolist->time, 8);
  107.                 date[8] = '\0';
  108.                 strncpy_s(infolist->time, date, 9);
  109.                 infolist = infolist->next;
  110.             }
  112.             // 对链表根据时间进行排序
  113.             ListSort(keylist);
  115.             infolist = keylist->next;
  116.             int *count = new int[WORD_MAX_NUM];
  117.             memset(count, 0, WORD_MAX_NUM);
  118.             strcpy_s(date, infolist->time);
  119.             int num = 0;
  120.             // 得到单个日期的文档数目
  121.             for (int j = 0; j < keylist->count; j++)
  122.             {
  123.                 if (strcmp(date, infolist->time) == 0) {
  124.                     count[num]++;
  125.                 } else {
  126.                     count[++num]++;
  127.                 }
  128.                 strcpy_s(date, infolist->time);
  129.                 infolist = infolist->next;
  130.             }
  131.             fprintf(fwp, "%s %d %d\n", words[i], num + 1, rownum);
  132.             WriteFile(keylist, num, fwp, count);
  133.             rownum++;
  134.         }
  135.     }
  137.     free(pbuf);
  138. //  fclose(frp);
  139.     fclose(fwp);
  140.     system("pause");
  141.     return 0;
  142. }

修改后编译运行，生成的index.txt文件如下： 基于给定的文档生成倒排索引的编码与实践 - 图8

为关键词添上编码

如上图所示，已经满足需求了。但可以再在每个关键词的背后添加一个计数表示索引到了第多少个关键词： 基于给定的文档生成倒排索引的编码与实践 - 图9

第五节、算法的二次改进

省去二次Hash

针对本文评论下读者的留言，做了下思考，自觉可以省去二次hash：

  1.         for (int i = 7; i < count; i++)
  2.         {
  3.             // 将关键字对应的文档内容加入文档结点链表中
  4.             //也就是说当查询到hash表中没有某个关键词之,后便会插入
  5.             //而查询的时候，search会调用hashstring，得到了nHashC ，nHashD
  6.             //插入的时候又调用了一次hashstring，得到了nHashA，nHashB
  7.             //而如果查询的时候，是针对同一个关键词查询的，所以也就是说nHashC&nHashD，与nHashA&nHashB是相同的，无需二次hash
  8.             //所以，若要改进，改的也就是下面这个if~else语句里头。July，2011.12.30。
  9.             if (keylist = SearchByString(items[i]))     //到hash表内查询
  10.             {
  11.                 doc_list infolist = SaveItems();
  12.                 infolist->next = keylist->next;
  13.                 keylist->count++;
  14.                 keylist->next = infolist;
  15.             }
  16.             else
  17.             {
  18.                 // 如果关键字第一次出现，则将其加入hash表
  19.                 int pos = InsertString(items[i]);       //插入hash表
  20.                 keylist = key_array[pos];
  21.                 doc_list infolist = SaveItems();
  22.                 infolist->next = NULL;
  23.                 keylist->next = infolist;
  24.                 if (pos != -1)
  25.                 {
  26.                     strcpy_s(words[wordnum++], items[i]);
  27.                 }
  28.             }
  29.         }
  30.     }
  31. }
  32. // 通过快排对关键字进行排序
  33. qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll);

除去排序，针对不同日期的记录直接插入

  1. //对链表进行冒泡排序。这里可以改成快速排序：等到统计完所有有关这个关键词的文章之后，才能对他集体快排。
  2. //但其实完全可以用插入排序，不同日期的，根据时间的先后找到插入位置进行插入：
  3. //假如说已有三条不同日期的记录 A B C
  4. //来了D后，发现D在C之前，B之后，那么就必须为它找到B C之间的插入位置，
  5. //A B D C。July、2011.12.31。
  6. void ListSort(key_list keylist)
  7. {
  8.     doc_list p = keylist->next;
  9.     doc_list final = NULL;
  10.     while (true)
  11.     {
  12.         bool isfinish = true;
  13.         while (p->next != final) {
  14.             if (strcmp(p->time, p->next->time) < 0) //不同日期的按最早到最晚排序
  15.             {
  16.                 SwapDocNode(p);
  17.                 isfinish = false;
  18.             }
  19.             p = p->next;
  20.         }
  21.         final = p;
  22.         p = keylist->next;
  23.         if (isfinish || p->next == final) {
  24.             break;
  25.         }
  26.     }
  27. }

综上两节免去冒泡排序和，省去二次hash和免去冒泡排序，修改后如下：

  1.         for (int i = 7; i < count; i++) {
  2.             // 将关键字对应的文档内容加入文档结点链表中
  3.             // 如果关键字第一次出现，则将其加入hash表
  4.             InitHashValue(items[i], hashvalue);
  5.             if (keynode = SearchByString(items[i], hashvalue)) {
  6.                 doc_list infonode = SaveItems();
  7.                 doc_list p = keynode->next;
  8.                 // 根据时间由早到晚排序
  9.                 if (strcmp(infonode->time, p->time) < 0) {
  10.                     //考虑infonode插入keynode后的情况
  11.                     infonode->next = p;
  12.                     keynode->next = infonode;
  13.                 } else {
  14.                     //考虑其他情况
  15.                     doc_list pre = p;
  16.                     p = p->next;
  17.                     while (p)
  18.                     {
  19.                         if (strcmp(infonode->time, p->time) > 0) {
  20.                             p = p->next;
  21.                             pre = pre->next;
  22.                         } else {
  23.                             break;
  24.                         }
  25.                     }
  26.                     infonode->next = p;
  27.                     pre->next = infonode;
  28.                 }
  29.                 keynode->count++;
  30.             } else {
  31.                 int pos = InsertString(items[i], hashvalue);
  32.                 keynode = key_array[pos];
  33.                 doc_list infolist = SaveItems();
  34.                 infolist->next = NULL;
  35.                 keynode->next = infolist;
  36.                 if (pos != -1) {
  37.                     strcpy_s(words[wordnum++], items[i]);
  38.                 }
  39.             }
  40.         }
  41.     }
  42. }
  44. // 通过快排对关键字进行排序
  45. qsort(words, WORD_MAX_NUM, WORD_MAX_LEN, strcoll);

修改后编译运行的效果图如下（用了另外一份更大的数据文件进行测试）： 基于给定的文档生成倒排索引的编码与实践 - 图10