好久没有写点内容了。
一是工作忙；另一个也是才疏学浅没什么独到见解可写；而且，我写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__