zhangJW_cn 阅读(1208) 评论(10)
好久没有写点内容了。
一是工作忙;另一个也是才疏学浅没什么独到见解可写;而且,我写blog往往都是想用于记录。

自己写的lzw算法的实现,vc8.0 和 g++ 3.2.3 编译通过(看看一堆的typedef typename就是为了g++)。
由于lzw是流式无损压缩算法,本想用于网络,实际测试下来压缩效果并不是很理想(可能和我所取的编码位数有关)。
现将代码贴于下面,有需要的朋友可以直接使用;如有性能、内存方面的优化实现,如果方便,希望能和我分享。
#ifndef __COMPRESS__
#define __COMPRESS__
//#pragma once
#include <cassert>
#include <vector>
#include <map>
#include <algorithm>

namespace coder
{

 template< unsigned bit >
 struct size_max
 {
  enum
  {
   VALUE = 2*size_max< bit-1 >::VALUE,
  };
 };
 template< >
 struct size_max< 1 >
 {
  enum
  {
   VALUE = 2,
  };
 };

 template< class source_t,class code_t,int bit = sizeof(code_t)*8 >
 struct encode_eq
 {
  ///最大静态编码
  static const code_t max_code = size_max< sizeof(source_t)*8 >::VALUE;
  const code_t operator()( const source_t &data ) const
  {
   return ( max_code - 1 ) & data;
  }
 };
 template< class source_t,class code_t,int bit = sizeof(code_t)*8 >
 struct decode_eq
 {
  ///最大静态编码
  static const code_t max_code = size_max< sizeof(source_t)*8 >::VALUE;
  const source_t operator()( const code_t &data ) const
  {
   assert( data < max_code );
   return static_cast< source_t >( data );
  }
 };

 ///源码、码字、源码位长、编码位长、静态编码器
 template< class source_t,
  class code_t,int bit = sizeof(code_t)*8,
  class encoder = encode_eq< source_t,code_t,bit > >
 struct compressor
 {
  ///源码流数据
  typedef std::vector< source_t >    datas_t;
  ///码字流数据
  typedef std::vector< code_t >    codes_t;
 private:
  ///动态码字
  struct codeEx_t
  {
   code_t prefix,suffix;
   bool operator < ( const codeEx_t &code ) const
   {
    if( prefix == code.prefix )
    {
     return suffix < code.suffix;
    }
    else
    {
     return prefix < code.prefix;
    }
   }
  };
  ///动态码表
  typedef std::map< const codeEx_t,code_t > codesEx_t;
  ///最多扩展编码数
  enum
  {
   num_codeEx = size_max< bit >::VALUE - encoder::max_code,
  };
 public:
  compressor( encoder en = encoder() ) : m_encode( en ) {}
  void operator()( const datas_t &in,codes_t &out )
  {
   assert( !in.empty() );
   codeEx_t code;
   code.prefix = m_encode( in.front() );
   typedef typename datas_t::const_iterator iter_t;
   for( iter_t i = in.begin() + 1; i != in.end(); ++i )
   {
    code.suffix = m_encode( *i );
    typedef typename codesEx_t::iterator iter2_t;
    iter2_t j = m_cat.find( code );
    if( j != m_cat.end() )
    {
     const code_t c = j->second;
     code.prefix = j->second;
    }
    else
    {
     if( m_cat.size() < num_codeEx )
     {
      const code_t c = m_cat.size() + encoder::max_code;
      typedef typename codesEx_t::value_type value_t;
      m_cat.insert( m_cat.end(),value_t(code,c) );
     }
     out.push_back( code.prefix );
     code.prefix = code.suffix;
    }
   }
   out.push_back( code.prefix );
  }
 private:
  ///基础编码器
  encoder m_encode;
  ///动态编码表
  codesEx_t m_cat;
 };

