<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>notes.md - +/squeeze @ master</title>
<meta name="description" content="notes.md in +/squeeze at master.">
<meta property="og:title" content="notes.md - +/squeeze @ master">
<meta property="og:description" content="notes.md in +/squeeze at master.">
<meta property="og:type" content="website">
<meta property="og:site_name" content="git.julia.blue">
<link rel="stylesheet" href="/css/style.css?v=62">
<script type="module" src="/js/main.js?v=62"></script>
</head>
<body>
<main data-ref="master" data-tip="b9619c27a6ff8a1e2ba969c2632fbfa250c99201">
<noscript>
  <div class="callout">
    <p>
      hey! this is a static git repo viewer. commit diffs, file history,
      older commits and other revisions won't load without javascript.
    </p>
    <p>
      you are still able to view source files on branch/tag tips,
      but the experience is degraded.
    </p>
  </div>
</noscript>
<header class="repo"><div>
<h1>+/squeeze</h1>
</div>
<pre class="clone">git clone https://git.julia.blue/+/squeeze</pre>
</header>
<p class="snapshot-commit"><span class="commit-author">Joseph Ryan</span><span class="commit-message" data-commit="b9619c27a6ff8a1e2ba969c2632fbfa250c99201">Give up for now</span><span class="snapshot-sha sha" data-commit="b9619c27a6ff8a1e2ba969c2632fbfa250c99201">b9619c2</span><time datetime="2019-01-04T13:44:20-06:00" title="2019-01-04 13:44:20 -0600">2019-01-04</time></p>
<header class="topbar"><details class="switcher"><summary>master</summary><div class="menu"><strong>branches</strong><a class="current" href="/%2B/squeeze/ref/master/">master</a><a class="all" href="/%2B/squeeze/refs">all refs →</a></div></details><nav class="crumbs"><a href="/%2B/squeeze/">squeeze</a> / <span class="cur">notes.md</span></nav>
<span class="view-stats"><span>1.7 KiB</span><span>29 lines</span></span><span class="actions"><a class="raw" href="/%2B/squeeze/raw/855d87799c4e3ba8303f9a6ac13a644e12b421f4/notes.md">raw</a></span></header>
<div class="markdown-view"><input type="radio" name="markdown-view" id="markdown-rendered" checked><label for="markdown-rendered">rendered</label><input type="radio" name="markdown-view" id="markdown-code"><label for="markdown-code">code</label><section class="readme rendered"><h1>Huffman coding</h1>
<p>The first byte in a encoded stream indicates the number of key value pairs that follow in the translation table. Each pair starts with the key byte, has a second byte indicating the length of the code in bytes, and then the bytes that make up a code.</p>
<p>In the table, if paths were stored as raw bytes, there would be no way to distinguish between 0001 and 01 due to the leading zeros. To fix this ambiguity, all codes are prepended with a 1 in the table. For those examples they would look like 00010001 and 00000101 respectively.</p>
<p>After the table, there is one more byte which contains the number of padding bits at the end of the data region. The rest of the byte stream can be interpreted as data.</p>
<h3>Table representation possibilities:</h3>
<ul>
<li>Set (4 byte?) code lengths (requires preceding 1 to determine starting point) vs prefix byte giving length of code in bits</li>
<li>Sparse representation requiring each code to be prefixed with its corresponding byte vs all bytes being given in order</li>
</ul>
<p><a href="https://www2.cs.duke.edu/csed/poop/huff/info/">Huffman trees</a>
<a href="https://github.com/rrbutani/mandelbrot/blob/master/.travis.yml">Docsite setup</a></p>
<h1>Run length encoding</h1>
<p>There is no header, the stream consists of a number of symbol-count pairs. The symbol is the byte repeated, and the variable length field that follows is the number of times to repeat it. For each byte, if the value is not 0, take its value and end the field. Otherwise add 256 to the remainder of the field.</p>
<h1>LZ78 compression</h1>
<h1>Burrows Wheeler</h1>
<h1>General</h1>
<ul>
<li>try rayon to speed stuff up</li>
<li>test benchmarks (ratios on audio/img/vid/english/binary/etc. fancy graphs?)</li>
<li>test benchmarks (speed)</li>
<li>test recompression dropoff curve and various combinations of methods</li>
<li>try chunking for huffman code improvement</li>
</ul>
</section><div class="code-panel"><pre class="code src language-markdown"><span class="code-line"><a class="ln" id="L1" href="#L1">1</a><span class="code-text"><a-p>#</a-p> <a-tt>Huffman coding</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L2" href="#L2">2</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L3" href="#L3">3</a><span class="code-text">The first byte in a encoded stream indicates the number of key value pairs that follow in the translation table. Each pair starts with the key byte, has a second byte indicating the length of the code in bytes, and then the bytes that make up a code.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L4" href="#L4">4</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L5" href="#L5">5</a><span class="code-text">In the table, if paths were stored as raw bytes, there would be no way to distinguish between 0001 and 01 due to the leading zeros. To fix this ambiguity, all codes are prepended with a 1 in the table. For those examples they would look like 00010001 and 00000101 respectively.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L6" href="#L6">6</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L7" href="#L7">7</a><span class="code-text">After the table, there is one more byte which contains the number of padding bits at the end of the data region. The rest of the byte stream can be interpreted as data.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L8" href="#L8">8</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L9" href="#L9">9</a><span class="code-text"><a-p>###</a-p> <a-tt>Table representation possibilities:</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L10" href="#L10">10</a><span class="code-text"><a-p>- </a-p>Set (4 byte?) code lengths (requires preceding 1 to determine starting point) vs prefix byte giving length of code in bits</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L11" href="#L11">11</a><span class="code-text"><a-p>- </a-p>Sparse representation requiring each code to be prefixed with its corresponding byte vs all bytes being given in order</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L12" href="#L12">12</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L13" href="#L13">13</a><span class="code-text"><a-p>[Huffman trees](https://www2.cs.duke.edu/csed/poop/huff/info/)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L14" href="#L14">14</a><span class="code-text"><a-p>[Docsite setup](https://github.com/rrbutani/mandelbrot/blob/master/.travis.yml)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L15" href="#L15">15</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L16" href="#L16">16</a><span class="code-text"><a-p># </a-p><a-tt>Run length encoding</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L17" href="#L17">17</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L18" href="#L18">18</a><span class="code-text"><a-p>There is no header, the stream consists of a number of symbol-count pairs. The symbol is the byte repeated, and the variable length field that follows is the number of times to repeat it. For each byte, if the value is not 0, take its value and end the field. Otherwise add 256 to the remainder of the field.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L19" href="#L19">19</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L20" href="#L20">20</a><span class="code-text"><a-p># </a-p><a-tt>LZ78 compression</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L21" href="#L21">21</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L22" href="#L22">22</a><span class="code-text"><a-p># </a-p><a-tt>Burrows Wheeler</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L23" href="#L23">23</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L24" href="#L24">24</a><span class="code-text"><a-p># </a-p><a-tt>General</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L25" href="#L25">25</a><span class="code-text"><a-p>- try rayon to speed stuff up</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L26" href="#L26">26</a><span class="code-text"><a-p>- test benchmarks (ratios on audio/img/vid/english/binary/etc. fancy graphs?)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L27" href="#L27">27</a><span class="code-text"><a-p>- test benchmarks (speed)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L28" href="#L28">28</a><span class="code-text"><a-p>- test recompression dropoff curve and various combinations of methods</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L29" href="#L29">29</a><span class="code-text"><a-p>- </a-p>try chunking for huffman code improvement</span></span></pre></div></div>
</main>
</body>
</html>
