微型搜索引擎-Tiny Search Engine

TSE是Tiny Search Engine（“微型搜索引擎”）的简称，由北京大学网络实验室出品
这个实验室推出过当年教育网搜索颇有名气的“北大天网搜索”
天网培养了中文互联网早期的一批的搜索技术专家
bd的技术路线和TSE很像
TSE包括网页抓取、分词、倒排索引生成等模块，可以视为天网的袖珍版。
代码用C++开发，短小精干，运行效率很高
我感觉实际效果比开源的一些Spider要好，修改起来也很方便
TSE网页抓取
开始是main函数,在main.cpp
如果控制台参数是1个,就进行搜索:
CSearch iSearch;
iSearch.DoSearch();
如果控制台参数是2个,就运行网络爬虫:
CCrawl iCrawl(argv[2],"visited.all");
iCrawl.DoCrawl();
其中argv[2]是inputfile visited.all是outputfile.
在DoCrawl函数里,初始化是把已经访问过的url加入到一个集合中去,
即调用函数GetVisitedUrlMD5(),这个函数里,主要是读取一个文件:
while( getline(ifsMD5,strMD5) ){
setVisitedUrlMD5.insert(strMD5);
}
setVisitedUrlMD5就是一个已经访问过的url集合
同理于GetVisitedPageMD5();GetIpBlock();
GetUnreachHostMD5();
分别读取文件内容到setVisitedPageMD5,mapIpBlock,setUnreachHostMD5
set<string> setVisitedUrlMD5;
set<string> setVisitedPageMD5;
map<unsigned long,unsigned long> mapIpBlock;
其中setUnreachHostMD5 是从文件读出不能到达的url,然后对这个url取了一个MD5值,存进内存中这个集合的.
这些前期工作做完以后,就开始读取种子文件,也就是开始爬取采用的起始url.
先是打开所有的输出流文件,函数是OpenFilesForOutput().也就是将来爬取得结果存放的文件.这里面包括索引文件(专门的类来打开),visited.url,link4SE.url,link4History.url(这个可能存放的是一篇HTML中的图像链接),unreach host file,visited url md5 file,visited page md5 file.
for(unsigned int i=0; i< NUM_WORKERS; i++){
if( pthread_create( &tids[i],NULL,start,this))
cerr << "create threads error" << endl;
}
启动10个线程,每个线程执行的函数是start,参数是this指针
在启动线程的同时,读取种子文件的url
while( getline(ifsSeed,strUrl) ){
//对读到的url进行一些处理后,调用AddUrl(strUrl)函数
AddUrl(strUrl.c_str());
}
也同时读取未访问的url
while( getline(ifsUnvisitedUrl,strUrl) ){
AddUrl(strUrl.c_str());
}
开看AddUrl函数做了哪些工作
AddUrl(const char * url)
在这个函数里,先判断是否是图像类型链接,是的话就加入m_ofsLink4HistoryFile 集合
string strUrl = url;
if (iUrl.IsImageUrl(strUrl))
{
if( m_ofsLink4HistoryFile ){
pthread_mutex_lock(&mutexLink4HistoryFile);
m_ofsLink4HistoryFile << strUrl << endl;;
pthread_mutex_unlock(&mutexLink4HistoryFile);
}
return;
}
在通过函数iUrl.ParseUrlEx(strUrl) ,解析strUrl代表的各种信息,如Host,scheme,port 以及request
如果不是图片链接,就把这个Host的MD5摘要加入到集合setUnvisitedUrlMD5中去,Host来源是iUrl.m_sHost成员.
CMD5 iMD5;
iMD5.GenerateMD5( (unsigned char*)iUrl.m_sHost.c_str(),iUrl.m_sHost.size() );
string strDigest = iMD5.ToString();
setUnvisitedUrlMD5.insert(strDigest);注意这个保存的是MD5
之后把<host,url>存到一个map映射里去mmapUrls.insert(mvalType( iUrl.m_sHost,strUrl));
这个mmap里保存的是没有访问过的url,不是MD5,上面的那个集合是用来判断用的,
实际的线程函数会用到mmap
再来看前面说的线程函数start
start(arg)-->fetch(arg)
参数arg是CCrawl对象指针
在函数fetch中,先打开天网索引文件,以便存放结果
string ofsName = DATA_TIANWANG_FILE + "." + CStrFun::itos(pthread_self());
CTianwangFile tianwangFile(ofsName);
再打开一个Link4SEfile文件(Link4SE.raw),ofsName = DATA_LINK4SE_FILE + "." + CStrFun::itos(pthread_self());
CLink4SEFile link4SEFile(ofsName);
在fetch函数里,遍历mmap,取出<host,url>对
multimap<string,string>::iterator it=mmapUrls.begin();
取出url：
string strUrl = (*it).second;
再调用下载函数
(( CCrawl* )arg)->DownloadFile(&tianwangFile,&link4SEFile,iUrl,nGSock);
开始下载实际网页.
在DownloadFile函数里,实际下载的功能由file_length = http.Fetch( strUrlLocation,&downloaded_file,&fileHead,&location,&nSock);这句来实现.
char *downloaded_file = NULL,
*fileHead = NULL,
*location = NULL;
下载来的网页文件保存在downloaded_file,fileHead,location内存中.
之后把这些内容作为参数传递进CPage对象里.
CPage iPage(iUrl.m_sUrl,strUrlLocation,fileHead,downloaded_file,file_length);
对已经爬取了的网页url处理,把它的MD5插入到已经爬取网页url集合中去
iMD5.GenerateMD5( (unsigned char*)iUrl.m_sUrl.c_str(),iUrl.m_sUrl.length() );
strDigest = iMD5.ToString();
if( setVisitedUrlMD5.find(strDigest) != setVisitedUrlMD5.end() ) {
//找到集合中有这个元素,其实
//可以不用检查的
cout << "!vurl: "; //1.crawled already
return; //立刻返回
}
setVisitedUrlMD5.insert(strDigest);
SaveVisitedUrlMD5(strDigest);//写入已经爬取的url的文件
之后把网页内容写入天网格式文件
SaveTianwangRawData(pTianwangFile,&iUrl,&iPage);
对爬取的网页内容提取超链接,这是用Lex完成的,上篇已经写过了TSE中的Lex流程.
先是struct uri page_uri;
uri_parse_string(iPage.m_sUrl.c_str(),&page_uri);
把该网页的url由String转换成结构来存放.
之后调用
hlink_detect_string(iPage.m_sContent.c_str(),&page_uri,onfind,&p);
就是上篇写的处理网页类.
TSE链接提取
TSE中提取html中链接uri 采用的是Lex分析
TSE中和lex相关的是hlink.l和uri.l
其中uri.l是用来处理一个提取出的uri，hlink.l是用来提取html中链接的。
代码流程：
在Crawl类的DownloadFile()方法中，当取得一个网页（HTML)的内容，并存到一个CPage类里。
开始对CPage类进行分析处理。先是处理这个网页的uri uri_parse_string(iPage.m_sUrl.c_str(),&page_uri); 结果存到page_uri里去。
之后调用hlink_detect_string(iPage.m_sContent.c_str(),&page_uri,onfind,&p);
这个hlink_detect_string函数是关键函数，这个函数的意思就是，把网页内容作为参数（iPage.m_sContent.c_str())传进去，当找到有链接信息后就调用onfind函数，onfind函数的参数是&p.
hlink_detect_string函数是在hlink.l中定义的。
int hlink_detect_string(const char *string,const struct uri *pg_uri,onfind_t onfind,void *arg)
参数string就是传入的网页内容，pg_uri是这篇网页的地址，onfind是找到链接后要执行的函数，arg是参数，会一直带着走的。
if (buf = yy_scan_string(string))
{
yy_switch_to_buffer(buf);
__base_uri = (struct uri *)pg_uri;
__is_our_base = 0;
__onfind = onfind;
__arg = arg;
BEGIN INITIAL;
n = yylex();
}
buf = yy_scan_string(string)和
yy_switch_to_buffer告诉程序，需要分析的字符串是参数string 并把传入的参数存为全局变量。
之后进入INITIAL状态，yylex()函数启动分析流程。
在INITIAL状态下遇到以下表达式的话"<"{cdata}/{blank}|">" 就是说，遇到类似"<A>"或者" <A "的话，就把"A" 那一行对应的数组赋给__cur_elem全局结构。比如，搜索到"<A "就把{"A",__elem_a_attr}赋给__cur_elem.相关代码为：
/* Element names are case-insensitive. */
for (yyleng = 0; __elems[yyleng].name; yyleng++)
{
if (strcasecmp(yytext + 1,__elems[yyleng].name) == 0)
{
__cur_elem = __elems + yyleng;
break;
}
}
其中数组的定义为
static struct __elem __elems[] = {
{"A",__elem_a_attr},
{"AREA",__elem_area_attr},
{"BASE",__elem_base_attr},
{"FRAME",__elem_frame_attr},
{"IFRAME",__elem_iframe_attr},
{"IMG",__elem_img_attr},
{"LINK",__elem_link_attr},
{"META",__elem_meta_attr},
{NULL,}
};
static const struct __elem *__cur_elem;
之后进入ATTRIBUTE状态
yy_push_state(ATTRIBUTE);
在ATTRIBUTE状态下想要找出ATTRIBUTE的值比如A href= 首先取得href (没有"=")
此时匹配的字符串yytext为"href" 就是把空格和等号去掉后的字符串相关代码为
匹配的正则表达式：{cdata}{blank}{0,512}"="{blank}{0,512}
去掉空格和等号：
yyleng = 0;
while (!HLINK_ISBLANK(yytext[yyleng]) && yytext[yyleng] != '=')
yyleng++;
yytext[yyleng] = '/0';
然后把属性值就是"href"串存到char *__cur_attr中，并用__curpos来标记存放uri的数组_buffer的位置
for (yyleng = 0; __cur_elem->attrs[yyleng]; yyleng++)
{
if (strcasecmp(yytext,__cur_elem->attrs[yyleng]) == 0)
{
__curpos = __buffer;
__cur_attr = __cur_elem->attrs[yyleng];
break;
}
}
进入URI状态，准备提取URI
BEGIN URI;
在URI状态下，如果遇到双引号，就进入双引号状态，反之单引号也一样
<URI>/"{blank}{0,512} BEGIN DOUBLE_QUOTED;
<URI>"'"{blank}{0,512} BEGIN SINGLE_QUOTED;
就是说现在已经读了<A href=" 准备读取实际的uri了
也就是一般会进入这个动作：
<UNQUOTED,DOUBLE_QUOTED,SINGLE_QUOTED,ENTITY>.|/n
.|/n 就是除了读取到引号之前的字符（因为引号代表href="xxx" xxx读取完毕） 当然也不包括"&lt;"这些很特殊的HTML代码。
读到字符时,最关键的语句是*__curpos++ = *yytext; 就是把字符读到_curpos指向的内存数组中去，并把_curpos指针加1，就这样一直读，直到把uri读取完毕，也就是读取到引号之类的
<DOUBLE_QUOTED>{blank}{0,512}/" |
<SINGLE_QUOTED>{blank}{0,512}"'" |
<UNQUOTED>{blank}|">" {
读取完毕后的操作是，首先在读取到的字符串后2位，全部加上结束字符"/0",
*(__curpos + 1) = *__curpos = '/0';
用一个指针指向uri数组的起始位置
ptr = __buffer;
之后把string类型的字符数组，存到uri结构体去
yyleng = uri_parse_buffer(ptr,__curpos - ptr + 2,&uri);
然后把找到的uri和该uri所在的uri merge成一个最终uri result
uri_merge(&uri,__base_uri,result);
最终调用onfind函数
__onfind(__cur_elem->name,__cur_attr,result,__arg)
关于_onfind函数的调用是一旦找到一个合法的uri 就会调用所以在扫描一篇HTML时会多次调用onfind函数
onfind函数的功能在获得的uri 如果是img类型就存到m_ofsLink4HistoryFile文件里去
如果是其他类型就交给AddUrl函数处理
这个是TSE中Lex 分析HTML过程的大致流程以后再写TSE的主代码如何爬取网页的流程

TSE是Tiny Search Engine（“微型搜索引擎”）的简称，由北京大学网络实验室出品
这个实验室推出过当年教育网搜索颇有名气的“北大天网搜索”
天网培养了中文互联网早期的一批的搜索技术专家
bd的技术路线和TSE很像