Questions tagged [data-compression]
The data-compression tag has no usage guidance.
247
questions
1
vote
0
answers
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-...
- 11
0
votes
1
answer
555
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 ...
CommunityBot
- 1
1
vote
1
answer
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 ...
- 306
3
votes
1
answer
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 ...
CommunityBot
- 1
3
votes
1
answer
48
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 ...
CommunityBot
- 1
1
vote
1
answer
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#...
- 21
0
votes
0
answers
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
1
vote
1
answer
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 ...
CommunityBot
- 1
1
vote
1
answer
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 ...
- 26
1
vote
1
answer
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 ...
CommunityBot
- 1
6
votes
1
answer
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
6
votes
1
answer
369
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 ...
CommunityBot
- 1
0
votes
1
answer
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 ...
CommunityBot
- 1
23
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 ...
CommunityBot
- 1
0
votes
0
answers
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 ...
- 93
1
vote
0
answers
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
1
answer
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 ...
D.W.♦
- 140k
0
votes
0
answers
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
24
votes
5
answers
7k
views
Data compression using prime numbers
I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data.
Basically ...
- 101
3
votes
2
answers
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 ...
D.W.♦
- 140k
2
votes
2
answers
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 ...
- 24.9k
2
votes
1
answer
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 ...
- 18.8k
0
votes
2
answers
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+...
- 33k
1
vote
2
answers
95
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 ...
CommunityBot
- 1
0
votes
1
answer
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 ...
- 18.8k
1
vote
2
answers
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 ...
- 1,389
0
votes
1
answer
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 ...
- 1,389
0
votes
2
answers
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:
...
- 584
1
vote
3
answers
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/...
- 296
2
votes
0
answers
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
1
vote
3
answers
191
views
Data compression with Turing Machine
For traditional algorithms compressed data may vary, while decompression algorithm is always the same. Are there any approaches, when (de)compression algorithm is also changing to provide best ...
- 1
1
vote
1
answer
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 ...
- 1,389
0
votes
2
answers
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 ...
- 1,389
0
votes
0
answers
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 ...
-1
votes
1
answer
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 ...
2
votes
0
answers
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
7
votes
1
answer
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
...
- 22.7k
0
votes
0
answers
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 ...
- 1
2
votes
1
answer
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 (...
- 268k
2
votes
1
answer
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...
- 268k
13
votes
4
answers
6k
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 ...
3
votes
0
answers
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
2
votes
2
answers
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 ...
- 123
0
votes
1
answer
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 ...
CommunityBot
- 1
0
votes
0
answers
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 ...
CommunityBot
- 1
2
votes
1
answer
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
0
answers
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
2
votes
2
answers
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 ...
D.W.♦
- 140k
0
votes
1
answer
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 ...
- 18.8k
1
vote
1
answer
61
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 % ...
CommunityBot
- 1