<p>Let us assume a file based on a character set where each character has equal probability of occurance. This will result in the maximum entropy for that character set. On calculating the entropy, let us say that the entropy is just above an integral value. Usually, in such cases, the number is rounded up(which makes sense when it comes to storage).</p>

<p>Using standard techniques, when a single character in the string changes, the entire binary representation changes along with it. So is there any efficient coding technique where the representation doesn't change much with small changes in the original string?</p>

CC BY-SA 4.0
2019-12-20T19:08:15.197Z
If this is not the right place to post this question, please let me know what might be the right stackexchange site or move the question to that site please. Thanks for tolerating a newbie to Theoretical CompSci(P.S: According to a couple of Google searches, this might be the right place after all)
Paddy
CC BY-SA 4.0
2019-12-21T12:15:32.067Z
This is not the right place, because your question is too elementary. Suppose your character set has 5 elements. Consider a length 3 sequence of symbols from your character set. Can you represent that by a non-negative integer less than 125? Now, how many bits do you need to represent this integer?
Peter Shor 
CC BY-SA 4.0
2019-12-21T13:02:47.057Z
Right, I'd already thought of that. However, that would make the binary representation dependent on every character in the sequence. So if a single character changes, the binary representation of the sequence could change entirely.
Paddy
CC BY-SA 4.0
2019-12-21T13:04:02.850Z
Where *could* I post elementary questions like this then?
Paddy
CC BY-SA 4.0
2019-12-21T14:25:27.613Z
Actually, if you edit the question so as to ask whether there's an efficient coding so that if you change a single character, the binary representation doesn't change very much, this becomes a non-elementary question and is entirely appropriate for this site. (And once you've edited it, I'll upvote the question.) And for elementary questions, you can post them on cs.stackexchange.com
Peter Shor 
CC BY-SA 4.0
2019-12-21T14:30:20.973Z
Done, thanks. So IS there an efficient coding technique you know?
Paddy
CC BY-SA 4.0
2019-12-21T22:09:39.637Z
The best you can get is $\lceil e k \rceil$, where $e$ is the entropy per bits and $k$ is the number of characters in the message.
Christopher King
CC BY-SA 4.0
2019-12-24T06:21:22.190Z
@PyRulez, that raises an interesting question on how you calculate entropy, doesn't it? For example, if your string is "abcdabcdabcd", and you calculate entropy using a,b,c and d as seperate characters, then entropy is pretty high. However, if you can locate the obvious pattern that "abcd" as a whole repeats thrice, then using "abcd" as a single "character", the entropy calculated is quite low.
Paddy
CC BY-SA 4.0
2019-12-24T06:23:40.430Z
Also, if you've worked in chaos theory before, seemingly erratic sequences are solutions to what appear to be trivial differential equations. Obviously, it must be very difficult to find a trivial looking differential equation for every erratic sequence, but then again, the question remains, is it possible?
Paddy
CC BY-SA 4.0
2019-12-24T06:27:25.500Z
@PeterShor, was the edit good enough or am I missing something? Unabashedly waiting for the upvote
Paddy
CC BY-SA 4.0
2019-12-24T11:19:20.177Z
@PradyothShandilya: my upvote was balanced by somebody else's downvote. And judging by some of the other comments, while I understand your revised question, not everybody does.
Peter Shor 
CC BY-SA 4.0
2019-12-24T16:42:42.340Z
@PradyothShandilya entropy has a precise definition. "abcdabcdabcdabcd" has 0 entropy since it is not probabilistic. Only probabilistic things have nonzero entropy.
Christopher King
CC BY-SA 4.0
2019-12-24T16:45:30.730Z
@PyRulez, let's say the string instead was "abcdabcdabcda". There's one extra 'a'. How would you calculate entropy in this case? P.S: Undergrad electrical engineering student here, so if I'm obviously not aware of certain trivial concepts here, I'd appreciate a nod in the right direction
Paddy
CC BY-SA 4.0
2019-12-24T16:46:49.033Z
@PradyothShandilya still 0. It will only be nonzero if the string is a random variable.
Christopher King
CC BY-SA 4.0
2019-12-24T16:49:08.060Z
@PyRulez I need some further clarification to the "still 0" statement. I calculated it by the summation of p*log(p) and since my string has more probability of occurance of the character 'a', wouldn't entropy be nonzero?
Paddy
CC BY-SA 4.0
2019-12-24T16:57:12.100Z
@PradyothShandilya since your string is "abcdabcdabcda", the probability of it equaling that string is 1. -1 * log(1) = 0. On the otherhand, let's say your string has a 50% probability of equalling "dog" and a 50% chance of equaling "Kansas". If you calculate the entropy of that, it will be 1 bit. The entropy actually doesn't depend on the string itself at all; it only depends on it's probability distribution.
Christopher King
CC BY-SA 4.0
2019-12-24T16:58:53.223Z
@PradyothShandilya (oh, I see your confusion. $p$ is the probability of the whole string, not the letter.)
Christopher King
CC BY-SA 4.0
2019-12-24T17:04:48.923Z
I clearly have a lot more to study. Thanks for the clarification
Paddy
CC BY-SA 4.0
2019-12-25T13:12:06.523Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/102560/discussion-between-pradyoth-shandilya-and-pyrulez).
Paddy
<it.information-theory><shannon-entropy><knowledge-representation>
Representing data with Shannon entropy predicted bits
Paddy
# Representing data with Shannon entropy predicted bits

