Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [compression]

Use this tag for questions about encoding information using fewer bits than the original representation.

0
votes
1answer
35 views

Combine two numbers into one and extract them back

I have two numbers(A,B), I want to combine the numbers into one(C) The constraints are A's range = 0 to 3 (4 values) B's range = 0 to 900 (900 values) C must have a maximum of 3 digits only. ...
0
votes
0answers
11 views

Compactly represent nearby GPS co-ords with equal [accuracy/error/density]

For the purpose of discussion assume the GPS geoid is a sphere of 6378137 metres radius The geoid has a surface area of : 4 * pi * 6378137 metres^2 = 80150033.4 m^2 I need to send GPS coordinates ...
3
votes
3answers
109 views

How to maximize the expected number of corrected guesses?

A, B are to play heads or tails for $N$ rounds. They win a round if both guess correctly. A and B are allowed to communicate their strategy before the game starts. A knows the full sequence of $N$ ...
0
votes
0answers
15 views

The spectrum of a compression of nonsymmetric matrix

If $A\in\mathbb{R}^{n\times n}$ with a spectrum $eig(A)\subset\mathbb{C}$. Define a matrix $P\in\mathbb{R}^{n\times m}$, where $m<n$ and $P$ is a nonnegative matrix, i.e. its entries are either ...
0
votes
1answer
24 views

Encoding numbers from 0 to 255 using Huffman coding.

How can I encode numbers from 0 to 255 using Huffman coding (or any other code), so that each number (especially the largest numbers such as 255) wouldn't take 8 bits of binary space? In other words, ...
8
votes
2answers
127 views

Compressing the primes using simple addition?

Consider the sets of integers $$ A = \{1, 3, 7, 13, 27\} \\ B = \{4, 10, 16, 40, 100\} $$ Elementwise addition of sets $A, B$ looks like $A + B := \{ a + b: a \in A, b \in B\}$. Now elementwise-add ...
0
votes
1answer
22 views

How much BPS(Bits per symbol) is enough to call a compression algorithm good, with respect to entropy?

Consider a general purpose lossless data compression algorithm, It compresses a randomly generated binary file of 100MB size, with random I mean I wrote a small Script to create a file with random ...
1
vote
1answer
45 views

Manual Text Compression Algorithm (done by hand)

