Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/strings/lcs/lcs_hirschberg.h
Go to the documentation of this file.
00001 #ifndef H_LCS_LCS_HIRSCHBERG
00002 #define H_LCS_LCS_HIRSCHBERG
00003 
00012 #include <vector>
00013 #include "utils/preconditions/preconditions.h"
00014 #include "strings/utils/sequence_helper.h"
00015 
00016 namespace strings {
00017 namespace lcs {
00018 
00023 template <typename T>
00024 class LCSHirschberg {
00025  private:
00026   static void saveBest(utils::SequenceHelper<const T> seq1,
00027       utils::SequenceHelper<const T> seq2,
00028       std::vector<int>* out)
00029   {
00030     std::vector<int> current(seq2.size() + 1, 0);
00031     std::vector<int> next(seq2.size() + 1);
00032 
00033     for (int i = 0; i < seq1.size(); i++) {
00034       // we are going to process best results for
00035       // LCS(seq1, seq2[0,j) into next[j] )
00036       for (int j = 0; j < seq2.size(); j++) {
00037         next[0] = 0;
00038         if (seq1[i] == seq2[j]) { // match
00039           next[j + 1] = current[j] + 1;
00040         } else { // take the best of previous values
00041           next[j + 1] = std::max(current[j + 1], next[j]);
00042         }
00043       }
00044       current.swap(next); // advance by 1 line
00045     }
00046 
00047     out->swap(current);
00048   };
00049   
00050   static void recurse(utils::SequenceHelper<const T> seq1,
00051       utils::SequenceHelper<const T> seq2,
00052       std::vector<T>* out)
00053   {
00054     assert(seq2.size() != 0);
00055 
00056     if (seq1.size() == 1) {
00057       // if there is match in character, output it
00058       for (int j = 0; j < seq2.size(); j++) {
00059         if (seq1[0] == seq2[j]) {
00060           out->push_back(seq1[0]);
00061           break;
00062         }
00063       }
00064       return;
00065     };
00066 
00067     // and now the hard work
00068     int middle = seq1.size() / 2;
00069     vector<int> best1;
00070     vector<int> best2;
00071     saveBest(seq1.subsequence(0, middle), seq2, &best1);
00072     saveBest(seq1.subsequence(middle, seq1.size()).reversed(),
00073              seq2.reversed(), &best2);
00074 
00075     // Find j such that L(i,j) + L*(i,j) = L(m,n)
00076     int j = -1;
00077     int best = -1;
00078     for (int i = 0; i <= seq2.size(); i++) {
00079       int t = best1[i] + best2[seq2.size() - i];
00080       if (t > best) {
00081         best = t;
00082         j = i;
00083       }
00084     }
00085 
00086     if (j > 0) {
00087       recurse(seq1.subsequence(0, middle),
00088               seq2.subsequence(0, j),
00089               out);
00090     }
00091     if (j < seq2.size()) {
00092       recurse(seq1.subsequence(middle, seq1.size()),
00093               seq2.subsequence(j, seq2.size()),
00094               out);
00095     }
00096   }
00097 
00098  public:
00099   static int subsequence(const T* seq1, int len1, const T* seq2, int len2,
00100       std::vector<T>* out) {
00101     Preconditions::check(len1 >= 0);
00102     Preconditions::check(len2 >= 0);
00103     out->clear();
00104     if (len1 == 0 || len2 == 0) {
00105       return 0;
00106     }
00107     
00108     recurse(utils::SequenceHelper<const T>(seq1, len1),
00109             utils::SequenceHelper<const T>(seq2, len2), out);
00110     return out->size();
00111   }
00112 
00113 
00114 };
00115 
00116 } // namespace lcs
00117 } // namespace strings
00118 
00119 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines