Questions tagged [data-compression]
The data-compression tag has no usage guidance.
227
questions
0
votes
1answer
23 views
Compression algorithm using key value mapping
Would it be possible to do better than standard compression if you fed a bunch of zipped files through a machine learning algorithm that kept track of the most common bit sequences and produced a ...
0
votes
2answers
47 views
How to find the compression method used on an unknown sequence of bytes?
I have a sequence of bytes:
https://drive.google.com/file/d/17sfchPgsySi2ilIxLuBb1q-UUqq5lO87
What the data is, is unknown (see NOTE below).
I'm pretty sure this data is compressed in some way, due to ...
3
votes
1answer
63 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 ...
-1
votes
0answers
18 views
Is defragmentation a kind of minification, a kind of compression or perhaps both?
As far as I understand defragmentation:
Removes spaces between objects by putting objects nearer one to the other
reorganizes objects for better performance
The first action feels to me as some kind ...
-1
votes
1answer
34 views
How does data compression relate to the ordinary meaning of “compression”?
When I think about "compressing" outside computers I can think about a compressed car which has become a metal rectangle.
It doesn't have less redundancy because it has everything it had ...
3
votes
1answer
35 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 ...
2
votes
0answers
33 views
Online algorithm for compressing multiple SETS?
Algorithms like LZW and others compress data sequences.
What I'm looking is an algorithm that compress multiple Sets. if possible online algorithm.
For example :
...
6
votes
1answer
853 views
Why does the Huffman coding algorithm produce a valid tree?
I am not asking about the Huffman Code, but the most widely described algorithm for generating one, also described on the english wikipedia: https://en.wikipedia.org/wiki/Huffman_coding#Compression
...
1
vote
1answer
29 views
LZW with dictionary clearing
How does LZW decompress data with dictionary clearing/flushing? I understand that a space is reserved in the dictionary that represents a clear code (usually 256), but how is this code actually used ...
0
votes
0answers
38 views
File compression using prime numbers
My theory
take a file examplesize:(3GB)
convert said file to a number
divide that number by a large prime number example:(2^82,589,932 · (2^82,589,933-1))[2018 Dec 07]
get the quotient and the ...
2
votes
1answer
16 views
How Data Compression relates to Estimating Distribution?
I recently read this paper Mahoney, 1999.
And encountered this line,
optimal compression of a probabilistic language L with unknown distribution (such as English) using an estimated distribution M (...
2
votes
1answer
32 views
Compressing a bit string when I know how many 1s and 0s there are
Say I have a 256 bit bit-string, and I know that there are 16 ones and 240 zeros. I know that this bit string can be compressed, because there are only 256 choose 16...
13
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 ...
23
votes
1answer
989 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 ...
1
vote
2answers
72 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
0answers
30 views
Can you give me insight into the time and space complexity of those pairing functions?
I am looking for a pairing function with linear time complexity.
I found
one in Steven Pigeon's thesis (p 115, §5.3.6.3) described in English on MathOverflow that works by bit interleaving.
another ...
1
vote
2answers
116 views
What is the simplest algorithm to compress a string?
I need to compress a string in my application but I am very limited in the operations I can perform. In particular, I cannot store data in any file and I cannot query any database. Also, I cannot call ...
0
votes
1answer
44 views
Prime factorization for compressing streams of random numbers
We covered compression/encoding/decoding of data streams very briefly last lecture and I had an odd idea:
Let's say I have a stream of random 8-Bit numbers. Now the probabilty to encounter each number ...
0
votes
0answers
14 views
Efficiently compressing and decompressing an array of combinations
I'm wondering if there exists a way to efficiently compress an array containing combinations ${n}\choose{k}$, so that it can be easily decompressed minimizing the data read from that array. An example ...
0
votes
0answers
22 views
How many strings of length |w| are unrelated?
For sufficiently large |w|, how many of the 2^|w| strings of length |w| are entirely unrelated?
A way to define this: two strings are unrelated if their joint Kolomogorov complexity is practically ...
2
votes
1answer
65 views
Can you build a solver from a verifier?
Given code to just an NP-verifier, where the certificate/witness is required to be of size polynomial in the instance, for a language L, can you, from that data alone, construct code for a solver, or ...
1
vote
0answers
43 views
How do I compress data vectors in broadcast messages?
Let us model a wireless broadcast network as an undirected graph $G(V,E)$ where there is an edge between every pair of nodes ${i,j}\in V$ if they are in transmission range of each other. $w_{i\to j}$ ...
2
votes
2answers
28 views
Compression algorithm for statistical data with a desired outcome size
I did some basic research on regular lossy and lossless compression algorithms but somehow I couldn't really figure the right direction for the information I need.
My basic problem is that I would ...
0
votes
1answer
447 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 ...
0
votes
1answer
40 views
Arithmetic Encoding vs Adaptive Arithmetic Encoding
I am working on a personal project and I am having some conceptual level questions on arithmetic encoding.
Let's take a scenario where I have an array of sensors and the data collected is transmitted ...
1
vote
1answer
47 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
76 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
58 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 ...
0
votes
0answers
46 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
57 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
41 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 ...
34
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
120 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
48 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
27 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
42 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
410 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
32 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
108 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
47 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
37 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
119 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
82 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
26 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
560 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
221 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
464 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
91 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 ...
