2007-08-20

Range Coding 的 D 实现

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

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

D1.0 Code
  1. /** Code for range coding, derived from public domain work by Dmitry Subbotin
  2. Modified to use 64-bit integer maths, for increased precision
  4. Authors: Dmitry Subbotin (initial author of the Carry-less Range Coder)
  5. Sachin Garg (C++)
  6. Wei Li (D language)
  8. Reference: http://sachingarg.com/compression/entropy_coding/64bit/
  9. */
  11. import std.stdio;
  13. template RangeCoding64Base()
  14. {
  15. const ulong Top = 1UL << 56UL;
  16. const ulong Bottom = 1UL << 48UL;
  17. const ulong MaxRange = Bottom;
  18. ulong m_low = 0;
  19. ulong m_range = ulong.max;
  20. }
  22. struct RangeEncoding64
  23. {
  24. mixin RangeCoding64Base;
  26. private bool m_flushed = false;
  27. private void delegate(ubyte) m_sink = null;
  29. void init(void delegate(ubyte) sink)
  30. {
  31. assert(sink !is null);
  32. m_sink = sink;
  33. }
  35. void close()
  36. {
  37. if(!m_flushed)
  38. flush();
  39. }
  41. void encode(ulong symbolLow, ulong symbolHigh, ulong totalRange)
  42. {
  43. m_range /= totalRange;
  44. m_low += symbolLow * m_range;
  45. m_range *= symbolHigh - symbolLow;
  47. while ((m_low ^ (m_low + m_range)) < Top || m_range < Bottom && ((m_range = -m_low & (Bottom - 1)), true))
  48. {
  49. ubyte b = m_low >> (m_low.sizeof * 8 - 8);
  50. m_sink(b);
  51. m_range <<= 8;
  52. m_low <<= 8;
  53. }
  54. }
  56. void flush()
  57. {
  58. if(!m_flushed)
  59. {
  60. for(int i = 0; i < m_low.sizeof; i++)
  61. {
  62. ubyte b = m_low >> (m_low.sizeof * 8 - 8);
  63. m_sink(b);
  64. m_low <<= 8;
  65. }
  66. m_flushed = true;
  67. }
  68. }
  69. }
  71. struct RangeDecoding64
  72. {
  73. mixin RangeCoding64Base;
  75. private ulong m_code;
  76. private ubyte delegate() m_emitter;
  78. void init(ubyte delegate() emitter)
  79. {
  80. assert(emitter !is null);
  81. m_emitter = emitter;
  82. for(size_t i = 0; i < m_code.sizeof; i++)
  83. {
  84. m_code = (m_code << 8) | emitter();
  85. }
  86. }
  88. ulong currentCount(ulong totalRange) //积累频率
  89. {
  90. return (m_code - m_low) / (m_range /= totalRange);
  91. }
  93. void decode(ulong symbolLow, ulong symbolHigh, ulong totalRange)
  94. {
  95. m_low += symbolLow * m_range;
  96. m_range *= symbolHigh - symbolLow;
  98. while ((m_low ^ m_low + m_range) < Top || m_range < Bottom && ((m_range = -m_low & Bottom - 1), true))
  99. {
  100. m_code= m_code << 8 | m_emitter(), m_range <<= 8, m_low <<= 8;
  101. }
  103. }
  104. }
  106. //简单的0阶自适应模型
  107. struct OrderZeroModel(uint SymMax = 255)
  108. {
  109. public const uint SymbolMax = SymMax;
  110. public const uint NoOfSymbols = SymbolMax + 2;
  112. //最后一个元素是积累频率
  113. private ulong[SymbolMax + 2] m_freq;
  115. void init()
  116. {
  117. for(size_t i = 0; i < m_freq.length; i++)
  118. {
  119. m_freq[i] = i;
  120. }
  121. }
  123. private void rescale()
  124. { //用了64位以后似乎这是不可能的
  125. ulong newTotal = 0;
  126. for(size_t i = 1; i < m_freq.length - 1; i++)
  127. {
  128. newTotal += ((m_freq[i] - m_freq[i - 1]) / 2) + 1;
  130. m_freq[i] = m_freq[i - 1] + ((m_freq[i] - m_freq[i - 1]) / 2) + 1;
  131. }
  132. m_freq[m_freq.length - 1] = newTotal;
  133. }
  135. void update(uint sym)
  136. {
  137. for(size_t i = sym + 1; i < m_freq.length; i++) {
  138. m_freq[i]++;
  139. }
  141. if(total() >= RangeCoding64Base!().MaxRange)
  142. rescale();
  143. }
  145. uint getSymbol(ulong n)
  146. {
  147. uint sym = SymbolMax;
  148. while(m_freq[sym] > n) --sym;
  150. return sym;
  151. }
  153. uint total()
  154. {
  155. return m_freq[m_freq.length - 1];
  156. }
  158. ulong low(uint sym)
  159. {
  160. return m_freq[sym];
  161. }
  163. ulong high(uint sym)
  164. {
  165. return m_freq[sym + 1];
  166. }
  168. ulong opIndex(uint rhs)
  169. {
  170. return m_freq[rhs];
  171. }
  172. }
  174. // sample:
  176. int main(string[] args)
  177. {
  178. const uint EndOfStream = 256;
  180. ubyte[] compressed;
  181. void sink(ubyte u)
  182. {
  183. compressed ~= u;
  184. }
  186. ubyte[] origin;
  187. for(int i = 0; i < 10000; i++)
  188. origin ~= ['A', 'B', 'C', 'D', 'E', 'F', 'G'];
  190. RangeEncoding64 encoder;
  191. encoder.init(&sink);
  192. OrderZeroModel!(EndOfStream) model; //我们把 256 作为 Range Coding 流结束符
  193. model.init();
  195. writefln("compression started...");
  196. foreach(ubyte b; origin)
  197. {
  198. encoder.encode(model.low(b), model.high(b), model.total);
  199. model.update(b);
  200. }
  201. encoder.encode(model.low(EndOfStream), model.high(EndOfStream), model.total);
  202. model.update(EndOfStream);
  203. encoder.close();
  205. writefln("originial size: %d", origin.length);
  206. writefln("compressed size: %d (%d%%)", compressed.length,
  207. (origin.length - compressed.length) * 100 / origin.length);
  209. writefln("decoding....");
  211. size_t pos = 0;
  213. ubyte delegate() emitter = {
  214. return compressed[pos++];
  215. };
  217. model.init();
  218. RangeDecoding64 dec;
  219. dec.init(emitter);
  221. ubyte[] decompressed;
  223. while(true)
  224. {
  225. ulong count = dec.currentCount(model.total);
  226. uint sym = model.getSymbol(count);
  227. if(sym == 256)break;
  228. decompressed ~= sym;
  229. dec.decode(model.low(sym), model.high(sym), model.total);
  230. model.update(sym);
  231. }
  233. writefln(decompressed.length);
  234. //确保解码无误
  235. assert(decompressed[] == origin[]);
  237. return 0;
  238. }
