经典的求公共子序列算法需要两个序列的长度已知.而且通常用于计算字符串的公共子序列.
我实现的算法针对原有的算法输入需求解耦合,使得算法极度可适配.能用于字符串公共子序列计算和文件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());
}
完整代码包括测试代码下载