diff diff算法实践

////////////////////////////////////////////////////////////////////// // CmpMngr.cpp: implementation of the CCmpMngr class. ////////////////////////////////////////////////////////////////////// #include "CmpMngr.h" ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// CCmpMngr::CCmpMngr():LCSBitMatrix(1,1) { } CCmpMngr::~CCmpMngr() { } ////////////////////////////////////////////////////////////////////////////////////// // A utility function ////////////////////////////////////////////////////////////////////////////////////// void myGetline(ifstream& ifs, std::string& s, char d = '\n' ) { char getbuff[400]; ifs.getline(getbuff,400,d); s = std::string(getbuff); } std::string strReplace(std::string s,char *toFind, char* replaceWith) { while (s.find(toFind,0) != std::string::npos) { s.replace(s.find(toFind,0),1,std::string(replaceWith)); } return s; } ////////////////////////////////////////////////////////////////////////////////////// // Interface function for client, To be called after 'baseFile' & 'compFile' // assigned with aexisting filename ////////////////////////////////////////////////////////////////////////////////////// bool CCmpMngr::compare() { ifstream base(baseFile.c_str()); ifstream comp(compFile.c_str()); //CFileException e; //match_pair diffmap; if ( (base.is_open()) && (comp.is_open()) ) { // Read the file into vectors readInto(base,baseFileMap); readInto(comp,compFileMap); base.close();comp.close(); // Hash the vectors hash(baseFileMap,baseHmap);hash(compFileMap,compHmap); compare_hashed_files(baseHmap,compHmap,match_pairs,std::string("LCS")); } else { //afxMessageBox(e.m_cause,MB_OK,0);ifstream } return true; } ////////////////////////////////////////////////////////////////////////////////////// // Read line-by-line from a input stream and store into filemap ////////////////////////////////////////////////////////////////////////////////////// bool CCmpMngr::readInto(ifstream &file, filemap &f) { std::string s; int lineNo; lineNo = 1; do { myGetline(file,s,'\n'); f.push_back(line (lineNo,s)); lineNo++; }while(!file.eof()); return true; } bool CCmpMngr::sort(filemap &fm) { // Yet to beimplemented return false; } ////////////////////////////////////////////////////////////////////////////////////// // Hash each line into a numeric value ////////////////////////////////////////////////////////////////////////////////////// bool CCmpMngr::hash(filemap &f, hashed_filemap &hf) { hashed_line hl; std::string toBeHashed; for (int i=0 ; i <= (f.size()-1); i++) { hl.first = f[i].first; toBeHashed = f[i].second; toBeHashed = strReplace(toBeHashed," ","");// Ignaore Space hl.second = hash_string(toBeHashed); hf.push_back(hl); } return false; } ////////////////////////////////////////////////////////////////////////////////////// // Implementation of Hashing for a single line of text // simple hashing // hash_string(ABCW) = 65*1 + 66*2 + 67*3 + 87*4 // = 65 + 132 + 201 + 348 // = 746 // Please note.... // hash_string(ABCW) != hash_string(AWBC) // because.. // 65*1 + 66*2 + 67*3 + 87*4 != 65*1 + 87*2 + 66*3 + 67*4 ////////////////////////////////////////////////////////////////////////////////////// int CCmpMngr::hash_string(std::string &s) { int value,len; value = 0;len = s.length()-1; for (int i=0;i<=len;i++) { value = value + (s[i] * (i+1)); } return value; } ////////////////////////////////////////////////////////////////////////////////////// // Select the desired comparison algorithm. ////////////////////////////////////////////////////////////////////////////////////// bool CCmpMngr::compare_hashed_files(hashed_filemap &bHm,hashed_filemap& cHm,match& dHm,std::string theAlgorithm) { std::string alg(theAlgorithm); if (alg == "LCS") { return compare_hashed_files_LCS(bHm, cHm, dHm); } else return compare_hashed_files_default(bHm, cHm, dHm); } ////////////////////////////////////////////////////////////////////////////////////// // Following routine implements LCS algorithm to find difference between two files. // // LCS stands for Longest Common Sequence, It is a linear space algorithm for // // computing maximal common subsequences. // // more info on LCS (with practical demonstration) // // http://www.ics.uci.edu/~eppstein/161/960229.html // // Dan Hirschberg's Publications on LCS // // http://www.ics.uci.edu/~dan/topic.html#lcs // ////////////////////////////////////////////////////////////////////////////////////// bool CCmpMngr::compare_hashed_files_LCS(hashed_filemap &bHm,hashed_filemap& cHm,match& dHm) { int i,j,k,m,n; m = bHm.size(); n= cHm.size(); LCSBitMatrix.resizeTo(m+2,n+2); std::vector<int> ci,ci1; nRange = n * m; nProgress = 0; ci.resize(n+2,0);ci1.resize(n+2,0); for (i=0;i<=n;i++) {ci[i]=0;ci1[i]=0;} // Prepare LCS matrix for (i = m; i >= 0; i--) { for (k=0;k<=n;k++) {ci1[k]=ci[k];} for (k=0;k<=n;k++) {ci[k]=0;} for (j = n; j >= 0; j--) { //if (bHm[i].second == 0 || cHm[j].second == 0) // beyond end // LCSMatrix(i,j) = 0; //else { nProgress++; if (bHm[i].second == cHm[j].second) { //LCSMatrix(i,j) = 1 + LCSMatrix(i+1, j+1); ci[j] = 1 + ci1[j+1]; } else { //LCSMatrix(i,j) = max(LCSMatrix(i+1, j), LCSMatrix(i, j+1)); if (ci1[j] > ci[j+1]) { LCSBitMatrix.put(i,j,true); //LCSMatrix(i,j) = LCSMatrix(i+1, j); ci[j] = ci1[j]; } else { LCSBitMatrix.put(i,j,false); //LCSMatrix(i,j) = LCSMatrix(i, j+1); ci[j] = ci[j+1]; } } /* Same above done with huuuuge 2D array LCSMatrix. if (bHm[i].second == cHm[j].second) { LCSMatrix(i,j) = 1 + LCSMatrix(i+1, j+1); } else { //LCSMatrix(i,j) = max(LCSMatrix(i+1, j), LCSMatrix(i, j+1)); if (LCSMatrix(i+1, j) > LCSMatrix(i, j+1)) { LCSBitMatrix.put(i,j,true); LCSMatrix(i,j) = LCSMatrix(i+1, j); } else { LCSBitMatrix.put(i,j,false); LCSMatrix(i,j) = LCSMatrix(i, j+1); } } */ } } } dHm.empty(); i = 0;j = 0; // Following link walks through the bitmatrix we created by the loop above // and produces a LCS, A LCS here is a while (i < m && j < n) { if (bHm[i].second == cHm[j].second) { dHm.push_back(match_pair (i,j)); // A pair match added to LCS. i++; j++; } else { // In case we were using that Huuuuge 2D array, The condition would // will be like below // if (LCSMatrix(i+1,j) >= LCSMatrix(i,j+1)) if (LCSBitMatrix.get(i,j) == true) i++; else j++; } } //print_diff_in_HTML(std::string("")); return true; } ////////////////////////////////////////////////////////////////////////////////////// // This routine does a blind comparison of two files // ////////////////////////////////////////////////////////////////////////////////////// bool CCmpMngr::compare_hashed_files_default(hashed_filemap &bHm,hashed_filemap& cHm,match& dHm) { hashed_filemapIt i,j,start,last_match; int compValue; int ordi,ordj,start_ordj,last_match_orj,z; //hashed_line hl; //AfxMessageBox("Comparing",MB_OK,0); ofstream ofs("out.txt"); start =