Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
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