# Tag Info

## Hot answers tagged encoding-scheme

53

You don't need a separator because Huffman codes are prefix-free codes (also, unhelpfully, known as "prefix codes"). This means that no codeword is a prefix of any other codeword. For example, the codeword for "e" in your example is 10, and you can see that no other codewords begin with the digits 10. This means that you can decode greedily by reading the ...

32

UTF-8 might not last forever, but you probably don't have to worry too much. Two universal truths: We can't predict the future. Nothing lasts forever, especially in software. But that doesn't mean the benefit of (trying to) future-proof your code always outweighs the cost. Is UTF-8 likely to become obsolete any time soon? I would say no. UTF-8 is quite ...

29

This answer isn't as long as it looks; this site just puts a lot of spacing between list items! Update: Actually it's getting pretty long... Morse Code isn't "officially" binary, ternary, quaternary, quinary, or even 57-ary (if I count correctly). Arguing about which one it is without context is not productive. It is up to you to define which of those five ...

26

Your code has the property that if you reverse all codewords, then you get a prefix code. This implies that your code is uniquely decodable. Indeed, consider any code $C = x_1,\ldots,x_n$ whose reverse $C^R := x_1^R,\ldots,x_n^R$ is uniquely decodable. I claim that $C$ is also uniquely decodable. This is because $$w = x_{i_1} \ldots x_{i_m} \text{ if and ... 20 Morse code is a prefix ternary code (for encoding 58 characters) on top of a prefix binary code encoding the three symbols. This was a much shorter answer when accepted. However, considering the considerable misunderstandings between users, and following a request from the OP, I wrote this much longer answer. The first "nutshell" section gives you the gist ... 19 When it comes to software, the future always means needing to handle more data--- bigger files, and more of them in a shorter period of time. How does UTF-8 processing scale in those situations? UTF-8 uses a variable number of bytes per character. This saves a lot of space if your text is ASCII plus the occasional emoji or accented letter. But a drawback ... 13 It's helpful to imagine it as a tree. You are simply traversing the tree until you hit a leaf node, and then restarting from the root. From the algorithm which does huffman coding, you can see that this sort of structure is created in the process. https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png 12 I wrote a paper on this. The short answer is that there is no optimal encoding, nor even an optimal sequence of better and better encodings. Kraft's inequality states that there is a prefix code with word lengths k_0,k_1,\ldots if and only if$$ \sum_{n=0}^\infty 2^{-k_i} \leq 1. $$This gives a positive answer to your question. Concretely, Elias gamma ... 11 The largest 12 digit number in base 10 is 10^{12} - 1. In general the largest n position number in a base b is b^{n} - 1. So in your case you need a base large enough that b^{9} - 1 > 999,999,999,999 (10^{12} - 1). Solving for b:$$b^{9} - 1 > 10^{12} - 1b^{9} > 10^{12}b^{9/9} > 10^{12/9}b > 10^{12/9}b >...

11

ASCII has 128 characters. Many countries had similar encodings for 128 characters. That is all history. Nobody uses ASCII anymore. There was a phase with lots of different encodings for more than 128 characters, some with 256 (Mac Roman and Windows 1152 were quite popular) and some like the Chinese GB with thousands of characters. Nowadays people mostly ...

9

Yes, there is such a set. You are actually on the right track to find the following example. Let $C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$. You can check the following. $|C|=32$. $d(u,v)\geq2$ for all $u,v\in C$, $u\not=v$. (In fact, $d(u,v)=2$ or 4 or 6.) Here are four related exercise, listed in the order of increasing difficulty. ...

9

UTF-8 is an elegant hack to remain backward compatible with ASCII and trivially compatible with Latin-1, which were both widely entrenched when Unicode started to take hold. UTF-8 can be extended further and still remain backward compatible with itself, by adding 5- and 6-byte encodings. So if Unicode decides it needs a few more bits to represent its ...

8

UTF-8 might not last forever, but if you permit long UTF-8 again, it will outlast all other encodings that exist today. I have heard it projected that we will eventually run out of UTF-16 codepoints, necessitating the abandoning of UTF-16. We can go all the way to 0x7FFFFFFF. Table from Wikipeida: 1 U+0000 U+007F 0xxxxxxx 2 U+...

7

Consider a Turing machine with $n$ tape symbols and $m$ states. We can assume that the symbols and the states are ordered, so that we can talk about the first, second, ..., $n$th tape symbol, and the first, second, ..., $m$th state. (This is similar to your idea of counting Turing machines up to isomorphism.) So without loss of generality, the tape alphabet ...

7

A Turing machine $M$ can be described as a 7-tuple $(Q,F,q_0,\Sigma,\Gamma,\delta, blank)$. This means that if someone gives you this 7-tuple, then the TM is well-defined, and you can precisely define how it behaves, etc. The encoding of a TM, usually denoted as $\langle M \rangle$ is a string that encompasses all the information of the 7-tuple describing $... 7 All words of even parity from a linear code with$2^{n-1}$codewords and minimum distance$2$. More generally, if$A_2(n,d)$is the maximum size of a code of length$n$and minimum distance$d$, then$A_2(n,2d) = A_2(n-1,2d-1)$. 6 Two's complement is the most commonly used way to represent signed integers in bits. First, consider unsigned numbers in 8 bits. Notice that$2^8 = 256 = 100000000_2$does not fit into 8 bits and will thus be represented as 0000 0000. Therefore$255 + 1 =$1111 1111 + 0000 0001 = 0000 0000 and in that sense 1111 1111 acts as if it was$-1$. Two's complement ... 6 First notice that a "file" is a sequence of 0s and 1s in binary format that are stored in some kind of persistent storage (an hard disk, a CD, an USB key, ...). According to the the type of information stored in the file (a plain text, a PDF document, an image, a video, a song, ...) its bits (bytes) are usually arranged using standard rules and they have ... 6 There are a few other good reasons to expand from 7-bit ASCII, but since you ask specifically about foreign languages, I want to tell you about that angle. English has words with diacritical marks, usually loan words like naïve or café. They are rare, and usually you'll get into no trouble for omitting the diacritics. Occasionally one might stumble into a ... 6 Your question appears to slightly conflate two related concepts (as people often do): Unicode is a standard, whose primary part is a "coded character set" - a list of "code points", and a lot of metadata around them, attempting to catalogue all the world's writing systems. It has a defined "code space" of the numbers 0 to 10FFFF (hexadecimal) inclusive (... 5 Files are always stored in the disk in binary format. Therefore if you know the binary version of the file, you simply know the file itself. A more interesting question is whether you can reconstruct the semantics of the file from its binary contents. Suppose you memorized the binary contents of a file, but forgot what type the file was. Could you ... 5 Despite my initial thoughts on this, it turns out this question can be formalized in a way that admits a fairly precise answer (modulo a couple of definition issues). The answer turns out to be 3 or 4, i.e. ternary or quaternary. The crowd-pleaser "everything goes from 2 to 57" answer is correct only in the sense that if someone asks you for a ... 5 As you mention in your question, everything that can be coded in binary (that is, every countable set) can also be encoded in unary. Arrange all binary strings in some order, say $$\epsilon, 0, 1, 00, 01, 10, 11, \ldots.$$ Let$w_i$be the$i$th string in this order. You can convert from binary to unary by mapping$w_i$to$1^i$and vice versa. You ... 5 Where the 21 bits come from: The idea of unicode is based on the Universal Coded Character Sets (short UCS). It's a concept for a 31bit character set ordered as a 4D hypercube where the first three dimensions use 8bit and the fourth uses 7bit. Per row there are$2^8$characters. Per plane there are$2^8$rows$=65.536$characters. Per cube there are$2^8$... 5 Effective model theory studies computable structures. The collection of all finite trees is a two-sorted computable structure in which one sort consists of vertices (which can be identified with the natural numbers) and the other sort consists of trees. It has the following relations:$\operatorname{vertex}(x)$, which is true if$x$is a vertex.$\...

5

If I give you any message that you are supposed to decode, then you can do the following: Reverse the message, starting with the last bit instead of the first bit. Reverse the code words. Decode the message. Reverse the decoded string. You can do that because after reversing the six code words, you get a prefix-free code: 1010, 1001, 01, 000, 11, 001 is ...

5

I'm frankly confused about why UTF-16 and UTF-32 etc. exist at all UTF-16 exists because Unicode was originally supposed to be a fixed-width 16-bit encoding and many systems were designed during this era and needed to be retrofitted to support more characters. These aren't some niche systems or systems that are on their way out, they are major current ...

4

I'm having trouble answering your question for two reasons. First, the entropy changes as you change the alphabet, so the "best" alphabet depends on the correlations between characters in the class of strings that you are trying to encode, not just the "dyadicness". (This is the problem with the notion of entropy: it depends on your model of what you know ...

4

The size required to store the Huffman code table scales like the number of codewords. We expect the number of unique $k$-letter words to be exponential in $k$, in fact roughly $2^{kH}$, where $H$ in the source entropy, though since the file is not infinite, for large $k$ we will actually see less. Still, this suggests that for logarithmically large $k$, ...

4

I believe I found a reduction from Hamiltonian path, thus proving the problem NP-hard. Call the word $w\in\Sigma^*$ a witness for $A$, if it satisfies the condition from the question (for each $L\in A$, there's $m\geq 1$ such that $\{w_{m+i}\mid 0\leq i<|L|\} = L$). Consider the decision version of the original problem, i.e. decide whether for some $A$ ...

Only top voted, non community-wiki answers of a minimum length are eligible