webcom.cpp

使用中科院ICTLAS和BM25算法的检索

		hashvalue = enCode(keyWord[0], keyWord[1]);
		if (mark[hashvalue] == 1)	{temppNode = temppNode->next; continue;}
		mark[hashvalue] = 1;
		index[0]++;
		index[index[0]] = hashvalue;
		tempLen[hashvalue] = ORIGINE_LEN_OF_CHINESE;
		hash[hashvalue] = (int*)calloc(tempLen[hashvalue], sizeof(int));
		temppNode = temppNode->next;
	}

	lh_Hash(buffer, hash, tempLen, mark);
	temppNode = pNode;
	
	while (temppNode != NULL)
	{
		temppNode->oTimes = lh_Count(hash, temppNode->key, buffer, mark);
		temppNode = temppNode->next;
	}
	for (i = 1; i <= index[0]; i++)		free(hash[index[i]]);//index[]记录哪些被alloc过，快速free,经过试验，free是很费时间的。
	return pNode;
}

//以下是对回帖在全部贴中的相关度的计算，根据BM25算法写成，由薛子骏编写。
/**********************************************************************************************************************
在苦思冥想如何进行相关度计算的时候，神奇的波波找到了OKAPI BM25，于是我利用BM25写出了计算回帖在全部帖中的相关度的allscore函数
下面对函数进行说明
allScore函数的作用是对于传入的关键字序列（Link * node）对于所有帖子（Reply * p）依次根据BM25算法进行评分，
对于每一个帖子的分数，最终储存在一个Srch链表（scorelist）里，返回给外部。

首先给出BM25的相关度计算公式，该函数可以计算出对于一个document，一个给定的关键字序列i对于该document的score：
score = ∑( IDF[ i ] * f [ i ] * ( k1 + 1) ) / (f [ i ] + k1 * ( 1 - b + b * k2 ) )  (i = 1 .... KeywordsNum ) 

下面对这个公式中的每一部分进行解释
f[i] 的原型是（term frequency）是指第i个关键字在该document中的出现次数。
k2 的值为 该帖的长度 与所有贴的平均长度的比值 。这个量其实是很关键的。它可以在一定程度上消除帖子长度对于它重要性的影响。
k1 和 b 是 BM25 中的两个系数 通常 k1 = 2.0 ， b = 0.75 。

IDF[i]全称是（inverse document frequency）是根据每个关键在在所有帖中出现次数的多少进行该关键字的重要性调整
一个直观的认识是如果一个关键字在大多数帖中都出现，那么它的代表性就很差，所以这个这个关键字的IDF值就一定会小，
而反过来如果一个关键字只在这一个帖子里出现过，那么这个关键字的代表性就很强，它的IDF值就会很大，该关键字的重要性就被强调了。
有了IDF，大量水贴的重复关键字的权值就会被降的很低，从而达到了我们防水抗洪救灾的目的.(^-^)

IDF[i]的具体计算公式如下：
IDF[i] = log( ( repNum + n[ i ] + 0.5 ) / ( n [ i ] + 0.5 ) ) ;
公式中的repNum值所有回帖的总数，n[i]指在所有回帖中出现关键字i的帖子总数.

有了上面的这些公式，我们就可以实现这个基于Okapi BM25算法的allscore函数了~
**********************************************************************************************************************/


double fscore ( int n , int f[], double IDF[]  , double k2 ) // 这里是根据BM25公式计算具体的score值
{
	double ans = 0, k1 = 2.0, b = 0.75;
	int i;
	for ( i = 0 ; i < n ; i ++ )
		ans += ( IDF[ i ] * f [ i ] * ( k1 + 1) ) / (f [ i ] + k1 * ( 1 - b + b * k2 ) ) ;
	return ans ;
}

