# Questions tagged [encoding-scheme]

The tag has no usage guidance.

141 questions
Filter by
Sorted by
Tagged with
1 vote
67 views

### Kolmogorov complexity of tuples

Exercise 14.1 of Elements of Information Theory asks us to prove that there is a constant c such that $$K(x,y)\leq K(x) +K(y)+c$$ for all binary strings $x,y$. Intuitively this seems true. Just write ...
74 views

### Intuitive explanation on why stochastic encoding performs better in channel coding

I am a little confused about stochastic encoding in channel coding. For example, in the identification problem (R. Ahlswede and G. Dueck, “Identification via channels”), the authors claim that we can ...
18 views

### A specification of all possible languages for representing graphs?

There are a few commonly used markup languages for specifying graph structures. I am interested in discovering alternative graph notations that may be counterintuitive yet more compact or useful in ...
1 vote
102 views

### Initialization of embedding space value for VQ-VAE

I am trying to study a research paper about VQ-VAE: Neural Discrete Representation Learning, Aaron van den Oord, Oriol Vinyals, Koray Kavukcuoglu, NeurIPS 2017. I have difficulty to understand the ...
411 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 ...
1 vote
96 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 ...
11 views

### Determining the benefit from increasing bits available in base 32 checksum

I'm looking at using something like Crockford Base-32 encoding in a situation where people have to manually write IDs in a very compact space. Crockford Base-32 describes a simple checksum algorithm ...
1 vote
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 ...
1 vote
47 views

### How to formally show computational equivalence or universality using encodings?

I want to formally show that a computational system $\mathcal M$ is computationally universal by showing it is computationally equivalent to some already known universal system, i.e. some UTM. To show ...
1 vote
299 views

### Number of unique prefixes in canonical huffman tree

I am trying to implement decompression algorithm based on huffman trees. I am trying to validate my assumptions. Assume that you have alphabet of 350 symbols. Maximum encoded code length is 15 bits. ...
74 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 ...
90 views

### What is the minimum number of bytes required to store the sum of two primitive integers?

Motivation An informal way word this question is, How would re-do some of the weird promotion rules in languages descended from C, like C# or Java. The goal would as to minimize human bewilderment ...
79 views

### ASCII invariant string for base64 Encoding

I know the basics about base64 encoding, but thinking about it abstractly I have a theoretical question. If we consider base64 a mathematical function(in our case computable), Does there exists an ...
1 vote
55 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 ...
53 views

### Correct way to encode strings

I'm interested in analyzing the randomness of strings using relative count for 1-, 2-, etc tuples. E.g. for a long string "abbccba.." with an alphabet <...
11k 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 ...
1 vote
53 views

### Are there adaptive algorithms/data structures for sparse and non sparse vectors?

A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value. A dense 1D array is commonly encoded as a linear array of values [value1, value2, ...
1 vote
523 views

### Hash / Compression algorithm to shorten text?

I desperately need a hash / compression function that is suited to shorten text. The context is this: I want to bring order and sort my box with hundreds of charging adapters (duh). After I determined ...
1 vote
50 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#...
1 vote
1k views

### What is the name of the following binary encoding?

S is a the set of binary strings in Shortlex order: [0,1,00,01,10,11,...] I want to encode / decode natural numbers with the following scheme: Encoding N: For ...
1 vote
455 views

### How bits translated into text on the screen?

recently i started studying computer science and computer graphics, and one question really haunts me. Mby someone can explain this. How bit patterns become translated into (for example ) text. I know ...
34 views

110 views

### Why is channel capacity of AWGN infinite?

My professor taught us that channel capacity of AWGN channel is infinite without any input power constraints. The noise is $Z \sim \mathcal{N}(0,\sigma^2)$. There is no constraint on input signal. I ...
472 views

### Are all prefix codes uniquely decodable?

I can't think of any counterexample but I can't find any such statement on the internet or my textbook either. I know that for each uniquely decodable code, there exists a prefix code with the same ...
971 views

### How to enumerate all Turing machines?

Why is this true: “There are countably many Turing Machines” In the top answer for this question a description of how to enumerate all Turing machines is given. It all is clear except for one part: ...
56 views

### Worked out example of Slepian-Wolf Theorem

Note: First posted this on Theoretical Computer Science Stack Exchange, but deleted it from there since it seems to be off-topic. The Slepian-Wolf theorem states that sequences of outputs from two ...
164 views

### Help in understanding 'reasonable' encoding of inputs

I read that a reasonable encoding of inputs is one where the length of the encoding is no more than a polynomial of the 'natural representation' of the input. For instance, binary encodings are ...