Range Coding 是算术编码的变种,二者的效率几乎没有差别,Range Coding 速度更快,且没有专利问题。下面的程序移植和改进自一个非常清晰简洁的C++实现。当然,直接使用下面的代码去压缩文件效果并不好,速度慢压缩率也低,Range Coding 更适合作为其他算法的后端,比如 LZ77、Block Sorting。
如果你看到这里一头雾水的话,可以上 wikipedia 参考“算术编码”,不过更好的选择是找一篇名为《笨笨数据压缩教程》的系列文章来入门。
D1.0 Code
-
-
-
-
-
-
-
-
-
-
-
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;
-
}
-
-
}
-
}
-
-
-
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()
-
{
-
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];
-
}
-
}
-
-
-
-
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;
-
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;
-
}
分享到:
相关推荐
ErrorResilientVideo Coding Using Unequally ProtectedKeyPictures
High Efficiency Video Coding (HEVC) Range Extensions 官方文档
In this paper, we introduce two innovative concepts which have not been present in cellular systems for IMT-Advanced so far: Device-to-device (D2D) communication and network coding. Both of them are ...
Contrastive Multiview Coding笔记
c coding standard
Phase coding
该PDF用图的方法描述了如何配置Toad Team Coding来实现数据库对象的版本控制
opencores_coding_guidelines.pdf. RTL_coding_hints.pdf simul-mismatch.pdf Talk about BiT length .pdf
The potential applications range from wireless sensor networks, ad-hoc networks, and surveillance networks, to robust low-complexity video coding, stereo/Multiview video coding, HDTV, hyper-spectral ...
Beginners and experienced programmers can use Python to build and play computer games, from mind-bending brainteasers to crazy action games with explosive sound effects and 3-D graphics. Each chapter ...
C# Coding Style Guide
这好像是网络编码最权威的书了,国内还没有出版,想要的加油了!绝对好书!
Coding Theory
in the general area of network coding and its applications in various areas of communication networks. We assume that the readers of this book have only a general background in networking, with no ...
coding coding (encrypted) coding coding (encrypted) coding coding (encrypted) coding coding (encrypted) coding coding (encrypted) coding coding (encrypted)
75 recommendations for secure Java coding
Comparison of the Coding Efficiency of Video Coding Standard