The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
3answers
120 views

Regular languages under change of encoding

Consider a regular language $L$ with alphabet $\Sigma = \{0,1\}$. Can we say that the set of strings in $L$ (representing non-negative integers in binary encoding) when represented in some other ...
2
votes
4answers
272 views

Research in Coding Theory

I have just started learning about coding theory. Hence, I would like to ask for your suggestions and guidance for a very beginner like me. Which books are good for beginning coding theory? (I start ...
0
votes
0answers
32 views

Adaptive coding algorithm with the possibility to delete symbols? [on hold]

Is there any adaptive coding (i.e. adaptive compression) algorithm that supports deleting some of the previously-seen symbols from the codewords? Note that I only need an encoder, so that deleting a ...
2
votes
0answers
79 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
523 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
263 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
655 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: ...
5
votes
1answer
249 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
2k 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 ...
22
votes
3answers
636 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
1k 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
544 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
662 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
312 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. ...