Range Coding 的 D 实现

Range Coding 是算术编码的变种，二者的效率几乎没有差别，Range Coding 速度更快，且没有专利问题。下面的程序移植和改进自一个非常清晰简洁的C++实现。当然，直接使用下面的代码去压缩文件效果并不好，速度慢压缩率也低，Range Coding 更适合作为其他算法的后端，比如 LZ77、Block Sorting。

如果你看到这里一头雾水的话，可以上 wikipedia 参考“算术编码”，不过更好的选择是找一篇名为《笨笨数据压缩教程》的系列文章来入门。

D1.0 Code

/** Code for range coding, derived from public domain work by Dmitry Subbotin
    Modified to use 64-bit integer maths, for increased precision

Authors:    Dmitry Subbotin (initial author of the Carry-less Range Coder)
            Sachin Garg (C++)
            Wei Li (D language)

Reference:  http://sachingarg.com/compression/entropy_coding/64bit/
*/

import std.stdio;

template
 RangeCoding64Base()
{
    const
 ulong Top = 1UL << 56UL;
    const
 ulong Bottom = 1UL << 48UL;
    const
 ulong MaxRange = Bottom;
    ulong m_low = 0;
    ulong m_range = ulong.max;
}

struct
 RangeEncoding64
{
    mixin RangeCoding64Base;

    private
 
bool
 m_flushed = 
false
;
    private
 
void
 delegate(ubyte) m_sink = null;

    void
 init(
void
 delegate(ubyte) sink)
    {
        assert(sink !is null);
        m_sink = sink;
    }

    void
 close()
    {
        if
(!m_flushed)
            flush();
    }

    void
 encode(ulong symbolLow, ulong symbolHigh, ulong totalRange)
    {
        m_range /= totalRange;
        m_low += symbolLow * m_range;
        m_range *= symbolHigh - symbolLow;

        while
 ((m_low ^ (m_low + m_range)) < Top || m_range < Bottom && ((m_range = -m_low & (Bottom - 1)), 
true
))
        {
            ubyte b = m_low >> (m_low.sizeof
 * 8 - 8);
            m_sink(b);
            m_range <<= 8;
            m_low <<= 8;
        }
    }

    void
 flush()
    {
        if
(!m_flushed)
        {
            for
(
int
 i = 0; i < m_low.
sizeof
; i++)
            {
                ubyte b = m_low >> (m_low.sizeof
 * 8 - 8);
                m_sink(b);
                m_low <<= 8;
            }
            m_flushed = true
;
        }
    }
}

struct
 RangeDecoding64
{
    mixin RangeCoding64Base;

    private
 ulong m_code;
    private
 ubyte delegate() m_emitter;

    void
 init(ubyte delegate() emitter)
    {
        assert(emitter !is null);
        m_emitter = emitter;
        for
(
size_t
 i = 0; i < m_code.
sizeof
; i++)
        {
            m_code = (m_code << 8) | emitter();
        }
    }

    ulong currentCount(ulong totalRange) //积累频率
    {
        return
 (m_code - m_low) / (m_range /= totalRange);
    }

    void
 decode(ulong symbolLow, ulong symbolHigh, ulong totalRange)
    {
        m_low += symbolLow * m_range;
        m_range *= symbolHigh - symbolLow;

        while
 ((m_low ^ m_low + m_range) < Top || m_range < Bottom && ((m_range = -m_low & Bottom - 1), 
true
))
        {
            m_code= m_code << 8 | m_emitter(), m_range <<= 8, m_low <<= 8;
        }

    }
}

//简单的0阶自适应模型
struct
 OrderZeroModel(uint SymMax = 255)
{
    public
 
const
 uint SymbolMax = SymMax;
    public
 
const
 uint NoOfSymbols = SymbolMax + 2;

    //最后一个元素是积累频率
    private
 ulong[SymbolMax + 2] m_freq;

    void
 init()
    {
        for
(
size_t
 i = 0; i < m_freq.length; i++)
        {
            m_freq[i] = i;
        }
    }

    private
 
void
 rescale()
    {   //用了64位以后似乎这是不可能的
        ulong newTotal = 0;
        for
(
size_t
 i = 1; i < m_freq.length - 1; i++)
        {
            newTotal += ((m_freq[i] - m_freq[i - 1]) / 2) + 1;

            m_freq[i] = m_freq[i - 1] + ((m_freq[i] - m_freq[i - 1]) / 2) + 1;
        }
        m_freq[m_freq.length - 1] = newTotal;
    }

    void
 update(uint sym)
    {
        for
(
size_t
 i = sym + 1; i < m_freq.length; i++) {
            m_freq[i]++;
        }

        if
(total() >= RangeCoding64Base!().MaxRange)
            rescale();
    }

    uint getSymbol(ulong n)
    {
        uint sym = SymbolMax;
        while
(m_freq[sym] > n) --sym;

        return
 sym;
    }

    uint total()
    {
        return
 m_freq[m_freq.length - 1];
    }

    ulong low(uint sym)
    {
        return
 m_freq[sym];
    }

    ulong high(uint sym)
    {
        return
 m_freq[sym + 1];
    }

    ulong opIndex(uint rhs)
    {
        return
 m_freq[rhs];
    }
}

