Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>These "start-step-stop" codes looks like a different way of calling <a href="http://en.wikipedia.org/wiki/Huffman_coding" rel="nofollow noreferrer">Huffman codes</a>. See the <a href="http://en.wikipedia.org/wiki/Huffman_coding#Basic_technique" rel="nofollow noreferrer">basic technique</a> for an outline of the pseudo-code for calculating them.</p> <p>Essentially this is what the algorithm does:</p> <p>Before you start the Huffman encoding you need to gather the statistics of each symbol you'll be compressing (Their total frequency in the file to compress).</p> <p>After you have that you create a <a href="http://en.wikipedia.org/wiki/Binary_tree" rel="nofollow noreferrer">binary tree</a> using that info such that the most frequently used symbols are at the top of the tree (and thus use less bits) and such that no encoding has a <a href="http://en.wikipedia.org/wiki/Prefix_code" rel="nofollow noreferrer">prefix code</a>. Since if an encoding has a common prefix there could be ambiguities decompressing.</p> <p>At the end of the Huffman encoding your start value will be depth of the shallowest leaf node, your step will always be 1 (logically this makes sense, why would you force more bits than you need, just add one at a time,) and your stop value will be the depth of the deepest leaf node.</p> <p>If the frequency stats aren't sorted it will take O(nlog n) to do, if they are sorted by frequency it can be done in O(n).</p> <p>Huffman codes are guaranteed to have the best average compression for this type of encoding:</p> <blockquote> <p>Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code.</p> </blockquote> <p>This should help you implement the ideal solution to your problem.</p> <p><strong>Edit:</strong> Though similar, this isn't what the OP was looking for.</p> <p>This <a href="http://www.stevenpigeon.org/Publications/publications/ssc_full.pdf" rel="nofollow noreferrer">academic paper</a> by the creator of these codes describes a generalization of start-step-stop codes, start-stop codes. However, the author briefly describes how to get optimal start-step-stop near the end of section 2. It involves using a statistical random variable, or brute-force funding the best combination. Without any prior knowledge of the file the algorithm is O((log n)^3).</p> <p>Hope this helps.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow can one compute the optimal parameters to a start-step-stop coding scheme?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USBen S
    1. USBen S
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHow can one compute the optimal parameters to a start-step-stop coding scheme?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHuffman is exactly what I thought of when reading this question. +1.
      singulars
      1. PO
      1. USstrager
    2. COIt reminded me of my sophomore year data structures class. :D
      singulars
      1. PO
      1. USBen S
    3. COHuffman codes are not prefixed by their length, as in a start, step, stop code. Therefore, your solution does not apply.
      singulars
      1. PO
      1. USfluffels
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload