The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
5answers
2k views

Using base 80 for compressing files

I want to compress file size through making my own numbering system which is 80-based number, I do really want to know whether this even possible ? I learnt that Hexadecimal uses symbols like A, B, C, ...
11
votes
2answers
62 views

Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
0
votes
0answers
13 views

How to decode multiple-digit gamma codes and get the gap sequence? [duplicate]

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...
2
votes
2answers
95 views

How to decode multiple-digit gamma codes and get the gap sequence?

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...
0
votes
1answer
33 views

Number of phrases of LZ compression

It is known that for the number $c(n)$ of phrases / tupel of the LZ compression for binary words of length $n$ the following relation holds: $$c(n)\leq\frac{n}{(1-\epsilon_n)\log_2 n}$$ With ...
3
votes
2answers
51 views

How does one choose an optimal alphabet for finding a Huffman encoding?

Huffman encoding will perform best when the distribution of symbols of an alphabet that the string to be encoded uses is dyadic. Given an arbitrary bit string S, ...
0
votes
0answers
20 views

Improving Vitter's Algorithm (Λ) for adaptive Huffman Coding

I'm attempting a problem that involves adaptive coding, so I've taken a look at Vitter's algorithm (I've taken most of my information from here), which seems to have the best compression rate for ...
0
votes
1answer
41 views

Compression technique exploiting common similarities

I asked this on StackOverflow, but it was determined more appropriate to post here. So it goes like this.. For people concerned about users having slow connections and timeout issues, it is known ...
3
votes
3answers
86 views

Compression of non-adjacent structure using grammar

I'm working with compression algorithms that use context-free grammars (e.g. RE-PAIR and SEQUITUR). These grammars look for frequently occurring digrams (pairs of adjacent symbols) in an input string ...
3
votes
1answer
102 views

What determines the entropy of a program's source code?

a few days ago I asked a question about the limits of compression: Can PRNGs be used to magically compress-stuff? The idea common to all the answers was that if you consider all programs of length ...
5
votes
2answers
50 views

What are all the differences between the Gibbs phenomenon artefects and JPEG artefacts?

I thought the Gibbs phenomenom is the result of Fourier analysis estimation (but was it Fourier Series estimation or can it also be Fourier Transform estimation?) JPEG uses the Discrete cosines ...
24
votes
7answers
2k views

Can PRNGs be used to magically compress stuff?

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange. Here's a 14 year-old's scheme for an ...
1
vote
1answer
24 views

Do the two huffman trees have the same corpus?

Consider the following Huffman trees: I was asked if those trees can have the same corpus. My answer was no, based on these calculations: For the right tree: $a_1 \le a_2$ $a_1 + a_2 \le a_5$ ...
4
votes
3answers
85 views

Data Compression: Which one is Better “Compress before Encrypt” or “Encrypt before Compression”

Which one is better approach do data compression before encrypting it or Encrypt data before compression ? I think it is biased towards the application requirement. Please share your views.
3
votes
1answer
207 views

Does there exist a data compression algorithm that uses a large dataset distributed with the encoder/decoder?

If my goal were to compress say 10,000 images and I could include a dictionary or some sort of common database that the compressed data for each image would reference, could I use a large dictionary ...
3
votes
2answers
133 views

Compressing normally distributed data

Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly? Given the entropy of the Gaussian distribution, ...
0
votes
2answers
38 views

Arithmetic code: from interval to code value

I've not clear how to pass from final interval to code value, for example: Suppose we have the set of symbols={0,1,2,3} with probability={0.2, 0.5, 0.2 , 0.1} and that we have to encode a source ...
6
votes
2answers
96 views

How to find the minimal description for an array?

The following array occupies 10000 slots in memory: a = [0,1,2,3,4,5,6,7,8,9,10,...,10000] But one could easily represent the same array as: ...
3
votes
0answers
34 views

Approximate estimation of stream compressibility?

I wish to estimate the compression ratio of a stream of bytes. Specifically, I'm interested in DEFLATE compression. I'm looking for some algorithm/heuristic that can estimate roughly the ...
3
votes
3answers
181 views

compressed information = randomness?

