New answers tagged

1

The technique idea is perfectly described in Yuval Filmus answer. Even if slightly different, it is called Truncated binary encoding in Wikipedia. I couldn't find an original source for that, apart from a mention in a patent, in this book, or in this Google API


1

Suppose $k = 2^{n-1} + t$, where $0 \leq t < 2^{n-1}$. Use the following to encode $z \in \{0,\ldots,k-1\}$: If $z < 2^{n-1}-t$ then encode $z$ as its own $(n-1)$-bit encoding. Otherwise, write $z = 2^{n-1}-t + 2\delta+\epsilon$, where $\delta \in \{0,\ldots,t-1\}$ and $\epsilon \in \{0,1\}$. Encode $z$ at the $(n-1)$-bit encoding of $2^{n-1}-t+\delta$...


1

Here's a partial "yes" answer to your question. Consider a file containing: 0000000000 0000000001 0000000010 0000000011 0000000100 ... 1111111111 That is, it is all binary numbers that are $b$ bits long (in this case $b=10$, but in the exercise that follows, try something smaller), in order, with each number separated by (say) a newline character. The ...


2

The essential problem is that most files are NOT compressible (see the counting argument). And an already compressed file is much less likely to be compressible.


3

The question of how foreign languages justifies expanding the encoding in actual usage is well explained by earlier answers. The question of why foreign languages would affect the American Standard Code for Information Interchange is subtly different. As you all know the ASCII chart needed to be extended from 127 encoding to 256 No. The original American ...


2

I keep getting different answers for both. You should get the same result for both orders. Please show your work so that the community can help you find your mistake. My guess is you have mistakenly substituted $f$ instead of $x$ towards the end, when $f$ is in fact free. The correct reduction procedure is shown below. $(\lambda f\ x\ldotp f\ (f\ x))\ (\...


5

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 ...


10

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 ...


0

The usual way to solve this problem is by adding leading zeroes. So i would still be represented by 1101001, while ! will be represented by 0100001. This is similar to how you digital clock might use 06:40 for 6:40, or 12:05 for 12:5.


Top 50 recent answers are included