學著站在巨人的肩膀上

由上一篇文章[原]自頂向下學搜索引擎——北大天網(wǎng)搜索引擎TSE分析及完全注釋[1]尋找搜索引擎入口 我們可以知道整個程序是從TSESearch.cpp 中的main函數(shù)開始的我們重點一下這段代碼

//TSESearch.cpp CQuery iQuery;
 iQuery.GetInputs();  //具體程序開始執(zhí)行
 // current query & result page number
 iQuery.SetQuery();
 iQuery.SetStart();

 // begin to search
 //開始具體搜索程序
 gettimeofday(&begin_tv,&tz); //開始計時獲取程序運行時間差

 iQuery.GetInvLists(mapBuckets);  //將所有字符集存入映射變量中 瓶頸所在
 iQuery.GetDocIdx(vecDocIdx);  //將倒排索引存入向量中  瓶頸所在
 
 CHzSeg iHzSeg;  //include ChSeg/HzSeg.h
 iQuery.m_sSegQuery = iHzSeg.SegmentSentenceMM(iDict, iQuery.m_sQuery); //將get到的查詢變量分詞分成 "我/  愛/  你們/ 的/  格式"
 
 vector vecTerm;
 iQuery.ParseQuery(vecTerm);  //將以"/"劃分開的關鍵字一一順序放入一個向量容器中
 
 set setRelevantRst;
 iQuery.GetRelevantRst(vecTerm, mapBuckets, setRelevantRst);
 
 gettimeofday(&end_tv,&tz);
 // search end
 //搜索完畢按照順序我們首先深入進iQuery對象的類CQuery  

//Query.cpp

1、GetInputs

這個方法的功能是將前臺get過來的變量轉(zhuǎn)換到HtmlInputs結(jié)構體數(shù)組中如下例子和代碼：

//假設前臺查詢的關鍵字是"1"著HtmlInputs中內(nèi)容輸出如下  //HtmlInputs[0].Name word  //HtmlInputs[0].Value 1  //HtmlInputs[1].Name www  //HtmlInputs[1].Value 搜索  //HtmlInputs[2].Name cdtype  //HtmlInputs[2].Value GB

 
/*
 * Get form information throught environment varible.
 * return 0 if succeed, otherwise exit.
 */
/**
 * 程序翻譯說明
 * 處理GET過來的表單
 *
 * @access  public
 * @return  string 0
 */
int CQuery::GetInputs()
{
    int i,j;
 char *mode = getenv("REQUEST_METHOD"); //返回環(huán)境變量的值 這里環(huán)境變量 REQUEST_METHOD 為 get 方法
    char *tempstr; //GET變量字符串或POST字符串內(nèi)容
 char *in_line; 
 int length;  //GET變量串長度或POST內(nèi)容長度

 cout << "Content-type: text/html\n\n";
 //cout << "Cache-Control: no-cache\n";
 //cout << "Expires: Tue, 08 Apr 1997 17:20:00 GMT\n";
 //cout << "Expires: 0\n";
 //cout << "Pragma: no-cache\n\n";

 cout << "\n";
 cout << "\n";
 //cout << "\n";
 //cout << "\n";
 //cout << "\n";
 cout << "\n";
 cout.flush(); //釋放輸出緩沖區(qū) 輸出頭部head和之前的html標簽內(nèi)容
 //cout <<"" << endl;

 if (mode==NULL) return 1;

 if (strcmp(mode, "POST") == 0)
 {
  length = atoi(getenv("CONTENT_LENGTH")); //如果是POST方法著獲得環(huán)境變量CONTENT_LENGTH的整型值
  if (length==0 || length>=256)
   return 1;
  in_line = (char*)malloc(length + 1);
  read(STDIN_FILENO, in_line, length);
  in_line[length]='\0';
 }
 else if (strcmp(mode, "GET") == 0)
 {
  char* inputstr = getenv("QUERY_STRING"); //如果是GET方法著獲得環(huán)境變量QUERY_STRING的字符串值
  length = strlen(inputstr);
  if (inputstr==0 || length>=256)
   return 1;

  //獲取get內(nèi)容長度并把get ？后面的參數(shù)賦值給變量in_line
  in_line = (char*)malloc(length + 1);
  strcpy(in_line, inputstr); //小心溢出攻擊
 }

 tempstr = (char*)malloc(length + 1); //獲取post內(nèi)容或get內(nèi)容長度
 if(tempstr == NULL)
 {
  printf("\n");
  printf("\n");
  printf("Major failure #1;please notify the webmaster\n");
  printf("\n");
  fflush(stdout); //輸出緩沖區(qū)
  exit(2); //錯誤返回
 }

 j=0;
 for (i=0; i char
   strcpy(HtmlInputs[HtmlInputCount].Name,tempstr);
   if (i == length - 1)
   {
    strcpy(HtmlInputs[HtmlInputCount].Value,"");
    HtmlInputCount++;
   }
   j=0;
  }
  else if ((in_line[i] == '&') || (i==length-1))
  {
   if (i==length-1)
   {
    if(in_line[i] == '+')tempstr[j]=' ';
    else tempstr[j] = in_line[i];
    j++;
   }
   tempstr[j]='\0';
   CStrFun::Translate(tempstr); //將URL編碼形式的參數(shù)轉(zhuǎn)換成字符型 %** -> char
   strcpy(HtmlInputs[HtmlInputCount].Value,tempstr);
   HtmlInputCount++;
   j=0;
  }
  else if (in_line[i] == '+')
  {
   tempstr[j]=' ';
   j++;
  }
  else
  {
   tempstr[j]=in_line[i]; //組合get中的變量如word www cdtype
   j++;
  }
  //cout<";
  //cout<";
  //cout.flush();
 }

 /*
 for (int kk = 0; kk < HtmlInputCount ; ++kk )
 {
  cout<<"Name="<";
  cout<<"Value="<";
 }
 //假設前臺查詢的關鍵字是"1"輸出如下
 //Name=word
 //Value=1
 //Name=www
 //Value= 搜索
 //Name=cdtype
 //Value=GB
 */

 if(in_line) free(in_line);
 if(tempstr) free(tempstr);

 return 0;
}
 
