Questions tagged [data-compression]
The data-compression tag has no usage guidance.
1
vote
0answers
30 views
Computing (near) optimal displacement tables
Suppose we have a two-dimensional table $T$ with $r$ rows and $c$ columns that is sparse. Let $T[i][j]$ be the element at the $i$th row and $j$th column of $T$, with zero-based indexing.
We can ...
34
votes
6answers
7k views
Do lossless compression algorithms reduce entropy?
According to Wikipedia:
Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter ...
2
votes
1answer
27 views
Is there an algorithm to achieve optimal compression in a “streamed” manner, assuming equal probability of each possibility?
(Sorry for the question title; edits are welcome.)
Let's say that you have a set of data made of repeating units, consisting of a value with $2$ possibilities, a value with $3$ possibilities, $5$ ...
2
votes
1answer
29 views
what is a shearlet/shearlet transform and how can i use it?
from what wikipedia says shearlet is a successor to wavelets(whatever that is) and that they are extremely good at representing complicated data efficiently. But neither wikipedia nor other articles ...
0
votes
3answers
133 views
I think you can always compress compressed data, is it true?
In compressed data, repetition of same pattern is not a lot, so, you can expect it to be with space inside to contain always. I found a way to compress data without limitation. Is it right? Am I ...
2
votes
1answer
87 views
What is the best way to compress a string with only numbers and commas in it?
I have a string like this:
11,512,64,23,46,12,67,85,84
And I'm sure it's following these rules below:
Only , and ...
2
votes
1answer
43 views
Compression algorithms for small strings - building upon / extending Huffman
I'm exploring algorithms to compress small strings like the following - every line is to be compressed individually, i.e. even those small strings should get compressed:
...
16
votes
4answers
5k views
Can data be compressed to size smaller than Shannon data compression limit?
I was reading about data compression algorithms and the theoretical limit for data compression. Recently I encountered a compression method called "Combinatorial Entropy Encoding", the main idea of ...
0
votes
1answer
71 views
What is the most compact (space efficient) method of storing an array of distinct integers?
I have an array of distinct integers which I want to save in the most compact manner. I may have to do occasional lookups, deletions, and insertions in this array so the compression algorithm must ...
5
votes
1answer
121 views
Most space-efficient lossy dictionary?
Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)?
Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ ...
0
votes
0answers
15 views
Is reinforcement learning the right tool for inferring graph structure from sequence?
Sorry that this is a complicated question - I will try to get to the essence of it.
I am interested in learning the structure of sequences of numbers in terms of a graph encoding specific types of ...
2
votes
1answer
46 views
Algorithm for estimating lossless compression factor
Is there any algorithm for estimating how well certain array of bytes could be compressed in lossless manner?
Usage for me is to automatically choose "best" data reorder method without knowing what ...
2
votes
2answers
68 views
Does this progressive image compression exists?
I want to know if this progressive image compression that I have in mind exists and it it does I want know its name and/or get some references about it.
The algorithm consists of converting one high ...
-3
votes
1answer
26 views
Character in Huffman encoding [closed]
Is a full stop regarded as a character along or must it be with a space in huffman encoding. I know of taking a comma with a space to a character.
1
vote
1answer
28 views
Compression with random dictionary
Is the following scenario theoretically possible, or provably impossible?
Alice generates a 1 GiB file with random bits and sends it to Bob. This file is a shared dictionary they call Q. Now, Alice ...
1
vote
0answers
20 views
Attribute Selection for minimum number of clusters
I have a table consisting of some headers $P, Q, R, S$ (shown in blue in Table 1). According to the headers, the column $T$ is populated using some predefined logic.
Now, any of the headers $P,Q,R,S$ ...
0
votes
2answers
42 views
Data compression with Turing Machine
For traditional algorithms compressed data may vary, while decompression algorithm is always the same. Are there any approaches, when (de)compression algorithm is also changing to provide best ...
0
votes
0answers
25 views
How much data can be send in 1 minute of audio with Smartphone speakers / microphones?
Having the current news about Google Assistant in mind, I thought that robots might use interfaces designed for humans to send data. Like a telephone interface.
Then I wondered: What is the maximum ...
0
votes
0answers
43 views
What algorithm is most suitable for large text compression?
Currently, I am looking for an lossless compression algorithm that is suitable for a large amount of text, that will be further encrypt by AES and use as the payload in steganography.
Based on A ...
1
vote
2answers
106 views
How would the use of an external lookup table affect file compression?
It occurred to me that, the way compression essentially works, is that you have a mapping of long patterns to short patterns, which you replace one way to compress and the other to decompress. My ...
1
vote
1answer
81 views
Was my Huffman coding solution wrong?
I finished my exam a moment ago and one of the question was to calculate Huffman coding for given probabilities:
A: 0.15
B: 0.2
C: 0.55
D: 0.1
I encoded them as ...
0
votes
0answers
8 views
Quantile Summary Example
I am reading a note on quantile summary.
I am not sure if I have already understood the definition of quantile summary. I am looking for concrete examples for the definition.
Another question is ...
1
vote
1answer
44 views
Generate numeric or string ID for a sequence of elements
How to generate a numeric or string id(not very large text) for a sequence of elements where ordering doesn't matter.
Example:
[41,1001,32] should generate the ...
2
votes
1answer
33 views
Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods
When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40.
Reference:
Here's a reference: https://en....
1
vote
3answers
106 views
Is there a method to compress all data without loss (lossless compression)?
I know that the answer is no but I'm not sure why. Here's where I started. We know that all data with length $n$ Bits and minimum $1$ Bit can be compressed, either lossless or lossy. But how do I ...
1
vote
1answer
64 views
Problem with determining the shape and direction of the Huffman Diagram
I have the phrase "abracadabra" and I want to encode it through the Huffman method. I first took the frequencies of each letters;
$$a=5$$
$$b=3$$
$$c=1$$
$$d=2$$
$$r=2$$
But I'm not sure as to how the ...
0
votes
1answer
47 views
Intuitive way to understand “Run-Length Encoding”
Run-Length Encoding is the simple form of lossless data compression in which compression in which runs (execution) of data are stored as a single data value and count rather than as the original run (...
24
votes
11answers
9k views
Is von Neumann's randomness in sin quote no longer applicable?
Some chap said the following:
Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.
That's always taken to mean that you can't generate ...
0
votes
0answers
70 views
Is it possible for a [futuristic] computer to contain the information of the whole universe?
(This is a question of information theory, data compression and entropy, so I believe it fits CS forum)
Does the fact that the computer itself is a part of the universe make it logically impossible ...
2
votes
1answer
114 views
monotonically increasing codeword length in optimal (maybe Huffman) code for alphabet with monotonically decreasing frequencies
I'm working on exercise 16.3-5 of CLRS:
Prove that if we order the characters in an alphabet so that their frequencies are monotonically decreasing, then there exists an optimal code whose codeword ...
1
vote
0answers
31 views
Using less Random Access Memory
Suppose you were to compress data before it was sent to Random Access Memory. Wouldn't you technically be using less R.A.M?
3
votes
2answers
304 views
Representation of used space and free space in hard drives
I've read from this How data is physically stored in hard drives, that the North/South orientation of the magnetic medium represents data as 0 or 1 physically in the hard drive. Data is stored in ...
1
vote
1answer
26 views
What is the Code2 and other concepts of variable encoding in Coding Redundancy?
Am learning the concept of Coding Redundancy in image compression and am finding it hard to understand the table on page 3 of this document. All other explanations seem to follow the same symbols and ...
3
votes
1answer
180 views
Is there a limit to data compression without mentioning Kolmogorov complexity?
I want to develop a previous answer to Is there a known maximum for how much a string of 0's and 1's can be compressed?.
I've looked at the Hutter Prize and various compression benchmarks. The ...
-1
votes
1answer
152 views
Universal Lossless Compression? [closed]
It is not possible to losslessly compress all files of size $n$ using a single algorithm, as there are more files of size $n (2^n)$ than of size $p, p: p < n ( 2^n-1)$. Via the pigeon hole ...
1
vote
1answer
107 views
Practicality of compressing data with hashing algorithms
I want to compress the string 0cc175b9c0f1b6a831c399e269772661. I can do so by storing the string a, and, when decompressing, using a as input for the MD5 hash algorithm to get the original string.
I ...
1
vote
0answers
88 views
Compression of gaussian variables
Say I have 2 Gaussian sources X and Y. They are generated with mutivariate gaussian distribution with ...
1
vote
0answers
72 views
Which algorithms provide high compression ratios for bit matrices?
I have an x*y bit matrix where the total number of bits fluctuates between ~1,000,000 and ~20,000,000 bits. The rows are much smaller than the columns. An example matrix might be of size 1,000,000 x ...
1
vote
1answer
109 views
How can I compress data that represents a number's change over time?
I have a value that increases by unknown increments at unknown times. Given a time, I need to check how much it has increased between that time and now.
I could simply store every time/increase pair ...
6
votes
1answer
418 views
Optional prefix code for the naturals
The naturals $\mathbb{N}$ can be encoded with a binary unary code such as
$$
\begin{align}
1&=0_b\\
2&=10_b\\
3&=110_b\\
&...
\end{align}
$$
The length this the ...
0
votes
0answers
59 views
[Choosing tunable parameter M in Golomb/Rice Encoding]
I am a Computer Science student and I study Data Compression now. I read many methods but Golomb-Rice Encoding was not clear for me. I understand the method how it works but in the algorithm there is ...
1
vote
1answer
45 views
How to predict the next image in a sequence, or predict the deblurring of an image?
I have 3 versions of an image at lower resolutions - 480p, 720p, and 1080p. Is it possible to use those 3 images to predict the next highest resolution image (the 4k image)?
My first guess was that ...
0
votes
1answer
54 views
Can I say is lossy compression to discard data having a way to recover it?
I'm working on a compression algorithm for a specific kind of data. I have found a way to discard (important) parts of the data during compression as I have also found a way to recover the missing ...
1
vote
0answers
32 views
Compressing dataset by cartesian products cover
I have the following problem and I wonder if there exist a solution (or some algorithm to approximate it, even if it's far from optimal, as long as it is tractable) to it.
Say I have a set $V\...
0
votes
0answers
363 views
How does youtube do video quality change/video compression?
After uploading a high definition video in youtube, youtube automatically makes a low definition(standard definition) version of the video.
I would like to know what algorithm they use to reduce the ...
1
vote
0answers
32 views
which paper to take that would best fit to becoming a data scientist? [closed]
My name is Webber from Auckland, New Zealand. I am currently in my second year studying the bachelor of computer and information science. I have chosen to do a double major in computational ...
1
vote
1answer
102 views
Compression for set of integers preserving their sequence
For a given positive number n. Numbers from 0 up to n, are streamed one by one in some order ...
0
votes
1answer
100 views
Choosing a shortest representative number from interval in arithmetic coding
In arithmetic coding a word is coded as the binary encoding of a number in a certain interval. The interval is determined from a sequence of nested intervals according to the probability distribution ...
1
vote
1answer
286 views
How the LZ77 compression algorithm handles the case when the entire look-ahead buffer is matched in the search buffer
The LZ77 compression algorithm uses a sliding window technique, where the window consists of a look-ahead puffer and a search-buffer. What I am wondering is how the algorithm handles the case if the ...
4
votes
5answers
197 views
How can I explain lossless compression to a misguided audio engineer?
I have recently been involved in a discussion with someone who doesn't accept that lossless compression is possible, even in principle. This person considers himself to be technically literate, and an ...