struct Srch * allScore(struct Reply * p , struct Link * node)
{
	int i , j ,*f , *n ,linkLen = 0 , totalLen = 0 ;
	double totScore = 0 , *IDF , k2 , avgL , Dlen ;
	struct Link * pNode = node;
	struct Reply * pReply = p ;
	struct Srch * scorelist = NULL ;
	while ( pNode != NULL)	{
		linkLen++;
		pNode = pNode -> next ;
	}//  统计查询关键字个数
	f = (int * ) calloc( linkLen , sizeof(int) ) ;// 每个关键字在该Reply中出现的个数
	n = (int * ) calloc( linkLen , sizeof(int) ) ;// 每个关键字在全部Reply中的出现的帖子的个数
	IDF = (double * ) calloc( linkLen , sizeof(double) ) ;//计算IDF函数
	 j = 0 ;
	 pNode = node;
	while ( pReply != NULL )	{//计算n（）函数

		pNode = countkey( pReply->comment , pNode );
		totalLen += strlen( pReply->comment );
		
		i = 0 ;
		while ( pNode != NULL )
		{
			if ( pNode -> oTimes ) 
				n[ i ] ++ ;
			i ++ ;
			pNode = pNode ->next ;
		}
		pReply = pReply -> next ;
		pNode = node;
		j ++ ;
	}
	int repNum = j ;
	for ( i = 0 ; i < linkLen ; i ++ )
		IDF[ i ] = log( ( repNum + n[ i ] + 0.5 ) / ( n [ i ] + 0.5 ) ) ;
	//计算IDF函数
	avgL = ( totalLen + 0.0 ) / repNum ;
	pReply = p;
	pNode = node ;
	while ( pReply != NULL )	{//计算所有score
		pNode = countkey ( pReply->comment , pNode ) ;
		i = 0 ;
		while ( pNode != NULL ) {
			f [ i ] = pNode -> oTimes ;
			i ++ ;
			pNode = pNode ->next;
		}
		Dlen = strlen( pReply ->comment ) ;
		k2 = Dlen / avgL ;
		double nscore ;
		nscore = fscore( linkLen , f , IDF , k2 ) ; 
		insertIdx( &scorelist , pReply , nscore ) ;
		pReply = pReply -> next ;
		pNode = node ;
	}

	free(f) ; free(n)  ;  free(IDF) ;
	return scorelist;
}

/**********************************************************************************************************************
关键字提取操作，封装了中科大编写的比较有效的ICTLAS3.0中文分词插件
有免费又强大的插件干嘛非得去写个不和谐的机械分词呢，嘎嘎嘎~
直接将字符串通过ICTLAS根据词性分词后保留长度为2-5的名词作为关键字传出进行检索。
关于ICTLAS3.0详情请见：
http://ictclas.org/
**********************************************************************************************************************/
Link *splitComment(char *sString)
{
	int nCount, i, j = 0;
	Link *Linkp = NULL, *LinkResult;
	const result_t *pVecResult = ICTCLAS_ParagraphProcessA(sString, &nCount);
	int Noun[4] = {21, 24, 30, 68};
	for (i = 0; i < nCount; i++)
	{
		for(j = 0; j < 4; j++)
			if (Noun[j] == pVecResult[i].POS_id)
				break;
		if (j < 4 && pVecResult[i].length >= 2 && pVecResult[i].length <= 12)
		{
			if (Linkp == NULL)
			{
				Linkp = (Link*) calloc (1, sizeof(Link));
				LinkResult = Linkp;
			}
			else 
			{
				Linkp->next = (Link*) calloc (1, sizeof(Link));
				Linkp = Linkp->next;
			}
			strncpy(Linkp->key, &sString[pVecResult[i].start], pVecResult[i].length);
		}
	}

	if (Linkp == NULL)
		return NULL;
	else
		return LinkResult;
}

//以下为主操作

//打印全部回复
void command1(Reply **p)
{
	printall(*p);
}

