# Questions tagged [data-compression]

The tag has no usage guidance.

247 questions
Filter by
Sorted by
Tagged with
1 vote
20 views

### Binary compression algorithem with decompress by index

I have a list of 256-bit data to store. How to compress it losslessly so that I can retrieve an entry by its index without decompressing the whole data. I will also need to code this algorithm ground-...
1 vote
170 views

### Undecidability in optimal data compression

There is this certain slide in Coursera Computer Science: Algorithms, Theory, and Machines course: I think it is saying finding the optimal size of given data is undecidable. However, I thought there ...
• 143
1 vote
27 views

### fpaq0.cpp is supposedly a "0-order" compressor. Why does it use a context then?

In http://mattmahoney.net/dc/dce.html#Section_32 Matt Mahoney states: The simplest of these is the order 0 coder fpaq0. in http://mattmahoney.net/dc/dce.html#...
22 views

### How to compress highly correlated arrays?

I want to write a compression algorithm for a specific use case that I have. I have many arrays which are for the most part, very similar. Each value in the array is an integer and is related to the ...
1 vote
37 views

### Video compression algorithm

I am working on a project for my CS subject and the topic is Video compression. After theoretical aspect, I want to implement and describe one algorithm that does video compression. I am not sure if ...
• 225
79 views

### What properties must a string satisfy to be a possible output of the Burrows-Wheeler transform?

The Buttows-Wheeler transform is a function that takes a string $S$ to a new string $S'$ and an index $I$. The new string $S'$ is always an anagram (rearrangement) of the input string $S$. However, if ...
• 171
32 views

### An efficient, probabilistic data structure for storing relationships between elements

I am fascinated by the bloom filter data structure. Is there a similar probabilistic data structure that can efficiently store and update the relationships between certain elements and the strength of ...
36 views

### How much CMIX compresses text data?

I have atleast a terabyte of text data which I need to compress as efficiently as possible. It is file of english words and numbers (Not randomly arranged but forming meaningful syntax just as regular ...
• 35
1 vote
72 views

### Theoretically the most efficient compression algorithm

I remember in high school we did this thing where we were given a bunch of numbers in a row that had a pattern. We were asked to work out what the next number in the pattern would be. It was very easy ...
1 vote
59 views

### Find repeated patterns in a string via lossy compression

Description The task is to identify repeated patterns in a string and do lossy compression of the input string using the found patterns. The output is a list containing different ways of encoding the ...
• 113
33 views

### temporal compression of binary data

I have a sequence of source files that are very similar (akin to frames in a video), and each file can be compressed by a codec independently, but there is no temporal compression. I want to further ...
• 101
47 views

### Storing a file by converting it into $n$ files, some of which can be lost

Let's say that I have a file that I really don't want to lose. I want to convert the original file into $n$ files in the way that will allow me to recover the original file if I have any $m$ of the ...
• 33
71 views

### Memory-efficient list of N unique integers from 0..N-1 with fast lookup

We want to represent a list of $n$ unique integers between $0$ and $n-1$ in a memory-efficient way. The only operation we need to support is looking up the $n\text{-th}$ element. What are some of the ...
• 121
1 vote
82 views

### Best compression algorithm for CNF SAT instances in DIMACS

For a CNF SAT instance in the DIMACS format what is the best algorithm to compress it? What is the best algorithm for 3-SAT instances in particular? In 2020 SAT competition used .xz which if I ...
• 11
47 views

### Using B+Tree to implement index, when the index-key size and the data-block size are of the same order

I want to implement an Index using a B+Tree as the underlying data structure. The index will have to support key sizes which are of order of my block size, what means I cannot save all the key as a ...
• 251
102 views

### Can more compression be achieved when data is sorted (in ascending or descending order)?

Let's say I have a file which is exactly 1 MB in size. Contents of file are : 0001001000... upto 128 bytes (128 bytes per line in file). If I sort it in ascending or descending order (using notepad+...
• 35
66 views

### Compress set of mostly known bitstrings

Let's say there is a sender sending messages with commands to a recipient. The sender knows a set of commands but doesn't know anything about the recipient. A command is simply an opaque uniform ...
• 1
1 vote
77 views

### What is the entropy of an unordered list?

I'm trying to compress unordered lists of a few thousand integers for transmission over HTTP, and Claude Shannon is disappointing me with his mathematical ambiguity :) Each integer is 6-digits, so ...
70 views

### Why XML dumps from Wikipedia are so compressed?

Few years ago I downloaded an XML dump of one of Wikipedia's fandom sites. It was the XML datadump of Marvel Fandom. The XML was zipped , size was 900 MB (approx). But when I unzipped it , it was ...
• 35
1 vote
66 views

### Is every binary sequence the output of some meaningful-text-input algorithm?

Here is the problem: Let's say we have a random binary sequence, just an arbitrary sequence of zeroes and ones (of some arbitrary length of digits). Can we find an algorithm that would decode/...
• 111
19 views

### Asymptotically Optimal Universal Code In Other Bases

Universal codes are fairly well studied, and many asymptotically optimal universal codes exist for binary data (see https://en.wikipedia.org/wiki/Universal_code_(data_compression) especially https://...
• 163
94 views

### Is this a general compression algorithm?

I'm aware that an algorithm that compresses every input doesn't exist (by the pigeonhole principle), however I tend to think about the problem sometimes and I came up with a (flawed, but why?) idea: ...
1 vote
88 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 ...
• 113
89 views

### How to find the compression method used on an unknown sequence of bytes? [closed]

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 ...
• 101
19 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 ...
44 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 ...
37 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 : ...
• 139
910 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 ...
59 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 ...
23 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 (...
• 131
92 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...
1 vote
139 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 ...
• 11
36 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 ...
• 205
425 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 ...
74 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 ...
• 203
23 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 ...
98 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 ...
• 315
1 vote
47 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}$ ...
• 21
41 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 ...
• 123
52 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 ...
98 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 ...
101 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 ...
76 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 ...
59 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
62 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 ...
• 11
46 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 ...
145 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: ...
• 101
90 views

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 ...
• 23