Questions tagged [data-compression]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
28 views

Is it possible to avoid encoding the state in streaming ANS?

regular ANS collects all the data into one big integer and provides optimal compression. In cases where all the symbol probabilities are powers of two, it is just as good as huffman coding (because ...
terepy's user avatar
  • 13
0 votes
0 answers
34 views

Compression Gzip/7Zip

When I calculate the entropy values of files compressed with Gzip, PKZIP, 7ZIP and Winrar, I find that the compression rate of Gzip is higher than the others. The entropy value is higher (indicating ...
Questions123's user avatar
0 votes
0 answers
28 views

Calculation of compression ratio using arithmetic encoding?

Arithmetic encoding is one of the most famous entropy encoding techniques, and I am using it to encode an image. For this, I am using the built-in function of Matlab that also gives other values such ...
Sahil Sharma's user avatar
0 votes
1 answer
30 views

What algorithm constructs the optimal code $f$ of size $a$?

I'm looking at Shannon's source coding theorem for symbol codes. It provides a very nice bound on the expected code length $S=|f(X)|$ of an optimal code $f$ over the sequence variable $X$: $$ \frac{H(...
accounted4's user avatar
1 vote
1 answer
40 views

Efficient way to calculate many Dutch auctions?

I have 4,500 ($N$) unique items, and I want to auction each one off to the highest bidder (break ties arbitrarily). Each item has $T$ binary traits. Since it is too complex for the $B$ bidders to ...
Neel's user avatar
  • 131
2 votes
0 answers
60 views

Permuting matrix entries to lower rank

Suppose I have a rank-$k$ matrix $A \in \mathbf{R}^{m \times n}$. Now suppose this matrix has its elements shuffled by an adversary to maximize the rank. Is there a way to reverse this permutation and ...
Calvin Elder's user avatar
1 vote
2 answers
32 views

An Arithmetic Encoding's length being ambiguous?

Say they are two tokens, A and B. A has probability weight 0.99 (and B has 0.01). If I want to encode the sequence "AAA", wouldn't the binary encoding just be "0"? And wouldn't ...
chausies's user avatar
  • 512
1 vote
1 answer
109 views

Kolmogorov complexity and data compression revisited

The question of the relationship between Kolmogorov complexity and data compression is rather difficult. However, at the heuristic level, the complexity of an object and the rate of its compression by ...
lesobrod's user avatar
  • 111
0 votes
1 answer
27 views

Why is data generated from a randomly constructed Markov chain not compressible?

For a project I'm working on, I need to generate some data to test the Gzip compressor, and I wrote my own implementation of Markov chain for it, and it's a 2-level nested one. But when I generate ...
DannyNiu's user avatar
  • 192
2 votes
3 answers
1k views

Storing N bits on the smallest possible space in a real computer

Update. Since my original question was misunderstood by many, and lead to a lot of debate about various issues, let me try to pose this modified and rephrased question: Assume that I have a computer ...
domotorp's user avatar
  • 260
0 votes
0 answers
31 views

Prove that Fibonacci code for data compression is a complete code using Kraft-McMillan inequality

I am Facing a problem when learning about data compression. I learned that the Fibonacci code for data compression is complete. I am trying to prove it using a hint from my professor to use Kraft-...
Dolev Dublon's user avatar
0 votes
2 answers
140 views

File conversion to binary format to save storage space

Our test log files are stored in .asc format. Each file contains around 5000 rows of these Logging Strings as shown in the image. I would like to reduce the size of these files.They are around 4-5 MBs ...
Sajeev Pillai's user avatar
1 vote
1 answer
28 views

Compressed string lookup by name or ordinal

I have a large list of strings with associated values. I need to do a fast lookup into the list by the string prefix, but also by the string's ordinal within the list. For example, ...
ccleve's user avatar
  • 129
0 votes
1 answer
34 views

Is it possible to decode an array stored in strings with constraint satisfaction?

I am currently experimenting on compression algorithms, I am using proven algorithms and I am just trying to see if I can make some things more efficient, so I am very sorry if this is a stupid ...
gushkash's user avatar
0 votes
2 answers
74 views

How do compression algorithms keep track of multiple files?

I noticed that when you compress data they can compress multiple files and since all files are made up of bytes how do these compression algorithms keep track of them? What seperators do they use? ...
gushkash's user avatar
0 votes
2 answers
115 views

is it possible to compress a sequence of progressive unique numbers dramatically?

Let's say I have a 60 set of numbers from 0-100,000 so like [81, 98, 115, 189, 254, ... , 97866, 98441, 99671] all unique and progressively increasing. Would it be ...
gushkash's user avatar
1 vote
1 answer
32 views

Good Practice : Which VAE latent variable to use in dimensionality reduction

I'm trying to use a VAE (CNN-VAE to be exact) to reduce the dimension of some images I have in a dataset. I successfully trained my VAE, but now I'm not sure of the latent variable to return. Should I ...
Liam F-A's user avatar
0 votes
1 answer
52 views

How many bits are required to encode information in probability set G = [0.001, 0.002, 0.003, 0.994]?

I am currently working on data compression and thought it would be a good time to read up on the basics of information theory to better understand data compression and its algorithms. As I understand, ...
prime_mover's user avatar
-1 votes
1 answer
75 views

How to Implement Static Dictionary Compression?

I am targeting a simple dictionary-coder compression algorithm that uses a static dictionary (code in an existing program, but I can supply my own dictionary). How can I write a compressor for such an ...
Justin Olbrantz's user avatar
0 votes
1 answer
107 views

Does a constant time compression algorithm proves that P=NP?

Supposed someone came up with a compression algorithm that doesn't iterate through bytes or anything to compress data, does that proves P=NP? That is, an algorithm that doesn't rely on patterns/...
Feyijinmi Adegoke's user avatar
0 votes
2 answers
114 views

Binary compression algorithm with decompress by index

I have a list of 256-bit binary data to store. Any algorithm for doing lossless compression on it in a way I can retrieve an entry by its index without decompressing the whole data (if possible). The ...
Noel Jacob's user avatar
1 vote
1 answer
227 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 ...
Sam's user avatar
  • 163
1 vote
1 answer
41 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#...
user363406's user avatar
0 votes
0 answers
38 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 ...
Shriram's user avatar
1 vote
1 answer
109 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 ...
Exzone's user avatar
  • 235
6 votes
1 answer
101 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 ...
Timwi's user avatar
  • 181
0 votes
0 answers
44 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 ...
magnetlion's user avatar
0 votes
1 answer
232 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 ...
Akash's user avatar
  • 35
1 vote
0 answers
221 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 ...
ApplePiePoodle's user avatar
2 votes
1 answer
163 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 ...
dizcza's user avatar
  • 123
0 votes
0 answers
81 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 ...
chaohuang's user avatar
  • 101
3 votes
2 answers
49 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 ...
vovan_se's user avatar
2 votes
2 answers
88 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 ...
glebm's user avatar
  • 121
1 vote
1 answer
129 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 ...
dimacs's user avatar
  • 11
2 votes
1 answer
127 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 ...
user5721565's user avatar
0 votes
2 answers
273 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+...
Akash's user avatar
  • 35
0 votes
1 answer
73 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 ...
rsjr's user avatar
  • 1
1 vote
2 answers
151 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 ...
TheEnvironmentalist's user avatar
0 votes
1 answer
91 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 ...
Akash's user avatar
  • 35
1 vote
3 answers
81 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/...
jdods's user avatar
  • 111
2 votes
0 answers
25 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://...
LambdaBeta's user avatar
0 votes
2 answers
117 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: ...
Davi Nonnenmacher's user avatar
1 vote
1 answer
241 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 ...
IrkenInvader's user avatar
0 votes
2 answers
258 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 ...
Capstone's user avatar
  • 101
0 votes
0 answers
24 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 ...
timesharer's user avatar
-1 votes
1 answer
57 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 ...
timesharer's user avatar
2 votes
0 answers
45 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 : ...
sten's user avatar
  • 139
6 votes
1 answer
997 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 ...
Karol Szustakowski's user avatar
0 votes
0 answers
115 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 ...
Steven's user avatar
  • 1
2 votes
1 answer
48 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 (...
Aether's user avatar
  • 141

1
2 3 4 5 6