Suppose I have a compressed file and it is not possible to compress it more without loss of information. We say that this file is random or pseudorandom. So, if the randomness means not ...
12
votes
1answer
200 views
1
vote
3answers
105 views

Is there a correlation of zip compression ratio and density of information provided by a text?

I'll phrase my question using an intuitive and rather extreme example: Is the expected compression ratio (using zip compression) of a children's book higher than that of a novel written for adults? ...
5
votes
1answer
98 views

To what factor can I compress information from binary to Quinary

I am trying to think if we can have an injective mapping $\mathcal{f}$, say something like $\Sigma_{bool}= \{0,1\}^* $ to $\Sigma_{5} = \{0,1,2,3,4\}^* $ such that $|x| \leq 2.|\mathcal{f}(x)|$ The ...
4
votes
2answers
107 views

Lossless data compression must make some messages longer? [duplicate]

I read on Wikipedia and in lecture notes that if a lossless data compression algorithm makes a message shorter, it must make another message longer. E.g. In this set of notes, it says: Consider, ...
1
vote
2answers
159 views

How optimal is Lempel-Ziv at reaching the Shannon limit?

I find this a bit difficult to describe, but I am interested in the following idea : The LZ algorithm factors (verb) an input stream into adjacent factors, these are by definition the maximal ...
5
votes
2answers
115 views

Behavior of iterative application of LZ77

I have been experimenting with LZ77 (naively $O(n^2)$ runtime, infinite window). Applying it to the 7th Fibonacci word $abaababaabaab$ yields the correct LZ factorization: $\qquad ...
3
votes
0answers
44 views

Bayesian Coding

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 ...
3
votes
1answer
244 views

Algorithm for determining minimal set of covering prefixes

I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set. For instance, if my set is: ...
5
votes
4answers
386 views

No compression algorithm can compress all input messages?

I just started reading a book called Introduction to Data Compression, by Guy E. Blelloch. On page one, he states: The truth is that if any one message is shortened by an algorithm, then some ...
5
votes
1answer
259 views

Will this algorithm terminate on any input?

One can compress data with straight-line grammars. An algorithm that employs this technique is called Sequitur. If I understood correctly, Sequitur basically starts with one rule representing the ...
4
votes
1answer
610 views

Minimum space needed to sort a stream of integers

This question has gotten a lot of attention on SO: Sorting 1 million 8-digit numbers in 1MB of RAM The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: ...
2
votes
1answer
95 views

Compression of sequence with Direct Access

I have a sequence of $n$ integers in a small range $[0, k)$ and all the integers have the same frequency $f$ (so the size of the sequence is $n = f * k$). What I'm trying to do now is to compress this ...
13
votes
2answers
241 views

Approximating the Kolmogorov complexity

I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors ...
2
votes
4answers
653 views

Is there any theoretically proven optimal compression algorithm?

Is Huffman coding always optimal since it uses Shanon's ideas? What about text, image, video, ... compression? Is this subject still active in the field? What classical or modern references should I ...
5
votes
3answers
787 views

Is Huffman Encoding always optimal?

The requirement of the encoding to be prefix free results in large trees due to the tree having to be complete. Is there a threshold where fixed-length non-encoded storage of data would be more ...
6
votes
1answer
255 views

Measuring entropy for a table (e.g., SQL results)

We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of ...
3
votes
0answers
46 views

Lossless Video Compression Pipeline

The only paper I can find about an implementation of a lossless video codec is an article by Michael Niedermayer which explains the FF1V compression pipeline. I'm wondering if anyone else has found ...
5
votes
1answer
103 views

Why are blocking artifacts serious when there is fast motion in MPEG?

Why are blocking artifacts serious when there is fast motion in MPEG? Here is the guess I made: In MPEG, each block in an encoding frame is matched with a block in the reference frame. If the ...
3
votes
1answer
170 views

Distinguishing between uppercase and lowercase letters in the “move-to-front” method

Is it not necessary to encode both the uppercase and lowercase letter while encoding a message with the move-to-front transform? From an old computer science course exam, the problem was to encode ...
12
votes
1answer
351 views

Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...