FireEmissary

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  14 随笔 :: 0 文章 :: 20 评论 :: 0 Trackbacks
 

经典的求公共子序列算法需要两个序列的长度已知.而且通常用于计算字符串的公共子序列.

我实现的算法针对原有的算法输入需求解耦合,使得算法极度可适配.能用于字符串公共子序列计算和文件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_ContainerR_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_begin0, SectionCommon:: R_begin10, SectionCommon::count5.就表示左边序列从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());

}


完整代码包括测试代码下载

posted on 2010-03-27 19:31 FireEmissary 阅读(2812) 评论(1)  编辑 收藏 引用

评论

# re: 最长公共子序列的泛型算法 2010-03-28 10:22 expter
我觉得用c语言直接写DP还清晰明了点。。。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理