//删除回帖
void command2(Reply **p)
{
	int (*Reply_search[4])(Reply *, char [], char []) = {searchInfo1, searchInfo2, searchInfo3, searchInfo4};
	int selectnum;
	char keyWord[50], IP[17], buffer[200], temp = 0;
	printf("准备删除和谐贴……\n输入查找方式及查找内容：样例：\nIP=162.105\nKEY=北极熊\nIP=162.105 & KEY=北极熊\nIP=162.105 | KEY=北极熊\n==========================\n");
	fflush(stdin);
	gets(buffer);
	if (strstr(buffer, " | ") != NULL || strstr(buffer, " & ") != NULL)
	{
		sscanf(buffer, "IP=%[.0123456789] %c KEY=%s", IP, &temp, keyWord);

		if (temp == '&')
			selectnum = 3;
		else if (temp == '|')
			selectnum = 4;
	}
	else if (strstr(buffer, "IP") != NULL)
	{
		sscanf(buffer, "IP=%[.0123456789]", IP);
		selectnum = 1;
	}
	else 
	{
		sscanf(buffer, "KEY=%s", keyWord);
		selectnum = 2;
	}
	printf("正在检索……\n\n");
	deleteHX(p, Reply_search[selectnum-1], IP, keyWord);
}

//回帖
void command3(Reply **p)
{
	int parentID;
	char buffer[1000];
	printf("回复对象:");
	scanf("%i", &parentID);
	fflush(stdin);
	printf("回帖内容:");
	gets(buffer);
	if (replypost(p, parentID, buffer))
		printf("回复成功！\n");
	else 
		printf("回复失败！\n");
}

//检索特殊贴
void command4(Reply ** p)
{
	int command;
	double maxScore = -1 , nowScore = 0 ;
	Srch * pSrch = NULL , *phSrch;
	Link * pLink = NULL , *phLink ;
	Reply *pReply = NULL , *paimReply = NULL;
	printf("请输入所需的特殊贴：\n1.最具代表性贴\n2.最与众不同贴\n");
	scanf( "%i" , &command ) ;
	int time1 = clock();
	if ( command == 2 ) 
	{
		maxScore = -1e9 ;
		command = -1;
	}
	pReply = *p ;
	if(!ICTCLAS_Init())
	{
		printf("Init fails\n");
		return ;
	}
	else 
		system("cls");
	printf("正在进行检索……\n\n");
	while ( pReply != NULL ) 
	{	
		pLink = splitComment( pReply -> comment );
		if (pLink == NULL)
		{
			pReply = pReply->next;
			continue;
		}
		phLink = pLink ;
		pSrch = allScore( pReply , pLink ) ;
		phSrch = pSrch ;
		nowScore = 0 ;
		while (pSrch != NULL) 
		{
			nowScore += pSrch->dScore ;
			pSrch = pSrch ->next ;
		}
		nowScore = command * nowScore ;
		if ( nowScore > maxScore) 
		{
			maxScore = nowScore ;
			paimReply = pReply ;
		}
		pReply = pReply -> next ;
	}
	

	ICTCLAS_Exit();
	output( paimReply ) ;
	printf("所需时间：%ims\n", (int)clock() - time1);
	while ( phLink != NULL ) { pLink = phLink ; phLink = phLink ->next ; free( pLink ) ; }
	while ( phSrch != NULL ) { pSrch = phSrch ; phSrch = phSrch ->next ; free( pSrch ) ; }
}

//按关键字检索，仍用相似度进行检索
//如果需要打印全部相似贴可以直接打印链表pSrch，用插入排序排好的
void command5(Reply **p)
{
	Srch *pSrch = NULL;
	Link *pLink = NULL, *phLink = NULL;
	Reply *pReply = *p;
	char sString[12];

	printf("请输入你感兴趣的话题关键字序列，以0结束\n例:俄罗斯 毛子 0\n");
	fflush(stdin);
	while (scanf("%s", sString) == 1)
	{
		if (strcmp(sString, "0") == 0)
			break;
		if (pLink == NULL)
		{
			pLink = (Link*) calloc(1, sizeof(Link));
			phLink = pLink;
		}
		else
		{
			pLink->next =  (Link*) calloc(1, sizeof(Link));
			pLink = pLink->next;
		}
		strcpy(pLink->key, sString); 
	}
	pSrch = allScore(pReply, phLink) ;
	output(pSrch->rep) ;
	while (phLink != NULL) 
	{ 
		pLink = phLink; 
		phLink = phLink ->next; 
		free(pLink); 
	}
}