| « | December 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | |
|
公告 |
在此正式宣布，这个Blog下的地盘，都是偶的啦  这个版面专用于技术...别的就先不贴了！ |
| 信息 |
|
blog名称:技术至上
日志总数:4
评论数量:1
留言数量:0
访问次数:73483
建立时间:2004年12月11日 |
| |
|
 [Algorithms]KMP、Monte Carlo、Las Vegas 匹配算法 (用C++ & STL实现)
原创空间, 软件技术
Stanley 发表于 2004/12/11 19:59:02 |
|
// StrMatcher.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"#include "basicmatcher.h"
#include <stdlib.h>#include <stdio.h>#include <time.h>
#define STRING_NUM 10000
//素数(Prime Number)产生器，这里利用讲义中提供的7素数分类，而非自行产生//PNM is short for "Prime Number Matrix"namespace PNM{ //不同范围内的素数矩阵 int pnm[6][7]={ {211,223,227,229,233,239,241}, {461,463,467,479,487,491,499}, {953,967,971,977,983,991,997}, {4957,4967,4969,4973,4987,4993,4999}, {9923,9929,9931,9941,9949,9967,9973}, {100003,100019,100043,100049,100057,100069,100103} };
//根据m、n的大小确定M，并随机抽取一个适当的素数 //注意在全局调用前应使用srand((unsigned)time(NULL)); int Generate(const CmpStrPair& csp){ int m=csp.second.second,n=csp.first.second; int M=2*m*n*n; //M=2*m*n*n int N=rand()%7; //N为随机数(0<=N<=6) if(M>0 && M<=250) return pnm[0][N]; else if(M>250 && M<=500) return pnm[1][N]; else if(M>500 && M<=1000) return pnm[2][N]; else if(M>1000 && M<=5000) return pnm[3][N]; else if(M>5000 && M<=10000) return pnm[4][N]; else return pnm[5][N]; }};
//计时器变量clock_t start,step;//计时结果double total_time,run_time;
int _tmain(int argc, _TCHAR* argv[]){ //产生大于5000组的随机串 CmpStrVector csv; Romdomizer rmd; for(int i=0;i<STRING_NUM;i++){ rmd.Romdomize(csv); } //就上述产生的随机串进行各类匹配操作 //KMP KMP kmp(csv[0]); start=clock(); for(int i=0;i<STRING_NUM;i++){ kmp.ReSet(csv[i]); kmp.FastFind(); } step=clock(); total_time=double(step-start)/CLOCKS_PER_SEC; run_time=total_time/STRING_NUM; cout<<"KMP Approach :"<<endl; cout<<"Total Time : "<<total_time<<endl <<"Run Time : "<<run_time<<endl<<endl <<"--------------------------------"<<endl<<endl;
//Monte Carlo MonteCarlo mc(csv[0]); start=clock(); for(int i=0;i<STRING_NUM;i++){ mc.ReSet(csv[i]); mc.Compare(PNM::Generate(csv[i])); } step=clock(); total_time=double(step-start)/CLOCKS_PER_SEC; run_time=total_time/STRING_NUM; cout<<"Monte Carlo Approach :"<<endl; cout<<"Total Time : "<<total_time<<endl <<"Run Time : "<<run_time<<endl<<endl <<"--------------------------------"<<endl<<endl; //Las Vegas LasVegas lv(csv[0]); start=clock(); for(int i=0;i<STRING_NUM;i++){ lv.ReSet(csv[i]); lv.Compare(PNM::Generate(csv[i])); } step=clock(); total_time=double(step-start)/CLOCKS_PER_SEC; run_time=total_time/STRING_NUM; cout<<"Las Vegas Approach :"<<endl; cout<<"Total Time : "<<total_time<<endl <<"Run Time : "<<run_time<<endl<<endl <<"--------------------------------"<<endl<<endl;
cout<<"Monte Carlo Approach's Mistake-Rate Is :" <<1-float(lv.match_num)/float(mc.match_num)<<endl; return 0;}
//Utility.h : 辅助工具的定义
#include<iostream>#include<string>#include<bitset>#include<limits>#include<vector>#include<utility>
using namespace std;
//程序中用到的一些预定义和函数namespace def{ //比特流原型，包含了比特流的数值信息 typedef bitset<numeric_limits<unsigned long>::digits> Bits; //比特流模拟串：后项为串实际长度（前截断） typedef pair<Bits,unsigned int> BitString; //比较串对：前项为源串，后项为目标串 typedef pair<BitString,BitString> CmpStrPair; //比较串对向量：用来存储已经生成的比较串对序列 typedef vector<CmpStrPair> CmpStrVector; //打印比特串BitString ostream& operator << (ostream& os,BitString& b_str);};
using namespace def;
//随机数列产生器类class Romdomizer{public: Romdomizer(); //将生成的比较串对送到待处理序列中 void Print(ostream& os=cout){ os<<"Source : "<<source<<endl <<"Target : "<<target<<endl; } bool Romdomize(CmpStrVector&); void Romdomize(); //随机生成新比较串对private: void Create(long& v,unsigned int& s,bool isSource); //随机产生比特串的必要构成：v,比特串值、s：比特串长
BitString source; //比较源串X：x1,...,xn BitString target; //比较目标串Y：y1,...,ym};
//Utility.cpp : 辅助工具的实现
#include "stdafx.h"#include "Utility.h"
#include <stdlib.h>#include <stdio.h>#include <time.h>
//---------------------------------------------------------------------------------------------
namespace def{ ostream& operator << (ostream& os,BitString& b_str){ for(int i=b_str.second-1;i>=0;i--) os<<b_str.first[i]; return os; }};
//---------------------------------------------------------------------------------------------
Romdomizer::Romdomizer(){ //根据时间设置随机 srand((unsigned)time(NULL));}
void Romdomizer::Create(long& v,unsigned int& s,bool isSource){ //串长度的最大值（目标串的最大长度应为源串的长度，根据isSource是否成真确定是否为源串） size_t size_max; long value_max=1; //根据随即产生的串长度决定串值可能取的最大值 //计算串长度的最大值 if(isSource){ size_max=numeric_limits<unsigned long>::digits; } else size_max=static_cast<size_t>(3*s/4+1);//为了增加成功率，假设目标串较短，长度不到源串3/4 //产生随机串长度 s=rand()%size_max+1; //根据串长计算串值的最大值 for(int i=static_cast<int>(s);i>0;i--) value_max*=2; value_max--; //产生随机串值 v=value_max*(float(rand())/float(RAND_MAX));}
void Romdomizer::Romdomize(){ long t_value=0; //临时串值 unsigned int t_size=0; //临时串长度 //随机生成源串 Create(t_value,t_size,true); source=make_pair(Bits(t_value),t_size); //随机生成目标串 Create(t_value,t_size,false); target=make_pair(Bits(t_value),t_size);}
bool Romdomizer::Romdomize(CmpStrVector& v){ if(v.size()<v.max_size()){ Romdomize(); CmpStrPair t_p(source,target); v.push_back(t_p); return true; } return false;}
// BasicMatcher.h : 基本匹配函数的定义
#include "Utility.h"
//说明：这里使用BitString特殊表现形式，以下方法采用反向匹配机制//即ym,...,y1与xn,...,x1匹配，如果成功，则原先的正向串也必然匹配//反之，则原先的正向串必然不匹配
class KMP{public: KMP(CmpStrPair& csp):p_source(&csp.first),p_target(&csp.second){ for(int i=0;i<numeric_limits<unsigned long>::digits;i++) fail[i]=-2; Fail(); } inline void ReSet(CmpStrPair& csp){ p_source=&csp.first; p_target=&csp.second; for(int i=0;i<numeric_limits<unsigned long>::digits;i++) fail[i]=-2; Fail(); } int FastFind(); //KMP的主匹配函数private: void Fail(); //失效函数 BitString* p_source; //源串的引用 BitString* p_target; //目标串的引用 int fail[numeric_limits<unsigned long>::digits];};
class MonteCarlo{public: MonteCarlo(CmpStrPair& csp):p_source(&csp.first),p_target(&csp.second),match_num(0){;} inline void ReSet(CmpStrPair& csp){ p_source=&csp.first; p_target=&csp.second; }
//Monte Carlo的匹配主函数 //p:随机产生的素数 int Compare(int p); int match_num;private: BitString* p_source; //源串的引用 BitString* p_target; //目标串的引用};
class LasVegas{public: LasVegas(CmpStrPair& csp):p_source(&csp.first),p_target(&csp.second),match_num(0){;} inline void ReSet(CmpStrPair& csp){ p_source=&csp.first; p_target=&csp.second; }
//Last Vegas的匹配主函数 //p:随机产生的素数 bool Verify(int pos); int Compare(int p); int match_num;private: BitString* p_source; //源串的引用 BitString* p_target; //目标串的引用};
//BasicMatcher.cpp : 基本匹配函数的实现
#include "stdafx.h"#include "BasicMatcher.h"
void KMP::Fail(){ int length=p_target->second; fail[0]=-1; for(int j=1;j<length;j++){ int i=fail[j-1]; while(p_target->first[j]!=p_target->first[i+1] && i>=0) i=fail[i]; if(p_target->first[j]==p_target->first[i+1]) fail[j]=i+1; else fail[j]=-1; }}
int KMP::FastFind(){ int posS=0,posT=0; int lenS=p_source->second,lenT=p_target->second; while(posT<lenT && posS<lenS) if(p_target->first[posT]==p_source->first[posS]){ posT++; posS++; } else if(posT==0) posS++; else posT=fail[posT-1]+1; if(posT<lenT) return 0; else return posS-lenT+1;//方向匹配结果}
int MonteCarlo::Compare(int p){ int n=p_source->second,m=p_target->second; int j=0; int temp=1; //用以求得2的m次方 for(int i=0;i<m;i++) temp*=2; int Wp=temp % p; //求源串指纹 //先求以X0开头m位的数值value作为递推的起点; long value=0; for(int i=0;i<m;i++){ value*=2; int bit=p_source->first[i]?1:0; value+=bit; } int Ipx=value % p; int Ipy=p_target->first.to_ulong() % p; //求目标串指纹 while(j<n-m){ if(Ipx==Ipy){ match_num++; return j+1; } //根据公式计算Ipx int t1=p_source->first[j]?1:0; int t2=p_source->first[j+m]?1:0; Ipx=(2*Ipx+t1*Wp+t2) % p; j++; } return 0;}
bool LasVegas::Verify(int pos){ for(int i=0;i<p_target->second;i++){ if(p_target->first[i]!=p_source->first[pos+i]) return false; } return true;}
int LasVegas::Compare(int p){ int n=p_source->second,m=p_target->second; int j=0; int temp=1; //用以求得2的m次方 for(int i=0;i<m;i++) temp*=2; int Wp=temp % p; long value=0; for(int i=0;i<m;i++){ value*=2; int bit=p_source->first[i]?1:0; value+=bit; } int Ipx=value % p; int Ipy=p_target->first.to_ulong() % p; //求目标串指纹 while(j<n-m){ //加入了验证环节 if(Ipx==Ipy && Verify(j)) { match_num++; return j+1; } //根据公式计算Ipx int t1=p_source->first[j]?1:0; int t2=p_source->first[j+m]?1:0; Ipx=(2*Ipx+t1*Wp+t2) % p; j++; } return 0;} |
|
|