// sample:

int
 main(string[] args)
{
    const
 uint EndOfStream = 256;

    ubyte[] compressed;
    void
 sink(ubyte u)
    {
        compressed ~= u;
    }

    ubyte[] origin;
    for
(
int
 i = 0; i < 10000; i++)
        origin ~= ['A', 'B', 'C', 'D', 'E', 'F', 'G'];

    RangeEncoding64 encoder;
    encoder.init(&sink);
    OrderZeroModel!(EndOfStream) model; //我们把 256 作为 Range Coding 流结束符
    model.init();

    writefln("compression started..."
);
    foreach(ubyte b; origin)
    {
        encoder.encode(model.low(b), model.high(b), model.total);
        model.update(b);
    }
    encoder.encode(model.low(EndOfStream), model.high(EndOfStream), model.total);
    model.update(EndOfStream);
    encoder.close();

    writefln("originial size: %d"
, origin.length);
    writefln("compressed size: %d (%d%%)"
, compressed.length,
            (origin.length - compressed.length) * 100 / origin.length);

    writefln("decoding...."
);

    size_t
 pos = 0;

    ubyte delegate() emitter = {
        return
 compressed[pos++];
    };

    model.init();
    RangeDecoding64 dec;
    dec.init(emitter);

    ubyte[] decompressed;

    while
(
true
)
    {
        ulong count = dec.currentCount(model.total);
        uint sym = model.getSymbol(count);
        if
(sym == 256)
break
;
        decompressed ~= sym;
        dec.decode(model.low(sym), model.high(sym), model.total);
        model.update(sym);
    }

    writefln(decompressed.length);
    //确保解码无误
    assert(decompressed[] == origin[]);

    return
 0;
}

评论

8 楼 oldrev 2008-04-17  

引用

oldrev 2008-01-12
LZMA SDK 只是一个 LZMA 算法的实现，并不包括压缩包的处理，也不支持其他算法

此说法要修正了，新版 LZMA SDK 包含了 7z 压缩包处理

7 楼 oldrev 2008-01-12  

LZMA SDK 只是一个 LZMA 算法的实现，并不包括压缩包的处理，也不支持其他算法

6 楼 liuwangxia 2008-01-11  

另外 LZMA SDK 提供4种许可协议：

引用

LZMA SDK is available under any of the following licenses:

   1. GNU Lesser General Public License (GNU LGPL)
   2. Common Public License (CPL)
   3. Simplified license for unmodified code (read SPECIAL EXCEPTION)
   4. Proprietary license

5 楼 liuwangxia 2008-01-11  

LZMA SDK 目前支持 C, C++, C#, Java, 在 Linux 下有支持。

sudo apt-get install p7zip-full

http://7-zip.org/sdk.html

4 楼 oldrev 2007-08-21  

lzma sdk是lgpl，跟 tango 的 bsd 不兼容。

lzma 的实现就是 lz77 + range coding

7-zip 确实很出色，所有的算法和压缩包格式支持都是自己实现的，比什么 ark, file-roller 通过调用命令行程序之流牛得多。缺点是它的那个小类库完全是为 windows 设计的，造成整个软件没可移植性

3 楼 shawind 2007-08-21  

好像lzma是gpl吧？

2 楼 oldrev 2007-08-20  

引用

嗯，不错，建议提交到tango,tango目前在搞VFS,封装好一个文件级的压缩，就很接近了

这个直接压缩文件很慢，而且压缩率不高，tango如果需要实用的压缩的话可以考虑移植 7-zip 的lzma算法

1 楼 DavidL 2007-08-20  

嗯，不错，建议提交到tango,tango目前在搞VFS,封装好一个文件级的压缩，就很接近了