评论
oldrev 2008-04-17
引用

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


此说法要修正了，新版 LZMA SDK 包含了 7z 压缩包处理
oldrev 2008-01-12
LZMA SDK 只是一个 LZMA 算法的实现，并不包括压缩包的处理，也不支持其他算法
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
liuwangxia 2008-01-11
LZMA SDK 目前支持 C, C++, C#, Java, 在 Linux 下有支持。 

sudo apt-get install p7zip-full


http://7-zip.org/sdk.html
oldrev 2007-08-21
lzma sdk是lgpl，跟 tango 的 bsd 不兼容。

lzma 的实现就是 lz77 + range coding

7-zip 确实很出色，所有的算法和压缩包格式支持都是自己实现的，比什么 ark, file-roller 通过调用命令行程序之流牛得多。缺点是它的那个小类库完全是为 windows 设计的，造成整个软件没可移植性
shawind 2007-08-21
好像lzma是gpl吧？
oldrev 2007-08-20
引用
嗯，不错，建议提交到tango,tango目前在搞VFS,封装好一个文件级的压缩，就很接近了


这个直接压缩文件很慢，而且压缩率不高，tango如果需要实用的压缩的话可以考虑移植 7-zip 的lzma算法
DavidL 2007-08-20
嗯，不错，建议提交到tango,tango目前在搞VFS,封装好一个文件级的压缩，就很接近了
发表评论

您还没有登录，请登录后发表评论

oldrev
搜索本博客
我的相册
7e9318d5-c74f-36e0-81a3-beb68acaa2b8-thumb
Screenshot
共 1 张
最近加入圈子
存档
最新评论