Questions tagged [data-compression]
The data-compression tag has no usage guidance.
208
questions
0
votes
1answer
40 views
Alternatives to multiplication/division/modulo for encoding choices?
The obvious way to encode, with minimum entropy, choosing s out of n (equiprobable) choices when x is already encoded is to identify s with a number [0, n) and set x = n * x + s, decoded with s = x % ...
2
votes
2answers
62 views
Is Prediction the same as Compression?
Just came across this transcript that states:
The principle is that prediction is the same thing as compression. And
what that means is that whenever you have a prediction algorithm, you
can also get ...
2
votes
0answers
37 views
Is arithmetic coding slightly more efficient than rANS?
I'm extending a framework for lossy compression of multidimensional floating-point data. At some point in the pipeline, sequences of symbols from a non-uniform distribution are losslessly compressed ...
1
vote
2answers
55 views
Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding?
With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is ...
2
votes
1answer
53 views
Clustering data for compression with PCA
If I have datapoints in a high dimensional space and want to find a (linear) subspace onto which a data-set projects well, I can use PCA and then discard less important dimensions of the new basis to ...
3
votes
1answer
33 views
Space-efficient data structure for analytical querying of multiple branching evolutions of a dataset
Problem Description
I have a data state space: a set of data sets, each of which can be modelled as a collection of arbitrary key-value pairs. These data sets are each a branch of evolution of a ...
22
votes
1answer
913 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 ...
0
votes
0answers
35 views
How can 4 GB of data can expand into 40 GB of data, when I install Windows on a Computer
Say I start with an iso with about 4GB of data and use this, to install windows on a computer. After installation, the operating system will take up about 40GB of disk space.
Where does all this &...
1
vote
0answers
50 views
Mathematical limits on lossless data compression
Let's say Bob wants to send a particular binary sequence to Alice. Imagine that Bob and Alice both have powerful machines but slow Internet connections. Bob could just send the sequence directly but ...
0
votes
0answers
33 views
Design of a synchronized clock
I was living in a country where Internet wasn't that fast so the younger me had the following idea for compressing data
Let say 2 parties want to send data to each other, we know that data can be ...
33
votes
5answers
6k 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
3answers
112 views
Can a 600 MB text file with digits of the square root of 2 be compressed to 600 KB?
I have a simple script to calculate gaps in a sequence of digits of the square root of 2 (or any other multi-precision constant).
As input, I generated files with the bigfloat module in Python:
...
2
votes
1answer
27 views
Adaptive arithmetic coding confusion
I'm confused about the point of adaptive arithmetic coding.
I understand that static arithmetic coding involves using preset probabilities of symbols that remain static during the whole process. I ...
0
votes
0answers
20 views
Significance of model in arithmetic coding
I am trying to understand the concept of arithmetic coding, i understand how the range is subdivided after each character is read from the string. But i am unable to understand why using a more ...
0
votes
1answer
23 views
How does value decompression work for Facebook's Gorilla in the case where count of leading zeroes is not stored
I am referring to this paper: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf
My question is regarding section 4.1.2 where it says:
When XOR is non-zero, calculate the number of leading and ...
0
votes
0answers
26 views
Source code or detailed explanation of “WKS” virtual memory compression algorithm?
I've been trying to find information on various program data virtual memory compression algorithms that are in the "WK" family of algorithms. So far, I've been successful with the "WKdm" compression ...
-1
votes
2answers
69 views
Is the source file size smaller than the executable file size?
Wondering if compilation increases file size in general, is the source file size smaller than the executable file size?
0
votes
0answers
31 views
How do you work out the Huffman code for an extension?
I have worked out the following:
v = 1101 0010 1101 0101 0100 1000
P(0) = 0.54
P(1) = 0.46
A = {0,1}
I have also worked out question (c) to be: H(A^2) = 1.991 and H(A^3) = 2.9859
I am having ...
0
votes
0answers
31 views
How would I make sure my compressed string has the smallest length possible?
I'm trying to make a function that takes a string and compresses the repeating blocks. The code I'm using is implemented in such a way that a single character like 'a' would be converted to '1(a)' ...
3
votes
1answer
89 views
Applying SVD compression to integral point images
Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular ...
0
votes
1answer
37 views
Data compression - Entropy
Let's say I have an alphabet
$$\Sigma = \{A, B, C, D, E\}$$
with probabilities
$$P(A) = P(B) = P(C) = 0.25 \text{ and } P(D)=P(E) = 0.125.$$
I know that the entropy then is:
$$H(\Sigma) = 3 \cdot 0....
2
votes
1answer
26 views
on-the-fly decompress a flat-file database
I'm facing the following problem. I have a flat-file database (e.g. CSV).
Since it's relatively large to store in memory, I'd like to compress it.
Given a key, I need to return the uncompressed text (...
1
vote
2answers
64 views
Data Compression :Compress a Compressed File
Suppose we have file A that has been compressed by the the method B and the output-file is C, now if I am not wrong We can not compress C more by method B, but there might another method=algorithm D ...
0
votes
1answer
53 views
How a Data Compression Software Reads a File as pure Binary File and makes Output?
I have an hybrid compression technique I want to implement, my implementation is (so far): I can encode a string into a encoded compressed string. These are binary strings. For example,
I read texts ...
0
votes
1answer
24 views
Find an infinite set of strings that are compressable better than in $O(\log n)$ space
The task is to find an infinite set of strings $a_1,a_2\ldots$, where $|a_{i+1}|>|a_i|$ and to find a compression algorithm $f$ for these strings, such that $|f(a_i)|=o(\log_2 |a_i|)$ with $i\to\...
3
votes
2answers
372 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:
...
7
votes
1answer
206 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$ ...
1
vote
0answers
293 views
Advantages/Disadvantages of adaptive contexual arithmetic coding
What are the advantages and drawbacks of considering ever longer block lengths or context lengths, if one was to work with estimated probabilities(measuring on the fly: aka "adaptive") rather than ...
3
votes
1answer
68 views
How many “compressible” strings are there?
Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this.
It is easy to see that almost all ...
10
votes
4answers
6k views
Compression of Random Data is Impossible?
A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to ...
0
votes
0answers
23 views
How can i compare lossy image compression techniques?
I need to find which lossy image compression technique is the best. I chose to test JPEG, WebP and BPG. Which criteria can I choose for comparison apart from quality and speed of compression and how ...
3
votes
3answers
119 views
Is it possible to have high compression but low predictability?
Can you have a process that generates a binary sequence with high compression rate (low entropy) but impossible to predict next symbol?
'impossible to predict' - sequence cannot be predicted ...
2
votes
1answer
28 views
Proof high-entropy sequences are hard to compress
When comparing random-variable sequences generated from probability distributions, what's a formal proof that a distribution with higher entropy produces a sequence that's "harder" to compress?
In ...
3
votes
3answers
2k views
Algorithm to convert a fixed-length string to the smallest possible collision-free representation?
I have a US-based telephone number (in the format 000-000-0000) and need to convert it to a "shorter" representation. Using base32/64 produces too long of a string. I've discovered CRC-16, which ...
1
vote
1answer
49 views
Is a complete code always optimal?
According to wikipedia, Kraft's inequality holds with equality when a code is complete. Huffman encoding produces a complete code that is optimal. Are all complete codes optimal and vice versa?
-1
votes
2answers
60 views
Can data be compressed through this hash function technique?
I'd like to know if this data compression scheme would work or not, and why:
Suppose we have a file. If we treat the bits that make up the file as the binary representation of a number n, we have n (...
3
votes
0answers
59 views
Modifying the JPEG compression to use custom block patterns
recently, while watching a video about machine learning, I had an idea about creating an image compression algorithm, that works similar to JPEG, but is based on arbitrary bitmaps as blocks.
I should ...
12
votes
4answers
5k views
Are there any compression algorithms based on PI?
What we know is that Ļ is infinite and quite likely it contains every possible finite string of digits (disjunctive sequence).
I've seen recently some prototype of Ļfs which assume that every file ...
-1
votes
3answers
290 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 ...
1
vote
0answers
45 views
Implementing binary arithmetic encoder
I have set integers that are normally distributed, and I'm trying to implement binary arithmetic encoding, as suggested in this post: Compressing normally distributed data
I'm running into trouble ...
1
vote
1answer
48 views
How to find optimal token set for compression?
By token I mean the smallest element of source data, that the compression algorithm works on. It may be a bit (like in DMC), a letter (like in Huffman or PPM), a word, or variable-length string (like ...
0
votes
2answers
48 views
is there a (FLAC like) loseless compression coding format for EEG data? [closed]
EEG and Audio data are very similar, both
are numerical samples in continuous sequence
have a sample rate
need and can have multiple channels
channels for multi-channel audio
channels for each ...
1
vote
1answer
128 views
Run Length Encoding Compression With Nested Level
I am studying about some compression methods, and I'm very interested in RLE Algorithms. But are there any Nested-Level RLE methods, such as:
ABABABCABABABC --> 3(AB)C3AB(C) --> 2(3(AB)C) ?
It's ...
0
votes
0answers
39 views
Is entropy a good indicator of the quality of a lossy compression?
Say I want to quantitively evaluate the effectiveness of several color-to-grayscale conversion algorithms, which can be considered as lossy compression. Would entropy be a good indicator?
To ...
1
vote
1answer
46 views
Question is about a paper “A Block-sorting Lossless Data Compression Algorithm” by M. Burrows and D.J. Wheeler
In the paper A Block-sorting Lossless Data Compression Algorithm by M. Burrows and D.J. Wheeler Link.
On page number 5. please describe this line
If the original string $S$ is of the form $Z^p$ for ...
0
votes
0answers
48 views
An interesting compression algorithm idea
I stumbled on this paper about compressing images using a kind of odd, but interesting idea. It seems pretty easy to implement and I was wondering if there is something wrong with it that I haven't ...
1
vote
1answer
50 views
Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)
For data compression, every codding that I've seen is binary. It means we convert a language with $N$ symbol size to a language with $M=2$ symbol size. For example, in Huffman coding, the goal is to ...
4
votes
1answer
731 views
How does a predictive coding aid in lossless compression?
I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm).
From the example seen ...
0
votes
1answer
62 views
Is it possible to achieve greater than perfect compression using machine learning and big data?
Imagine Google wanted to make their chrome browser faster. Let "database" be all the machines which serve content from Google's servers, including Search and Google cloud services. Google begins using ...
3
votes
2answers
4k 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) ...