Last year (I'm in 10th grade), during most unit/chapter tests, we were allowed to bring notes. We could prepare a 3 x 5 in. (7.62 x 12.7 cm) index card at home, and cram it with as many notes as ...
0
votes
0answers
11 views

Performance of conventional estimation approaches for sparse recovery

If we use conventional estimation methods (like Least squares or MMSE) to recover a sparse vector for which we have random measurements, is the result accurate? Why?
3
votes
1answer
57 views

Does Ramsey theory prove that all sufficiently long random sequences can be slightly compressed?

First, my apologies if this has already been asked and answered. I did search this community for five to ten minutes looking for similar questions and found none. My lay understanding of Ramsey ...
1
vote
0answers
27 views

Is compressed sensing for digital signals or could also be applied for discrete time signals?

I was wondering if is compressed sensing for digital signals? or could also be applied for discrete time signals? What I mean is lets say I have a sampled but not quantized signals, can I find the ...
1
vote
1answer
49 views

Constraint on number of codes of maximum length in a binary Huffman code.

A Random Variable '$X$' take values from a discrete alphabet $K = \{k_1, k_2, k_3,k_4 \}$, with probability mass function {$p(k_i)$} = {$0.6, 0.2, 0.15, 0.05$}. The constructed Binary Huffman codes ...
0
votes
0answers
13 views

Generating Huffman codes from unsorted code lengths.

As an exercise for myself, I am writing an Ogg Vorbis decoder. Part of the decoding process involves generating Huffman codes from a series of code lengths that is later used when decoding audio ...
0
votes
1answer
60 views

compressive sensing and biorthogonal wavelet matrix

I want to use compressive sensing to reconstruct an image from fewer samples. My problem is with Psi matrix which I want to be Biorthogonal wavelet coefficients but I don't know how to define it. I ...
1
vote
0answers
27 views

Can you help me find a Fourier transform-able approximation function basis for compression?

I have four-dimensional, piece-wise smooth, discrete (4D voxel) data that I want to approximate/ compress using as few basis functions as possible. The data are discontinuous in three dimensions, ...
-1
votes
1answer
48 views

compressing random permutation of N

Is it possible to compress the given random permutation of any integer using N*(lg(N) -1) bits? For example if N= 512, then it could be represented using 512 * 9 = 4608 bits and its optimal ...
0
votes
1answer
29 views

Getting the compression ratio

Given a picture of $200x200$ pixels. Without compression, each pixel uses $10$ bits to represent a color. This image is compressed lossless by giving the colors a new coding. The coding of ...
0
votes
1answer
36 views

how to compress a 1D sampled signal

Assume you have a 1D function f(x) that you would like to sample and then reconstruct. What are some techniques of sampling that function with the fewest samples but to still get close to ...
1
vote
1answer
64 views

Is there any way to compress two or more numbers which I can get back without any errors?

I want to find out if there are any function $f$ which takes, lets say two numbers $a$, $b$ and outputs $x$, such that $f^{-1}(x)$ returns $a$ and $b$. $$f(a,b) = x$$ $$f^{-1}(x) = a,b $$ I think ...
0
votes
1answer
40 views

Can't understanding information entropy and data compression, for beginners

I watched a very well done video about information entropy, and I thought I got the concept in my mind but then I asked my self a question that denied every certainty I had. The video if you are ...
0
votes
0answers
39 views

Proving that at least half of all words with length bigger than $n$ are not compressible.

We say that a word is not compressible, if it's Kolmogorov-Complexity is bigger than the length of the word. We know that for every natural number $n$, we have at least one word which is not ...
0
votes
0answers
110 views

Typical Sets In Source Coding

I'm struggling with the following question: For typical sets in source coding, decide if it is true or false and provide a detailed proof. My ideas: a. true, since by definition we get 2^log(p) > 2^...
1
vote
3answers
339 views

Is compression possible on a uniform distribution of symbols?

I was reading about limits of data compression and I had this question that kept me thinking. Alphabet set: Set of all the unique symbols in the input data Q. If the distribution over the alphabet ...
1
vote
1answer
385 views

Change of basis for image compression (toy example)

In linear algebra course, prof. Strang uses JPEG image compression as an example of basis change (lecture 31). I would like to make sure that I understood the concept. For simplicity, let's assume ...
0
votes
0answers
47 views

How does the escape code in a Markov chain compression help?

This question is regarding the following video by google developers (after 11:20 mins) . He explains how a markov probability updated table can be used to do compression. Since it's a dynamic ...
1
vote
0answers
195 views

how to compress sound waves?

there is voice sound wave as series of numbers: we sample them into discrete numbers like: i need to compress it in half. most existing ways as simple as ignoring even samples to become half length ...
0
votes
0answers
333 views

Matrix Compression: Mapping between padded Compressed Row Storage and Compressed Column Storage?

Context There are a handful of ways to compress a matrix, $\mathbf{M}$, but Compressed Row Storage (CRS) is fairly popular due to its fast access. Similarly, there exists Compressed Column Storage (...
1
vote
1answer
111 views

For square images, do SVD and diagonalization always produce the same result in compressing images?

If not, then does SVD always work better than diagonalization? It seems to me that for square images, diagonalization is the more straightforward method when compressing images in MATLAB. However, I ...
1
vote
1answer
101 views

Shifting and compressing signal

I have a signal $$x[n] = n(u[n] - u[n-7])$$ So it is a discrete signal that goes from 0 to 6 when $n$ goes from 0 to 6, then it is 0 for all other $n$. I want to figure out what $x[4n+3]$ will look ...
1
vote
2answers
317 views

no $k$-sparse vector in null space of $A$ where $y=Ax$

Here is a part of my notes on compressed sensing. Suppose we are given an underdetermined linear system of equations $Y=AX$. For a unique solution, What we need: subtraction of no two $k$-sparse ...
3
votes
1answer
214 views

How to find Turing Machine for given arbitrary output

Are there general methods / algorithms for finding a Turing Machine that will output a given binary number? For example, I want the machine to write ...
3
votes
2answers
516 views

squashed sine wave

Sinewave I'm slightly out of my comfort zone with this one. I need to produce a function for use in an animation, but a sine wave isn't quite right. I tried adding a square wave, but that didn't work ...
1
vote
0answers
4k views

Is there any online Huffman code/decoder?

I need to see and work with Huffman code and see how does it compress data. Anyone has any link of online Huffman coder and decoder (compressor)?
0
votes
0answers
63 views

Is there any two way algorithm for compressing numbers?

I have this question that is there any way we can convert a number to another number with less character in the new number? For example, Imagine we have 811008 and if we divide this 13 times by 2, we ...
1
vote
3answers
865 views

How is this possible to convert a long string to a number with less characters?

I'm going to write a program (function) that can convert a long string to a number. For this, first I convert each character (letter) to a number; like ...
2
votes
0answers
363 views

Compressing permutations

I am looking at a compression technique that finds a permutation of the bits of a 64-bit block of data that collects all 1 bits at the beginning of the block, and sends all 0 bits to the end of the ...
2
votes
0answers
86 views

Math of Repetition

Let R = A (A | B) (A | B | C) (A | B | C | D) ... be an R-Form(A sort of repetition matching grammar). Where A,B,C,D,... are symbols that allow equality comparison. Any sequence of A,B,C,D,... can ...
1
vote
1answer
26 views

Compressing bitchains

Let there be a bit-chain consisting of $n$ characters with the following rules: The probabilities of the first character being $0$ and $1$ are $1/2$. From then on the probabilities are $p$ when the ...
1
vote
0answers
24 views

Source coding with 2 distinct distributions and entropies

I'm learning about source coding, and many of the books/resources I've read give examples of the source $X^n$ being defined as a sequence of iid random variables. How about when the sequence is ...
1
vote
2answers
108 views

What's theoretical maximum information compression rate?

Let's say I've got a random bit sequence s and a reversible function f(s), for which the following statement ...
2
votes
1answer
880 views

Is there a difference between cosine and sine transform?

Surely both should work with the same set of functions. Why is only cosine transform used in JPEG? Why not sine? It seems that using fourier transform rather than cosine transform would result in ...
0
votes
1answer
127 views

Lempel-Ziv-Welch Encoding of single character sequence

So I have this typical exam question: Consider an LZW coder for an alphabet with 32 symbols (thus represented by 5-bit symbols) using a dictionary of size 256 (thus indexed by 8-bit words). The ...
1
vote
1answer
37 views

How does a wavelet help in compressing data

I have an understanding of how we carry out image compression by using DCT along with Huffman encoding. The next subject is wavelets. I understand that wavelets are small waves and there are different ...
5
votes
1answer
53 views

Spare storage of a tree

I can store any undirected simple graph N vertices using $b = (N-1)N/2$ bits, by creating a mask of the edges on the upper diagonal of the adjacency matrix. For example the adjacency matrix of $K_3$ ...