qiyi.cpp

最大概率法分词的数据结构与算法

#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#include <stdio.h>
#include<math.h>
#define CorpusSize 200000


/*struct Candidate
{
	short offset,length;
	short goodPrev;
	float fee,sumFee;
}Candidates[100];
*/

CString SegmentHzStrMP(CString s1)
{
	int len=s1.GetLength();
	short n=getTmpWords(s1);
	short minID=-1;
	short i;
	for(i=0;i<n;i++)
		getPrev(i);
	if(Candidates[i].offset+Candidates[i].length==len)
	{
		if(minID==-1||Candidates[i].sumFee<Candidates[minID].sumFee)minID=i;}
}
CString s2="";
for(i=minID;i>=0;i=Candidates[i].goodPrev)
  s2=s1.Mid(Candidates[i].offset,Candidates[i].length)+Separator+s2;
return s2;
}
short getTmpWords(CString& s)
{
	short i=0,j,len,freq,n=s.GetLength();
	CString w;
	for(j=0;j<n;j+=2)
	{
		for(len=2;len<=MaxWordLength;len+=2)
		{
			w=s.Mid(j,len);
			freq=pDict->GetFreq(w);
			if(freq==-1)freq=0;
			Candidates[i].offset=j;
			Candidates[i].length=len;
			Candidates[i].fee=-log((double)(freq+1)/CorpusSize);
			Candidates[i].sumFee=0.0F;
			i++;
		}
	}
	return i;
}
void getPrev(short i)
{
	if(Candidates[i].offset==0)
	{
		Candidates[i].goodPrev=-1;
		Candidates[i].sumFee=Candidates[i].fee;
		return;
	}
	short j,minID=-1;
	for(j=i-1;j>=0;j--)
		if(Candidates[j].offset+candidates[j].length==Candidates[i].offset)break;
		for(;Candidates[j].offset+Candidates[j].length==Candidates[i].offset;j--)
			if(minID==-1||Candidates[j].sumFee<Candidates[minID].sumFee)minID=j;
			Candidates[i].goodPrev=minID;
			Candidates[i].sumFee=Candidates[i].fee+Candidates[minID].sumFee;
			return;
}

/*
FILE * in,* out;
in = fopen("199801.txt","rt");
out = fopen("199802.txt","wt");
if(in == NULL||out == NULL)
{
	AfxMessageBox("无法打开或创建文件!");
	return;
}
char s[1000];
int i=1;
while(fgets(s,1000,in))
{
	fprintf(out,"%4d%s",i,s);
	i++;
}
fclose(in);
fclose(out);
return;