markov.c

C编写的用来实现search engine的推荐功能

/**
 * markov.c, markov model based recommendation
 * zhiyong zhang
 * louisville May 23th
 **/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <gdbm.h>

#include "recdef.h"
#include "session.h"

static char markov_two[256] = "/home/zhiyong/software/apache2/cgi-bin/markov_two.gdbm";
static char markov_three[256] = "/home/zhiyong/software/apache2/cgi-bin/markov_three.gdbm";
static int getMarkovRecsByOrder(SESSION_LINKS links, REC_LINKS* recs, int order);


/**
 * order markov order
 **/
static int getMarkovRecsByOrder(SESSION_LINKS links, REC_LINKS* recs, int order)
{
	int i,j,iRet;
	char sessions[256];
	char recoms[30960];
	char temp[30960];
	char* ptr = NULL;
	char* pptr = NULL;
	char* ptr_tmp = NULL;
	char* pptr_tmp = NULL;
	GDBM_FILE db = NULL;
	datum name;
	datum value;
	char gdbmFile[256];
	bzero(recs, sizeof(REC_LINKS));
	bzero(recoms, 30960);
	//get first order output
	if(order == 1)
	{	
		strcpy(sessions, links.urls[links.num-1].url);
		strcpy(gdbmFile, markov_two);
	}
	else if(order == 2)
	{
		strcpy(sessions, links.urls[links.num-2].url);
		strcat(sessions, "+");
		strcat(sessions, links.urls[links.num-1].url);
		strcpy(gdbmFile, markov_three);
	}
	db = gdbm_open(gdbmFile, 2048, GDBM_READER, 0644 ,0);
	if (db ==NULL)
	{
		fprintf(stderr, "open %s for read error\n", gdbmFile);
		return -1;
	}
	name.dptr = sessions;
	name.dsize = strlen(sessions);
	iRet = gdbm_exists(db, name);
	if(iRet != 0) 
	{
		value = gdbm_fetch(db, name);
		if(value.dptr != NULL)
		{
			strcpy(recoms, value.dptr);
			free(value.dptr);
			value.dptr = NULL;
			recoms[strlen(recoms)-1] = '\0';
			recoms[strlen(recoms)] = '\0';
		}
		else
		{
			fprintf(stderr, "error fetching gdbm lib file");
			gdbm_close(db);
			return -1;
		}
		strcpy(temp, recoms);
		pptr = recoms;
		i = 0;
		while((ptr = strchr(pptr, ' ')) != NULL)
		{
			*ptr = '\0';
			strcpy(temp, pptr);
			ptr_tmp = strchr(temp, '(');
			if(ptr_tmp != NULL) *ptr_tmp = '\0';
			strcpy(recs->urls[i].url, temp);
			pptr_tmp = ptr_tmp + 1;
			ptr_tmp = strchr(pptr_tmp, ')');
			if(ptr_tmp != NULL) *ptr_tmp = '\0';
			recs->urls[i++].wt = atof(pptr_tmp);
			recs->num++;
			pptr = ptr+1;
			if((i>=MAX_RECS_PER_VISIT/2) || (*pptr == '\0') || (pptr == NULL)) break;
		}
		if(pptr != NULL)
		{
			strcpy(temp, pptr);
			ptr_tmp = strchr(temp, '(');
			if(ptr_tmp != NULL) *ptr_tmp = '\0';
			strcpy(recs->urls[i].url, temp);
			pptr_tmp = ptr_tmp + 1;
			ptr_tmp = strchr(pptr_tmp, ')');
			if(ptr_tmp != NULL) *ptr_tmp = '\0';
			recs->urls[i++].wt = atof(pptr_tmp);
			recs->num++;
		}
		
	}
	iRet = recs->num;
	if(db!=NULL) 
	{
		gdbm_close(db);
		db = NULL;
	}
	return iRet;
}


int getMarkovRecs(SESSION_LINKS links, REC_LINKS* recs)
{
	int iRet;
	int num1, num2;
	char sessions[256];
	REC_LINKS rec_one, rec_two;
	bzero(&rec_one, sizeof(REC_LINKS));
	bzero(&rec_two, sizeof(REC_LINKS));
	if(links.num < 2)
	{
		return getMarkovRecsByOrder(links, recs, 1);
		//return getMarkovRecsByOrder(links, recs, 2);
	}
	num1 = getMarkovRecsByOrder(links, &rec_one, 1);
	if(num1 < 0)
	{
		fprintf(stderr, "error getMarkovRecsByOrder 1");
		return -1;
	}
	num2 = getMarkovRecsByOrder(links, &rec_two, 2);
	if(num2 < 0)
	{
		fprintf(stderr, "error getMarkovRecsByOrder 2");
		return -1;
	}
	iRet = mergeRecLinks(&rec_one, &rec_two);
	*recs = rec_one;
	return iRet;
}