2、SetQuery
 
//Query.cpp
void CQuery::SetQuery()
{
 string q = HtmlInputs[0].Value;
 CStrFun::Str2Lower(q,q.size()); //大寫變小寫
 m_sQuery = q;  //準備查詢關鍵字
}
3、SetStart
void CQuery::SetQuery()
{
 string q = HtmlInputs[0].Value;
 CStrFun::Str2Lower(q,q.size()); //大寫變小寫word變量里的值
 m_sQuery = q;  //設置查詢關鍵字
}

4、GetInvLists
 bool CQuery::GetInvLists(map<string, string> &mapBuckets) const
{
 ifstream ifsInvInfo(INF_INFO_NAME.c_str(), ios::binary); //以二進制形式打開一個文件的輸入流緩沖，INF_INFO_NAME在頭文件Comm.h中定義了的， const string INF_INFO_NAME("./Data/sun.iidx");
 //倒排索引文件索引字和文檔好之間有一個制表符"\t"
 //朱德  14383 16151 16151 16151 1683 207 6302 7889 8218 8218 8637
 //朱古力  1085 1222
 
 if (!ifsInvInfo) {
  cerr << "Cannot open " << INF_INFO_NAME << " for input\n";
  return false;
 }
 string strLine, strWord, strDocNum;
 //以行讀取輸入流緩沖到字符串對象strLine中并做處理
 while (getline(ifsInvInfo, strLine)) {
  string::size_type idx;
  string tmp;
  idx = strLine.find("\t");
  strWord = strLine.substr(0,idx);
  strDocNum = strLine.substr(idx+1);
  mapBuckets.insert(map<string,string>::value_type (strWord, strDocNum)); //倒排表二項二維表存入映射中
 
  /*
  map<string, string>::iterator iter;
  int kkk = 0;
  for (iter = mapBuckets.begin(); kkk != 10; ++iter)
  {
   cout<<iter->first<<"  "<<iter->second<<"<br>";
   ++kkk;
  }
  cout.flush();
  */
 }
 return true;
}
 
5、GetDocIdx
 
bool CQuery::GetDocIdx(vector &vecDocIdx) const
{
 ifstream ifs(DOC_IDX_NAME.c_str(), ios::binary); 
 //0  0  bc9ce846d7987c4534f53d423380ba70
 //1  76760 4f47a3cad91f7d35f4bb6b2a638420e5
 //2  141624 d019433008538f65329ae8e39b86026c

 if (!ifs) {
  cerr << "Cannot open " << DOC_IDX_NAME << " for input\n"; //以二進制形式打開一個文件的輸入流緩沖，DOC_IDX_NAME在頭文件Comm.h中定義了的， const string INF_INFO_NAME("./Data/Doc.idx"); 
  return false;
 }

 string strLine, strDocid, strUrl;
 while (getline(ifs,strLine)){
  DocIdx di;

  sscanf( strLine.c_str(), "%d%d", &di.docid, &di.offset ); //只保留了前面兩項文檔號和偏移量
  vecDocIdx.push_back(di); //導入結(jié)構體向量中
 }

 return true;
}

由于百度博客http://hi.baidu.com/jrckkyy發(fā)表文章字數(shù)有限，以后原創(chuàng)文章全部都先發(fā)表到csdn和cu上，再發(fā)表到百度博客上，百度博客除了放原創(chuàng)的文章還主要放網(wǎng)上尋找到的優(yōu)秀文章。

