2
$\begingroup$

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?

Improve this question
$\endgroup$
19
  • $\begingroup$ 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) $\endgroup$
    – Paddy
    Dec 20, 2019 at 19:08
  • 1
    $\begingroup$ 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? $\endgroup$
    – Peter Shor
    Dec 21, 2019 at 12:15
  • $\begingroup$ 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. $\endgroup$
    – Paddy
    Dec 21, 2019 at 13:02
  • $\begingroup$ Where could I post elementary questions like this then? $\endgroup$
    – Paddy
    Dec 21, 2019 at 13:04
  • 2
    $\begingroup$ 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 $\endgroup$
    – Peter Shor
    Dec 21, 2019 at 14:25

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.