(Asked by: username_0 on 2019-12-20)

Let us assume a file based on a character set where each character has equal probability of occurance. This will result in the maximum entropy for that character set. On calculating the entropy, let us say that the entropy is just above an integral value. Usually, in such cases, the number is rounded up(which makes sense when it comes to storage).

Using standard techniques, when a single character in the string changes, the entire binary representation changes along with it. So is there any efficient coding technique where the representation doesn't change much with small changes in the original string?

**Tags:** it.information-theory, shannon-entropy, knowledge-representation
> **Comments:**
> **username_0**: If this is not the right place to post this question, please let me know what might be the right stackexchange site or move the question to that site please. Thanks for tolerating a newbie to Theoretical CompSci(P.S: According to a couple of Google searches, this might be the right place after all)  
> **username_1**: This is not the right place, because your question is too elementary. Suppose your character set has 5 elements. Consider a length 3 sequence of symbols from your character set. Can you represent that by a non-negative integer less than 125? Now, how many bits do you need to represent this integer?  
> **username_0**: Right, I'd already thought of that. However, that would make the binary representation dependent on every character in the sequence. So if a single character changes, the binary representation of the sequence could change entirely.  
> **username_0**: Where *could* I post elementary questions like this then?  
> **username_1**: Actually, if you edit the question so as to ask whether there's an efficient coding so that if you change a single character, the binary representation doesn't change very much, this becomes a non-elementary question and is entirely appropriate for this site. (And once you've edited it, I'll upvote the question.) And for elementary questions, you can post them on cs.stackexchange.com  
> **username_0**: Done, thanks. So IS there an efficient coding technique you know?  
> **username_2**: The best you can get is $\lceil e k \rceil$, where $e$ is the entropy per bits and $k$ is the number of characters in the message.  
> **username_0**: @PyRulez, that raises an interesting question on how you calculate entropy, doesn't it? For example, if your string is "abcdabcdabcd", and you calculate entropy using a,b,c and d as seperate characters, then entropy is pretty high. However, if you can locate the obvious pattern that "abcd" as a whole repeats thrice, then using "abcd" as a single "character", the entropy calculated is quite low.  
> **username_0**: Also, if you've worked in chaos theory before, seemingly erratic sequences are solutions to what appear to be trivial differential equations. Obviously, it must be very difficult to find a trivial looking differential equation for every erratic sequence, but then again, the question remains, is it possible?  
> **username_0**: @PeterShor, was the edit good enough or am I missing something? Unabashedly waiting for the upvote  
> **username_1**: @PradyothShandilya: my upvote was balanced by somebody else's downvote. And judging by some of the other comments, while I understand your revised question, not everybody does.  
> **username_2**: @PradyothShandilya entropy has a precise definition. "abcdabcdabcdabcd" has 0 entropy since it is not probabilistic. Only probabilistic things have nonzero entropy.  
> **username_0**: @PyRulez, let's say the string instead was "abcdabcdabcda". There's one extra 'a'. How would you calculate entropy in this case? P.S: Undergrad electrical engineering student here, so if I'm obviously not aware of certain trivial concepts here, I'd appreciate a nod in the right direction  
> **username_2**: @PradyothShandilya still 0. It will only be nonzero if the string is a random variable.  
> **username_0**: @PyRulez I need some further clarification to the "still 0" statement. I calculated it by the summation of p*log(p) and since my string has more probability of occurance of the character 'a', wouldn't entropy be nonzero?  
> **username_2**: @PradyothShandilya since your string is "abcdabcdabcda", the probability of it equaling that string is 1. -1 * log(1) = 0. On the otherhand, let's say your string has a 50% probability of equalling "dog" and a 50% chance of equaling "Kansas". If you calculate the entropy of that, it will be 1 bit. The entropy actually doesn't depend on the string itself at all; it only depends on it's probability distribution.  
> **username_2**: @PradyothShandilya (oh, I see your confusion. $p$ is the probability of the whole string, not the letter.)  
> **username_0**: I clearly have a lot more to study. Thanks for the clarification  
> **username_0**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/102560/discussion-between-pradyoth-shandilya-and-pyrulez).  

---

## 0 answers

