TSE中关于分词的算法的改写最少切分

今天比较闲，想到以前也看了好多tse的代码，还没有上手改过呢，一时也不知从何入手，后来在书上看到了分词的算法，TSE用的是正向最大匹配，其中貌似有个好玩的算法-----最少切分，捣鼓了一下午，终于把代码弄出来了。

如果有人有兴趣的话，在HzSeg中修改SegmentSentenceMM函数的代码，将s2+=SegmentHzStrMM(dict, s1.substr(0,i));

改成s2+=SegmentHzStr_min_cut(dict, s1.substr(0,i));就OK了。

代码显得还是有些冗余，还是有优化的余地的，有时间再改吧。

string get_res(map<int,map<int,int> > path,    map<int,int>  min_path,string s1,int l){
#undef _debug_hzseg
#ifdef _debug_hzseg
    cout<<"s1:"<<s1<<"l"<<l<<endl;
    for (int i = 0; i < l; i++) {
        cout<<"<!-- ";
        for (int j = 0; j < l; j++) {
            cout<<path[i][j]<<" ";
        }
        cout<<"-->"<<endl;
    }
    for (int i = 0; i < l; i++) {
        cout<<min_path[i];
    }
#endif
    int i,j,start,next_start,tmp_min;
    string res;
    start=0;
    while(start<l){
        tmp_min=min_path[start];
        for(j=start;j<l-1;j++){
            if((1==path[start][j])&&tmp_min==path[start][j]+min_path[j+1]){//如果这个是最少切分的话，就记录下来
                res=res+s1.substr(start*2,j*2-start*2+2)+SEPARATOR;
                start=j+1;
                break;
            }
        }
        if ((1==path[start][j])&&j == l-1 ) {
            res = res + s1.substr(start * 2, j * 2 - start * 2 +2) + SEPARATOR;//说明是最后一个了
            start=l;
            break;
        }
    }
return res;
}



// 最小切分算法
string SegmentHzStr_min_cut (CDict &dict, string s1)
{
    int j;
    int s1_size=s1.size()/2;
    string tmp;
    map<int,map<int,int> > path;
    map<int,int>  min_path;
    bool isw;

    for (int i = 0; i < s1_size; i++) {
        for (int j = 0; j < s1_size; j++) {
                path[i][j] = 0;
        }
    }

    for(int i=0;i<s1_size;i++){
        for(int j=i;j<s1_size;j++){
            tmp=s1.substr(i*2,j*2-i*2+2);
            isw=dict.IsWord(tmp);
            if(isw)
                path[i][j]=1;
        }
    }
    for(int i=0;i<s1_size;i++)
        path[i][i]=1;//每个单独的字认为是一个词

    map<int,int> min_cut;
    min_path[s1_size-1]=1;
    for(int i=s1_size-2;i>=0;i--){//动态规划做的
        min_path[i]=10000;
        for(j=i;j<s1_size-1;j++){
            if(1==path[i][j]&&(min_path[i]>path[i][j]+min_path[j+1])){
                    min_path[i]=path[i][j]+min_path[j+1];
            }
        }
        if (path[i][j] ) {
            min_path[i] = 1;
        }
    }
    string s2=get_res(path,min_path,s1,s1_size);//根据上边算出来的min_path获得最少切分
    return s2;
}