Questions tagged [data-compression]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
15 views

Conway's Game of Life to expand QR code

If you use a QR code as a seed for Conway's Game of Life, and have information for A) How many steps you should run it for, and B) The size of the new square (where to put the border after you are ...
3 votes
1 answer
455 views

LZ-type compression vs. entropy-encoding of BWT data

Why does there seem to be a preference for using Huffman (or Arithmetic) coding instead of a Lempel-Ziv type compression algorithm for Burrows-Wheeler Transformed data? I noticed that data ...
0 votes
3 answers
285 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 ...
3 votes
1 answer
139 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 ...
17 votes
5 answers
7k 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 vote
1 answer
163 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 ...
2 votes
1 answer
91 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 ...
25 votes
1 answer
1k 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
0 answers
95 views

Succint data structure for storing n numbers using a mask-based partition

I've a set $N$ of $n$ distinct numbers of $d$-bits each; call them words ($1\leq n\leq 2^d$, with $d\geq 1$). I want to store $N$ using as least space as possible, by partitioning $N$ and factoring ...
1 vote
2 answers
108 views

Memory-efficient representation of keys over a huge domain

I don't know if the title of the question is accurated or not, but I was thinking of the following problem: I have a set of numbers, let's call them identifiers. Each identifier is stored on a 64-bit ...
29 votes
7 answers
30k views

Efficient compression of simple binary data

I have a file containing ordered binary numbers from $0$ to $2^n - 1$: 0000000000 0000000001 0000000010 0000000011 0000000100 ... 1111111111 7z did not compress ...
3 votes
1 answer
87 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 ...
1 vote
1 answer
442 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
0 answers
31 views

What are the steps to create an intuitive and straightforward proof of the optimality of Huffman coding?

I am having great difficulty following the proof in class. I assume "optimal" means it minimizes the Average bit length to encode an alphabet with known frequencies. My understanding of how ...
6 votes
2 answers
5k views

Does there exist a data compression algorithm that uses a large dataset distributed with the encoder/decoder?

If my goal were to compress say 10,000 images and I could include a dictionary or some sort of common database that the compressed data for each image would reference, could I use a large dictionary ...
1 vote
1 answer
36 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 ...
0 votes
0 answers
39 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 ...
0 votes
0 answers
66 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 ...
0 votes
1 answer
36 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(...
7 votes
3 answers
618 views

Are there lossless data compression techniques that do not exploit repetitive patterns?

Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy). Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern ...
26 votes
12 answers
11k 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 ...
2 votes
0 answers
64 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 ...
1 vote
2 answers
47 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 ...
1 vote
1 answer
184 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 ...
0 votes
1 answer
30 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 ...
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 ...
0 votes
1 answer
284 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 ...
2 votes
4 answers
773 views

Using Data Compression on the output of Data Compression

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Is there a data compression method/algorithm that uses another data ...
1 vote
1 answer
35 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, ...
5 votes
1 answer
10k views

When would the worst case for Huffman coding occur?

I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the ...
0 votes
2 answers
89 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? ...
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 ...
0 votes
2 answers
173 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 ...
1 vote
1 answer
41 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 ...
0 votes
1 answer
114 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, ...
7 votes
1 answer
407 views

LZ-type compression with a limited recursion depth

I would like to begin by apologizing. I am not a computer scientist, so my use of terminology will be off. I came across an interesting problem, which I believe to be pretty hard and would love to get ...
0 votes
1 answer
134 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 ...
2 votes
3 answers
4k 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 ...
6 votes
1 answer
105 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 ...
0 votes
2 answers
175 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 ...
0 votes
1 answer
122 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/...
0 votes
1 answer
939 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
1 answer
243 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 ...
1 vote
1 answer
47 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#...
0 votes
0 answers
42 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
1 answer
131 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 ...
0 votes
0 answers
46 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 ...
1 vote
0 answers
274 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 ...
2 votes
1 answer
199 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 ...
0 votes
0 answers
91 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 ...

1
2 3 4 5 6