The encoding tag has no wiki summary.
2
votes
0answers
75 views
Bayesian compression
Suppose you have a sequence generated by an i.i.d. process (such as repeatedly rolling a die and recording the values in order) parameterized by some K-dimensional vector $\vec{\gamma}$ (the ...
1
vote
2answers
495 views
Arithmetic coding, the termination symbol, and the empty string
Suppose the source alphabet is $a, b, c$ with $a$ as the termination symbol and so the unit interval is correspondingly divided as
$[0, P(a), P(a)+P(b), 1]$.
Strings consisting of a bunch of $b$'s ...
4
votes
2answers
213 views
Combinations with symbols
Suppose we have the following symbols: $\{a,b\}$. Now there are some rules. More than 3 $b$'s are now allowed and $aa$ is not allowed. So $ababab$ is allowed, but for example $abbbbaba$ not (more than ...
7
votes
6answers
541 views
Efficient encoding of integers with constant digit sum
How can a large set of integers all with a known constant digit sum be encoded?
Example of integers in base 10, with digit sum 5:
...
3
votes
1answer
178 views
Can Bencodes Be Described With a Context-Free Grammar?
Bencoding is the encoding scheme used by Bittorrent applications. You’re probably most familiar with bencoding via the .torrent file format used by Bittorrent ...
11
votes
5answers
1k views
Why does Huffman coding eliminate entropy that Lempel-Ziv doesn't?
The popular DEFLATE algorithm uses Huffman coding on top of Lempel-Ziv.
In general, if we have a random source of data (= 1 bit entropy/bit), no encoding, including Huffman, is likely to compress it ...
18
votes
3answers
492 views
Adding integers represented by their factorization is as hard as factoring? Reference request
I'm looking for a reference for the following result:
Adding two integers in the factored representation is as hard as factoring two integers in the usual binary representation.
(I'm pretty sure ...
3
votes
2answers
787 views
Why does the Fibonacci sequence produce a worst-case Huffman encoding?
I noticed this in my Algorithms class, but just now got around to asking.
8
votes
5answers
511 views
Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters
Let $\Sigma$ be an alphabet, ie a nonempty finite set. A string is any finite sequence of elements (characters) from $\Sigma$. As an example, $ \{0, 1\}$ is the binary alphabet and $0110$ is a string ...
2
votes
2answers
561 views
Graph encoding algorithms that you know of ?
Is there any compilation of graph encoding algorithms? I know about Prufer and Huffman encoding. But papers say, prufer is not good enough to represent Minimum Spanning Trees in the sense it may ...
9
votes
2answers
307 views
Quick encoding of balanced vectors
It is easy to see that for any $n$ there exists a 1-1 mapping $F$ from {0,1}$^n$ to {0,1}$^{n+O(\log n)}$ such that for any $x$ the vector $F(x)$ is "balanced", i.e., it has equal number of 1s and 0s. ...