本著黑客精神我將陸續(xù)把最近分析注釋TSE搜索引擎的心得發(fā)布出來，老鳥，大蝦，大牛，高手飄過就是了，若愿意浪費指點下小弟的在下不甚感激，有問題的朋友直接留言討論。由于本人水平有限，分析和翻譯難免有錯大家見笑了。

上學期拜讀了James F.Kurose著的《計算機網(wǎng)絡-自頂向下方法與internet特色(第三版陰影)》，覺得寫得確實不錯(希望沒看的朋友一定要買來看看)，自己也來搞個高自頂向下的學習方法，先從用戶看得到的東西出發(fā)分析研究搜索引擎，下面我們就來看看各大搜索引擎搜索界面的代碼，你所需要特別注意的是form表單中的action

雅虎http://www.yohoo.com/：

<form name=s1 style="margin-bottom:0" action="<table cellpadding=0 cellspacing=0 border=0><tr><td>
<input type=text size=30 name=p title="enter search terms here">&nbsp;
<input type=submit value=Search>&nbsp;&nbsp;</td><td><font face=arial size=-2>·&nbsp;
<a href=" search</a><br>·&nbsp;
<a href=" popular</a></font></td></tr></table></form>
谷歌http://www.g.cn：

<form method=GET action=/search><tr><td nowrap>
<font size=-1><input type=text name=q size=41 maxlength=2048 value="jrckkyy" title="Google 搜索"> <input type=submit name=btnG value="Google 搜索"><input type=hidden name=complete value=1><input type=hidden name=hl value="zh-CN"><input type=hidden name=newwindow value=1><input type=hidden name=sa value="2"></font></td></tr></form>
百度http://www.baidu.com：

<form name=f2 action="/s">
<tr valign="middle">
<td nowrap>
<input type=hidden name=ct value="0">
<input type=hidden name=ie value="gb2312">
<input type=hidden name=bs value="jrckkyy">
<input type=hidden name=sr>
<input type=hidden name=z value="">
<input type=hidden name=cl value=3>
<input type=hidden name=f value=8>
<input name=wd size="35" class=i value="jrckkyy" maxlength=100>
<input type=submit value=百度一下> <input type=button value=結(jié)果中找 onclick="return bq(f2,1,0);">&nbsp;&nbsp;&nbsp;</td>
<td nowrap><a href="</tr>
</form>
天網(wǎng)http://www.tianwang.com/：

<form name=f action="/cgi-bin/tw" method=get>
                <td valign=center width=634 background=images/index_image_02.gif>
                    <table height=46 cellspacing=0 cellpadding=0 width=600 align=right  border=0>
                        <tbody>
                            <tr>
                                <td height=50>
                                    <table cellspacing=0 cellpadding=0 width=600 border=0>
                                        <tbody>
                                            <tr>
                                  <td width="524" height="30" valign="bottom">
                                        <div align="center">                                  <input name="word" type="text" size="40" maxlength="255" onClick="this.focus();checkWord(this,1)" onblutesr='checkWord(this,0)' value='請輸入資源名稱'>
                                            <font color=#ffffff> &nbsp;
                                            <select onChange=reRange(this.selectedIndex) name=range>
                                                <script language=javascript>...
                           <!--
                           for(var i = 0; i < rescode.length; i++) ...{
                               if(i == 0) ...{
                                   document.write('<option value="0" selected>' + rescode[i][0] + '</option>');
                               } else ...{
                                   document.write('<option value="' + i + '">' + rescode[i][0] + '</option>');
                               }
                           }
                           document.f.range.selectedIndex = 0;
                           -->
                         </script>
                                            </select>
                                            </font>-<font color=#ffffff>
                                            <select name=cd>
                                                <script language=javascript>...
                           <!--
                           var ind = document.f.range.selectedIndex;
                           var len = (rescode[ind].length - 1) / 2;
                           var sel = 0;
                           for(var i = 0; i < len; i++) ...{
                               document.write('<option value="' + rescode[ind][2*i+1] + '">' + rescode[ind][2*i+2] + '</option>');
                               if(rescode[ind][2*i+1] == 0)
                                   sel = i;
                           }
                           document.f.cd.selectedIndex = sel;
                           -->
                 </script>
                                            </select>
                                            </font></div>
                                    </td>
                <td width="71" valign="bottom"><input id=submit2 type=image height=22 width=40 src="images/so2.gif" align=absMiddle name=submit></td>
              </tr>
                                            <tr>
                                                <td colspan=3 height=25 class=style16>
                                                    <div align=center></div>
                                                </td>
                                            </tr>
                                        </tbody>
                                    </table>
                                </td>
                            </tr>
                        </tbody>
                    </table>
                </td>
            </form>