 ///源码、码字、每码位长、静态解码器
 template< class source_t,
  class code_t,int bit = sizeof(code_t)*8,
  class decoder = decode_eq< source_t,code_t,bit > >
 struct decompressor {
  ///源码流数据
  typedef std::vector< source_t >    datas_t;
  ///码字流数据
  typedef std::vector< code_t >    codes_t;
 private:
  ///动态码字
  struct codeEx_t
  {
   code_t prefix,suffix;
   bool operator < ( const codeEx_t &code ) const
   {
    if( prefix == code.prefix )
    {
     return suffix < code.suffix;
    }
    else
    {
     return prefix < code.prefix;
    }
   }
  };
  ///动态码表
  typedef std::map< const codeEx_t,code_t > codesEx_t;
  typedef std::map< code_t,const codeEx_t > decode_t;
  ///最多扩展编码数
  enum
  {
   num_codeEx = size_max< bit >::VALUE - decoder::max_code,
  };
 public:
  decompressor( decoder de = decoder() ) : m_decode( de ) {}
  void operator()( const codes_t &in,datas_t &out )
  {
   assert( !in.empty() );
   code_t code0 = in.front();
   out.push_back( m_decode(code0) );
   typedef typename codes_t::const_iterator iter_t;
   for( iter_t i = in.begin() + 1; i != in.end(); ++i )
   {
    code0 = decode( code0,*i,out );
   }
  }
 private:
  bool valid( code_t code ) const
  {
   if( code >= decoder::max_code )
   {
    typedef typename decode_t::const_iterator iter_t;
    iter_t i = m_dec.find( code );
    return i != m_dec.end();
   }
   else
   {
    return true;
   }
  }
  const code_t suffix( code_t code ) const
  {
   assert( valid(code) );
   if( code >= decoder::max_code )
   {
    const codeEx_t &c = m_dec.find( code )->second;
    assert(  c.suffix < decoder::max_code );
    return c.suffix;
   }
   else
   {
    return code;
   }
  }
  const code_t prefix( code_t code ) const
  {
   assert( valid(code) );
   while( code >= decoder::max_code )
   {
    const codeEx_t &c = m_dec.find( code )->second;
    code = c.prefix;
    assert( valid(code) );
   }
   return code;
  }
  const code_t encode( code_t prefix,code_t suffix )
  {
   const codeEx_t k1 = { prefix,suffix };
   typedef typename codesEx_t::iterator iter_t;
   iter_t i = m_cat.find( k1 );
   if( i != m_cat.end() )
   {
    return i->second;
   }
   else
   {
    if( m_cat.size() < num_codeEx )
    {
     const code_t k2 = m_cat.size() + decoder::max_code;
     typedef typename codesEx_t::value_type value1_t;
     m_cat.insert( m_cat.end(),value1_t(k1,k2) );
     typedef typename decode_t::value_type value2_t;
     m_dec.insert( m_dec.end(),value2_t(k2,k1) );
    }
    return suffix;
   }
  }
  const code_t decode( code_t previous,code_t code,datas_t &out )
  {
   assert( valid(previous) );
   if( code >= decoder::max_code )
   {
    typedef typename decode_t::iterator iter_t;
    const iter_t i = m_dec.find( code );
    if( i != m_dec.end() )
    {
     const codeEx_t &c = i->second;
     decode( previous,c.prefix,out );
     out.push_back( m_decode(c.suffix) );
    }
    else
    {
     assert( code == m_cat.size() + decoder::max_code );
     const code_t tmp = encode( previous,prefix(previous) );
     assert( tmp == prefix(previous) );
     decode( previous,code,out );
    }
   }
   else
   {
    encode( previous,code );
    out.push_back( m_decode(code) );
   }
   return code;
  }
  ///基础解码器
  decoder m_decode;
  ///解码动态表
  decode_t m_dec;
  ///动态编码表
  codesEx_t m_cat;
 };

};

#endif //__COMPRESS__

评论列表
晓寒
re: 自己的lzw实现
自己测试了没有?我最近在协助女朋友写一篇论文,其中要用到压缩技术,不知道这个怎么样?我想采用nsis使用的那个,因为那个是开元的。 :)
清风雨
re: 晓寒
自己跑过。
做解压时网上找资料都不是很明确,自己通过数据和压缩推测的解压。
说压缩效果不是很好,就是通过测试得来的。
不过,比较担心测试不是很全面。—— 自己的数据是全都通过了,毕竟解压是自己推测的,是否完备比较担心。——不知道怎么做这个覆盖测试。
清风雨
对了
有什么好的流失压缩算法,各位路过的朋友还请推荐一下,不过,希望压缩解压都要简易的、不能占CPU和内存。要找一个比较可观的用于网络传输时的压缩和解压。
Merjoum
ambien where to buy  sleep pill ambien . is ambien bad for you buy zolpidem tartrate  can you buy zolpidem online buy ambien 10mg online ambien free trial zolpidem dosage 10 mg . what is zolpidem prescribed for long term ambien effects generic for ambian <a href=>ambien zolpidem tartrate</a>. zolpidem tartrate used for ambien trip dosage herbal ambien ambien drug information .
FreaBox
ambien uses ambiencr ambien cr buy online <a href=>buy ambien on line</a>. ambien pill dosage ambien cr price ambiencr ambient sleep medication . buy ambien online no prescription  ambien safety . ambien trade name overnight ambien  ambien 12.5 zolpidem tartrate 10 mg price ambien addiction stories long term ambien use
KoipSiny
10mg ambien  buy astelin . ambien classification ambien sleeping pills  ambian sleep aid ambien overnight delivery zolpidem 5mg buy tenormin . ambien high dose ambien online reviews ambien mail order <a href=>zolpidem usage</a>. ambien 10mg cost zolpidem overnight delivery highest dose of ambien overdose ambien .
Sadnus
where can i buy ambien ambian pill ambien hallucinations <a href=>zolpidem benzodiazepine</a>. zolpidem tartrate brand name what ambien buy sleeping pills online australia ambien in canada over the counter . zolpidem withdrawal symptoms  ivedal 10mg tablets . medicine ambien zolpidem dosing  dangers of ambien buy pepcid cheap ambien online ambien anxiety
Hytcem
zolpidem tartrate 10 mg price  ingredients in ambien . ambien trip ambien prescribing information  buy ambien online fast shipping purchase ambien overnight delivery ambien cr generic cost ambien identification . get ambien online ambien identification zolpidem iv <a href=>ambien cr 12.5</a>. ambien dosage women where to buy zolpidem online dose of ambien canada ambien order .
XertJak
10mg zolpidem tartrate can you take more than one ambien ambien tolerance <a href=>can ambien cause seizures</a>. ambien ingredients buy depakote ambien experience affects of ambien . buy ambien online reviews  buy generic ambien online . addiction to ambien symptoms zolpidem ambien  generic ambien cost ambien ambien ambien dosage range ambien 12.5 mg
MukkAlomo
<a href=></a>. .  .  

发表评论
切换编辑模式