經典的求公共子序列算法需要兩個序列的長度已知.而且通常用于計算字符串的公共子序列.
我實現的算法針對原有的算法輸入需求解耦合,使得算法極度可適配.能用于字符串公共子序列計算和文件diff計算.理論上能用于任何具備相似特征的兩個序列的公共子序列計算.
LCS_Calculate有三個變種:
template<typename L_Iterator,typename R_Iterator,typename Container>
LCS_Size FEtool::LCS_Calculate(L_Iterator lbeg,L_Iterator lend, R_Iterator rbeg,R_Iterator rend,Container &out);
template<typename L_Iterator,typename R_Container,typename Container>
inline LCS_Size FEtool::LCS_Calculate(L_Iterator lbeg,L_Iterator lend, R_Container const&rcontainer, Container &out);
template<typename L_Container,typename R_Container,typename Container>
inline LCS_Size FEtool::LCS_Calculate(L_Container const& lcontainer, R_Container const&rcontainer, Container &out);
L_Iterator接受輸入迭代器. R_Iterator接受隨機迭代器. L_Container和R_Container分別調用它們的begin()和end()方法轉調用到LCS_Calculate的第一個版本.
L_*打頭的指代比較序列中左邊那個,R_*打頭的指代比較序列中右邊那個.
最后一個參數Container&out接收一個容器用來輸出序列各段相同的地方.典型的Container參數為std::deque<FEtool::SectionCommon> section;也可以為FEtool:: EmptyContainer.
class EmptyContainer
{
public:
void push_back(SectionCommon const&){};
LCS_Size size(){return 0;}
void clear(){}
};
如果為FEtool:: EmptyContainer參數則通過模板特化代碼選擇不計算兩段序列的相同部分。
struct LCS_Compare_Trait
{
template<typename L,typename R>
static bool equal(L const& left, R const& right)
{
return left==right;
}
};
定義了比較算法,默認用operator==.你可以在FEtool空間通過特化或偏特化LCS_Compare_Trait:: equal來定制它.
struct SectionCommon
{
LCS_Size L_begin;
LCS_Size R_begin;
LCS_Size count;
void clear(){L_begin=0;R_begin=0;count=0;}
};
指示兩個序列的相同部分. 比如SectionCommon:: L_begin為0, SectionCommon:: R_begin為10, SectionCommon::count為5.就表示左邊序列從0開始的5個數據，和右邊序列從10開始的5個數據都相同.
LCS_Calculate內部根據傳入參數優化實現.經過對經典的動態規劃解公共子序列算法的考察發現,外圍那個循環只需要遍歷它代表的序列一次；即左邊序列則滿足輸入迭代器即可.它要求右邊序列始終是傳入隨機迭代器.內部計算用到的數組使用了滾動數組(LCSArray)實現,空間占用為右邊序列長度*2.
LCS_Calculate的最后一個參數不為EmptyContainer則會計算公共子序列在左右序列中各段的順序和長度.這里L_Iterator是不是隨機訪問迭代器就會影響到性能了.L_Iterator不是隨機迭代器內部就會用到一個動態增長的輔助數組(TrackArrayDynamic)來做回溯; L_Iterator是隨機迭代器則直接一次申請(左序列*右序列)這么大的空間(TrackArrayStatic)來輔助回溯計算.
而如果LCS_Calculate的最后一個參數為EmptyContainer則會選擇一個空數組(TrackArrayEmpty)實現.TrackArrayEmpty類把所有操作展開為空操作.
所有這些,基于模板來自動選擇.用戶不需要指定不同的函數來優化性能:
template<typename L_Iterator,typename R_Iterator,typename Container/**//*vector<LCS_Section>*/>
LCS_Size LCS_Calculate(L_Iterator lbeg,L_Iterator lend,
R_Iterator rbeg,R_Iterator rend,
Container &out)
{
out.clear();
detail::LCSArray array(rend-rbeg);
typedef detail::SelectTrackArray<Container,typename std::iterator_traits<L_Iterator>::iterator_category> SelectTrack;//選擇適當的回溯數組
typename SelectTrack::Array trackArr(SelectTrack::TotalRows(lbeg,lend),array.columns());//選擇適當的回溯數組
LCS_Size leftSize;
LCS_Size rightSize;
for( leftSize=1;lbeg!=lend;++lbeg,++leftSize)//外層只需要是輸入迭代器就可
for( rightSize=1;rightSize<=array.columns();++rightSize)
{
if(LCS_Compare_Trait::equal(*lbeg,*(rbeg+rightSize-1))){
array(leftSize,rightSize)=array(leftSize-1,rightSize-1)+1;
trackArr(leftSize,rightSize)=0;
}
else if(array(leftSize-1,rightSize)>=array(leftSize,rightSize-1)){
array(leftSize,rightSize)=array(leftSize-1,rightSize);
trackArr(leftSize,rightSize)=1;
}
else{
array(leftSize,rightSize)=array(leftSize,rightSize-1);
trackArr(leftSize,rightSize)=-1;
}
}
detail::LCS_KeepTrack(trackArr,out);
return array(leftSize-1,array.columns());
}
完整代碼包括測試代碼下載