測試服務器TSE：

<form method="get" action="/cgi-bin/index/TSESearch" name="tw">
        <td width="100%" height="25" align="center">                          
        <input type="text" name="word" size="55">
        <input type="submit" value=" 搜索" name="www">
        </td>                          
        <input type="hidden" name="cdtype" value="GB">                        
        </form>   
由以上幾個form的屬性可以看出全部采用的是get方法，CGI做為處理程序，也就是C/C++，CGI全稱是“公共網(wǎng)關界面”(Common Gateway Interface)，HTTP服務器與你的或其它機器上的程序進行“交談”的一種工具，其程序須運行在網(wǎng)絡服務器上。CGI逐漸被近幾年來的PHP，JAVA，ASP，PERL，Python，Ruby等動態(tài)語言所取代。但是其在速度和運行效率上的優(yōu)勢是無法取代的。

以下是TSE CGI入口程序注釋，其他搜索引擎的入口也應該類似

/**//**
 * 程序翻譯說明
 * @Copyright (c) 2008, 研發(fā)部
 * All rights reserved.
 *
 * @filesource  TSESearch.cpp
 * @author  jrckkyy <jrckkyy@163.com>
 *
 * Let's start
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/time.h>
#include <unistd.h>

#include <iostream>
#include <fstream>
#include <list>

#include "Comm.h"    //包含2個索引和1個數(shù)據(jù)文件
#include "Query.h"    //包含數(shù)據(jù)查詢處理頭文件
#include "Document.h"    //html文檔處理頭文件
#include "StrFun.h"        //字符串處理頭文件
#include "ChSeg/Dict.h"    //字元字典處理頭文件
#include "ChSeg/HzSeg.h"   
#include "DisplayRst.h"    //返回查詢結(jié)果頁面頭文件，返回結(jié)果分為頭部，中部，底部

using namespace std;

/**//*
 * A inverted file(INF) includes a term-index file & a inverted-lists file.
 * A inverted-lists consists of many bucks(posting lists).
 * The term-index file is stored at vecTerm, and
 * the inverted-lists is sored at mapBuckets.
 */

/**//**
 * 程序翻譯說明
 * 搜索程序入口前臺關鍵字提交到該cgi程序 例如：./cgi-bin/index/TSESearch?word=123&start=1
 * 倒排文件包括一個記錄檢索詞文件和一個倒排列表文件。
 * 倒排列表包含很多標志（提交名單）。
 * 記錄檢索詞文件使用vecTerm來排序，和倒排列表是用mapBuckets來排序。
 *
 * @access  public
 * @param   int char 參數(shù)的漢字說明 用于接收前臺get傳遞的參數(shù)
 * @return  string 0
 */
int main(int argc, char* argv[])
...{
    struct timeval begin_tv, end_tv;
    struct timezone tz;

    CDict iDict;
    map<string, string> dictMap, mapBuckets;
    vector<DocIdx> vecDocIdx;    //Document。h

    CQuery iQuery;
    iQuery.GetInputs();        //具體程序開始執(zhí)行
    // current query & result page number
    iQuery.SetQuery();
    iQuery.SetStart();

    // begin to search
    //開始具體搜索程序
    gettimeofday(&begin_tv,&tz);    //開始計時獲取程序運行時間差

    iQuery.GetInvLists(mapBuckets);        //將所有字符集存入映射變量中    瓶頸所在
    iQuery.GetDocIdx(vecDocIdx);        //將倒排索引存入向量中        瓶頸所在
   
    CHzSeg iHzSeg;        //include ChSeg/HzSeg.h
    iQuery.m_sSegQuery = iHzSeg.SegmentSentenceMM(iDict, iQuery.m_sQuery);    //將get到的查詢變量分詞分成 "我/        愛/        你們/    的/        格式"
   
    vector<string> vecTerm;
    iQuery.ParseQuery(vecTerm);        //將以"/"劃分開的關鍵字一一順序放入一個向量容器中
   
    set<string> setRelevantRst;
    iQuery.GetRelevantRst(vecTerm, mapBuckets, setRelevantRst);
   
    gettimeofday(&end_tv,&tz);
    // search end
    //搜索完畢

    //下面開始顯示
    CDisplayRst iDisplayRst;
    iDisplayRst.ShowTop();

    float used_msec = (end_tv.tv_sec-begin_tv.tv_sec)*1000
        +((float)(end_tv.tv_usec-begin_tv.tv_usec))/(float)1000;

    iDisplayRst.ShowMiddle(iQuery.m_sQuery,used_msec,
            setRelevantRst.size(), iQuery.m_iStart);

    iDisplayRst.ShowBelow(vecTerm,setRelevantRst,vecDocIdx,iQuery.m_iStart);

    return 0;

}